Dynamic Hill cipher
in [Cryptography]
|
From: Mok-Kong Shen on 29 Apr 2010 14:18 Maaartin wrote: > Mok-Kong Shen<mok-kong.s...(a)t-online.de> wrote: >> the second PRNG will generate a plaintext vector consisting of 2 elements > >> I personally hitherto "hate" that money be involved >> in scientific discussions on principle grounds. > > I agree, but time is money. DJB does it, and it shows his trust in his > design and motivates the people to analyze it: http://cubehash.cr.yp.to/prizes.html > > There seem to be a misunderstanding here. If trying to break a cipher, > you always need quite a lot of plaintext and/or ciphertext. For any > contemporary cipher worth its name, one assumes unlimited amount of > plaintext-ciphertext pairs, which may or may not be chosen by the > attacker (CPA = chosen plaintext attack, CCA = chosen ciphertext > attack, CPA2 = adaptively chosen plaintext attack, etc.). > > You can't assume anybody to be able to crack anything when the output > is shorter than the inner state. You can't assume anybody to use a > cipher which is secure only in such a scenario, since she could OTP > instead. > > I'll answer to your offer after we have resolved all unclean points. > Can you write python programs? Can you read them? Can you run them? We > need to define it all precisely and a program is the most unambiguous > way. Instead of python we could use a different language, but since > about two days ago I consider python to be ideal for this. I have no knowlege of Python. Everything concerning programming has to be done in standard C. The essence is: I'll give you the coefficients and the seeds of the PRNGs and a code to generate the Hill matrices and the plaintext vectors. You may generate as many plaintext vectors as you like for the analysis, but one Hill matrix is to be used for one plaintext vector only. You have to show me a C code that from the plaintext and ciphertext vectors you are able to determine the PRNG that generates the Hill matrix at a definite number of steps of processing. The attack is thus known-plaintext attack. M. K. Shen
From: Scott Fluhrer on 29 Apr 2010 15:23 "Mok-Kong Shen" <mok-kong.shen(a)t-online.de> wrote in message news:hrcgem$vee$03$1(a)news.t-online.com... > Scott Fluhrer wrote: >> "Mok-Kong Shen"<mok-kong.shen(a)t-online.de> wrote: >>> Scott Fluhrer wrote: >>> [snip] >>>> In other words, you're claiming that it is secure unless someone else >>>> demonstrates that it is not? Sorry, but that's not how the game is >>>> played. >>> >>> Note what I wrote in my original post: >>> >>> I should be grateful to learn concrete hints of techniques of attack, >>> if any. >>> >>> So, if nobody either (1) can or (2) will give hints, then why all the >>> winds that had since been generated?? >> >> Actually, Bryan did give hints; you've been ignoring them. > > Could you elaborate that through quotes? Anyway, I don't see anything > that is concrete engough for guiding any practical work at all. (Of > course, non-concrete stuffs are trivial to provide. For crypto in > genereal, one could always say "do some statistical analysis" etc. etc. > etc.) Bryan wrote: Hmmm... bit of a mess, but I'll try to rise to the challenge. Start small, even trivially small if you need. Purely linear ciphers are obviously a joke, but at least break that . For example, start with a LFSR for the PRNG, with following Hill-cipher matrix operations in GF2**n. That will generate to linear system, which one can certainly break. Or try a lagged Fibonacci generator with matrix operations over the corresponding arithmetic field. Next, vary enough that the solution is not purely linear. That's certainly a hint, unless by "hint", you mean "giving you an exhaustive description". -- poncho
From: Mok-Kong Shen on 29 Apr 2010 15:30 Scott Fluhrer wrote: > "Mok-Kong Shen"<mok-kong.shen(a)t-online.de> wrote in message > news:hrcgem$vee$03$1(a)news.t-online.com... >> Scott Fluhrer wrote: >>> "Mok-Kong Shen"<mok-kong.shen(a)t-online.de> wrote: >>>> Scott Fluhrer wrote: >>>> [snip] >>>>> In other words, you're claiming that it is secure unless someone else >>>>> demonstrates that it is not? Sorry, but that's not how the game is >>>>> played. >>>> >>>> Note what I wrote in my original post: >>>> >>>> I should be grateful to learn concrete hints of techniques of attack, >>>> if any. >>>> >>>> So, if nobody either (1) can or (2) will give hints, then why all the >>>> winds that had since been generated?? >>> >>> Actually, Bryan did give hints; you've been ignoring them. >> >> Could you elaborate that through quotes? Anyway, I don't see anything >> that is concrete engough for guiding any practical work at all. (Of >> course, non-concrete stuffs are trivial to provide. For crypto in >> genereal, one could always say "do some statistical analysis" etc. etc. >> etc.) > > Bryan wrote: > > Hmmm... bit of a mess, but I'll try to rise to the challenge. Start > small, even trivially small if you need. Purely linear ciphers are > obviously a joke, but at least break that . For example, start with a > LFSR for the PRNG, with following Hill-cipher matrix operations in > GF2**n. That will generate to linear system, which one can certainly > break. Or try a lagged Fibonacci generator with matrix operations over > the corresponding arithmetic field. Next, vary enough that the > solution is not purely linear. > > > That's certainly a hint, unless by "hint", you mean "giving you an > exhaustive description". But how to build that linear system? My main trouble is explained in a recent post demonstrating the inability to setup any system to somehow gain access to the elements of the Hill matrix. For, if any attack, then that must go through the Hill matrix, right? M. K. Shen
From: Bryan on 29 Apr 2010 17:50 Maaartin wrote: > DJB does it, and it shows his trust in his > design and motivates the people to analyze it:http://cubehash.cr.yp.to/prizes.html Another fine example is this sci.crypt thread from 1997: http://groups.google.com/group/sci.crypt/browse_frm/thread/ef605e718529068a/f623de5102e3144e -- --Bryan
From: Bryan on 29 Apr 2010 19:51
Maaartin wrote: > No, you missed it. The PRNG has a final initial state, Obviously Maaartin meant, "The PRNG has a *finite* initial state". > the matrix > multiplication is a linear operation. You can get any number of linear > equations for fixed number of variables. Broken. Near as I can tell, that's key to what Shen is missing. The initial unknowns are the variables in the PRNG state. The Hill-matrix entries are determined by the PRNG state. If we consider each new matrix entry to be a new variable, another unknown, each also gives us another equation: the equation expressing the entry as a function of the PRNG state. Then as we see the encryption of known plaintext, we get yet more equations, without additional unknowns. The system of simultaneous equations becomes solvable. -- --Bryan |