carrick, Blowfish & the NSA

One reason we chose to use Blowfish as the basis for carrick is that it _is_ a new algorithm.  One has to assume that the NSA et al. has tools optimized to crack DES and possibly IDEA/RSA.  At least let's give them something else to sweat over.  In the short term there's a high probability that a cross-platform Blowfish-based encryption toolkit will muddy the waters and make life interesting for us and a bit more challenging for them.

We're shooting for a May 1 release for Windows with the Mac and DOS 6 weeks behind and VAX/Sun a month after that.  We're aiming for the stars: encryption, time/date stamps, signatures, message digests, etc. all based on Blowfish.  We're doing a core engine with APIs, a standardized file format, and extensability for other developers.  We're very committed to making the spec including the API and file format VERY PUBLIC.  Like I said, we're aiming high.

So yes, if we're successful Blowfish should be taken more seriously.  And yes, when I outlined the above to the NSA while asking for an export permit, I was met with silence on the phone.  I can't wait to meet with them mid-May when they come out to visit.  My sense is that some junior level person(s) looked at Blowfish when Bruce originally published it in Dr. Dobb's and that their report was filed away waiting for the day when someone actually used it in the real world.

Our marketing tag ("Encryption software so good, the Feds won't let us export it.") may well become a self-fulfilling prophecy.  But that's OK because having others adopt carrick is our real goal.  Building up a strong U.S. user base is OK while we wrestle with the NSA over how big a key length we can export.  Their initial response was that 40-bit keys were specific to RC2 and RC4 and that Blowfish was another kettle of fish (bad pun intended).

Either way we're going to publish an extensive FAQ on carrick that should allow someone to not only work with carick but perhaps clone our efforts.  IANAL but my understanding is that publishing such a document, with or without source code, and making it publicly available to non-U.S. citizens is perfectly legal.

So NSA if you're reading this: This may be yet another example of locking the barn door after the genie is out of the bottle.  Prohibiting us from exporting carrick the product is pointless if we're allowed to fully document carrick the API and file spec.



    Jerry Whiting         jwhiting@azalea.com         1 800 ENCRYPT

On Sat, 13 Apr 1996, Jerry Whiting wrote:

> We're shooting for a May 1 release for Windows with the Mac and DOS 6
> weeks behind and VAX/Sun a month after that.  We're aiming for the
> stars: encryption, time/date stamps, signatures, message digests, etc.
> all based on Blowfish.  We're doing a core engine with APIs, a
> standardized file format, and extensability for other developers.  We're
> very committed to making the spec including the API and file format VERY
> PUBLIC.  Like I said, we're aiming high. 

This sounds like an interesting project.  However, I'm having trouble
understanding your goals.  Blowfish is a block cipher.  Why are you using
it to do anything but encryption?  I know there are cryptographic
constructions that allow you to do message digests with block ciphers, but
they are slow and not guaranteed to be as secure as the underlying block
ciphers.  I suggest that instead you use an established message digest 
algorithm such as SHA.  How are you planning to do timestamps and
signatures?  I presume you'll need some other algorithms besides
Blowfish.  Also, will the software be freeware, shareware, or commercial?

Wei Dai

Jerry Whiting writes:
> One reason we chose to use Blowfish as the basis for carrick is that
> it _is_ a new algorithm.  One has to assume that the NSA et al. has
> tools optimized to crack DES and possibly IDEA/RSA.  At least let's
> give them something else to sweat over.

They won't sweat over it long. Blowfish was broken.

> Like I said, we're aiming high.

I believe you are having trouble distinguishing "up" from "down" while
looking through your sights....

> So yes, if we're successful Blowfish should be taken more seriously.

Why? Why exactly would it be hard to produce a crypto package based on
any given algorithm? Its not exactly like Blowfish wasn't out and
available already or anything.

