Breaking LFSR-based pseudo-random number generators

January 22nd, 2011 · 11 Comments · hacking

Another english post? Yes because this is related to the first Security By Default Wargame that took place a few days ago. Congratulations to Int3pids!

Nowadays, I think most security related people know the importance of random numbers in cryptography. We need to generate IVs, session keys, challenges, tokens, etc. that make our crypto systems secure, if the PRNG is predictable the whole system is shattered (right Sony? btw, remember the “Crypto Tales” talk? check the slide 29 xD)

PRNGs… that’s what made me think about crypto03 for the contest. I hate all those crypto levels which are just a matter of luck, iluminated ideas or non realistic scenarios, so I tried to avoid all of those and show something new.

Here, a file was encrypted with a key obtained from the first 128 bits of a PRNG and as a starting point you had a small stream of bits from the PRNG. The purpose was to break the PRNG to know every output you could obtain, then generate a dictionary of possible keys and crack the encryption. The file was encrypted with 128 bit AES, let’s say non-breakable, but with that PRNG you only got ~32k possible keys, and that’s very very broken.

Unfortunately, this ended in a big #doublefacepalm and from here I apologize, specially to Int3pids and Painsec, who did great at the contest and to Security By Default. Apparently I skipped the lesson where they teach you that 1000 in binary is 8 and not 4, so after doing the hard part I encrypted the file with the wrong key “F76AB499B1DDBD2DAC6D90923E3457A0″ instead of the correct one “F76AB499B1DDBD2DAC6D90923E3857A0″.

Yeah, I know, I deserve a …

Anyways, this post is to explain how to break a LFSR-based PRNG. Well, a LFSR is a shift register where some of the output bits are used as feedback with a linear combination of them. This is really easy to implement both in hardware and in software and probably that’s why they were (still are) so extended.

A LFSR will have a finite number of states and after that the output will repeat itself. Depending on the feedback the output length will be maximized or decreased. The feedback is a linear combination of the output bits so you can represent it as a polynomial.

Disclaimer: the latex plugin is not working properly, I’m sorry for your eyes

For example, a 4 bit LFSR. Input: s3, s2, s1, s0, feedback: C(D) = D^4+D and output: s0, s1, s2, s3, s4, s5, s6, …. Then the connection polynomial is c(x) = x^4 + x + 1 and the new bits will be obtained xor’ing the shift register contents with the bits specified in the polynomial.

I implemented everything on Matlab.

function k = lfsr(c,s0,n);
 
%
% Use:
% k = lfsr(c,s0,n)
%
% Generates a sequence of n bits produced by a shift register LFSR
% with connection polynomial c and an initial state s0.
%
% Input variables:
% c: Coefficients of the connection polynomial
% $c(D)=1+c_1 D + c_2 D^2 + ... + c_L D^L$:
% [1 c_1 c_2 ... c_L ]
% s0: Initial state [s(L-1) s(L-2) ... s(0)]
% n: Length of the sequence we aim to generate.
% Output variables:
% k: Generated sequence
 
if (nargin ~= 3), %number input arguments
    error('The number of input parameters must be 3');
end
if (nargout ~= 1),
    error('The number of output parameters must be 1');
end
if ( (length(c)-1) ~= length(s0) )
    error('The sizes of the polynomial and the initial stated do not agree');
end
 
k = zeros(1,n);
reg = zeros(1,length(s0));
statelen = length(s0);
reg = s0;
mask = c([2:end]); % forget about "+1" value
 
for i=1:n
    k(i) = reg(statelen); % output current bit
    feedback = 0;
    for j=1:statelen
        if ( mask(j) == 1 )
            feedback = xor(feedback,reg(j));
        end
    end
    reg = reg([ end 1:end-1]);
    reg(1) = feedback;
end

Let’s try it:

>> stream = lfsr([1 1 0 0 1], [1 1 1 1], 20)
 
stream =
 
     1     1     1     1     0     1     0     1     1     0     0     1     0     0     0     1     1     1     1     0

An n-LFSR can have 2^n – 1 inner states and under certain conditions a maximal period of 2^n – 1 (if the connection polynomial is primitive modulo 2). They pass statistical tests for randomness so they are good for simulations but as we will now see they’re quite broken.

Primitive what? A primitive polynomial of degree n is an irreducible polynomial dividing x^(2^n – 1) + 1, not dividing x^d + 1 for every d dividing 2^n – 1. Before you run away, let’s have an example:

x^4 + x^3 + 1 is primitive because

