Subject: RE: [Cfrg] Authenticated encryption primitive -- SOBER-128

From: Doug Whiting <[email-masked]>
Date: Mon, 12 May 2003 13:54:50 -0700

Well, it seems maybe you're mixing metaphors.  

If the goal is to replace RC4, then perhaps SOBER (without MAC) might make
some sense.
First of all, however, I'd like to be convinced that there's a real problem
with RC4, as opposed to how it is misused.  Saying that somebody has an
unpublished attack doesn't do much for me.  For better or worse, RC4 has
had lots of years to be attacked, so far with only a few very avoidable 
or fairly inconsequential dings in its armor (AFAIK), and replacing it with 
something new could end us up in far worse shape in a few years.  You may
know who has looked at it, but the crypto community in general probably
doesn't.
Have they published all their  analyses? Where?  This is the kind of stuff
that 
must be very carefully considered before making a change from "the devil we
know".
I guess basically I'd like some proof that RC4 needs deprecation. I'm not
aware
of any compelling motives for that, thought I certainly may be wrong.

If the goal is a combo encryption+MAC algorithm, then I stand by my
desire for quite a while for open study.  Saying that the possible need for
an RC4 replacement dictates acceptance of a new type of algorithm that does
something that RC4 doesn't even attempt to do seems like a bad argument.

So, which point are you trying to argue?  They're quite separate ones, from
my
perspective.

> -----Original Message-----
> From: Greg Rose [mailto:[email-masked]]
> Sent: Monday, May 12, 2003 9:16 AM
> To: Doug Whiting
> Cc: 'Greg Rose'; [email-masked]; Alex Alten
> Subject: RE: [Cfrg] Authenticated encryption primitive -- SOBER-128
> 
> 
> I very much agree with the sentiments you express below. The only 
> difference between us is that I do know how much 
> cryptanalysis has been 
> applied, and who by. This makes me feel much more confident 
> in SOBER-128 
> than I have any right to expect others to feel.
> 
> Note that I, personally, think that Turing, SNOW 2.0 and 
> Helix are much 
> more "interesting" ciphers than SOBER-128. But I, like you, would not 
> recommend use of any of them yet.
> 
> But the reason we created SOBER-128 is not for cryptographic 
> interest. It's 
> because RC4 should be deprecated, but isn't. Perhaps we 
> should have named 
> it Chicxulub, which would address your concern about there 
> being too many 
> versions of SOBER :-).
> 
> Note: there have been 4 "kinds" of SOBER including this 
> latest. By "kinds" 
> I mean different word-sizes but same fundamental structure. 
> The first was 
> certainly broken (linear key loading). The second "S-class" 
> was marginal 
> against guess-and-determine attacks, and presumably has the same 
> distinguishing attacks as... The third "t-class" has no known attacks 
> except distinguishing attacks with insane (IMHO) amounts of known 
> plaintext, but a few rough edges. The fourth is SOBER-128. 
> There will be no 
> more.
> 
> regards,
> Greg.
> 
> At 03:50 AM 5/12/2003 -0700, Doug Whiting wrote:
> >I just want to express my concern about trying to make an RFC out of
> >anything like
> >this without considerable more time for analysis.  I agree 
> that various
> >flavors
> >of SOBER have seen some good amounts of cryptanalysis, 
> though I'm not sure
> >that
> >it has had enough yet (I'm simply not sure how many really 
> good folks have
> >spent
> >significant time on it).  One concern is that there have 
> simply been too
> >many SOBER
> >versions already, which urges some caution from my 
> perspective, although
> >there may
> >be very good reasons for the different versions. More 
> importantly, adding a
> >very significant new cryptographic "feature" such as a MAC 
> does not in any
> >way
> >constitute a "tweak" that should be assumed to inherit the security
> >properties of
> >the original algorithm(s).
> >
> >I say this as a co-author of Helix, and as someone who 
> belives, like you,
> >that such
> >combo algorithms are quite interesting. However, I believe 
> that this entire
> >concept
> >needs time for being carefully analyzed by the crypto 
> community before being
> >put into
> >serious use.  We simply are not there yet. The Helix folks 
> would consider it
> >quite
> >inappropriate to start standardizing at this time on any 
> such algorithm,
> >including Helix,
> >without quite a bit of time passing, perhaps a few years.  
> That's roughly
> >how much time
> >AES had, and it had (and continues to have) basically all the best
> >crpytanalysts looking
> >at it very seriously.  Of course, even just the passage of 
> time doesn't
> >guarantee that a
> >new algorithm (class of algorithms) has been propertly 
> vetted; the algorithm
> >must also
> >receive serious scrutiny from several well qualified folks. 
> That is, the
> >passage of such
> >time is a necessary but not sufficient condition.
> >
> >Don't take this as a criticism of SOBER-128 per se. I 
> believe that this
> >caution should
> >be applied to all algorithms of this class.
> >
> >Doug Whiting
> >
> > > -----Original Message-----
> > > From: Greg Rose [mailto:[email-masked]]
> > > Sent: Sunday, May 11, 2003 3:07 PM
> > > To: Alex Alten
> > > Cc: Greg Rose; [email-masked]
> > > Subject: Re: [Cfrg] Authenticated encryption primitive -- 
> SOBER-128
> > >
> > >
> > > At 11:00 PM 5/10/2003 -0700, Alex Alten wrote:
> > > >Have you had any serious independent cryptanalysis done 
> on SOBER-128
> > > >that proves that it is well designed?  It's no good throwing
> > > it to the wolves
> > > >until you can defend it properly.
> > >
> > > Yes. If you read the details, SOBER-t32 has been analysed up
> > > the wazoo, and
> > > was secure at the 128-bit level; just not at the 256-bit
> > > level that we
> > > thought, which ruled it out of NESSIE. Most of this analysis
> > > was done on
> > > the "unstuttered" -t32, and applies directly to SOBER-128.
> > >
> > > regards,
> > > 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
> > >
> 
> 
> 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: Greg Rose <[email-masked]>
Date: Tue, 13 May 2003 07:51:17 +1000

