Hacker News Reader

The BBC ran a service called BBC Select in the early 90s with a VideoCrypt derivative, rather than line cut they shuffled blocks of lines around the screen - which worked better over more lossy and interference prone terrestrial transmissions.

The technical paper from BBC R&D is quite interesting: http://downloads.bbc.co.uk/rd/pubs/reports/1995-11.pdf

There are a couple of captures of the scrambled transmission on Youtube - it's definitely far more advanced than the earlier Canal method https://youtu.be/HcCdw97_ESA

I see that has a reference to European Scrambling Systems 5 – The Black Book by John McCormac. I actually have a copy of that, it gives a rather entertaining overview of the arms race between the broadcasters and the hackers.

I had it too ;-)

In general you don't even need to use the whole line to do the correlation.

I remember writing a small program to decrypt image stills in the late 90s and it was surprisingly easy and straightforward, though obviously doing it in real time may have been another story...

In Spain we had Canal+ with Nagravision and you had either a combo of two software under Windows, or xawtv-nagra under Linux to decode it (ilegally OFC).

Was also used in N. America. It had many vulnerabilities in every card generation. You could program OEM cards, have man-in-the-middle devices, and full emulators.

You Never needed to actually use the cards for Nagra. But The competitor DTV system built by NDS had an ASIC on the chip, so all solutions required a card at some level. But some setups could use one slave card for multiple receivers. Even over IP.

Fun times!

Those cardsharing schemes still exist today, although they're being cracked down more and more.

Yeah, DirecTV's aggressive legal actions in the early 2000s drove that whole scene very deep underground.

It’s a funny full circle.

Instead of using OEM receivers and compromised cards, they’ve gone to running emulated receivers and regular full-sub cards.

Do you have more info on this?

I used to be really into FTA satellite, but have not played with it in awhile.

Never really played with them hands on. Ubiquitous broadband and streaming services really nailed InternetKeySharing’s coffin.

Yes, with PICF84 microcontrollers.

Nagra hacks exclusively ran Atmels. But dunno what chips F cards used. The H cards were the ones that had ASICS.

I remember seeing pirate decoders (probably Discret 11, not Nagra, though) at the time, obviously for scientific curiosity only, which used a Motorola microcontroller. I think it may have been a 68HC705.

I did not realise that NDS is actually the News Datacom referred to by McCormac in European Scrambling Systems. The wikipedia entry for them makes interesting reading.

News Digital, but ya, owned (for a while) by Rupert Murdoch’s News Corp.

Ah I'm not sure there was fast (and cheap) enough RAM for that kinds of tricks in the 80's

Most likely they would use a delay line https://en.wikipedia.org/wiki/Analog_delay_line

Regular PAL (and I guess SECAM) TVs used one of those

You also had Bucket-Brigade devices.

https://en.wikipedia.org/wiki/Bucket-brigade_device

So essentially sleep sort in actual practice?

If you created a graph where the lines where the nodes and the difference between the lines where the edges then a traveling salesman algo might recreate it efficiently (or its vertical mirror I guess)

Reducing a problem to the traveling salesmen usually doesn't go in the same sentence as efficiency.. It's almost the paradigmatic NP-hard problem.

(And I don't understand how the reduction to traveling salesman problem would help here?)

>(And I don't understand how the reduction to traveling salesman problem would help here?)

Let the similarity between line i when rotated to position k and line i+1 when rotated to position j be d_k,j. Then you want to find a sequence of rotations r_1..r_n so that

d_1,r_1,r_2 + d_2,r_2,r_3 + ... + d_(n-1),r_(n-1),r_n

is minimized. In plain terms, you want to align each line so that it's most alike the previous line you rotated, but that in turn depends on the next-to-previous line you rotated, and so on up.

This is a restricted type of traveling salesman problem: you want to visit all the nodes corresponding to each adjacent pair of rotation offsets so that the total edge cost (distance between the lines) is minimized.

Since it's 1D, it should be pretty easy to solve with some dynamic programming (straightforward memoization). Calculate the minimal cost for each line down to k. Then for every possible choice of rotating the (k+1)th line, check which order of rotations of the preceding k lines that would minimize the objective down to the (k+1)th line, given that you rotated the k+1th line in that particular manner. Then determine the minima for every k+1 position and go on to line k+2.

EDIT: It's even easier, since you can hold one line constant and rotate the next. Whenever you rotate the first line k, if you know the second line's optimal rotation for a zero rotation of the first line is j, you just rotate the second line k+j. So none of the above complexity is actually needed. I'll keep the comment to show how it could be considered a restricted TSP.

Thanks!

Yes, you can always reduce problems in P or in NP to a TSP. (In this case, I didn't see the reduction immediately, hence my question.)

But a reduction to the general TSP is basically never useful, since general TSP is so hard to solve. (Perhaps the reduction is useful, when you don't know whether your problem is even in NP or perhaps more complicated, yet.)

Sometimes you only need an approximation. I read a paper once about using TSP approximations for data recovery.

For any pair of picture data fragments, you'd calculate a goodness of fit score to placing these next to each other. E.g. a JPG of an apple would fit badly with a JPG of a car because they don't share any edges, but two consecutive car JPG fragments would fit well.

Then the problem of ordering the data fragments so that each fragment has a high goodness-of-fit (low distance) to the previous one, is a traveling salesman problem.

The paper then went on to say that nobody can exactly solve TSP instances of the size required, but gave examples where the spanning tree heuristic worked pretty well.

Interesting. Though when talking about how to solve combinatorial problems like that, a much more common approach seems to be to formulate them as an integer linear programming problem.

Integer linear programming is also in NP in general. (It has to be, since you can solve the TSP with integer linear programming.) But it's usually much easier to 'write' a linear programme than to reduce a combinatorial problem to a TSP.

Linear programming solvers are very advanced these days.

The other general workhorse I know of for these kinds of problems are SMT solvers. (https://en.wikipedia.org/wiki/Satisfiability_modulo_theories)