> Our marketing tag ("Encryption software so good, the Feds won't let
> us export it.")

They won't let you export DES and we know how good that is. Heck, they
won't let you export 41 bit RC4 or better and we all know how good 41
bit RC4 would be.

Perry

> Jerry Whiting writes:
> > One reason we chose to use Blowfish as the basis for carrick is that
> > it _is_ a new algorithm.  One has to assume that the NSA et al. has
> > tools optimized to crack DES and possibly IDEA/RSA.  At least let's
> > give them something else to sweat over.
> 
> They won't sweat over it long. Blowfish was broken.

Yikes!  Are you sure?  This is the first I've heard of it.  This would mean
that PGPPhone is not secure.

SINCLAIR DOUGLAS N writes:
> > Jerry Whiting writes:
> > > One reason we chose to use Blowfish as the basis for carrick is that
> > > it _is_ a new algorithm.  One has to assume that the NSA et al. has
> > > tools optimized to crack DES and possibly IDEA/RSA.  At least let's
> > > give them something else to sweat over.
> > 
> > They won't sweat over it long. Blowfish was broken.
> 
> Yikes!  Are you sure?

At least partially broken, yes. I've forgotten the details. I believe
they were discussed at Eurocrypt. It may be that with the full number
of rounds that no one yet has a cryptanalysis but I don't recall and
it doesn't particularly matter from my perspective.

> This is the first I've heard of it.  This would mean
> that PGPPhone is not secure.

I was unaware that PGPPhone used Blowfish, but if it does that was a
stupid idea in the first place.

Perry

-----BEGIN PGP SIGNED MESSAGE-----

On Sun, 14 Apr 1996, Perry E. Metzger wrote:

> At least partially broken, yes. I've forgotten the details. I believe
> they were discussed at Eurocrypt. It may be that with the full number
> of rounds that no one yet has a cryptanalysis but I don't recall and
> it doesn't particularly matter from my perspective.

I haven't heard of any efficient cryptanalysis against Blowfish.  I know there
are weak keys, but they are difficult to exploit.  16 round Blowfish can be
broken using differential cryptanalysis with 2^128+1 chosen plaintexts.

>
> > This is the first I've heard of it.  This would mean
> > that PGPPhone is not secure.
>
> I was unaware that PGPPhone used Blowfish, but if it does that was a
> stupid idea in the first place.

Blowfish is unpatented, free for commercial use, and very fast so I don't see
how the use of Blowfish could be considered stupid.  IDEA and triple-DES may
be more secure, but I think that they are too slow for voice communication.

- -- Mark

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
markm@voicenet.com              | finger -l for PGP key 0xf9b22ba5
http://www.voicenet.com/~markm/ | bd24d08e3cbb53472054fa56002258d5
"The concept of normalcy is just a conspiracy of the majority" -me

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: noconv

iQCVAwUBMXEmo7Zc+sv5siulAQFNugP/eajuzeBDrGi5LfQy5IYANVzYnt/FRQYF
egUkJuWtkxI8ff/CzS9dKxOW95c8SuvYyis9D8NfwAcPesKI/YQp734l/v+NYH4V
G7AZvzdLEKpDWVzo524o326o4ufXV7ycysLNq4yrkPJ5LJyLdm5A3z/0IYeoXStK
2HWAf22Iksc=
=cwEh
-----END PGP SIGNATURE-----

"Mark M." writes:
> > I was unaware that PGPPhone used Blowfish, but if it does that was a
> > stupid idea in the first place.
> 
> Blowfish is unpatented, free for commercial use, and very fast so I don't see
> how the use of Blowfish could be considered stupid.  IDEA and triple-DES may
> be more secure, but I think that they are too slow for voice communication.

Huh?

Voice communication is typically under 20kbps. Using Phil Karn's
latest code, a pentium can do about 10Mbps for single DES, and
presumably about 3Mbps for 3DES. Thats orders of magnitude larger than
you need. 3DES is unencumbered.

Perry

On Sun, 14 Apr 1996, Perry E. Metzger wrote:

> At least partially broken, yes. I've forgotten the details. I believe
> they were discussed at Eurocrypt. It may be that with the full number
> of rounds that no one yet has a cryptanalysis but I don't recall and
> it doesn't particularly matter from my perspective.

It doesn't make much sense to condemn an iterated cipher based on attacks
on reduced-round versions.  Any such cipher becomes weak if you use
sufficiently few rounds.  Conversely, many broken ciphers become secure if
you use sufficiently many rounds (in which case they also become too slow
to be useful).  I don't think there are currently any public attacks that
seriously affect the security of Blowfish.

On the other hand, if you ask cryptographers what they would use if they
were not concerned with efficiency, I think most of them would say triple
DES.

Wei Dai

Wei Dai writes:
> On the other hand, if you ask cryptographers what they would use if they
> were not concerned with efficiency, I think most of them would say triple
> DES.

I'd say that for most applications these days one needn't worry too
much.

Almost all my internal communications these days inside my own LAN are
encrypted. I hardly if ever notice performance issues. When I do, I
decide if I don't care about the traffic (which sometimes is the case)
and then I use RC4.

Anyway, the point is that performance shouldn't be thought of as an
issue unless you have a system built and in use and you find that it
is a bottleneck. Often you would be surprised at how little of a
bottleneck it really is.

Perry

In article <Pine.LNX.3.92.960414121820.358A-100000@gak> "Mark M." <markm@voicenet.com> writes:

> I haven't heard of any efficient cryptanalysis against Blowfish.  I
> know there are weak keys, but they are difficult to exploit.  16
> round Blowfish can be broken using differential cryptanalysis with
> 2^128+1 chosen plaintexts.

Doesn't this assume known S-boxes, though?  If so, since the S-boxes
are key dependent, is this anything to worry about?

On Sun, 14 Apr 1996, SINCLAIR DOUGLAS N wrote:

> > They won't sweat over it long. Blowfish was broken.
> 
> Yikes!  Are you sure?  This is the first I've heard of it.  This would mean
> that PGPPhone is not secure.
> 
If it's the one that's in applied crypto 2 (p.339) and ddj, then it's only a 
partial crack on a low number of rounds (according to AC2). Schneier still 
thought it was secure at the time of the publishing of AC2, but then he 
may be biased. (and since this is crypto why not be paranoid, eh?)
ú   
Besides, doesn't PGPfone give you a choice of algorithms? (including IDEA?)
I haven't gotten it yet, no sound card.

Perry, you've mentioned this before, was this the same crack that's in 
the book or something newer? (paper references?)

(I just caught your reply to Sinclair after writing this. In any case 
Schneier lists the diff. cryptanalysis of blowfish paper as unpublished.)

s1113645@tesla.cc.uottawa.ca writes:
> If it's the one that's in applied crypto 2 (p.339) and ddj, then it's only
> partial crack on a low number of rounds (according to AC2). Schneier still
> thought it was secure at the time of the publishing of AC2, but then he
> may be biased. (and since this is crypto why not be paranoid, eh?)

Its only the partial crack, from what I know. It still makes me
nervous, and besides there are very good cryptosystems like 3DES
that are available and well studied.

.pm

At 11:01 am  -0700 4/14/96, s1113645@tesla.cc.uottawa.ca wrote:
>Besides, doesn't PGPfone give you a choice of algorithms? (including IDEA?)
>I haven't gotten it yet, no sound card.

PGPfone currently offers Blowfish (fast, iffy) and TripleDES (slow, secure).

Jerry Whiting writes:
 > One reason we chose to use Blowfish as the basis for carrick is that
 > it _is_ a new algorithm.  One has to assume that the NSA et al. has
 > tools optimized to crack DES and possibly IDEA/RSA.  At least let's
 > give them something else to sweat over.

Algorithms die. If you want to publish and implement an API that will last,
try to improve on of the many multi-algorithm specs that are already out 
there. If the next round of research kills one particular algorithm, your 
work will then still not be wasted. (Apologies for writing something so 
obvious and general.)