efort inutil nagra 3

Nagravision scrambles the image by permuting lines within a eld. In addition,
the boundaries between elds are shifted by 32 lines between the
scrambled and descrambled image as Fig. 1 shows. Line 287 of any eld is
not aected by Nagravision. The last 32 lines (eld lines 255{286) of one
scrambled eld and the rst 255 lines (eld lines 0{254) of the following eld
together form a group of 287 lines that are permuted and then used together
to form a single eld in the descrambled signal. The decoder sends out the
rst line of the descrambled eld while the 33rd line of the scrambled eld
is being received. This line scrambling can be described by a permutation
function p : f0; : : : ; 286g ! f−32; : : : ; 254g which says that eld line i from
the clear image appears as eld line p(i) in the scrambled signal. A negative
eld line number p(i) refers to eld line number 287 + p(i) in the previous
eld. The descrambling permutation p−1 : f−32; : : : ; 254g ! f0; : : : ; 286g is
just the inverse function of p such that line −32 j 254 in the scrambled
eld can be found as line p−1(j) in the descrambled signal. The 4.43 MHz
PAL color burst signal in the back porch is not permuted. However, in the
SECAM variant of Nagravision, the unmodulated 4.406 or 4.250 MHz chroma
subcarrier in the back porch is permuted together with the rest of the line.
Nagravision permutes the 287 lines that will form a eld in the descrambled
signal by buering 32 lines in RAM and by writing and reading lines into
and out of this buer in a pseudo-random order. We shall refer to these 32
buer lines as B0; : : :; B31. While eld line number i is being received, the
content of buer Bv(i) is sent out as the descrambled signal, and then buer
Bv(i) will be immediately overwritten with the signal of the incoming line.]
The buer selection function v has the form
v(i) = ( S(u(i)); for 0 i 254
i − 255; for 255 i 286
:
Using v, we can write the descrambling permutation function as
p(i) =maxfj j−32 j < i ^ v(j mod 287) = v(i)g
p−1(i) = minfj ji < j < 287 ^ v(j) = v(i mod 287)g:
S : f0; : : : ; 255g ! f0; : : : ; 31g is a substitution table stored in non-volatile
memory in the descrambler. It is constant over a long time, but it can be
updated over the radio interface from time to time.
The function u : f0; : : : ; 255g ! f0; : : : ; 255g depends on two parameters
r 2 f0; : : : ; 255g and s 2 f0; : : : ; 127g. It has the form
u(i) = (r + ti) mod 256 with t = 2s + 1:
The 15-bit seed value (r; s) changes for every eld. It is calculated from the
decrypted 64-bit control word that the smartcard sends to the decoder every
two seconds.
Since t = 2s + 1 has no common factor with 256, the function u is for all
combinations of r and t a permutation on f0; : : : ; 255g. The odd numbers
form a multiplicative subgroup in the set of integers modulo 256. This means
that for every i 2 f1; 3; : : : ; 255g there exists exactly one inverse element
i−1 2 f1; 3; : : : ; 255g such that i i−1 mod 256 = 1. With 215 = 32768
M. Kuhn: Analysis of the Nagravision Video Scrambling Method 5
possible combinations of r and t, there are 32768 dierent functions u and
depending on the structure of S there are up to as many dierent functions
v and p possible with a xed substitution table S.
To learn more about the relationship between members of the set VS of all
functions v for a xed S, we rst have a look at the structure of the set U of
all 215 functions u:
For any pair of functions u; u0 2 U with u(i) = (r + ti) mod 256 and u0(i) =
(r0 + t0i) mod 256 there exists exactly one pair of numbers a and b such that
u(a + bi) = u0(i). Proof: The numbers a = (r0 − r)t−1 and b = t0t−1 do
the job, because u(a + bi) = (r + t(a + bi)) mod 256 = (r + t((r0 − r)t−1 +
t0t−1i)) mod 256 = (r + (r0 − r) + t0i) mod 256 = (r0 + t0i) mod 256 = u0(i).
Equivalent transformations are possible in the set VS of functions v. However,
there could exist more than one pair of numbers a and b such that v(a+bi) =
v0(i) for a given pair of functions v; v0 2 VS. This can happen with certain
pathological substitution tables S. For instance, if S(i) = 0 for all i, then
any pair (a; b) will result in v(a + bi) = v0(i) for all i.
The nature of the scrambling method restricts the permutation p by the
condition p(i) < i or equivalently p−1(i) > i, and by the condition that the
sequence p(0); : : : ; p(286) can be split up into 32 monotonically increasing
subsequences. Each of these subsequences corresponds to the sequence of
lines that were stored in one of the 32 buers, that is for any 0 i < j 286
with v(i) = v(j) we have p(i) < p(j). This leaves 32287−32 = 21275 possible
permutations p if S is not known, compared to only 215 possible permutations
if S is known.
3 Attack techniques
The following techniques are based on the observation that in a typical TV
image C, the correlation of two pixels drops quickly as the distance between
these pixels increases. This means for instance that for two pixel luminosities
Cx;y and Cx0;y0 , the average absolute dierence E(jCx;y − Cx0;y0 j) is smaller
or alternatively the normalized correlation E(Cx;yCx0;y0)=qE(C2
x;y)E(C2
x0;y0)
is larger if the two pixels are direct neighbors than if they are many lines
apart. The permuted lines can be sorted back into an arrangement close to
their original order just by rearranging them in a way that maximizes the
similarity (correlation) between neighbor lines.
M. Kuhn: Analysis of the Nagravision Video Scrambling Method 6
3.1 Reconstructing the Permutation
Let Cx;y be the luminosity or even the whole three-dimensional color vector of
the pixel (x,y) in the scrambled eld, where as before negative line numbers
refer to pixels in the preceding eld. Then the matrix K 2 IR288288 shall be
the correlation matrix for a eld, dened as
Ki;j = Pk Ck;i−33Ck;j−33
qPk jCk;i−33j2 Pk jCk;j−33j2
:
Ki;j is a measure for the similarity of lines i − 33 and j − 33. Obviously
Ki;j = Kj;i and Ki;i = 1, therefore we only have to determine Ki;j for all
1 i < j 288. Exchanging two lines i − 33 and j − 33 in the image
C corresponds in K to swapping the contents of the lines i and j, plus
swapping the columns i and j. The goal of rearranging the lines of C to form
the original image corresponds to permuting lines and columns in K to bring
the largest values as close as possible to the diagonal, so that we maximize
the value of a prot function such as
G(K) =
287
Xi=1
Ki;i+1:
This corresponds to nding the permutation matrix P that maximizes the
value G(PKPT). P relates to the permutation p that we want to reconstruct
by Pp(i)+33;i = 1 for all i and all other Pi;j are zero.
In an alternative formulation of the same problem, we look at an undirected
graph GK with nodes Ni (−32 i 254), of which each corresponds to
a eld line i in the scrambled image. The edge connecting Ni and Nj in
this graph has the value Ki+33;j+33 for all i and j. We then look for a
Hamiltonian path (i.e., a path that visits all nodes exactly once) of the form
Np(0); : : :;Np(287), that fulls the previously stated conditions for p and whose
sum of edge labels is maximal. Finding such a path is a variant of the
Traveling Salesman Problem [10, 11], which unfortunately is known to be NPcomplete,
although there exist a number of useful approximation algorithms.
3.2 Reconstructing the Substitution Table
One possible way of determining S is to reverse engineer a Nagravision decoder
and read the entire table out of its non-volatile memory. Since this
procedure might be illegal in some regions, alternative approaches might be
M. Kuhn: Analysis of the Nagravision Video Scrambling Method 7
attempted. A logic analyzer can be used to just observe the sequence of
accesses to the line buers Bi, which results in a large recorded collection of
functions v 2 VS.
If we assume that opening the decoder is also not acceptable for legal reasons,
we can use a PC video adapter to perform a chosen cipher image attack in
which we send to the decoder a test image that contains genuine encrypted
control word information in the vertical blank interval and that uses a redundant
binary code to mark every line with its eld line number. We record the
descrambled test image and by reading the sequence of line number markers
in there, we get the permutation p. If no access to a Nagravision decoder
at all is allowed or possible, we can also attempt to use one of the Traveling
Salesman approximation algorithms to determine samples of p from the correlation
matrix of scrambled TV images alone as described in the previous
section.
In both cases, we have to transform the observed permutations p into buer
access functions v before we can extract S. This can be accomplished with
the following simple algorithm, provided that the given p is error-free: We
set bi := i − 32 for all 0 i 31. Then for each line 0 j 254 that the
decoder outputs, we nd the i for which bi = p(j) and we set both v(j) := i
and bi := j. As a nal check, we verify that after these 255 steps we have
bi = p(255 + i) for all 0 i 31.
In this way, we collect a number of members of VS. Any of these reconstructed
functions v(i) = S((r + ti) mod 256) for 0 i 254 shows all values of S
except for one, but permuted by unknown parameters r and t. We just pick
one v and chose our reconstructed table ~ S such that ~ S(i) := v(i) for all
0 i 254. We then reconstruct another buer access function v0 and
search for parameters a and b such that v0((a + bi) mod 256) = ~ S(i) for
0 i 254 and once we found these (assuming we didn't by bad luck get
some with (a + b 255) mod 256 = 255), we have also found the remaining
value of ~ S with ~ S(255) = v0((a + b 255) mod 256).
We are not concerned about the fact that our ~ S is just a permuted version of
S, because if ~ S(i) = S((a+bi) mod 256) for some (a; b) then this means that
in the correlation search for the correct parameters (r; t) that follows now, we
just nd instead parameters (~r; ~t) that compensate exactly this permutation
of ~ S and result in the same v that we would have obtained with the correct
table S and parameters (r; t).
M. Kuhn: Analysis of the Nagravision Video Scrambling Method 8
3.3 Realtime Determination of the Permutation Based
on a Known Substitution Table
3.3.1 Using Pixel Correlations
Once we know S either by extracting it from a Nagravision decoder or by
determining it as outlined in the previous section, we can reverse the scrambling
rather eciently. A simple approach as implemented for instance in
[12] is to perform a brute force search over all 215 possible (r; t) tuples. For
every possible (r; t) pair, the value of a penalty function is estimated by measuring
the dierence jCx;p(y)−Cx;p(y+1)j between a small number of randomly
selected selected pixel pairs in the scrambled image that would under the
tested (r; t) become neighbor pixels in the descrambled image. This can be
implemented very eciently since the permutation has to be performed only
for the few test pixels and not for the entire image. We search for the (r; t)
pair, for which the penalty function
H =
n
Xi=1 jCxi;p(yi) − Cxi;p(yi+1)j
is minimal. The (p(yi); p(yi + 1)) pairs are precalculated for all 215 (r; t)
pairs for increased eciency. Once this (r; t) pair has been identied, the
corresponding permutation function is used to rearrange all lines in realtime.
A potentially much more ecient approach could be a binary subdivision
search instead of a linear search over all 215 possible (r; t) tuples. To implement
this, we need a preparatory phase in which for a given substitution
table S we build a binary decision tree. Each node in this decision tree lists
a number of test pixel coo***nates (xi; yi) and we branch to the left or the
right subtree depending on whether H for these test pixels is above or below
a threshold. Each leave of this tree is labeled with the (r; t) tuple that shall
be used as the most likely candidate. A carefully built decision tree should
be roughly balanced such that the maximum depth is not much over 15.
3.3.2 Using the SECAM Color Carrier
For Nagravision scrambled SECAM signals, there exists a simple alternative
to looking at pixel luminosity correlations. In SECAM, color is encoded on a
frequency modulated carrier in form of the two dierence signals R−Y (red
minus luminance) and B −Y (blue minus luminance) [8, 9]. The modulated
R − Y and B − Y signals are added on alternating lines, where R − Y uses
M. Kuhn: Analysis of the Nagravision Video Scrambling Method 9
a 4:406 MHz = 282 15:625 kHz carrier and B −Y uses a 4:250 MHz = 272 15:625 kHz carrier to allow the TV receiver to synchronize its color decoder.
The unmodulated color carrier signal is present on the front and back porch
in the horizontal blanking interval and since it is permuted together with the
active line, it is easy to see whether a scrambled line is in the descrambled eld
an odd or even numbered line. The sequence of 4.406 MHz and 4.250 MHz
color carrier frequencies in the back porch of a scrambled SECAM signal is
characteristic for the (r; t) pair that has been used to scramble this eld.
A pirate decoder only has to form a bit string representing the sequence of
carrier frequencies found in the back porches of the lines 255{286 and use
this bit string as the key in a hash-table lookup to access the (r; t) pair
that descrambles this sequence correctly into one with alternating carrier
frequencies. This (r; t) pair is then used to descramble the remaining eld
correctly.
Commercial hardware implementations of this attack became available in
France around 1995 [13]. As a counter measure, the broadcaster Canal+
uploaded a new substitution table S that ensures that the sequence of the
color carrier frequencies is always alternating and therefore does not leak
information about the (r; t) pair. An improved version of the attack looks
not only at the frequency but also at the phase of the color carrier in the back
porch. The SECAM color carrier is phase shifted by 180 for every third line
to suppress visible dot patterns caused by the carrier signal. Again, a bit
sequence that indicates which of the rst 32 lines shows this phase shift acts
as a hash-table lookup key to nd the appropriate (r; t) pair quickly.
Since the PAL color burst is not permuted, the SECAM color carrier attack
technique cannot directly be transferred to Nagravision for PAL. However,
with the continuing introduction of the EBU Wide Screen Signal (WSS) in
frame line 23 [14], the rst line in every second clear eld often has an easily
recognizeable known structure. If theWSS line can be located in line w of the
scrambled eld, then we know that 0 > p(0) = w and v(0) = w +32 = S(r),
which reduces the number of possible r values from 256 down to around 8
and speeds up the (r; t) search by a factor of 32.
4 Properties of the Substitution Table
The substitution table S used by the broadcasters Premiere, Teleclub and
many others until today has the form
10, 11, 12, 13, 16, 17, 18, 19, 13, 14, 15, 16, 0, 1, 2, 3,
M. Kuhn: Analysis of the Nagravision Video Scrambling Method 10
21, 22, 23, 24, 18, 19, 20, 21, 23, 24, 25, 26, 26, 27, 28, 29,
19, 20, 21, 22, 11, 12, 13, 14, 28, 29, 30, 31, 4, 5, 6, 7,
22, 23, 24, 25, 5, 6, 7, 8, 31, 0, 1, 2, 27, 28, 29, 30,
3, 4, 5, 6, 8, 9, 10, 11, 14, 15, 16, 17, 25, 26, 27, 28,
15, 16, 17, 18, 7, 8, 9, 10, 17, 18, 19, 20, 29, 30, 31, 0,
24, 25, 26, 27, 20, 21, 22, 23, 1, 2, 3, 4, 6, 7, 8, 9,
12, 13, 14, 15, 9, 10, 11, 12, 2, 3, 4, 5, 30, 31, 0, 1,
24, 25, 26, 27, 2, 3, 4, 5, 31, 0, 1, 2, 7, 8, 9, 10,
13, 14, 15, 16, 26, 27, 28, 29, 14, 15, 16, 17, 18, 19, 20, 21,
22, 23, 24, 25, 5, 6, 7, 8, 19, 20, 21, 22, 12, 13, 14, 15,
17, 18, 19, 20, 27, 28, 29, 30, 10, 11, 12, 13, 11, 12, 13, 14,
6, 7, 8, 9, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 6, 7,
3, 4, 5, 6, 8, 9, 10, 11, 15, 16, 17, 18, 23, 24, 25, 26,
29, 30, 31, 0, 25, 26, 27, 28, 9, 10, 11, 12, 21, 22, 23, 24,
20, 21, 22, 23, 30, 31, 0, 1, 16, 17, 18, 19, 28, 29, 30, 31
This particular table has the curious property
S(i) = (S(i − i mod 4) + i mod 4) mod 32;
but it is not clear what the reason behind this is.
The broadcaster Canal+ in France replaced the above table in September
1997 with the following one, as a response to the availability of unauthorized
Nagravision for SECAM decoders that reconstructed the (r; t) pair from the
sequence of the color carrier frequencies in the scrambled image:
0, 1, 2, 3, 4, 5, 6, 7, 2, 5, 4, 7, 8, 9, 10, 11,
14, 17, 16, 19, 22, 25, 24, 27, 28, 31, 30, 1, 24, 27, 26, 29,
8, 11, 10, 13, 20, 23, 22, 25, 20, 21, 22, 23, 30, 31, 0, 1,
16, 17, 18, 19, 28, 29, 30, 31, 10, 11, 12, 13, 16, 17, 18, 19,
12, 15, 14, 17, 0, 1, 2, 3, 20, 23, 22, 25, 18, 19, 20, 21,
22, 25, 24, 27, 26, 27, 28, 29, 18, 21, 20, 23, 10, 13, 12, 15,
28, 29, 30, 31, 4, 5, 6, 7, 22, 23, 24, 25, 4, 7, 6, 9,
30, 1, 0, 3, 26, 29, 28, 31, 2, 5, 4, 7, 8, 9, 10, 11,
14, 15, 16, 17, 24, 27, 26, 29, 14, 17, 16, 19, 6, 9, 8, 11,
16, 19, 18, 21, 28, 31, 30, 1, 24, 25, 26, 27, 20, 21, 22, 23,
0, 3, 2, 5, 6, 7, 8, 9, 12, 13, 14, 15, 8, 11, 10, 13,
2, 3, 4, 5, 30, 31, 0, 1, 24, 25, 26, 27, 2, 3, 4, 5,
30, 1, 0, 3, 6, 9, 8, 11, 12, 15, 14, 17, 26, 27, 28, 29,
14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 4, 7, 6, 9,
18, 21, 20, 23, 12, 13, 14, 15, 16, 19, 18, 21, 26, 29, 28, 31,
10, 11, 12, 13, 10, 13, 12, 15, 6, 7, 8, 9, 0, 3, 2, 5
M. Kuhn: Analysis of the Nagravision Video Scrambling Method 11
This new table has the property S(i) i (mod 2). This way, the resulting
permutation always alternates between odd and even numbered lines and the
sequence of color subcarrier frequencies in a scrambled SECAM image can
only reveal the value r mod 2 and not the complete r and t values.
If S were selected such that
i 6 j (mod 6) =) S(i) 6= S(j);
then even the combination of color carrier phase and frequency, which is
repeated every six lines in the clear signal, could only reveal r mod 6 and
t mod 3. Apparently the Canal+ or Kudelski technicians who designed the
above countermeasure table failed to understand the threat of a color carrier
phase analysis at that time.
5 Conclusion and Final Remarks
Nagravision uses a surprisingly weak scrambling technique that can rather
easily be defeated without using any cryptographic secrets that might be
stored in the subscriber smartcard. While image processing attacks can only
approximate the original signal for cryptographic scrambling systems such
as VideoCrypt and EuroCrypt, Nagravision allows the attacker to determine
reliably the seed value in such a short time that the clear image can be reconstructed
without any quality loss in real time using standard personal
computers or decoder designs that cost not much more than the ocial decoder.
The color-carrier sensing pirate decoders for the SECAM version of
Nagravision can easily be defeated by a more carefully designed substitution
table. Whether lasting countermeasures are possible against pixel-correlation
based pirate decoders depends on whether the broadcasters can upgrade the
elded decoders easily to use a larger set of permutation parameters than 215
and whether v can be replaced by a cryptographically strong cipher function.
This paper is work in progress and might still contain errors. I started writing
it in order to get a better understanding of the mathematical properties of
the Nagravision scrambling method and the algorithms used in the various
currently available pirate decoders. These have been designed by individuals
who want to stay anonymous because they are afraid that the work on these
decoders might be considered illegal in their home country (France). I also
wrote this paper to collect and discuss possibly useful ideas and insights
towards more advanced attacks and countermeasures. Since the Nagravision
system is anyway scheduled to be replaced by a DVB conditional access
M. Kuhn: Analysis of the Nagravision Video Scrambling Method 12
system, I do not think that publishing my thoughts on the topic can do any
economic harm, but I hope they might be of some educational benet.
Special thanks to Fabian Petitcolas, Roberto Deza Asensio, and \Zorglub" for
comments on the paper and to Ralph Metzler for providing frame-grabber
images for experiments. Suggestions for improving this text are very welcome.