Lair Of The Multimedia Guru

2024-01-24

How correlated is pcg-dxsm output?

Lets try picking some correlated combinations with (using my very simple pcg-dxsm implementation)

Multiplier 15750249268501108917 15750249268501108917 15750249268501108917
Increment 123456789 15750249268624565705 31500498537125674621
Seed 31415 31414 31413
0x563B0DB76F45EEC2 0xDEE2CC4990CDBE1E 0xDEE2CC4990CDBE1E
0x064C612B5E0A4853 0x064C612B5E0A4853 0x704228ECB09FC1D5
0x4727428C93C1A285 0x5A7E3EA39E71C29F 0x5A7E3EA39E71C29F
0x2745482D3BDBC1C0 0x2745482D3BDBC1C0 0x15D15980AE293340
0x6055DF5FCE178AB2 0xC5DC9DC897A78F1E 0xC5DC9DC897A78F1E
0x05DDF19C395C342F 0x05DDF19C395C342F 0x51705B299006C1C1
0xD7AFDA4C1654626B 0x89A204161A53CA99 0x89A204161A53CA99
0x2C1FCD6649DB8016 0x2C1FCD6649DB8016 0x338710EA7C027382
0xEDE28080A228A6DC 0xED272B75717128A4 0xED272B75717128A4
0xB05EFD2651E59BC7 0xB05EFD2651E59BC7 0x20911E0B5D6AE551
0xD6045D380A566F2D 0xE6584BDE2C470387 0xE6584BDE2C470387
0x1BF91549D870370F 0x1BF91549D870370F 0xF434399E25ED24B5
0x1D9EB55CB071B60A 0x1DA3A160F1C93F66 0x1DA3A160F1C93F66
0x892A16096BF94286 0x892A16096BF94286 0x8F5678078367E87A
0xA7292EEE7AF4777F 0x281913D2D3F2DFC5 0x281913D2D3F2DFC5
0x08AB29210A0B6FF1 0x08AB29210A0B6FF1 0xC0DD5B88BF6885A3
0x20E581A9EA8BF155 0xB17BBB3957418DBB 0xB17BBB3957418DBB
0x768E7BD7B5223C36 0x768E7BD7B5223C36 0x086B7F8F81A5CEDA
0xF67313E1E5454A96 0xD3026BC096FEDDE2 0xD3026BC096FEDDE2
0xAB091F6C4C169476 0xAB091F6C4C169476 0xF29E461BBD7C6952
0xB18D1BC34F78E4D1 0x205033BF4C77D237 0x205033BF4C77D237
0x5BBCD31929B10ED3 0x5BBCD31929B10ED3 0xFDCB8D05F8C862FD
0xC64AFD5DFC7654A7 0x54C875057AAA9DCD 0x54C875057AAA9DCD
0x34866A3DF2054E13 0x34866A3DF2054E13 0x4C9D903AB9738D79
0x29CA92D156E93DD4 0x1174B427B597C82C 0x1174B427B597C82C
0x46B0D6BFFE3BD1C3 0x46B0D6BFFE3BD1C3 0x18A4BCCC15242755
0x74DF62C8A26F65CD 0xF5CAC48CFC7B4D47 0xF5CAC48CFC7B4D47
0xE737155A33FC916F 0xE737155A33FC916F 0x2A8E83BF16B3C6F5
0x0E0E87DB2724235B 0x82EA039F9945EE0D 0x82EA039F9945EE0D
0x2367AB4D5FA3ABBE 0x2367AB4D5FA3ABBE 0x274FC0D71A60FF82

Besides the exactly equal ones, the more carefull reader will have noticed that each line either has even or odd entries, so the 3 seed/increment pairs generate equal results in the lowest bit.

You might ask why does this all happen? Well, the identical numbers happen because the lowest bit is ored away in DXSM, that is forced to be 1. So any cases differing only by that bit at the LCG stage become identical in later stages. The other similarities happen because the mixing isnt as good as it needs to be to remove all differences from very similar input and LCGs can produce such very similar input when one picks the “wrong” parameters.

Did i hand pick the worst ? Is that the only case ?
lets see

Multiplier 15750249268501108917 15750249268501108917
Increment 123456789 1134925067785824341058664979018534165
Seed 31415 340282366920938463463302549837730314935
0x56 3B0DB76F45EEC2 0x04 3B0DB76F45EEC2
0x06 4C612B5E0A4853 0xC7 4C612B5E0A4853
0x47 27428C93C1A285 0x54 27428C93C1A285
0x27 45482D3BDBC1C0 0xE7 45482D3BDBC1C0
0x60 55DF5FCE178AB2 0x96 55DF5FCE178AB2
0x05 DDF19C395C342F 0xCE DDF19C395C342F
0xD7 AFDA4C1654626B 0xEE AFDA4C1654626B
0x2C 1FCD6649DB8016 0xE2 1FCD6649DB8016
0xED E28080A228A6DC 0xD1 E28080A228A6DC
0xB0 5EFD2651E59BC7 0x75 5EFD2651E59BC7
0xD6 045D380A566F2D 0x03 045D380A566F2D
0x1B F91549D870370F 0xEE F91549D870370F
0x1D 9EB55CB071B60A 0xCB 9EB55CB071B60A
0x89 2A16096BF94286 0x83 2A16096BF94286
0xA7 292EEE7AF4777F 0xCA 292EEE7AF4777F
0x08 AB29210A0B6FF1 0xE1 AB29210A0B6FF1
0x20 E581A9EA8BF155 0x53 E581A9EA8BF155
0x76 8E7BD7B5223C36 0xC8 8E7BD7B5223C36
0xF6 7313E1E5454A96 0x9C 7313E1E5454A96
0xAB 091F6C4C169476 0x19 091F6C4C169476
0xB1 8D1BC34F78E4D1 0x64 8D1BC34F78E4D1
0x5B BCD31929B10ED3 0x70 BCD31929B10ED3
0xC6 4AFD5DFC7654A7 0x59 4AFD5DFC7654A7
0x34 866A3DF2054E13 0xE7 866A3DF2054E13
0x29 CA92D156E93DD4 0x55 CA92D156E93DD4
0x46 B0D6BFFE3BD1C3 0x0F B0D6BFFE3BD1C3
0x74 DF62C8A26F65CD 0x31 DF62C8A26F65CD
0xE7 37155A33FC916F 0xAA 37155A33FC916F
0x0E 0E87DB2724235B 0x67 0E87DB2724235B
0x23 67AB4D5FA3ABBE 0x05 67AB4D5FA3ABBE

