Lair Of The Multimedia Guru

Now after breaking videocrypt, lets take a look at (old analog) nagravision

Nagravision

the PRNG seed

Same as videocrypt (Binary data from the vertical blanking interval is feeded into a smartcard which then among other things produces a PRNG seed for the nagravision decoder, but none of this matters to us here)

the PRNG

The PRNG (pseudo random number generator) is feeded with a 15bit seed and a 256 5bit entry table, and produces 287 5 bit values, the following code will do exactly that:

void prng(int seed, int *cle2enc){
  uint8_t keyNdx= seed >> 7;
  int keyInc= ((seed & 0x7F) << 1) + 1;
  int buffer[32];

  for(int i=0; i<32; i++) buffer[i]= i;

  for(int i=0; i<255; i++){
    cle2enc[i]= buffer[ keyTable[keyNdx] ];
    buffer[ keyTable[keyNdx] ]= i + 32;
    keyNdx+= keyInc;
  }

  memcpy(cle2enc+255, buffer, 32*sizeof(int));
}

the actual decryption

nagravision has a 32 line buffer, each line can contain a line of video, for each of the 287 lines of a field there are 5bits from the PRNG which are used as index into the buffer to decide into which entry to store the next received line and from where to output one, or in other words nagravision reorders lines using a 32line temporary buffer

Breaking Nagravision without knowledeg of the PRNG

The naive and ideal solution would be to try all 32^287 possibilities and compare the resulting decoded images, obviously thats not realistic
if OTOH we just use a compare function which compares 2 lines and lets assume its just simple correlation then and wish to find the global minimum then we actually didnt improve by that much as thats equivalent of solving the TSP
old versions of 2010 used the following algorithm to find a good permutation of the lines, which resulted in watchable movies

Step 1 (downsampling)

to speedup the linecompare later, the lines can be horizintally downsampled

Step 2 (comparing lines)

all lines which are not near black and which have not yet been merged with 2 lines are compared to all other such lines, the compares are done blockwise so that the number of cache misses is minimzed, for each line a fixed number of best matches is kept

Step 3 (sorting)

all the line pairs are sorted depending upon their similarity

Step 4 (merging)

from best matching line pair to worst the following steps are done

Step 4A (out of pairs)

if we hit the last pair for any line (we just keept a fixed number of best matches for each line) then we goto Step 2

Step 4B (impossible merges 1)

if either of the lines is in the middle of a block or they are the ends of the same block we continue with the next pair at Step 4

Step 4C (impossible merges 2)

we maintain 2 position limits for each block one for each possible orientation, if a merge would force the block outside the image we continue with the next pair at Step 4
the limits are calculated based on the fact that no line can be output before it has been received

Step 4D (impossible merges 3)

we maintain the fullness state of the 32 line reorder buffer if a merge would require overflowing it then we again continue with the next pair at Step 4

Step 4E (merge)

we merge the 2 blocks and update the buffer fullness and limits

Step 5 (sort blocks)

all blocks are sorted by their less restrictive position limit (=orientation is so that the limit is less restrictive)

Step 6 (reorder lines)

we reorder the actual lines

Breaking Nagravision with knowledge of the PRNG

as there are just 2^15 possible permutations so the naive bruteforce becomes alot more realistic but its still somewhat expensive for realtime decoding, so 2010 used a faster method

Step 1 (downsampling)

to speedup the linecompare later, the lines can be horizintally downsampled

Step 2 (compare)

every keyline is compared against all lines, the best 2 are keept

Step 3 (find seedlists)

for every line triplet (keyline and the 2 best matches) we assume that they will be consecutive
in the decoded image, we look up a list of seeds for which this is true from a precalculated table
or tree structure

Step 4 (find seed)

we find the most often occuring seed in the seedlists and if its number of occurances is above some threshold we decode the image, if not we drop it, this ensure practcally zero wrong decoded images

Step 5 (reorder)

after we know the seed we just need to reorder the lines and fix the chroma

To complement my last blog entry, heres a description of how VideoCrypt works and how it can be broken with reasonable quality

