From: Scott Contini on
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
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

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
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
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.
--