Here 7 out of 8 bytes match apparently for each. Is that the worst ? no we could make part of the first byte match too, it just becomes harder to color the table to match that.

Filed under: Cryptanalysis,Pseudo random number generators — Michael @ 18:08

Breaking pcg-dxsm (no implementation)

All PCG implementations seem to allow more or less easy computation of the seed, but a new PCG implementation has appeared in 2019 or so.
PCG-DXSM, the source code tells us “This is a new, more powerful output permutation” and “This latter aspect means that the scrambling applied to the high bits depends on the low bits, and makes it (to my eye) impractical to back out the permutation without having the low-order bits.”
Ok. lets try
Heres for reference, what this is about:
multiplier is a odd 64bit constant, SHR1 is half the state bits, SHR2 is quarter the state bits and SHR3 is 3 eights of the state so 64, 32, 48 for the 128/64 bit variant and 32, 16, 24 for the 64/32bit one. inc is forced to be odd too.

    state = state * multiplier + inc;

    l1 = state | 1;
    h1 = state >> SHR1;
    h2 = h1 ^ (h1 >> SHR2);
    h3 = h2 * multiplier;
    h4 = h3 ^ (h3 >> SHR3);
    return h4 * l1;

l1 is forced to be odd as we can see, so what do we know if pcg_dxsm returns 0 ? When is X * (2Y+1) = 0 ? Yes when X is 0 so h4 has to be 0 (yes i jump over some details of rings) and what can h3 be ? only 0, and h2 ? again only 0 and h1 ? yes its 0.
So when pcg_dxsm() return 0 you just learned half its internal state.
This can be extended a bit, for example when it returns a odd number h4 must be odd, when it returns a number that contains a factor of 2x then so must h4.

Can we compute the seed and increment from this ? I did not try, but i think so.
Just consider this: we decide how many bits we want to look for in the data and we brute force the rest. (there quite possibly could be an easier way, thats just the obvious one)
if we want 16bits to be from the data we would look for about 100k output data values, look for the values that are multiplies of 65536, these points would have h4 a multiple of 65536 and thus the low 17bits of h4 would be known. If we now brutefoce the 32-17 that is 15 low bits of the state and increment, these together fully determine, first all the low 15bits of all states and together with that the cases where we know the low 17 bits of h4 we now can invert the multiply and find the rest of h4. For each known h4 its trivial to find the upper half of the state. And the rest is identical to finding the state and increment of a truncated LCG and after the upper bits are found the lower can be trivially found from the h4*l1.
As i have not implemented this it is very possible that i have missed something or made some mistake.

Btw i think PCG and other PRNGs are really great little math exercises. Some are also good PRNGs as long as one understands their limitations.

Filed under: Cryptanalysis,Pseudo random number generators — Michael @ 02:44

2024-01-16

simple and good PRNGs

As ive looked at many PRNGs in the last few days, heres a quick list/note about which seem good.
To be on this list they must be

  • Fast
  • Fail 0 general statistical tests
  • 64bit output
  • minimum period of at least ~264

I tried a bit to create a list of diverse types of generators. If i hear about any of these generators failing some tests, i will remove them (unless i forget), i also may add more in case i see others in the future. The list is in alphabetical order. None of the generators is secure, and i expect that the state can be found from the output with little effort for every fast PRNG. Some of these generators allow efficient seeking. For others I do not know how to efficiently seek.
Also see https://pracrand.sourceforge.net/RNG_engines.txt, https://prng.di.unimi.it/,

Name state period seekable Class
MWC256 256bit ~2255 yes multiplicative congruential generator with prime modulus
SFC64 256bit ≥264 ? chaotic RNG + counter
splitmix64 64bit 264 yes counter + mixer
xoroshiro128** 128bit 2128-1 yes LFSR + mixer
XSM64 256bit 2128 yes LCG + mixer

This omits basic LCGs, LFGs, LFSRs as well as simple variants of these because they fail tests. (The mersene twister is a purely linear generator and fails related tests).
JSF64 is omitted because its minimal cycle length is unknown, and thats like using code that very likely will work instead of knowing it will work for no compelling advantage.
PCG is omitted because all variants i saw either fail some test or are slower than the generators listed above. Also PCG has issues with sequence correlation because LCGs have that issue. The generator most similar to PCG in the table above is XSM64
Cryptographic PRNGs are omitted because they are slow.
xoroshiro /xoshiro plus are omitted as they fail tests. I picked one from what remained.