PAL

First before we can talk about VideoCrypt, we need to understand how PAL works
Video information in PAL (and NTSC and SECAM) is stored linewise top to bottom, and interlaced so all the even and then in the next field all the odd lines are stored (313 lines in even fields, 312 in odd from which ~288 lines contain a vissible picture for PAL)
each line has a sync pulse to mark the end of a line, a horizontal blanking interval during which the electron beam in crts “moves” back to the left after the end of the previous line at the right and obviously the vissible part in which brightness = amplitude
In case of Color the U and V components of the YUV color value are stored quadrature amplitude modulated at the color subcarier frequency and the V component has its sign inverted in every 2nd line of a field, theres also a short reference color burst added in the HBI

VideoCrypt

the PRNG seed

Binary data from the vertical blanking interval is feeded into a smartcard which then among other things produces a PRNG seed for the videocrypt decoder, but none of this matters to us here

the actual decryption

The PRNG (pseudo random number generator) outputs a sequence of 8bit values (cutpoints), one for each line of video, each of these lines is then split into 4 parts, parts 0 and 3 are outside the vissible area and arent touched by videocrypt, parts 1 and 2 are the vissible area and are exchanged, the location which seperates 1 and 2 is the cutpoint, videocrypt does nothing special with the color information it just exchanges raw digitally sampled data
because this exchange operation cannot be done with zero-delay the videocrypt decoder will also output parts 1 and 2 one line later then when they where transmitted

Breaking VideoCrypt

Lacking informaion about the PRNG we can only guess the cutpoints based on the assumtation that color/luminance values for pixels which are close will be strongly correlated while distant pixels will have more different color/lumi
still, naive bruteforce would require 256^288 images of w*288 pixels to be compared
depening on how we test a image for how good it is, we are able to significantly reduce the complexity, if we use a score function which is the sum of some compare function which uses just consecutive line pairs and their cutpoints then the dynamic programing algorithm / viterbi algorithm can be used to reduce the complexity to 256*256*288 such 2 line checks, if we now further limit ourselfs to the common cross correlation + some edge detector and only consider a few cutpoint differences close to the best result from cross correlation then the complexity would be w*log(w)*288 + 9*w*288 which is what markus kuhns antisky.c did, though antisky was far from realtime decoding, mainly because it was inefficiently written (floating point code everwhere at a time where no cpu had a reasonable fast fpu, …)

Note, if you think comparing 256^288 images would be stupid, its not, think about choosing the image which is compressed best with jpeg or another codec, this might (or might not) be better then the linewise method

Step 1 (downsampling)

to speedup the cross correlation and other things the whole image can be optionally downsampled

Step 2 (luminance cross correlation)

antisky.c used a FFT based cross correlation, this while asymptotically quite fast is really not fast at all for the case of finding the best matching cutpoint difference in reality, 2010 uses a adaptive comparission which first tries a few coarsly spaced cutpoint differences and then tries recursively more around the better ones, its simpler and faster

Step 3 (missmatched lines detection)

lines which simply cant be matched by cross correlation (mean under some threshold or variance under some threshold or best matching score from cross correlation not much better then average score)
must be marked otherwise the (random) cross correlation result will trash the other surrounding lines

Step 4 (PAL phase detection)

as already described somewhere above, PAL flips the sign of the V component every second line, the first line may or may not be fliped, and if the capture hw doesnt provide us with this info then we need to find it if we want to decode color, one way to solve this is to let the user set the flag and then just flip the flag after every frame, a much more robust method is to compare the color of the first and last pixel of the encrypted line which will be exchanged, these are guranteed to be always adjacent in the decrypted image so they will have almost the same color in the decrypted image, while in the encrypted image their difference depends upon the PAL phase thingy

Step 5 (finding the Chroma phase difference)

we know the approximate cutpoint difference from the luma cross correlation, so we can simply find the chroma phase/hue difference by calculating the complex correlation coefficient (U and V are real and imag values) (note a little care needs to be taken here due to various things i dont remember exactly …)