is irreducible in Z2
divides to x^(2^4 – 1) + 1:
- x^(2^4 – 1) + 1 = (x^4 + x^3 + 1) * (x^11 – x^10 + x^9 – x^8 + x^6 + x^4 – x^3 – 1)
do not divides neither x^5 + 1 nor x^3 + 1

Another nice thing is that primitive polynomials are sparse so we can do fast calculations on computers.

So, now we want to synthesize the feedback formula given an output. The first option is trying to solve a linear system, have on mind that each inner state corresponds to the next n outputs, so from 2n consecutive output bits we can determine the feedback function.

If you don’t have enough bits to build the equations you would have to bruteforce dependent variables in the linear system.

Other attack (the one I used) is the Berlekamp-Massey algorithm that given a sequence of bits allows you to find the linear complexity and the feedback function of an LFSR.

THE BERLEKAMP-MASSEY ALGORITHM

You can read about it on wikipedia although I implemented it from other notes. You can find multiples references in math/crypto papers.

function [L,C] = berlekamp(S)
 
%
% Use:
% function [L,C]=berlekamp(S)
%
% Obtains the connection polynomial and the linear complexity of
% the sequence $S$.
% Remark: the Berlekamp-Massey algorithm do not returns the
% initial state.
%
% Input parameters: S (Sequence of bits)
% Output parameters:
% L (Linear complexity of the sequence)
% C Polynomial with MSB first
 
% Checking
if (nargin ~= 1),
error('The number of input parameters must be 1');
end
if (nargout ~= 2),
error('The number of output parameters must be 2');
end
 
% Initialization
L = 0;
C = 1;
m = -1;
B = 1;
N = 1;
 
n = length(S);
 
% Loop
while ( N <= n)
    % discrepancy
    sumatory = 0;
    for i=1:L
        sumatory = sumatory + C(i)*S(N-i);
    end
    d(N) = rem( (S(N)+sumatory), 2);
 
    if ( d(N) == 0)
        % Linear complexity of S^(N+1) is L
        % not sure if I need to do sthg.
    elseif ( d(N) == 1 )
        T = C;
        % C = C + B*D^(N-m)
        % C and B have to be same size to be added
        % first we pad B wih zeros
        Bpadded = [ B zeros(1,N-1-m) ];
        % lengths
        lenC = length(C);
        lenB = length(Bpadded);
        if ( lenC > lenB )
            % insert zeros in the beginning
            Bpadded = [ zeros(1,lenC-lenB) Bpadded ];
        end
        if ( lenC < lenB )
            % make C longer
            C = [ zeros(1,lenB-lenC) C ];
        end
        % both are equal length so we can add
        C = C + Bpadded;
 
        if ( L <= (N-1)/2 )
            L = N - L;
            m = N - 1;
            B = T;
        end
    end
 
    N = N + 1;
end

Let’s see if it works:

>> [L C] = berlekamp(stream)
 
L =
 
     4
 
C =
 
     1     0     0     1     1

Now let’s use given bits in Crypto03. Depending on the bits stream the algorithm can converge better, so the best option is to start from a long group of ones (just move some bits forward from the beginning as a starting point)

This was the original bit stream from the PRNG:

10100000000000011000000000000010000000000000011111111111111101010101010101001100
11001100111011101110111010010110100101100011011000110111101101111011010110110101
10110010010011011011100011101101101000010110110110000011011011011111101101101101
01011011011011001101101101101110110110110110100100100100100111000111000111010000
10111101001111100101001110101000110001011001111011110010001010010100011110011100
11110101110100010100110100111100111011000101000101101111001111001001010001010001
11001111001111010001010001010011110011110011101011101011101001101001101001110110
00100111010010000111010011100000101100010111111001000011010101110000010011001011
11110001000110101011110000100110010100000111011100111111010010111010101100011010
01100100001001110111000001110100101111110100111001010100111010001100111010011110
11101001110101101001110100110110001011000100100001101111000111110110101111010100
10011010110011100010011011101000011101101001111101001001110101001110001011001110
10000110111010011111011010011101010010011101001100011101001110111101001110100101
00111010011100111010011101000101100010110000110111100100000100101000111111000110
00010101000010000011001111100000010001010111111100001100101010111110111001100101
01101000100011001001111000010001110101111100001011001010111110010001100101011100
00100011001011111000010001101010000011110110011111101011011101010110010010110011
01110001101110110100001001011011000001110010010000001011100011111110010111101010
10001101011001100001001101110111110001001011010100001110010011000001011100010000
00110100001111111011000001010101101111110011001001010100010001110011000011110100
01000001010011110000001100010100000001000011000000001111101111111110101001010101
01100111001100110111010001000100101100001111000110111110101111011010100110101101
10011101100100100010110111000111100100101111010111000110101100101111011001000110
10110111000010011011010000011101101100000010110110111111100100100101010111000111
00110010111101000100011010110000111101100100000101001000111111001110000101010001
01111100110000110101000100000100110000111111000100000101010000111111001100000101
01000100000011001111000000010001010000000011110011111111101011101010101001101001
10011000100111011101111000101101001010000110110001100000100100001000000111000001
11111101000000101010110000000110011011111111011101101010101101