SFC64 and XSM64 are testet here The others in the table ive tested with practrand to 32TB:
mwc256_test,
splitmix64_test,
xoroshiro128starstar_test
also several of them have been tested here,

Filed under: Pseudo random number generators — Michael @ 22:09

2024-01-12

SFC64

As i was looking for the best PRNG ;) i found SFC64, its fast, seems to pass all tests, and it was fun to find a way to compute the seed from a few output values.
But the more one looks the more one finds, there are many other great PRNGs. I would stay away from hyped up generators, like the mersene twister was in the distant past and PCG is now. PCG isnt “bad” but its not that fast, and some of the claims surrounding, if taken litteral (like about security, difficulty predicting output or ability to generate uncorrelated data by adjusting the increment) can lead to bad results.

Now about SFC64, heres a simple implementation. It can also compute values backward.

And for fun, heres an implementation that will turn 10+ values back into the 3 seeds and counter used to create them.
The way this works is that first we guess the 16-19 MSB of the a or b register. Next we assume that the corresponding MSB of the counter are 0. Because its 64bits, thats reasonable and pretty difficult to be otherwise. From this and a = b ^ (b >> 11) and tmp = a +b + counter++; we can estimate teh MSBs of the future and past a and b registers (they slowly become less exact due to the counter but thats insignificant over the distance we need them)
For the 8 rotation states we then invert b = c + (c << 3); for the MSBs we have (which has 9 solutions and iterating over them gives us 3 extra bits knowledge of c). The 8 rotation states are iterated over in 2 forward steps of 3 followed by a backward step of 5. This way we minimize the distance we move away from the start point which limits effects of the unknown LSBs and also limits the needed amount of data. In addition the 3,3,-5 pattern splits the previously determined part of the c register so that the lower part of the MSB becomes shifted into the MSB. This allows us to check the lower part of our data from the c register together with the MSB of the b register at that point and the known output data. This is crucial to limit the otherwise exponential increase of computations with each part of c that is iterated over. Towards the end of the c register, we then compute the a,b and counter from it and the known output and if it matches, backstep to counter =1 to output the seed at the start. It would also be possible to use a heuristic in guessing the initial a/b values, so as to not search the 17-19 bit space but it seems the bad ones get rejected naturally quickly so this lead to little gain and its already quite fast.
I do realize after writing above that this description is probably hard to understand. I should expand this and draw diagramms, but ATM i have no time so please read the source :)

Example: of finding the seeds after 1000 rounds

./sfc64 0x123456785 0x978653 0xCCAADDEE0F 1000 30 16 
0x8A9912C022EA7402
0x26971AE36A1CEACA
0x97B4CF575274B9F4
0xC9212C12EEE58E49
0x9B45979745BB2E20
0x857B5EEB83507D6D
0x243E719FF5356874
0xE6EB4E22DDDEDCA6
0xAF0DC4AF0234A763
0x9946B8BD21C71BE9
0x14D42990A607161B
0x66A19FF0771F930C
0xE3E580CA96D08FD3
0xDAED73C40D44E397
0x90A0E96731283123
0x183075440F78DA33
0xE46ACCC1AECD9C6C
0x1CA82D6053C47933
0xC707C633E34377CA
0xF60FC6DB95DE2631
0x0B2342552B1B4912
0xC32F27E766B148FD
0x055FDF9DC44345CF
0xADFD892D38628512
0x5AA6881F0C6E3ADE
0x72FD99BE0899B07C
0x6F31D2773AB970F6
0xC07850CC6EFD7868
0x5EC7E6C020A407CA
0xF048FCEDEA87BE0A


