Subject: Re: [Cfrg] SOBER-128 draft rfc

From: Greg Rose <[email-masked]>
Date: Fri, 20 Feb 2004 11:11:01 +1100

At 06:36 PM 2/9/2004 -0500, John Viega wrote:
>In FSE there was a MAC forgery attack that succeeded with very high
>probability.  Should something with such an attack really be an RFC,
>or was the attack actually incorrect?  I did see the talk and it
>seemed to make sense.

I wrote:
>(I assume you mean:
>fse048
>Title: A MAC forgery attack on SOBER-128
>Authors: Dai Watanabe and Soichi Furuya

Well, this is one of those very hard things to write...

The attack certainly works, although the authors didn't make it very clear 
that it only works when MACing unencrypted material.

For those who haven't seen it, here's my one-paragraph synopsys: you flip 
the 0x100 bit of one input word, the same bit of the word two words later, 
the 0x001 bit of the word 13 words later, and the 0x100 bit again of the 
word 17 words later. (These correspond to the LFSR feedback stages.) Then, 
with p=1/32, the MAC doesn't change.

I'm very embarrassed, because it falls into the category of things I/we 
should have though of. Which is not to detract from Watanabe and Furuya 's 
work, which is neat. If it was obvious, I like to think we would have seen 
it. In a way, we did see it, because we extensively analysed the MAC 
function in combination with encryption. The reason that plaintext was 
input to the MAC feedback function was to ensure that differences in 
plaintexts would appropriately change the keystream output, thus leveraging 
the stronger nonlinearity of the keystream NLF. (That was a handwaving 
description of something I think we express more clearly in the design 
document.) I failed to take into account that this left us potentially 
vulnerable in the plaintext-only scenario; after all, we were designing a 
cipher, right?

Is this problem fixable? Without sacrificing too much performance? As it 
happens, yes... there's a simple fix to this problem that we'd already 
considered in the design phase (that the authors above missed). Feed back 
ciphertext, not plaintext, when not encrypting. We originally didn't do 
this purely for the efficiency of not generating the unneeded keystream, 
not realizing that we'd opened up the same problem we'd already avoided once.

To clarify: The input to the MAC feedback function now uses ciphertext bits 
when transmitting plaintext, and plaintext bits when transmitting 
ciphertext. These can be mingled at the level of individual bits, although 
our reference code only supports a byte-at-a-time interface.

This mirrors our PEMI (Partial Encryption with Message Integrity) 
enhancement of Jutla's IAPM parallel encryption-and-MAC mode, which has 
been proven secure. The good outcome of this is that we might even be able 
to develop a proof of security for the MAC functionality based on the 
assumption of security for the stream cipher; but that's in the future. In 
the meantime, at least the fix is "pre-analyzed", because we are confident 
that duality applies and the MAC function now has the same security in both 
directions, and we believe that to be quite strong, although time will tell.

While adapting the RFC we also noticed another "D'oh" moment. We hadn't 
fully specified how the MAC behaved when not using entire words, and 
allowed extension of partial words with zero bits to have the same MAC. We 
fixed this along the way.

New versions of the reference (C and Java) source code, an updated design 
document, and updated RFC will be available on our website 
www.qualcomm.com.au  approximately contemporaneously with this message. 
Note that the only behaviour that has changed has to do with MACing 
unencrypted plaintext. The keystream generator hasn't changed, and the 
result of MACing entirely encrypted plaintext hasn't changed. So we're not 
making a big change to the name of the cipher, just adding a version number 
for clarity to the various code and document names.

Please bear in mind that our goal here is to produce a practical and usable 
cipher that has had lots of cryptanalysis applied to it. So we've done a 
lot of the development, historically, in public (and taken the necessary 
hits) and have been trying evolutionary, not revolutionary, changes. We 
consider this to be another step along that path, albeit an embarrassing one.

Greg.

Greg Rose                                       INTERNET: [email-masked]
Qualcomm Australia          VOICE:  +61-2-9817 4188   FAX: +61-2-9817 5199
Level 3, 230 Victoria Road,                http://people.qualcomm.com/ggr/
Gladesville NSW 2111    232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: "David A. McGrew" <[email-masked]>
Date: Thu, 19 Feb 2004 18:36:26 -0800

Greg,

thanks for the update.  No embarrassment, this happens to everyone in 
the business at one point or another, and evolution is certainly an 
important process here.

I have one quick question: the attack is only on the MAC component, 
right?  Is exhaustive search still the best known attack against the 
keystream generator?

thanks,

David

On Feb 19, 2004, at 4:11 PM, Greg Rose wrote:

> The attack certainly works, although the authors didn't make it very 
> clear that it only works when MACing unencrypted material.
>
> For those who haven't seen it, here's my one-paragraph synopsys: you 
> flip the 0x100 bit of one input word, the same bit of the word two 
> words later, the 0x001 bit of the word 13 words later, and the 0x100 
> bit again of the word 17 words later. (These correspond to the LFSR 
> feedback stages.) Then, with p=1/32, the MAC doesn't change.
>
> I'm very embarrassed, because it falls into the category of things 
> I/we should have though of. Which is not to detract from Watanabe and 
> Furuya 's work, which is neat. If it was obvious, I like to think we 
> would have seen it. In a way, we did see it, because we extensively 
> analysed the MAC function in combination with encryption. The reason 
> that plaintext was input to the MAC feedback function was to ensure 
> that differences in plaintexts would appropriately change the 
> keystream output, thus leveraging the stronger nonlinearity of the 
> keystream NLF. (That was a handwaving description of something I think 
> we express more clearly in the design document.) I failed to take into 
> account that this left us potentially vulnerable in the plaintext-only 
> scenario; after all, we were designing a cipher, right?
>
> Is this problem fixable? Without sacrificing too much performance? As 
> it happens, yes... there's a simple fix to this problem that we'd 
> already considered in the design phase (that the authors above 
> missed). Feed back ciphertext, not plaintext, when not encrypting. We 
> originally didn't do this purely for the efficiency of not generating 
> the unneeded keystream, not realizing that we'd opened up the same 
> problem we'd already avoided once.
>
> To clarify: The input to the MAC feedback function now uses ciphertext 
> bits when transmitting plaintext, and plaintext bits when transmitting 
> ciphertext. These can be mingled at the level of individual bits, 
> although our reference code only supports a byte-at-a-time interface.
>
> enhancement of Jutla's IAPM parallel encryption-and-MAC mode, which 
> has been proven secure. The good outcome of this is that we might even 
> be able to develop a proof of security for the MAC functionality based 
> on the assumption of security for the stream cipher; but that's in the 
> future. In the meantime, at least the fix is "pre-analyzed", because 
> we are confident that duality applies and the MAC function now has the 
> same security in both directions, and we believe that to be quite 
> strong, although time will tell.
>
> While adapting the RFC we also noticed another "D'oh" moment. We 
> hadn't fully specified how the MAC behaved when not using entire 
> words, and allowed extension of partial words with zero bits to have 
> the same MAC. We fixed this along the way.
>
> New versions of the reference (C and Java) source code, an updated 
> design document, and updated RFC will be available on our website 
> www.qualcomm.com.au  approximately contemporaneously with this 
> message. Note that the only behaviour that has changed has to do with 
> MACing unencrypted plaintext. The keystream generator hasn't changed, 
> and the result of MACing entirely encrypted plaintext hasn't changed. 
> So we're not making a big change to the name of the cipher, just 
> adding a version number for clarity to the various code and document 
> names.
>
> Please bear in mind that our goal here is to produce a practical and 
> usable cipher that has had lots of cryptanalysis applied to it. So 
> we've done a lot of the development, historically, in public (and 
> taken the necessary hits) and have been trying evolutionary, not 
> revolutionary, changes. We consider this to be another step along that 
> path, albeit an embarrassing one.
>
> Greg.
>
> Greg Rose                                       INTERNET: 
> [email-masked]

