Timeline for How Brittle Are LCG-Cracking Techniques?
Current License: CC BY-SA 3.0
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://crypto.stackexchange.com/ with https://crypto.stackexchange.com/
|
|
| Dec 2, 2015 at 8:52 | answer | added | Andrew Bortz | timeline score: 7 | |
| Dec 11, 2014 at 1:28 | answer | added | Thomas M. DuBuisson | timeline score: 4 | |
| Dec 9, 2014 at 9:53 | answer | added | Charphacy | timeline score: 15 | |
| Dec 8, 2014 at 17:59 | answer | added | fgrieu♦ | timeline score: 8 | |
| Dec 7, 2014 at 19:48 | comment | added | fgrieu♦ |
@Thomas M. DuBuisson: interesting; if time allows I'll try translation to SAT by more primitive means, and state-of-the-art solvers. $\;$ Side note: the @ sign before a name in a comment creates a notification; the name itself does not.
|
|
| Dec 7, 2014 at 18:10 | comment | added | Thomas M. DuBuisson | fgrieu: I suspected the same thing and have learned 1) SMT solvers are pretty slow at this sort of thing (already known by others in the field, so I've found out) 2) There is a bug in either Cryptol or SMTs I used that caused Cryptol to exit with an exception when the solution was discovered instead of printing the seed etc. | |
| Dec 7, 2014 at 17:30 | comment | added | fgrieu♦ | @Thomas M. DuBuisson: My intuition is that even Case 3 could be solved using Cryptol and a SAT/SMT solver, as you did in this nice answer to a much more trivial problem. $\;$ If it indeed works, that would be a very convincing demo! | |
| Dec 7, 2014 at 3:55 | history | edited | Charphacy | CC BY-SA 3.0 |
Minor edit to remove some (now redundant) material about the “too broad” issue.
|
| Dec 5, 2014 at 17:09 | comment | added | Thomas M. DuBuisson | Have you tried to apply any of the lattice reduction code available online to this problem? NTL has some, for one pointer. | |
| Dec 4, 2014 at 13:09 | history | edited | mikeazo | CC BY-SA 3.0 |
It wasn't moderators, but users who voted it as too broad.
|
| Dec 4, 2014 at 13:07 | history | reopened | mikeazo | ||
| Dec 3, 2014 at 8:12 | history | edited | Charphacy | CC BY-SA 3.0 |
Add missed word.
|
| Dec 3, 2014 at 8:04 | history | edited | Charphacy | CC BY-SA 3.0 |
Put question more clearly at start so it shows up better in the questions list.
|
| Dec 3, 2014 at 5:06 | review | Reopen votes | |||
| Dec 4, 2014 at 13:10 | |||||
| Dec 3, 2014 at 4:51 | history | edited | Charphacy | CC BY-SA 3.0 |
Fix minor issues from last edit.
|
| Dec 3, 2014 at 4:39 | comment | added | Charphacy | user3201068, I think you're mistaken about “bias”. If anything, the lattice structure of LCGs makes them “too uniform”. In any case, your comment has nothing to do with the question I'm asking. | |
| Dec 3, 2014 at 4:04 | comment | added | user3201068 | Multiply-with-carry is a better RNG by Marsaglia with less biases than LCG. LCGs has some biases, unlike LSFR which are much more uniform. | |
| Dec 2, 2014 at 23:46 | history | closed |
D.W. e-sushi DrLecter poncho archie |
Needs more focus | |
| Dec 2, 2014 at 6:15 | comment | added | Charphacy |
Antimony, you mention brute-forcing. Brute forcing 64-bit constants, or even 62-bit constants, isn't practical. Also, FWIW, I already linked to papers about the lattice techniques and explicitly stated where they clearly apply; they do indeed apply to unknown SEED, INC, and MULT. Mathematica has LatticeReduce and I'm sure the same thing is available in free systems, but, as you say, it's challenging to turn the theoretical sketch given in the papers into actual running code.
|
|
| Dec 2, 2014 at 6:05 | comment | added | Antimony | Incidentally, unknown SEED and INC should be easily solveable using lattice techniques. Unfortunately, I can never get lattice solvers to work in practice even though the proofs look good on paper. It's so frustrating. | |
| Dec 2, 2014 at 6:04 | comment | added | Antimony | INC has to be odd and MULT has to be 1 mod 4. So that's already removed 3 bits of entropy. On a general note, your later examples effectively just use a much larger key. So a break on any of the stages trivially extends to a theoretical break on the later stages by brute forcing the remaining unknowns. | |
| Dec 2, 2014 at 5:30 | comment | added | Charphacy |
Antimony, I'm afraid you're mistaken. INC can be any odd constant (or zero). See L'Ecuyer 1999.
|
|
| Dec 2, 2014 at 4:38 | comment | added | Antimony | The problem is that you can't just pick INC to be anything because certain values will give you a reduced period. So in practice INC can be assumed a fixed constant. | |
| Nov 30, 2014 at 7:22 | review | Close votes | |||
| Dec 2, 2014 at 23:46 | |||||
| Nov 27, 2014 at 18:29 | comment | added | Charphacy | In the current (3rd, 1998) edition of tAoCP, Question 7 at the end of Section 3.6 (volume 2, page 193) is the only place in the book where he talks about RNG-based encryption. The answer to that question (page 599) references his 1985 paper without any reservation and also cites many of the other papers Boyar, Frieze, etc. | |
| Nov 27, 2014 at 17:03 | comment | added | Charphacy | I'm not sure how your quote is relevant. Lagged fibonacci generators are not linear congruential generators. And in any case, we're talking here about predictability rather than statistical quality. (It's possible to have RNGs that pass reasonable statistical tests yet are predictable.) | |
| Nov 27, 2014 at 6:59 | history | tweeted | twitter.com/#!/StackCrypto/status/537863229729697792 | ||
| Nov 27, 2014 at 1:57 | review | First posts | |||
| Nov 27, 2014 at 10:42 | |||||
| Nov 27, 2014 at 1:57 | history | asked | Charphacy | CC BY-SA 3.0 |