time ./sfc64-breach  0x8A9912C022EA7402 0x26971AE36A1CEACA 0x97B4CF575274B9F4 0xC9212C12EEE58E49 0x9B45979745BB2E20 0x857B5EEB83507D6D  0x243E719FF5356874 0xE6EB4E22DDDEDCA6 0xAF0DC4AF0234A763 0x9946B8BD21C71BE9 0x14D42990A607161B 0x66A19FF0771F930C 0xE3E580CA96D08FD3 0xDAED73C40D44E397 0x90A0E96731283123  0x183075440F78DA33 0xE46ACCC1AECD9C6C 0x1CA82D6053C47933 0xC707C633E34377CA 0xF60FC6DB95DE2631 0x0B2342552B1B4912 0xC32F27E766B148FD 0x055FDF9DC44345CF 0xADFD892D38628512 0x5AA6881F0C6E3ADE 0x72FD99BE0899B07C 0x6F31D2773AB970F6 0xC07850CC6EFD7868 0x5EC7E6C020A407CA 0xF048FCEDEA87BE0A
attempt 0
Found (a=0x0000000123456785 b=0x0000000000978653 c=0x000000CCAADDEE0F counter=0x0000000000000001 original_counter=1002
step 5121675

real	0m0.083s
user	0m0.071s
sys	0m0.012s

Filed under: Cryptanalysis,Pseudo random number generators — Michael @ 02:09

2024-01-08

Finding the increment of PCG/LCG/truncated LCGs and some (for me) surprising consequences about their structure.

For plain LCG the problem is trivial and an implementation shown in my last post. PCG falls in 2 categories, the PCG-XSL-RR which is based on an LCG, this was solved in the Paper by Bouillaguet, Martinez and Sauvage.
The remaining PCG generators are different and simpler, they are based on an truncated LCG. The problem of finding an increment and seed is marginally harder as it is for the corresponding truncated LCG. It can be done using Lattice reduction (even some half bastardized version seems to work). The problem and the surprise for me really is that the solution in general is not unique. I guess it was a surprise after reading in the original PCG paper how additional random streams can be created by changing the increment. This is really not true. Changing the increment does not really produce “different” random data, it just offsets it.

Let me first show an example with a plain LCG (using the multiplier 6364136223846793005 from PCG with 64bit state)

Seed 314159 314160
Increment 1442695040888963407 13525302890751722019
Output0 1758213515780721042 1758213515780721043
Output1 8369501526408240633 8369501526408240634
Output2 14286244372924288276 14286244372924288277
Output3 12908628925188209107 12908628925188209108
Output4 17643264774698309734 17643264774698309735
Output5 10761879962653451581 10761879962653451582
Output6 11615400545074122760 11615400545074122761
Output7 5243018629741398711 5243018629741398712
Output8 1055069346400300154 1055069346400300155
Output9 14628082432468752577 14628082432468752578

This is not a odd exception, no, for every choosen LCG and choosen offset (here it is +1) theres a seed and increment that will produce a offset sequence of random numbers.
You can use lcg-breach to find them by just asking it to find parameters for a modified sequence.
Now thats LCGs, What about truncated LCGs ? its worse because they discard the low bits. You get sequences that can be exactly equal for MANY values even with different increment and seed. And that is what the problem is in determining the increment for truncated LCGs and the corresponding PCGs. For PCG-XSL-RR the low LCG bits are XORed in so there remains a effect on the output and its possible to determine the increment but for 128/64 and 64/32 PCG-XSH-RR the low bits of the state do not affect the output as long as their effect stays limited to these low 27bit (for 64/32 bit) in future states they cannot be computed from the output. Or in other words the output from 2 PCG-XSH-RR with differing increments can be identical for a long time.

On top of that, there is also a set of seed,increment pairs that produce constant output.
consider this:

LCG         : out[i+1] = out[i] * m + a mod n
what we want: C        = C      * m + a mod n

just solve it:

C - C * m = a mod n

choose the constant C you want and this will tell you the increment a that will keep the generator at that constant when its started on it.

and how do we now create a offseted LCG ?
simply add it with the constant above

out[i+1]     =  out[i]      * m + A     mod n
           C =           C  * m +     a mod n
out[i+1] + C = (out[i] + C) * m + A + a mod n

And yes LCGs of the same multipler and modulo seem to form an abelian group with addition.

Filed under: Cryptanalysis,Pseudo random number generators — Michael @ 18:06

2024-01-06

Breaking LCGs

Just for fun, heres a program to generate random numbers using a Linear Congruential Generator from a specified multiplier, increment, seed and number of bits.
And a second one that will tell you the multiplier, increment, seed for a given 3 output numbers from above.

Have fun encrypting important messages


./lcg 64 6364136223846793005 1442695040888963407 314159 5
1758213515780721042
8369501526408240633
14286244372924288276
12908628925188209107
17643264774698309734

$ ./lcg-breach 64 1758213515780721042 8369501526408240633 14286244372924288276
Seed: 314159 0x000000000004CB2F
Multiplier: 6364136223846793005 0x5851F42D4C957F2D
Increment: 1442695040888963407 0x14057B7EF767814F

Filed under: Cryptanalysis,Pseudo random number generators — Michael @ 01:00

2024-01-04

Breaking the PCG-XSH-RR PRNG

How did this start ? Someone found a bug or 2 in the libavutil/eval.c random(), so i proposed a patch replacing it by Marsaglias 64-bit KISS PRNG. Nicklas Haas then ask me why iam not using PCG yesterday. And i didnt know really what PCG is :) so i looked found the paper found a wegpage that was down the exact day i tried to look at it (yeah its up again now). And a wikipedia page taking about “It has been shown that it is practically possible (with a large computation) to recover the seed of the pseudo-random generator given 512 consecutive output bytes.”. That triggered me a bit ;)

The paper about PCG is 58 Pages so reading that is not an option. But we skim it and look at the pretty pictures, theres one that marks several PCG variants as insecure. Luckily the one listed at wikipedia (PCG-XSH-RR is not marked as insecure) In fact there are 2 PCG-XSH-RR, one with 64bit state and 32bit output and one with 128bit state and 64bit output. So i tried them. Theres also a paper about breaking PCG-XSL-RR which differs by some shifts it seems from XSH. That paper talks about also recovering the increment and that for that it needs “512 bytes of challenge input;in the worst case, the process takes 20 000 CPU hours” ugh, i dont have that. Luckily we know the increment as its not a variable in the implementation and with that, the paper tells us “breaking XSL-RR needs 23 core minutes”. But we took XSH-RR because it was on wikipedia :) and the original paper also recommends it

6.3.1 32-bit Output, 64-bit State: PCG-XSH-RR
Here the design goal is to be a good all-purpose random number generator. The intent
is to balance speed with statistical performance and reasonable security, charting a
middle-of-the-road path. (It’s the generator that I recommend for most users.)”

