Authentication
in [Cryptography]
|
Prev: Announcing a new Chaocipher-related paper: Deciphering Exhibit #1 from John F. Byrne's "Silent Years"
Next: [M-R test] Formula for p(k,t)
From: Scott Contini on 9 Aug 2010 20:30 On Aug 10, 7:51 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Scott Contini wrote: > > It is trivially breakable. Two attacks: (i) the first > > block, and (ii) extension attacks. You should be able > > to figure out the rest. I hope. This is very basic stuff. > > I have in the meantime also thought about a little bit myself. > Would the following slight modification tighten up the matter? > > S[0] = E(K,IV); > > for (i=0; i<n; i++) > { C[i] = E(K,S[i]^P[i]); > S[i+1] = E(K,S[i]^P[i]^C[i]); > } > > E(K,S[n]) = authentication. > > Thanks. > > M. K. Shen I mentioned two attacks in my previous reply, you only attempted fixing one. Some suggestions: 1. The crypto community is not interested in new, heuristic MACS. We want to see some security reduction. The burden is on the designer to convince us that the design is good. Presenting a design and asking others to analyse it for you is not going to bring a lot of interest. 2. Having said that, I think your algorithm is still vulnerable to extension attacks. But I'm not going to do your analysis work for you. 3. Any designer of a new primitive should have some background in cryptanalysis, or else your design has zero credibility. I'm going to let you earn your own credibility by breaking your own design. It is not too hard. 4. In general, if you want to design a new primitive, you should deal with the case that the message length is not a multiple of the block size. You have not. Scott
From: Mok-Kong Shen on 10 Aug 2010 02:23 Am 10.08.2010 02:30, schrieb Scott Contini: > On Aug 10, 7:51 am, Mok-Kong Shen<mok-kong.s...(a)t-online.de> wrote: >> Scott Contini wrote: >>> It is trivially breakable. Two attacks: (i) the first >>> block, and (ii) extension attacks. You should be able >>> to figure out the rest. I hope. This is very basic stuff. >> >> I have in the meantime also thought about a little bit myself. >> Would the following slight modification tighten up the matter? >> >> S[0] = E(K,IV); >> >> for (i=0; i<n; i++) >> { C[i] = E(K,S[i]^P[i]); >> S[i+1] = E(K,S[i]^P[i]^C[i]); >> } >> >> E(K,S[n]) = authentication. > I mentioned two attacks in my previous reply, you only > attempted fixing one. > > Some suggestions: > > 1. The crypto community is not interested in new, heuristic > MACS. We want to see some security reduction. The burden > is on the designer to convince us that the design is good. > Presenting a design and asking others to analyse it for you > is not going to bring a lot of interest. > > 2. Having said that, I think your algorithm is still > vulnerable to extension attacks. But I'm not going to > do your analysis work for you. > > 3. Any designer of a new primitive should have some > background in cryptanalysis, or else your design has > zero credibility. I'm going to let you earn your own > credibility by breaking your own design. It is not > too hard. > > 4. In general, if you want to design a new primitive, > you should deal with the case that the message length > is not a multiple of the block size. You have not. Thank you for your remarks. However, you said before my modification that the scheme was 'trivially' breakable. Would you please at least write a couple of lines sketching how that is to be very roughly done (in principle)? While I am certainly not intelligent and even clueless, I presume that there could be at least some readers in the group for whom the issue is not apparent. So it would be very fine, if you would be kind enough to reveal a short minimum sketch of your 'recipe'. Thanks in advance. M. K. Shen
From: Mok-Kong Shen on 12 Aug 2010 19:26 Mok-kong.shen wrote: > S[0] = E(K,IV); > > for (i=0; i<n; i++) > { C[i] = E(K,S[i]^P[i]); > S[i+1] = E(K,S[i]^P[i]^C[i]); > } > > E(K,S[n]) = authentication. In order to facilitate further discussions, I like to explain how I arrived at this scheme. Consider the CBC MAC, which may be described, if I don't err, in my notation as follows: C[-1] = IV1; for (i=0; i<n; i++) C[i] = E(K1,C[i-1]^P[i]); S[-1] = IV2; for (i=0; i<n; i++) S[i] = E(K2,S[i-1]^P[i]); S[n-1] = authentication. Both processes are CBC, which has the well-known property of being able to recover (in later blocks) from an error (or malicious modification) that occurs in a previous block, a property that some people deem, as far as I know, as favourable but that I 'personally' however consider to be unfavourable. I found that one apparent way to render errors to become irrecoverable is to have the two processes above coupled through their chaining values. Naturally, the chaining values would thereby become a bit more complicated in form, which would in my personal view be a benefit with respect to security. Doing this, I arrived at the following: C[-1] = IV1; S[-1] = IV2; for (i=0; i<n; i++) { C[i] = E(K1,S[i-1]^P[i]); S[i] = E(K2,S[i-1]^P[i]^C[i]); } S[n-1] = authentication. An additional motivation of mine is to use one key instead of two, which in my view is more convenient. Now, letting K = K1 = K2 and using (as a consequence of the coupling) only one IV and shifting the start of indexing of S by 1, one gets: S[0] = IV; for (i=0; i<n; i++) { C[i] = E(K,S[i]^P[i]); S[i+1] = E(K,S[i]^P[i]^C[i]); } S[n] = authentication. From the above depicted process of derivation, I believe that this scheme can be equivalent to CBC MAC in security, with the more complicated chaining compensating for the fact that now only one key is used. (Should I do err, though I at the moment don't think so, one could revert to employing two keys, one for computing C[i] and the other for computing S[i+1] in the loop above.) Pending response of Contini to my latest post, I doubt that the two kinds of attacks he mentioned are applicable to the scheme shown immediately above (which is what was before my modification of 09.08.2010 23:51.) For firstly, I am ignorant of any trouble with "the first block" for CBC MAC and my scheme is a modification of CBC MAC. Secondly, the "extension attacks" apply only to use of iterated hash functions (instead of a block cipher as in CBC), if I don't err. For, in the case of use of a block cipher, there is nothing that could be "extended" in the sense of "extension attacks" according to my current humble understanding of these attacks. Finally, since I consider performing additional encryptions to two of the blocks involved, namely the S[0] and S[n] in the above, to be a worthwhile 'additional' measure of security that should normally be tolerable in the total computational cost, I decided to introduce that, leading thus to the modified version given in the quote at the beginning of this post. Thanks. M. K. Shen
From: Scott Contini on 12 Aug 2010 20:39 On Aug 13, 9:26 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: I am disappointed in myself for replying to you again about this. > > S[0] = IV; > > for (i=0; i<n; i++) > { C[i] = E(K,S[i]^P[i]); > S[i+1] = E(K,S[i]^P[i]^C[i]); > } > > S[n] = authentication. > (i) If you flip a bit in the IV and flip the same bit in the plaintext, you get the same MAC. (ii) If you have message M with MAC T, and message M' with MAC T', then you can construct a new message with MAC T'. That new message consists of first the message M (and its IV) followed by message M', except changing P'[0]. The new value for P'[0] is T xor IV' xor P'[0]. This assures that the value of C'[i] when processing the first word of the combined message are C'[i] = E(K,S'[i]^P'[i]) = E(K, T ^ [T xor IV' xor P'[0]]) = E(K, IV' xor P'[0]]) which is the same as the first word that is processed for M'. Likewise, the same is true for the computation of S'[i+1]. I refuse to be drawn into this more. If you can't see the problem now, then you shouldn't be designing algorithms like this. These are basic attacks. Scott
From: Greg Rose on 12 Aug 2010 21:15
In article <40a7b45a-f979-42cf-abd9-8b820b0927c8(a)m17g2000prl.googlegroups.com>, Scott Contini <the_great_contini(a)yahoo.com> wrote: >On Aug 13, 9:26�am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > >I am disappointed in myself for replying to you again >about this. Yeah, me too! :-) [snip] >I refuse to be drawn into this more. If you can't see >the problem now, then you shouldn't be designing algorithms >like this. These are basic attacks. Exactly... Greg. -- |