>> [L C] = berlekamp(prngData)
 
L =
 
    15
 
C =
 
     1     0     0     0     0     0     0     0     0     0     0     0     0     0     1     1

I tried with different subsets of the bits from the PRNG and sometimes I had some curious results.

>> [L C] = berlekamp(prngData2)
 
L =
 
    15
 
C =
 
     1     2     0     0     0     0     0     0     0     0     0     0     0     0     1     1

That “two” could turn into a “zero” or a “one”, means it still was iterating so we could only say it could be x^15+x^14+x+1 or x^15+x+1. But if we are speaking about a cryptographic use we could almost discard the first one because is not primitive, so might not be of maximal period, which is a nice feature in this case.

Of course, there’s a shortcut to solve the challenge, once you decided it was LFSR-based you could take a list of primitive polynomials in modulo 2, try them all and check which one overlaps with the given bits xDD

Once we had the feedback polynomial we still didn’t know the seed but it doesn’t matter. We could generate all 2^15 – 1 keys and try them all.

This was the correct key:

>> key = lfsr([1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1], [1 0 1 0 1 1 0 1 1 1 0 1 1 1 1], 128);
>> fprintf('%d',key)
11110111011010101011010010011001101100011101110110111101001011011010110001101101100100001001001000111110001110000101011110100000

Painsec it seems they just guessed the feedback by checking the stream by hand and Int3pids did a nice script that completed the LFSR sequence although I’m not sure if it would work with any feedback.

To encrypt/decrypt the file I used OpenSSL, the file was a GIF with the flag “aLFSRist00WeaKz” written on it.
That’s all!

–
Fuente original en http://vierito.es/wordpress

11 responses so far ↓

1 Tweets that mention Breaking LFSR-based pseudo-random number generators | It should work... -- Topsy.com // Jan 22, 2011 at 10:39 pm

[...] This post was mentioned on Twitter by Joxean Koret, Roi Mallo, fuska , phr0nak, vierito5 and others. vierito5 said: New post: Breaking LFSR-based PRNGs and about crypto03 from @secbydefault 's first wargame http://bit.ly/f12pj9 [...]
2 Phicar // Jan 24, 2011 at 1:58 am

I enjoyed a lot this post
3 vierito5 // Jan 24, 2011 at 6:56 pm

Thank you Phicar!
4 BatchDrake // Jan 26, 2011 at 12:46 pm

Nice post. It’s a shame we couldn’t enjoy the math then as we were so focused on finding bit patterns, whatever they were.

I have to remark the chaotic behavior of this algorithm: it’s not usual for discrete systems to generate such a complex output (although it was easily hackable when you think a little about it). Maybe I post something in my blog about it.

I wrote a writeup of this challenge. I have to confess, my favourite one of all of them. Take a look (it’s not in English, I hope I have it translated at the end of the day):

http://batchdrake.wordpress.com/2011/01/19/writeup-sbd-wargame-cry03/

Thanks for this challenge btw, it’s been so long since I enjoyed something so much!
5 vierito5 // Jan 26, 2011 at 6:17 pm

I feel rewarded BatchDrake, thank you for your comment and very very nice write-up!
6 Martes13 // Jan 27, 2011 at 5:27 pm

Awesome! very educative!
7 Rompiendo generadores de números aleatorios basados en LFSR, por vierito5 | CyberHades // Feb 5, 2011 at 3:03 pm

[...] Aquí tienes el artículo completo. [...]
8 Rompiendo generadores de números aleatorios basados en LFSR // Feb 5, 2011 at 4:35 pm

[...] Rompiendo generadores de números aleatorios basados en LFSR vierito.es/wordpress/2011/01/22/breaking-lfsr-based-pseud… por mezvan hace 2 segundos [...]
9 Guillermo // Jun 3, 2011 at 12:36 am