So we are not totally wasting our time but we can have fun exercising breaking a “not insecure” PRNG with “reasonable security”.

A few hours later, am i lucky ? am i smart ? or is the PCG-XSH-RR a insecure generator, i dont know, I think i maybe picked the easier one but still. These following need 3-4 output values from the PCG-XSH-RR to find and verify its state, from which all future and past output can be computed.
For the 64/32bit variant we compute all tables at runtime, for the 128/64 variant we hardcode the 152 entry table needed as it needs a few minutes to be computed. But the table doesnt depend on the seed nor on the increment, just a new multiplier would need a new table.
The actual execution for both including loading the program, generating the random numbers finding the seed again and printing it all together takes less than 100ms
Code is here


time ./pcg-xsh-rr-64-32-breach $((0x1234578ACDEF11))
INV 0xC097EF87329E28A5 0x1 gcd=0x1
Seed = 0x1234578ACDEF11
PCG output 0 = 0x90DA0D79
PCG output 1 = 0xCF0EAEE6
PCG output 2 = 0x423D36BE
PCG output 3 = 0xAE152565
PCG output 4 = 0x2C48B4D4
PCG output 5 = 0x9EE6CC50
PCG output 6 = 0x903FC56A
PCG output 7 = 0xC85B3AED
PCG output 8 = 0x87B29579
PCG output 9 = 0xA486F671
Table 0 0x00000000000000005851F42D4C957F2D 0x0000000000000001
Table 1 0x000000000000000008F5DC87E5C07D87 0x0000000000000003
Table 2 0x00000000000000000148A921ACEF6819 0x000000000000001D
Table 3 0x00000000000000000006C363D4CB5B28 0x00000000000000C8
Table 4 0x00000000000000000002BCFA0DFD0A8F 0x000000000000262B
Table 5 0x00000000000000000001738A552BC485 0x00000000000071B9
Table 6 0x000000000000000000002A1A9C5A7E7B 0x000000000000BD47
Table 7 0x0000000000000000000007652A02ADCE 0x00000000000635C6
Table 8 0x0000000000000000000002445FB59459 0x000000000024855D
Table 9 0x0000000000000000000001AC54D3A396 0x00000000008BDFAE
Table 10 0x00000000000000000000011449F1B2D3 0x0000000000F339FF
Table 11 0x00000000000000000000007C3F0FC210 0x00000000015A9450
Table 12 0x000000000000000000000060733D935D 0x00000000031C82F1
Table 13 0x000000000000000000000044A76B64AA 0x0000000004DE7192
Table 14 0x000000000000000000000028DB9935F7 0x0000000006A06033
Breaching spin:.........................................................................................................................................................................................................................................................................................................................
Candidate 0x48EAFC5649EE9492 for 90DA0D79 CF0EAEE6 423D36BE
found Seed = 0x1234578ACDEF11

real 0m0.074s
user 0m0.074s
sys 0m0.000s


And the PCG-XSH-RR-128/64 one:

time ./pcg-xsh-rr-128-64-breach $((0x1234578ACDEF11))
INV 0x98ABC8B0716EAC8D 0x1 gcd=0x1
Seed = 0x1234578ACDEF11
PCG output 0 = 0xE49F66304A892198
PCG output 1 = 0x58C80AA8C2F10A26
PCG output 2 = 0xD2B380859B808368
PCG output 3 = 0x60715FDB8EE68956
PCG output 4 = 0xB0D0AAF3073F2EDA
PCG output 5 = 0xC5876DE56C99EDB3
PCG output 6 = 0x68371CCDC061F3D
PCG output 7 = 0x7118EC9199028ED5
PCG output 8 = 0xAC0DAAF55D9A009C
PCG output 9 = 0x709AD75080EDE32E

Breaching spin:.................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
Candidate 0x5928FB686BFAEF01 for E49F66304A892198 58C80AA8C2F10A26 D2B380859B808368...............................................................................................................................................................................................................................................................................................................................................................................................................................................
Breaching spin:...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
Candidate 0xF0BA68A1B616E6B1 for 58C80AA8C2F10A26 D2B380859B808368 60715FDB8EE68956
found Seed = 0x1234578ACDEF11

real 0m0.089s
user 0m0.069s
sys 0m0.020s

Maybe its a great PRNG, i dont know i did not look at that aspect, but its not secure if i can break it after a few hours work :)

Filed under: Cryptanalysis,Pseudo random number generators — Michael @ 21:58

2023-05-18

Hardware password managers, accelerometers and random data

I was looking for a way to securely manage my passwords, anything storing my passwords with a 3rd party or all accessible to my computer fail IMHO. Also it had to be practical, something limited to 5 passwords is not. Be convenient, something where one would have to search for a password in a list by hand fails that. And it needed to have a screen so one knew what one approved. A simple one button USB stick does not qualify either as one does ultimately not know what one actually approved. The only device i could find was the mooltipass. So i bought one. It is a cute little thing storing all passwords both securely and also conveniently. And being a nerdy geeky person, i of course had to play with and analyze it. The first thing that sprang out to me was its random number generator

Can we exploit it ?

