Lair Of The Multimedia Guru


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

No Comments »

No comments yet.

RSS feed for comments on this post.

Leave a comment

Powered by WordPress