Dynamic Hill cipher
in [Cryptography]
|
From: Mok-Kong Shen on 23 Apr 2010 12:53 The classical Hill cipher is well known to be susceptible to known plaintext attack, since with plaintext materials of an amount equal to that of the Hill matrix, that matrix could 'normally' be determined and thus the cipher broken. However, I don't see how one could attack an approriately modified dynamic version of the Hill cipher at all. To be concrete, let's assume the availability of a (not too poor) PRNG that is unique for the message and that the dimension n of the matrices used is even and that we work with 32-bit words (e.g. n=4 so that we work with 128 bits at a time). Let the PRNG generate n^2 words to build two matrices L and R, one lower and the upper triangular. L has all 1's on its diagonal, while the diagonal elements of R are adjusted such that they are odd. The encryption equation is then L*R*P = C, where P and C denote the plaintext and the ciphertext vectors of dimension n. We shall let each pair of L and R to encrypt up to n/2 vectors (and not more, i.e. new pairs of L and R will be generated as required). This evidently ensures that it is not feasible to set up systems of linear equations to determine L and R from the cipertext and the plaintext vectors that are assumed to be available to the analyst. I should be grateful to learn concrete hints of techniques of attack, if any. Thanks, M. K. Shen
From: Bryan on 26 Apr 2010 12:21 Mok-Kong wrote: > The classical Hill cipher is well known to be susceptible to known > plaintext attack, since with plaintext materials of an amount equal > to that of the Hill matrix, that matrix could 'normally' be determined > and thus the cipher broken. Lester Hill did not, and as he has passed away he will not, go down in history as a great cryptographer. We should not judge people of the past by the standards of the present. Falling to known-plaintext and purely linear computation is a joke in recent times, but in 1929, when Hill did it, the rules and techniques were less clear. Why base a modern cipher on an old and broken idea such as Hill's?. Even if the defects can be patched, the advantages are gone. What's the motivation today? > However, I don't see how one could attack > an approriately modified dynamic version of the Hill cipher at all. Mr. Shen, the fact that you do not see an attack on some method would be more impressive if you could cite your successful attacks. You are this group's most prolific writer (with the sole exception of spam- bots). We've seen many, many, weak ciphers posted here on sci.crypt. How many have you broken? If "broken" is too strong, in how many have you shown weakness? Distinguished from random? Demonstrated any cryptanalytic result at all? Mr. Shen, you write, "I don't see how one could attack [...]", but in your many years here, and in your many many posts, what did you *ever* successfully attack? > To be concrete, let's assume the availability of a (not too poor) PRNG > that is unique for the message Is this some obscure usage of the word "concrete"? I understand the term can mean solid and specific, and there's nothing solid or specific your post, Mr. Shen. A good cryptographic PRNG "that is unique for the message" immediately provides a secure steam cipher. One can simply XOR the PRNG withe the plaintext to produce the ciphertext. If the PRNG stream is indistinguishable from random, then the cipher is secure. Thus a PRNG that fails is "too poor" by definition. > and that the dimension n of the matrices > used is even and that we work with 32-bit words (e.g. n=4 so that we > work with 128 bits at a time). Let the PRNG generate n^2 words to build > two matrices L and R, one lower and the upper triangular. L has all 1's > on its diagonal, while the diagonal elements of R are adjusted such > that they are odd. The encryption equation is then L*R*P = C, where P > and C denote the plaintext and the ciphertext vectors of dimension n. > We shall let each pair of L and R to encrypt up to n/2 vectors (and not > more, i.e. new pairs of L and R will be generated as required). This > evidently ensures that it is not feasible to set up systems of linear > equations to determine L and R from the cipertext and the plaintext > vectors that are assumed to be available to the analyst. > > I should be grateful to learn concrete hints of techniques of attack, > if any. 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. Scale down to what you can easily break, then see how far you push with serious effort. This kind of vaguely-stated problem presents multiple, reasonable, way to proceed. You could try variants in which multiple messages are encrypted with key-streams that are mathematically related in simple ways. Again, as a super-simple first step, you could assume the variants have a linear relationship; then vary incrementally and see how far you can push. The key, Mr. Shen, is to get concrete results. Solve something. If purely linear is far as you can get, that's obviously not going to advance the state of art, but this group will likely provide good guidance on how to push farther. -- --Bryan Olson
From: Mok-Kong Shen on 26 Apr 2010 13:20 Bryan wrote: > Mok-Kong wrote: [snip] > 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. Scale down to what you can easily > break, then see how far you push with serious effort. > > This kind of vaguely-stated problem presents multiple, reasonable, way > to proceed. You could try variants in which multiple messages are > encrypted with key-streams that are mathematically related in simple > ways. Again, as a super-simple first step, you could assume the > variants have a linear relationship; then vary incrementally and see > how far you can push. > > The key, Mr. Shen, is to get concrete results. Solve something. If > purely linear is far as you can get, that's obviously not going to > advance the state of art, but this group will likely provide good > guidance on how to push farther. Referring to your first sentence above, take just the case of 2*2 matrices, each encrypting a vector of dimension 2. The PRNG generates thus 4 words for every 2 plaintext words. Given a pair of corresponding plaintext and ciphertext vectors, i.e. 2 plaintext and 2 ciphertext words, how could one determine the output of the PRNG? There simply aren't enough equations that could be set up to do that. This is the gist of my original post. Is this still vague for you, or should I write out the Hill matrix formally or even provide a numerical example? M. K. Shen
From: Maaartin on 26 Apr 2010 17:01 On Apr 26, 7:20 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Bryan wrote: > > Mok-Kong wrote: > [snip] > > 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. Scale down to what you can easily > > break, then see how far you push with serious effort. > > > This kind of vaguely-stated problem presents multiple, reasonable, way > > to proceed. You could try variants in which multiple messages are > > encrypted with key-streams that are mathematically related in simple > > ways. Again, as a super-simple first step, you could assume the > > variants have a linear relationship; then vary incrementally and see > > how far you can push. > > > The key, Mr. Shen, is to get concrete results. Solve something. If > > purely linear is far as you can get, that's obviously not going to > > advance the state of art, but this group will likely provide good > > guidance on how to push farther. > > Referring to your first sentence above, take just the case of 2*2 > matrices, each encrypting a vector of dimension 2. The PRNG generates > thus 4 words for every 2 plaintext words. Given a pair of corresponding > plaintext and ciphertext vectors, i.e. 2 plaintext and 2 ciphertext > words, how could one determine the output of the PRNG? There simply > aren't enough equations that could be set up to do that. Let me give two extreme examples: 1. Providing the PRNG is perfect, you're wasting words, since simple XOR would do. 2. Providing the PRNG has a period of 4, than you get with every 2 input words 2 equations. So after 4 words you can solve it (unless you have bad luck and get linear dependent equations). I agree, that both examples are extreme. So take the formula x[n+2] = a*x[n+1] + b*x[n+0] with the unknowns x[0], x[1], a, and b and solve it. > This is the > gist of my original post. Is this still vague for you, or should I > write out the Hill matrix formally or even provide a numerical example? I'd suggest, you select a PRNG and go *solve* it.
From: Mok-Kong Shen on 26 Apr 2010 17:53
Maaartin wrote: > Let me give two extreme examples: > 1. Providing the PRNG is perfect, you're wasting words, since simple > XOR would do. I only assume a "not too poor" PRNG, see my original post. > 2. Providing the PRNG has a period of 4, than you get with every 2 > input words 2 equations. So after 4 words you can solve it (unless you > have bad luck and get linear dependent equations). > > I agree, that both examples are extreme. So take the formula x[n+2] = > a*x[n+1] + b*x[n+0] with the unknowns x[0], x[1], a, and b and solve > it. I personally would in normal cases favour using a second or higher degree full-period congruential PRNG mod 2^32 or 2^64, depending on software used. >> This is the >> gist of my original post. Is this still vague for you, or should I >> write out the Hill matrix formally or even provide a numerical example? > > I'd suggest, you select a PRNG and go *solve* it. It was my point that one "couldn't" solve for the outputs of the PRNG at all :-) But perhaps some ingeneous expert could nonetheless indeed surprise me with a solution. M. K. Shen |