So i looked at its random number generator until i found something. It uses the 2 LSB of each of the 3 axis of an LIS2HH12 accelerometer. This generator was tested with the DIEHARDER battery of tests by its creator before me. I was at first not able to run the DIEHARDER tests because they needed more random data than the device could generate quickly. I tried various tests, simple things like simply trying to compress the data showed no anomalies. The first anomaly i found, i believe was through looking at the frequency spectrum in audacity. To my eye it looked like there was a bias between high and low frequencies. The next step was checking the correlation of various bits. And indeed when one looked at 2 bits and the previous 2 bits from the same channel They where equal 3% more often than they should be. I guess i could have stoped here, but i didn’t :) So i looked at the distribution of matching bits, (3% of these shouldn’t be there and we dont know which of 100 are the 3 bad ones). These 3 could be randomly distributed of course. But by now i had enough data to run some of DIEHARDER and while most tests passed, some of its tests failed for me. I have to say though little things in the command line of DIEHARDER can lead to unexpected results.

The original findings on the 3% anomaly

I simply counted the number of times each 2bit matches the previous
2bits of the same channel and this occurs about 3% more often than it should.

With 1 mb of data:
Channel 0 [1.026829 : 1.980986 : 0.992185]
Channel 1 [1.031329 : 1.978283 : 0.990388]
Channel 2 [1.039171 : 1.974176 : 0.986653]
Average   [1.032443 : 1.977815 : 0.989742]
All 3     [0.968019 1.010415 1.052310 1.111489]