---

From: Greg Rose <[email-masked]>
Date: Fri, 20 Feb 2004 17:34:16 +1100

>right?  Is exhaustive search still the best known attack against the 

Yes. The keystream generator is completely bulletproof, unless someone 
comes up with an entirely new kind of attack. There was also a paper at FSE 
that claimed (when submitted) a distinguishing attack, but they got the 
complexity way wrong and retracted the result at the conference. Nothing 
comes even close to 2^128, that we know of.

Greg.

---

From: Greg Rose <[email-masked]>
Date: Tue, 24 Feb 2004 04:27:58 +1100

So...

Based on Watanabe & Furuya's work, even with the new scheme, there is a 
differential cryptanalysis MAC forgery attack on SOBER-128, whether 
encrypting or not. We're evaluating it, deciding what to do. This will not 
be a quick thing, though, so we're not publishing the updated RFC yet. To 
the best of our knowledge, the keystream generator is still very solid.

Greg.

At 11:11 AM 2/20/2004 +1100, Greg Rose wrote:
>plaintexts would appropriately change the keystream output, thus 
>leveraging the stronger nonlinearity of the keystream NLF. (That was a 
>handwaving description of something I think we express more clearly in the 
>design document.) I failed to take into account that this left us 
>potentially vulnerable in the plaintext-only scenario; after all, we were 
>designing a cipher, right?
>
>that duality applies and the MAC function now has the same security in 
>both directions, and we believe that to be quite strong, although time 
>will tell.
>
>making a big change to the name of the cipher, just adding a version 
>number for clarity to the various code and document names.
>
>usable cipher that has had lots of cryptanalysis applied to it. So we've 
>done a lot of the development, historically, in public (and taken the 
>necessary hits) and have been trying evolutionary, not revolutionary, 
>changes. We consider this to be another step along that path, albeit an 
>embarrassing one.
>
>Greg.
>