Dynamic Hill cipher
in [Cryptography]
|
From: Bryan on 27 Apr 2010 00:53 Mok-Kong Shen wrote: > 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. How many times do we have to explain the same thing? A sufficiently strong PRNG immediately solves the problem; any PRNG that does not is "too poor" by definition. You are "wasting words", as Maaartin put it. > > 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. What people who have never broken ciphers happen to favor is not of great interest, but at least this gives you something specific to start working on: You could use a linear congruential mod 2**n PRNG, and for a first cut do the Hill cipher matrix operations mod 2**n. How much known plaintext do you need to break that? Then try matrix operations mod 2**m, m != n. Next, try matrix ops mod v, where v is not a power of 2. How far can you get? > >> 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? That sounds like a good idea. Show an example, and break it. Then add a "too poor" PRNG, and break that. Improve the PRNG, bit by bit, and see how far you can push your attacks. > > 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. Mr. Shen, you might recall that in the history of sci.crypt, people have shown you solutions that you did not believe to exist, over and over and over (though I never heard any of them call themselves "expert"). Here, you asked for guidance, hints on how to attack. You got some. I'm not sure why you think the Hill cipher is all that interesting today, but you brought it up, so let's see you follow through. -- --Bryan
From: Bryan on 28 Apr 2010 17:09 Mok-Kong Shen wrote: > Bryan wrote: > > Mok-Kong Shen wrote: > >> 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. > > > How many times do we have to explain the same thing? A sufficiently > > strong PRNG immediately solves the problem; any PRNG that does not is > > "too poor" by definition. You are "wasting words", as Maaartin put it. > > I don't assume a cryptologically sufficiently strong PRNG, but only > a statistically sufficiently good PRNG. Is that o.k. for you? How many times do we have to go over the same thing? Many Linear PRNG's have good statistical properties. Mr. Shen, you state that you assume mere statistical qualities for the PRNG to be "good enough". At this point, after all your years on sci.crypt, after all the linear schemes you've proposed and seen trashed, you still don't know that "non-linear" is a requirement? Mr. Shen, you asked for concrete hints on how to attack. I already (twice) suggested that you start by attacking a version of your scheme that uses a PRNG that is linear over the same field as the matrix operations of the Hill cipher. What is stopping you, other than your own unwillingness to put forth a serious effort? Next you might look into linear approximations, but that's a bit too speculative until we see your solution in the purely linear case. [...snip long ramble...] > I am sorry to have written too much in this post, It's not a "this post" problem. Mr. Shen, you've been sci.crypt's most prolific writer over the course of decades. Nevertheless, this thread is where we are now, and in your opening post you said you'd be grateful for "concrete hints of techniques of attack". You got some. You've been the opposite of grateful, but that's not important here. This is a 'sci' group. Given the hints, what results can you show? How far can you push? One thing *not* to do is fix what you have not broken. No need, at this point, to reformulate your Dynamic Hill Cipher. As Maaartin said, "select a PRNG and go *solve* it". -- --Bryan
From: Mok-Kong Shen on 29 Apr 2010 07:33 Am 28.04.2010 23:09, schrieb Bryan: > Mok-Kong Shen wrote: >> Bryan wrote: >>> Mok-Kong Shen wrote: >>>> 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. >> >>> How many times do we have to explain the same thing? A sufficiently >>> strong PRNG immediately solves the problem; any PRNG that does not is >>> "too poor" by definition. You are "wasting words", as Maaartin put it. >> >> I don't assume a cryptologically sufficiently strong PRNG, but only >> a statistically sufficiently good PRNG. Is that o.k. for you? > > How many times do we have to go over the same thing? Many Linear > PRNG's have good statistical properties. Mr. Shen, you state that you > assume mere statistical qualities for the PRNG to be "good enough". At > this point, after all your years on sci.crypt, after all the linear > schemes you've proposed and seen trashed, you still don't know that > "non-linear" is a requirement? > > Mr. Shen, you asked for concrete hints on how to attack. I already > (twice) suggested that you start by attacking a version of your scheme > that uses a PRNG that is linear over the same field as the matrix > operations of the Hill cipher. What is stopping you, other than your > own unwillingness to put forth a serious effort? Next you might look > into linear approximations, but that's a bit too speculative until we > see your solution in the purely linear case. You have "entirely" missed (or purposedly ignored) what is the main point of the modified Hill system. Because the anylyst couldn't even come to "any" output values of the PRNG (there are no sufficient number of equations that could be set up), then it is "absolutely" irrelvant, whether the PRNG is linear, non-linear. The only thing is it couldn't be too poor (like generating 1, 2, 3 ....). Do you see that? > [...snip long ramble...] > >> I am sorry to have written too much in this post, > > It's not a "this post" problem. Mr. Shen, you've been sci.crypt's most > prolific writer over the course of decades. Nevertheless, this thread > is where we are now, and in your opening post you said you'd be > grateful for "concrete hints of techniques of attack". You got some. > You've been the opposite of grateful, but that's not important here. > This is a 'sci' group. Given the hints, what results can you show? How > far can you push? > > One thing *not* to do is fix what you have not broken. No need, at > this point, to reformulate your Dynamic Hill Cipher. As Maaartin said, > "select a PRNG and go *solve* it". I have clearly pointed out in my reply to Maaatin that his sentence should apply to you rather then to me. For I claimed that in my view it is not solvable. If you could ever crack the modified Hill system, even using a linear PRNG of your "own" choice (but evidently not "trivially" poor), then I'll certainly readily concede that it is broken. Otherwise it is secure and you have "gravely" deceived yourself!! I challenge you to do that, since you clearly claim that the scheme is "nothing". M. K. Shen
From: Mok-Kong Shen on 29 Apr 2010 08:13 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 with known-plaintext. Suppose one uses a 2*2 Hill matrix (aij) and there are two pairs of plaintext and ciphertext vectors (each vector has 2 elements) processed by it. Thus (assuming alphabet size is 2^m): | a11 a12 | | p11 p12 | | c11 c12 | | | * | | = | | mod 2^m | a21 a22 | | p21 p22 | | c21 c22 | 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.) 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. M. K. Shen
From: Mok-Kong Shen on 29 Apr 2010 08:17
Mok-Kong Shen wrote: > > ..... 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. Sorry, typo: Please read (p11, p21). M. K. Shen |