/dev/random
Channel 0 [1.000765 : 1.998530 : 1.000705]
Channel 1 [0.997429 : 2.001644 : 1.000927]
Channel 2 [0.997357 : 2.003375 : 0.999268]
Average   [0.998517 : 2.001183 : 1.000300]
All 3     [1.001617 0.999233 0.997958 0.995425

This allows relatively reliably distingishing the mooltipass random numbers from /dev/random with 10kb of data

Periodic anomalies

Looking again at the randomdata. The 3% extra repeats within a channel occur 32 samples apart (that is 24 bytes in the stream or 192 bits). These locations sometimes shift around but preferably occur at indexes 31,63 and 95 of the 96 sample block. When such a run of anomalies breaks from teh same index, the new index tends to be the next in the set {95,63,31}. With these patterns it is possible to reliably distinguish as little as 100-200 bytes from random data. That said, the randomness of this is still plenty for a password and the average human would be way worse generating random data. Care though may need to be applied if this is used for other purposes than passwords. For example DSA signatures are notorious for being sensitive to biases in the used random number generator. I reported the anomalies in the RNG in January of 2023. It was fixed on Apr 18th 2023 with 49359dfc52cdfe743000ac512092085328d5f15b. Software to detect the specific pattern reliably as well as 2 small test samples is availble at randomtests

The original findings on perodic anomalies

Heres how this compares to /dev/random
dd if=/dev/random of=/dev/stdout count=1 bs=1000 status=none | ./mooltitestwalker
mooltiness:     0.89 expected: < 1 in 68% cases, < 2 in 95%, < 3 in 99.7%

dd if=/dev/random of=/dev/stdout count=1 bs=10000 status=none | ./mooltitestwalker
mooltiness:     0.25 expected: < 1 in 68% cases, < 2 in 95%, < 3 in 99.7%

dd if=/dev/random of=/dev/stdout count=1 bs=100000 status=none | ./mooltitestwalker
mooltiness:     0.04 expected: < 1 in 68% cases, < 2 in 95%, < 3 in 99.7%

dd if=/dev/random of=/dev/stdout count=1 bs=1000000 status=none | ./mooltitestwalker
mooltiness:     2.99 expected: < 1 in 68% cases, < 2 in 95%, < 3 in 99.7%

dd if=/dev/random of=/dev/stdout count=1 bs=10000000 status=none | ./mooltitestwalker
mooltiness:     0.08 expected: < 1 in 68% cases, < 2 in 95%, < 3 in 99.7%

and now the random data from mooltipass

dd if=~/mooltirandom.bin-copy of=/dev/stdout count=1 bs=1000 status=none | ./mooltitestwalker
mooltiness:     3.16 expected: < 1 in 68% cases, < 2 in 95%, < 3 in 99.7%

dd if=~/mooltirandom.bin-copy of=/dev/stdout count=1 bs=10000 status=none | ./mooltitestwalker
mooltiness:     4.21 expected: < 1 in 68% cases, < 2 in 95%, < 3 in 99.7%

dd if=~/mooltirandom.bin-copy of=/dev/stdout count=1 bs=100000 status=none | ./mooltitestwalker
mooltiness:    12.91 expected: < 1 in 68% cases, < 2 in 95%, < 3 in 99.7%

dd if=~/mooltirandom.bin-copy of=/dev/stdout count=1 bs=1000000 status=none | ./mooltitestwalker
mooltiness:    37.46 expected: < 1 in 68% cases, < 2 in 95%, < 3 in 99.7

dd if=~/mooltirandom.bin-copy5 of=/dev/stdout count=1 bs=10000000 status=none | ./mooltitestwalker
mooltiness:   115.95 expected: < 1 in 68% cases, < 2 in 95%, < 3 in 99.7%

As you can see with just 1000 bytes we are already more than
3 standard deviations away from random data. And after that it very quickly
becomes something that a random number generator would not generate in the lifetime of
the universe not even if you fill the whole universe with random number generators should
you see this sort of statistics once

Heres the test results for 100,200,300,400,500 bytes with mooltitestcycler

for i in `seq 100 100 500` ; do dd if=~/mooltirandom.bin-copy of=/dev/stdout bs=$i count=1 status=none | ./mooltitestcycler ; done
moolticycles:     3.00, this or larger is expected 0.27 % of the time in random data.
moolticycles:     4.58, this or larger is expected 0.00046 % of the time in random data.
moolticycles:     6.00, this or larger is expected 2E-07 % of the time in random data.
moolticycles:     6.93, this or larger is expected 4.3E-10 % of the time in random data.
moolticycles:     7.75, this or larger is expected 9.5E-13 % of the time in random data.

Same but with another testsample to make sure this is not a one off

for i in `seq 100 100 500` ; do dd if=~/mooltirandom2.bin of=/dev/stdout bs=$i count=1 status=none | ./mooltitestcycler ; done
moolticycles:     3.00, this or larger is expected 0.27 % of the time in random data.
moolticycles:     4.58, this or larger is expected 0.00046 % of the time in random data.
moolticycles:     6.00, this or larger is expected 2E-07 % of the time in random data.
moolticycles:     6.93, this or larger is expected 4.3E-10 % of the time in random data.
moolticycles:     7.75, this or larger is expected 9.5E-13 % of the time in random data.

In fact i notice now the results are exactly the same, interresting
cmp  ~/mooltirandom2.bin ~/mooltirandom.bin-copy
/home/michael/mooltirandom2.bin /home/michael/mooltirandom.bin-copy differ: byte 1, line 1


heres the control test with /dev/random
for i in `seq 100 100 500` ; do dd if=/dev/random  of=/dev/stdout bs=$i count=1 status=none | ./mooltitestcycler ; done
moolticycles:     0.00, this or larger is expected 1E+02 % of the time in random data.
moolticycles:     0.31, this or larger is expected 76 % of the time in random data.
moolticycles:     0.58, this or larger is expected 56 % of the time in random data.
moolticycles:     0.44, this or larger is expected 66 % of the time in random data.
moolticycles:     0.77, this or larger is expected 44 % of the time in random data.

and a bigger sample to show the runs:

dd if=~/mooltirandom.bin-copy5 of=/dev/stdout bs=2000000 count=1 status=none | ./mooltitestcycler
Run 1731 at phase 31
Run 7496 at phase 95
Run 3323 at phase 63
Run  196 at phase 31
Run  195 at phase 95
Run 3540 at phase 63
Run 2459 at phase 31
Run  777 at phase 95
Run  775 at phase 63
Run  195 at phase 31
Run  583 at phase 95
Run  778 at phase 63
Run 1585 at phase 31
Run 1126 at phase 95
Run  971 at phase 63
Run 5047 at phase 31
Run 7141 at phase 95
Run 1741 at phase 63
Run 4643 at phase 31
Run  197 at phase 95
Run  577 at phase 63
Run  197 at phase 31
Run 2907 at phase 95
Run 4040 at phase 63
Run 1572 at phase 31
Run  196 at phase 95
Run 2903 at phase 63
Run 1355 at phase 31
Run  195 at phase 95
Run  196 at phase 63
Run  584 at phase 31
Run  143 at phase 95
Run   51 at phase 63
Run  195 at phase 31
Run 3099 at phase 95
Run  196 at phase 63
Run 1164 at phase 31
Run 2445 at phase 95
Run 2589 at phase 63
Run 4553 at phase 31
Run 7145 at phase 95
moolticycles:   499.67, this or larger is expected 0 % of the time in random data.

Shaken not Stirred

A 2nd issue i found and reported on 7th feb 2023 is that when the device is violently shaken, the accelerometer saturates and clips at 2g, this makes the 2 LSB of the affected channel(s) be 00 or 11 more often than expected in a random stream of data. So please dont use the mooltipass while doing high G maneuvers in a fighter jet or any other activity that subjects it to high g forces. Also with some effort one can shake a 3 axis accelerometer so that all 3 axis clip at the same time. There also may be a delay between the generation and use of random data. Ideally when the full 16bit sample clips it should be discarded and not used. While discarding one kind of sample that was equally frequent, introduces a bias, the clipping cases are not equally frequent. They either do not occur at all in a still environment or occur disproportionally frequent.

Random now?

Except these, i found no further flaws in the random data. Personally i would recommend to use some sort of hash or other cryptography to mix up the accelerometer bits. Heating or cooling (in my freezer with long USB cable) the device did not introduce measurable bias and also feeding ~60 mega byte stream of data into the PRNG NIST-Statistical-Test-Suite did not show any anomalies after the fix. Of course one can only find flaws in such data streams, never proof the absence of flaws. Also it must be said that i could not find any reference by the manufacturer of the chip to randomness of the LSBs. So while AFAIK many devices use accelerometer data as source of random data, there seems no guarantee that a future revision of that chip doesn't produce less random bits. What i can say, is thus just about the device i looked at and for that, the random data is much better than what a person would generate by "randomly" pressing keys. People are very biased in what characters they use in passwords even when they try to be random. Also passwords are generally too short for this anomaly to allow distinguishing 1 password from another with a unbiased RNG. A password that one believed contained n*192 bits of entropy really only contained n*190 before the fix. All this assumes the device is not violently shaken while used.

Audacity spectra

Took me a bit to find and restore the original spectrum i saw. While doing that i also noticed that using signed 8bit results in a spectrum biased the other way. The original ones are unsigned 8bit.

mooltipass pre fix spectrum /dev/random control spectrum mooltipass post fix spectrum

Audacity spectra with more data and in signed 8bit ints

recreated mooltipass pre fix spectrum /dev/random spectrum mooltipass post fix spectrum

Dieharder testsuite

Ill write a separate article about dieharder later, the thing is finicky and this is already quite complex

Updated this article multiple times (last on 2023-05-24) to include more details, pictures and minor corrections
Full disclosure, i was offered a reward for finding and reporting the bug.

Filed under: Cryptanalysis,Hardware,Off Topic,Security — Michael @ 22:52

2023-02-15

EU Schuko plug

Today i learned a new feature of the EU Schuko plug.
I moved some stuff to a different apartment, plugged it in and slowly build the feeling something wasn’t quite right. Some electronics behaved a bit odd, somehow grounded things didn’t feel quite grounded.
So i connected a DMM between the grounds of 2 plugs

and

and between we have

ehm, 126 Volts
On closer inspection we can see the ground lead on the wall outlet has been painted over. Sure thats a rare exception, lets look at the other lead

sure its not the 2nd plug too that our green wire eventually was connected to

sure its not all plugs on that wall

whatever, cleaning that off and retesting


Problem solved, lets pretend we didnt notice this EU population control feature ;)
Having the ground leads exposed so that morons can paint over them and then anything pluged in simply has no ground connection. Bad design, simply bad design.