I used Berlekamp-Massey and i don’t know wich is my polinomy:

L =

77

C =

1.0e+013 *

Columns 1 through 9

0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0001 0.0001

Columns 10 through 18

0.0003 0.0007 0.0015 0.0030 0.0055 0.0097 0.0163 0.0265 0.0415

Columns 19 through 27

0.0626 0.0915 0.1295 0.1779 0.2376 0.3087 0.3907 0.4822 0.5807

Columns 28 through 36

0.6829 0.7847 0.8815 0.9687 1.0415 1.0962 1.1296 1.1399 1.1267

Columns 37 through 45

1.0909 1.0347 0.9614 0.8750 0.7800 0.6809 0.5820 0.4870 0.3987

Columns 46 through 54

0.3194 0.2501 0.1915 0.1432 0.1045 0.0744 0.0516 0.0349 0.0230

Columns 55 through 63

0.0147 0.0091 0.0055 0.0032 0.0018 0.0010 0.0005 0.0003 0.0001

Columns 64 through 72

0.0001 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000

Columns 73 through 78

0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
10 vierito5 // Jun 3, 2011 at 8:08 pm

@guillermo: On which data? With my implementation? Have you tried starting on different points of the data stream?
11 Guillermo // Jun 5, 2011 at 6:55 pm