Step 6 (edge detection)

simply run your favorite edge detector over the 256 possible cutpoints to detect the picture edge, for example log(abs(l[x-2] + l[x-1] – l[x+0] – l[x+1]))

Step 7 (dynamic programming search)

Well here we simply combine all the previous stuff to find the best cutpoint sequence to reach every cutpoint of line X assuming we know the best sequence to all cutpoints of line X-1 already
lines which couldnt be matched to their previous line are a special case which is handled like the first line (every cutpoint has the same score) the same is done with yet another special case, namely the one where no cutpoint is possible anymore, that can happen as we restrict ourselfs to a few relative cutpoints around what the cross correlation guessed is correct and theres a small deadzone in which no cutpoints lie, so not every sequence of relative cutpoints is possible depending upon how you define relative

Step 8 (cutpoint sequence cache)

over some timeperiod cutpoint sequences where repeating after an hour or so, so i added a cache to 2010 which lead to perfect decoding until the repeations dissapeared …

Step 8a (finding the current sequence)

we select several consecutive relative cutpoint pairs and look them up in a hashtable, we also try to add +-1 to both as to compensate for errors in our cutpoint guess
for each pair we will get a list of pointers to cutpoint sequences
we count the number of occurances of each pointer and choose the most often occuring as the correct sequence if its number of occurances is above some threshold or return no match if not

Step 8b (merging the current cutpoint estimates)

we add the current relative cutpoints to the sequence so that each line has a list of relative cutpoints, if that gets too long the least often occuring is discarded
for each line the most often occuring relative cutpoint is choosen and used in later steps, the hashtable is also updated with it

Step 9 (cut and exchange)

this is simple, just 2-3 memcpys and rotating the UV values so as to compensate for the effects of the shift and 1 line delay on the color

A really long time ago, 1997 or maybe it was even a little earlier i wrote a program to decrypt the at that time used analog pay tv systems videocrypt and nagravision sadly i was too afraid of legal issues at that time so i never released either source or binary, well both systems are AFAIK dead nowadays, the old code hasnt been touched since 2000, doesnt compile with any compiler i have, so i thought its the perfect time for finally releasing that trash

When was the first working version born?

well i dont know, the oldest file i could find was a 2do list from 1997 which contains notes about improving videcrypt and nagravision decoding so these must have been working already …

Does it contain any cryptografically new knowlegde about the systems

no, before the nagra PRNG was reverse engeneered i belived that the PRNGs both systems used would be very secure and there would be no point in “looking” at their output, afterwards besides feeling silly as even a blind man would have noticed how the nagra PRNG works (its just permutating 256 5bit values in trivial 32768 ways, 127 only if we ignore new[x]= old[x+C])
i tried to look at the videocrypt PRNG output but failed to find anything, 2 cutpoint sequences where either different and their difference random or there where exactly equal, which happened either commonly (repeating after an hour or so) or never, depending upon when you recorded them, i also failed to find any other relations in the sequences …

Is this clean ANSI C code?

its ultra messy DJGPP-GCC-DOS-C code, i started to clean it but gave up, a patch with my unfinished cleanup work is included for the insane. with the patch a few files compile under current gcc-linux

what else does it do? could it make coffee?

Theres some teletext decoding code, some half working sync suppression decoder (with unmodified hardware) and probably a few other things i dont remember, after all it doesnt compile and i dont have my matrox meteor card here (which was the only card it supported, as that was what i had)

did you port it to java?

yes, i ported part of it to java a really long time ago, why i did that iam not sure anymore, was i seriously beliving the sun propaganda that java was a useable general propose programming language?i guess my excuse is that my previous java code at that time where just tiny applets & applications where the java-effect isnt so noticeable
the java version was even with hand coded mmx over jni about 3 times slower, there where ~1sec garbage collector pauses every 30secs or so and after 15min the computer needed a hard reset (yeah that was even without any mmx/jni)

download this crap\h\h\h\hmasterpiece

2010

license?

GPL but what do you want to do with it?!