Filed under: Uncategorized — Michael @ 00:00

2023-01-10

Too many gpg keys ?

The key iam using everyday is really becoming old. OTOH the new key iam using for signing my git commits isnt really good as a general key as it needs to be available on the machiene i work on to sign rebased commits and all that. So its more “my git development box” key than mine.
And i have that cute little ledger that has a gpg plugin. So i thought, thats something i should look into. Yeah, or maybe i shouldnt have done that.
It supports ed25519 and cv25519. So i created one and signing worked, decryption failed with a gpg: public key decryption failed: Card error. So i tried again with default options which generates the encryption key apparently on the host backs it up and uploads. That worked fine, it asked for a password to encrypt the backup, signing worked decryption worked, all was fine, or was it? I had set the ledger to require a button before decryption and it didnt. Hmm, i started to have a odd feeling. I disconnected the ledger and tried again, yes it still decrypted it. Was it caching the key or passphrase ? i killed gpg-agent, it still decrypted it. It took me a moment before i fully believed it but yes there was a unencrypted private key where a stub should have been pointing to the ledger.
More testing showed that the ledger works fine with RSA and NISTP256 keys for decryption and RSA and ED25519 for signing. Though it is not able to generate NISTP256 keys, or at least not when i tried, these need to be copied onto. RSA upto 4096 can be generated on the thing if one has patience. CV25519 seems not to work no matter what i tried even though it seems to be supposed to be supported.
Now, i have setup mine (and the public keys are below if you want to send me something secret) but the whole experience leaves me with afterthoughts about wanting to use this. The way this failed and the thing that the source code sometimes speaks of “ed2559” and sometimes of “ed255519” leaves me with some desire for a different device for storing my key on in the long run. Not that any of this is pointing to any real security issues once one got a working key on it and made sure no plain copies remain.

-----BEGIN PGP PUBLIC KEY BLOCK-----

mDMEY73h4hYJKwYBBAHaRw8BAQdAsSAAq3LxY0Fcw29nsG39GDF4CMgAoDV8Qb27
aHh2obq0MU1pY2hhZWwgTmllZGVybWF5ZXIgPG1pY2hhZWwta2V5MkBuaWVkZXJt
YXllci5jYz6IlgQTFggAPhYhBFwRfsTnHWQ2HRuoQq1G6+FU56XXBQJjveHiAhsD
BQkDwmcABQsJCAcCBhUKCQgLAgQWAgMBAh4BAheAAAoJEK1G6+FU56XXPyoBAJTK
YelgVZBdkSK0zo4IYqyXR+dUJMjT8SlXvAxsbHVwAP97VsXCcXWxH6oPR/LKGJgA
PDO+X5iy6pDFO6eQNmzgA4hdBBMRCAAdFiEEn/ISixR+9nMLrfEzYR7HhwQLD6sF
AmO96VUACgkQYR7HhwQLD6uDZQCfTc2K/GL0A6wi5BIGuQMM5iYMX2sAnAvxsZfA
bUjviZzbdsuCplgQduG7uFYEY73h4hIIKoZIzj0DAQcCAwS96wJJL1mSdwT94Atc
c2Q0r1O4vIkEIqnGDLGXGu3egxWzStCjojpCg+ELEDjU2rxtu51GzYLQUTazEzWU
Ql+IAwEIB4h4BBgWCAAgFiEEXBF+xOcdZDYdG6hCrUbr4VTnpdcFAmO94eICGwwA
CgkQrUbr4VTnpdflbQD+KCouQqLQ6Gl9bNrPZfXf8055b6qVtfzsQzQF+LOeo4EB
AK+6cxLVHB2jcYyvlIv73R8JWvNHcxE/3mDEYKiP3D0J
=IkKl
-----END PGP PUBLIC KEY BLOCK-----
Filed under: Crypto — Michael @ 23:43
Next Page »

Powered by WordPress