Dynamic Hill cipher
in [Cryptography]
|
From: Maaartin on 29 Apr 2010 08:40 On Apr 29, 1:33 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > 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? No, you missed it. The PRNG has a final initial state, the matrix multiplication is a linear operation. You can get any number of linear equations for fixed number of variables. Broken. > > 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. But why should he do it? It's not his homework, you're not going to pay him, and he doesn't believe it works. Claiming it works, is you right, but it's not enough to convince him (or me). You need much better arguments (e.g., probabilities if linear and differential trails). Or you need to be known for strong crypto designs - this is where the history comes into play. > If you could ever crack the modified Hill system, even > using a linear PRNG of your "own" choice (but evidently not "trivially" > poor), But he can. Or linear systems are broken, there's no need to actually solve it, when he knows it can be done. > then I'll certainly readily concede that it is broken. > Otherwise it is secure Wrong again. There a huge gap between broken and secure. Most of what I can't break is very insecure. Even most of what Bruce Schneier can't break is insecure by contemporary standards. Moreover, most of what NSA didn't break is not secure enough, because one day somebody may put more effort into it and break it. > and you have "gravely" deceived yourself!! I challenge you > to do that, since you clearly claim that the scheme is "nothing". What is the prize for the challenge?
From: Scott Fluhrer on 29 Apr 2010 09:11 "Mok-Kong Shen" <mok-kong.shen(a)t-online.de> wrote in message news:hrbqq5$ul8$00$1(a)news.t-online.com... > 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? No, I don't see that at all. Neither, I'm sure, does Bryan. In fact, it would actually appear to be false (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). Bryan suggested some things you can do yourself to start analyzing it yourself; if you show people that you're interested enough in it to put in some work yourself, it's possible that someone would help you. However, if it's not important enough for you, why would you expect other people to bother? > >> [...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!! 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. -- poncho
From: Mok-Kong Shen on 29 Apr 2010 11:54 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?? M. K. Shen
From: Mok-Kong Shen on 29 Apr 2010 12:05 Maaartin wrote: > Claiming it works, is you right, but it's not enough to convince him > (or me). You need much better arguments (e.g., probabilities if linear > and differential trails). Or you need to be known for strong crypto > designs - this is where the history comes into play. I assume that you are certainly acquainted with the issue of solution of systems of linear equations in the special case of the determinant being zero. In that case the system is indeterminate, because it doesn't have a unique solution but instead a large number of eligible solutions. The situation is "analogous" to what is involved here. In the 2*2 case I illustrated, with 2 pairs of plaintext and ciphertext vectors one has sufficient data to determine the Hill matrix, but with half of that data, i.e. only one pair of corresponding vectors, one lacks that data. so that a large number of eligible solutions exist. Isn't that very clear? BTW, I very much wonder your altitude expressed above. It means that in your opinion a well-known person basically don't need to provide any good arguments, just anything he claims is "gold". M. K. Shen
From: Maaartin on 29 Apr 2010 12:21
On Apr 29, 6:05 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Maaartin wrote: > > Claiming it works, is you right, but it's not enough to convince him > > (or me). You need much better arguments (e.g., probabilities if linear > > and differential trails). Or you need to be known for strong crypto > > designs - this is where the history comes into play. > > I assume that you are certainly acquainted with the issue of solution > of systems of linear equations in the special case of the determinant > being zero. In that case the system is indeterminate, because it doesn't > have a unique solution but instead a large number of eligible solutions. Yes, it's quite improbable (see below), but it may happen. Nonetheless, if you want any security, you can't count on this. There are 2 possibilities: - Either collecting more data helps, i.e., gives enough independent equations to find a unique result - Or it doesn't, but then I take any solution, since all lead to the same ciphertext If you don't trust me, just try it out. > The situation is "analogous" to what is involved here. In the 2*2 case > I illustrated, with 2 pairs of plaintext and ciphertext vectors one > has sufficient data to determine the Hill matrix, but with half > of that data, i.e. only one pair of corresponding vectors, one lacks > that data. so that a large number of eligible solutions exist. Isn't > that very clear? Not to you. Assuming a perfect PRNG it works, but is useless, as already said. Assuming any other PRNG, you can collect equations *over more outputs*. If the PRNG is linear, the equations are linear as well, you get any number of them, you compute it's initial state, it's broken. QED. > BTW, I very much wonder your altitude expressed above. It means that > in your opinion a well-known person basically don't need to provide > any good arguments, just anything he claims is "gold". I claim about the opposite. In fact, an acknowledged cryptographer need no arguments in order for others to start analyzing his algorithm. However, nobody starts using his algorithm until there good arguments for its security. |