>Well, it seems maybe you're mixing metaphors.

"To boldly mix metaphors, where no man has gone before..."

>unpublished attack doesn't do much for me.

I've never referred to any unpublished attacks, on either cipher? If I was 
aware of any, I might have done so, but I'm not.

The key-bias problems are well known, starting with Kocher and ending (so 
far) with Fluhrer-Mantin-Shamir. The distinguishing attacks against RC4 
with data complexity about 2^32 are, I think, from Golic and Fluhrer (I'm 
not near my references at the moment). Actually, a quick web search shows 
Fluhrer and McGrew as the authors of the most recent (FSE 2000) paper 
talking about bias in RC4.

>   For better or worse, RC4 has
>something new could end us up in far worse shape in a few years.

The keystream bias is, in no sense, avoidable. I'd call it inconsequential 
if it wasn't measurable in a few seconds' worth of high speed ethernet traffic.

>   You may

Sorry to disagree. Regarding SOBER, just look at the proceedings from the 
NESSIE conferences, and the FSE conferences, for the past few years. 
Everything I've referred to about SOBER-128 is published and the references 
are in the SOBER-128 paper.

>of any compelling motives for that, thought I certainly may be wrong.

We may well have different guidelines for deprecation. To me, trying to 
deprecate something without a viable alternative is futile, so we've 
attempted to provide an alternative. But I'm not trying to force it on anyone.

>something that RC4 doesn't even attempt to do seems like a bad argument.

That's a fair cop. It's certainly the case that our arguments for security 
of the MAC construct are, at best, just plausible arguments. They rely on 
the fact that the mechanisms for the MAC parallel mechanisms that already 
appeared in the cipher, which have been closely studied.

>So, which point are you trying to argue?  They're quite separate ones, from

Yes, I agree that they should be separate arguments. So, here's a claim, 
restated:
Anywhere you can use RC4, you can use SOBER-128 in single-stream mode, and 
be reasonably assured, today, that it will be more secure. It's also faster 
to key, faster to generate output, and uses less RAM. On the downside, you 
can't code it from memory, and you'd better have some ROM for tables; in my 
experience these are rarely limiting factors.

I'm not aware of any other algorithm that can credibly make that claim. I 
don't claim it for Turing, even though I believe that to be a stronger 
algorithm. You don't make it for Helix. Ekdahl and Johansson don't make it 
for SNOW 2.0.

Note: the claim could still be incorrect. C'est la guerre.

Anyway, I'm not trying to force SOBER-128 on anyone, but I, for one, will 
never allow my company to use RC4 in any new development.

Sorry if this sounds argumentative; it's not meant to. "The road to hell is 
paved with good intentions."

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

---

From: Adam Back <[email-masked]>
Date: Tue, 13 May 2003 02:20:18 +0100

Well I for one am very pleased to see work on primitives such as Helix
and SOBER-128 which try to provide authentication as well as
encryption.  It seems that construction flaws typically creep in where
not-so-crypto-savy programmers make up ways to authenticate, and with
AES we have this whole messy scenario where there are multiple
competing modes which provide authentication and confidentiality --
some of the more efficient of which are patented, and most of the less
efficient of which basically amount to no more than just that: MAC the
mesage and encrypt the message (great).

One question about using SOBER-128.  Greg mentioned in his
announcement free use of the source code or other implementations, and
on the web page it says "freely available", but then there is also a
patent section at the bottom of:

	http://www.qualcomm.com.au/publications.html

What is the overall picture: can anyone use the algorithms without
negotiating a license even though there are patents which may be
argued to cover aspects of SOBER-128's design?

Thanks

Adam

---

From: Greg Rose <[email-masked]>
Date: Wed, 14 May 2003 01:48:17 +1000

>argued to cover aspects of SOBER-128's design?

Short answer: yes. There's a license in the source code modules that grants 
a free license to use the source, or to use any of our patents for an 
independent implementation to interoperate. If you want to use your own 
implementation, and want to do it "clean room" (that is, not even *look* at 
our code), there's a separate web page that you can print and file. If 
anyone wants more guarantees than that (like a signable license), I'm sure 
we could work something out.

This is not quite as good as putting our patents in the public domain, but 
Qualcomm is an IPR company, and it took me most of 6 years to get agreement 
to make them free. Note, for example, that the license does *not* grant you 
the ability to use our patents to run a non-SOBER encryption algorithm. 
Like Linus, we want to keep control of the development process. The 
internal agreement actually covers any cipher algorithms we have developed 
or may develop.

I hope that's clear. I'm happy to elaborate.

Greg.