Well,i have to find the next 10 numbers of a 1000 numbers..
17678
24994
3327
5175
26793
27970
30228
23396
15205
14274
12045
10281
3702
32550
22798
12337
19389
9585
17708
22985
7524
23857
17326
10885
29629
17740
6023
17197
1372
9
18963
5357
9586
4449
23313
15292
3179
4230
2272
10764
28363
30899
11517
4531
32324
9526
26812
13849
12572
17595
7750
5026
27581
20443
29138
2141
26781
20196
20262
27118
31312
31465
12112
13496
1002
1548
6817
16462
17305
5898
8938
9499
19330
17416
20986
16208
17628
6300
18518
31501
22859
29470
2105
21971
24190
17712
10447
16681
8203
906
28078
21132
25481
20747
32404
27804
750
12540
15207
19844
14635
19622
26728
11945
32005
6167
11962
24983
1589
25136
11538
5671
22723
7154
5311
13812
29342
25353
3805
256
30591
7064
26069
22433
30464
9542
12055
23986
10487
30601
28955
25334
15384
12594
404
15567
4810
26425
6134
32032
2632
16073
20522
12926
10235
7822
6543
7582
18710
829
20020
2042
12403
17252
28244
10181
3756
20084
15378
15632
24701
13067
13173
21565
16216
30854
6821
22948
73
6086
9830
27267
15628
8001
28373
3883
9068
20043
12385
19048
9950
13222
5389
10800
28764
6984
483
17806
10374
22379
9403
21457
30711
12506
15917
18672
23013
2681
25555
9024
7419
1045
14018
22105
11898
10350
19019
32581
2957
29313
14061
19946
29932
13850
5534
20409
16565
14234
24379
1942
26246
32516
27723
32522
8670
12877
4347
15528
18100
740
4437
19388
9304
31360
27075
16697
4745
13097
10179
27108
1239
18056
20204
3516
16443
115
1568
29869
3828
8371
2322
6261
3747
14359
6651
12245
29865
27838
28567
32507
25792
12704
23397
6447
13783
15709
9247
32700
16690
19530
20599
18976
6082
31160
24084
17271
14785
15495
8396
10532
11409
21226
17954
30401
2774
10620
14593
27465
27345
2435
25017
13187
14078
6786
32314
26033
21745
773
3728
14969
13933
13480
4510
12050
12485
12137
3614
31922
13943
18478
9176
4407
20229
16025
8481
29972
26902
11786
22678
19071
25293
9717
13082
20951
25705
30053
14860
8026
26909
30160
5580
28168
4657
24861
15472
15313
8281
32498
19651
6918
12116
13634
20862
25853
4040
18454
26825
14854
23388
21659
3059
31373
7958
21355
29552
9616
14327
11808
21267
18499
15828
13334
27277
27393
6263
31359
9765
10102
6901
29612
19385
21513
16721
18841
28660
28815
27729
18362
12240
16429
14239
24581
27215
15501
17956
5951
30324
20037
8352
25738
4487
30339
654
20526
394
22013
12598
23975
10230
15639
14610
3311
185
12630
11621
32525
18804
5124
17945
2525
19696
22051
30680
18209
3809
26007
25198
27335
21471
16270
12638
27772
16801
21555
19138
20594
4987
10131
26726
7021
7961
23502
30503
15891
9596
4226
22665
884
11317
17268
25239
20183
23264
7807
14847
13510
6371
24257
25197
15197
26471
16644
8486
19918
13207
8042
3560
12088
7447
11355
28161
30889
27847
30387
13741
28271
14265
8999
19380
14503
27246
1783
27460
19199
14424
4058
16395
1998
11148
9509
6296
27223
20678
28222
19186
17496
15266
10816
10105
23257
24344
1262
5629
28210
30264
5340
14620
31069
31015
28380
13279
13437
23129
31398
28055
9903
2064
29899
28661
21263
28180
18907
15208
19725
29619
14036
11706
16370
12795
23245
22253
13740
24117
9699
22610
10465
9381
20835
10731
11827
28544
19769
25090
16592
22061
20120
23305
32317
12480
27626
21428
23907
2995
29177
25940
11481
30694
24158
27766
25715
29400
11050
16315
5643
25382
22482
20729
2446
25924
23392
5266
20554
25723
27607
19220
23414
15394
18149
2322
25090
23840
26575
6465
8608
13217
22169
5333
18193
18710
31861
19997
2484
24179
10606
26972
17996
31395
14164
16362
9489
10575
30185
27019
5882
26064
19532
2062
13896
28272
15270
12585
22102
31720
12051
4755
20126
6422
17618
11362
19727
5885
31920
15783
15245
22786
30641
16199
1225
30052
13568
2332
17474
26108
30744
32075
11675
17718
17459
21991
14110
21327
6386
28870
21392
16336
23629
13731
18231
29514
7613
29300
25641
21842
7847
18957
14806
19135
19468
4341
984
26658
5486
13448
25593
5253
19716
2125
13188
6247
32033
5528
30672
21752
24289
18787
17930
8080
24086
7272
8770
32117
22129
4483
9656
15309
30195
9799
30823
8160
28822
4574
27089
11155
28983
28197
13581
12833
29638
9991
15374
14618
29872
19480
17974
24993
8588
8309
3610
21985
30468
1243
10902
30415
30726
6150
7955
17958
27179
10572
7959
18591
17255
22905
20750
23664
13553
1516
7255
16392
32629
23025
20113
17672
31863
8800
9255
27523
2314
16247
25
24953
15793
20724
24332
8849
8085
30838
20884
13333
14056
19989
2496
14643
13975
25406
18405
23410
8503
28628
12975
17265
5929
1412
26213
7655
14863
25960
18300
26838
20851
21471
25695
1297
7349
1706
29308
18417
32308
2378
12945
2387
27584
13209
18488
27092
20543
3751
20656
19791
19102
17366
17645
17814
30202
29240
29410
26992
9999
1575
6669
21459
19168
28453
30531
18274
21158
20470
19390
12840
22781
1275
11107
3478
27725
7377
7768
22202
10871
7977
25029
6849
6592
15849
21481
21422
27393
19588
22368
4443
4367
6550
14770
10928
22887
1730
26911
29474
29214
31439
1449
12399
2312
2561
6498
19607
28710
28852
1015
29
29525
15423
25981
28798
19252
15878
5242
32497
22869
9440
27446
17249
6567
22700
30787
28583
29987
29742
24137
5899
25012
31022
28438
5628
31596
6867
19942
5647
740
14907
9455
27189
27891
29023
14895
16192
28562
18469
28537
23703
14351
28614
31165
28984
13936
8290
23447
10478
10793
29920
28442
1492
23553
24843
2782
14857
12609
7657
3654
32180
1054
10334
24854
7482
28008
11777
12853
15294
27507
1085
446
1497
4677
1452
16973
20633
12545
29103
7559
24767
6291
10833
10218
22068
28572
27740
4055
30669
16287
23996
5084
23359
10092
3604
19525
9572
24268
17822
5093
24239
30574
15943
7201
6125
1809
8970
30782
23357
9970
29068
11243
9553
29816
6648
2321
25317
32541
31004
26841
11903
20383
2244
3070
19049
29799
25174
11860
4844
16184
28590
6552
25805
8220
26170
17274
13324
18827
26713
17127
20187
2524
26864
10395
2268
1520
11598
1767
19102
16669
2369
13502
16729
7768
12664
6149
10985
18086
16411
795
31240
8387
I think that i can’t used berlekamp because it doesn’t find the polynom

It should work…

Cuando cualquier trasto es útil