Dynamic Hill cipher
in [Cryptography]
|
From: Maaartin on 29 Apr 2010 20:13 On Apr 30, 1:51 am, Bryan <bryanjugglercryptograp...(a)yahoo.com> wrote: > Maaartin wrote: > > No, you missed it. The PRNG has a final initial state, > Obviously Maaartin meant, "The PRNG has a *finite* initial state". Sure. Never read what I write, read what I think. :D > > 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. I suppose he wants to keep the coefficients of the PRNG secret as well, which leads to non-linear equations for them (or am I talking non-sense and should go to bet now?). This can get complicated for me, but there are methods for computing the coefficients from the sequence which may get adapted for the case you know only a linear combination of them.
From: Mok-Kong Shen on 30 Apr 2010 04:39 Maaartin wrote: > Bryan wrote: >> Maaartin wrote: >>> No, you missed it. The PRNG has a final initial state, >> Obviously Maaartin meant, "The PRNG has a *finite* initial state". > > Sure. Never read what I write, read what I think. :D > >>> 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. > > I suppose he wants to keep the coefficients of the PRNG secret as > well, which leads to non-linear equations for them (or am I talking > non-sense and should go to bet now?). This can get complicated for me, > but there are methods for computing the coefficients from the sequence > which may get adapted for the case you know only a linear combination > of them. Of course, the coefficients and the seed of the PRNG that generates the Hill matrices "is" the "key" of the scheme and has to be kept secret as in all symmetric encryption schemes. Otherwise, why does one bother to do the computations at all instead of sending the plaintext rightaway? Certainly, this key is fixed and known before the start of the challenge work, which consists in finding it from the plaintext vectors (generated by another fixed and known PRNG) and the ciphertext vectors alone. If you need literature references on analysis of higher-order congruential PRNGs to better decide whether you'll like to accept my offer, please say so, for I once had spent some effort looking around in that direction. Regards, M. K. Shen
From: Tom St Denis on 30 Apr 2010 07:53 On Apr 29, 8:13 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > To save the time of the general readers, I like to explain why I > consider that the modified scheme is secure. Consider a chosen plaintext attack. Tom
From: Mok-Kong Shen on 1 May 2010 12:05 Mok-Kong Shen wrote: > Maaartin wrote: >> Bryan wrote: [snip] >> I suppose he wants to keep the coefficients of the PRNG secret as >> well, which leads to non-linear equations for them (or am I talking >> non-sense and should go to bet now?). This can get complicated for me, >> but there are methods for computing the coefficients from the sequence >> which may get adapted for the case you know only a linear combination >> of them. > > Of course, the coefficients and the seed of the PRNG that generates > the Hill matrices "is" the "key" of the scheme and has to be kept > secret as in all symmetric encryption schemes. Otherwise, why does > one bother to do the computations at all instead of sending the > plaintext rightaway? Certainly, this key is fixed and known before the > start of the challenge work, which consists in finding it from the > plaintext vectors (generated by another fixed and known PRNG) and the > ciphertext vectors alone. > > If you need literature references on analysis of higher-order > congruential PRNGs to better decide whether you'll like to accept my > offer, please say so, for I once had spent some effort looking > around in that direction. I think I could afford to significantly lower the threshold of difficulty of the task of the challenge work by not requiring the determination of the PRNG that generates the Hill Matrices but instead only the sequences of the last bytes of the words output by that PRNG. Being layman, I myself have no clue at all of how that could ever be attempted. Concrete hints given by experts on this will not affect my challenge offer and are in fact welcome. (Note that, as I indicated previously in another thread, the prediction of congruential generators with the LSBs could be easily foiled by performing pseudo-random rotations of the bits output from the PRNG, using e.g. some of its own output. This is however absent in the context of the current challenge.) M. K. Shen
From: Bryan on 1 May 2010 14:57
Mok-Kong Shen wrote: > To save the time of the general readers, I like to explain why I > consider that the modified scheme is secure. > > Let's first see why the original Hill cipher can be broken [...] > Now, in case the plaintext is such that the matrix (pij) is > non-singlar, one can compute its inverse. Multiplying this inverse > onto both sides of the above equation, one recovers the Hill Matrix > (aij). With the values of its elements (assumed to be from a PRNG), > one can start to predict the parameters of the PRNG. > > But in the modified scheme I proposed, a n*n Hill matrix is "only" > used to encrpyt n/2 plaintext vectors. (If more plaintext is to > be processed, more Hill matrices have to be generated.) More Hill matrices are generated *from the PRNG*. The entries in the matrices can be be expressed in terms of the PRNG state. > Thus we > would in the case of 2*2 Hill matrix have only one plaintext vector > (p11, p12). There is no matrix (pij), there being only one vector. > So there can be no inverse of the (pij) matrix from the very > beginning and consequently it is not feasible at all to recover the > matrix (aij) as in the case of the original Hill scheme, excepting > perhaps through pure guess work. The simple method to break the old Hill cipher does not work on this new variant. That fact does *not* imply that this one is immune from all attacks save guess work. Mr. Shen, in addition to the hints I gave you, Scott Fluhrer gave you a big one and labeled it, for your convenience, "hint:". Here it is again: Scott Fluhrer had written: | (hint: the goal of the cryptanalyst wouldn't be to reconstruct the internal | PRNG state, but instead the operation of the cipher as a whole). Note that Scott is not saying the cryptanalyst doesn't care about the PRNG state. -- --Bryan |