[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Rest of World encryption hardware products?



At 07:42 AM 6/10/98 -0400, Steve Bellovin wrote:
> >
> >I read the whitepaper on the site.  It contains a number of phrases
> >which should set off any crypto expert's snake-oil detectors, the most
> >crucial being "virtual one time pad".
> >
>	 
> I don't think you need to take quotes out of context and change
> their wording.  Here's exactly what was written.
> 
> "With RKS, a Random KeyStream derived from a physical random 
> number generator is used as the cipher key.  Conforming to the 
> requirements for a practical Vernam Cipher, the Random KeyStream
> is the same length as the message and will not repeat with a 
> small statistical probability. The secret is the effective 
> management of a virtual keystream over 10³º bytes long."
> 
> It is not claiming to be perfect, there is a small statistical
> probability of a repetition.  Obviously you can't store a 10^30
> byte 1-time pad.  So it has to be generated from a smaller
> amount of random data.  However the solution is elegant and
> has been reviewed by some top cryptographers, like Bart Preneel
> and Fred Piper.  So far it has held up under tough analysis,
> including by some cryptographers over at Bell Labs. It's 
> effective key strength is 128 bits.
>
>Your own excerpts prove Bill's point.  The web page is full of statements
>about how the Vernam cipher is theoretically unbreakable.  But a Vernam
>cipher requires a *true* random key stream as long as the message.  It
>is *not* a cipher where you XOR the message with a pseudo-random key stream.
>But that's precisely what this cipher is doing -- you say so, in about
>those words.  This is an ordinary stream cipher, not a one-time pad.
>

There is no PRNG involved. Every bit, and I mean every bit, used
to create the final pad is ultimately generated from a Fortezza 
card RNG.  This is one of the reasons why it is not a normal 
stream cipher.

As you point out below, it is impractical to manage large amounts 
of 1-time pads throughout a system.  So a compromise is made.  A
finite pad has to be generated on demand by using a unique random 
key and a large finite amount of pre-generated random data (of 
which there is one per security server).  Each new pad is the size 
of a text block to be encrypted.  So to encipher a message of 
several blocks, a series of keys, one per block, *must* be 
generated randomly.  This is why there is a small probability of 
repetition.  In effect each unique pad is created from both static
and dynamic random data.  If the pre-generated random data is 
public, then all the strength resides in the bit length of the 
random key (128 bits here).  The work factor can be easily 
modified by adjusting the amount of pre-generated random data 
and by the number of simple operations needed to generate a single
finite pad--increase either and the number of bits needed 
in a key then increases.  (Sorry, I can't give you more details.)

It is possible to come arbitrarily close to the infinite unicity 
of a true Vernam 1-tape system.  However it is a asymptotic limit,
it can not be reached.  The beauty of this system is that it is 
very easy to increase its strength to any level one desires, or 
that is practical given the technology of the moment.  The same
is true of speed, one can make time-memory tradeoffs to come 
arbitrarily close to a true single pad speed (a single XOR 
operation).  The distribution of the single chunk of pre-generated
random data to all users is easy compared to the impossible chore
in a true Vernam system.  The drawback is that the large number of
random keys being generated on the fly and distributed makes key 
management more difficult than in typical public or symmetric
key cipher systems.

>I have no intrinsic objection to stream ciphers, though using them
>properly requires a great deal of care.  I have serious objections to
>misleading advertising.
>	 

I don't think there was any attempt to mislead.  I talked with the 
author of the white paper.  He was trying hard to be accurate
without giving away the store.

> >It also has built-in key recovery, and appears to require interaction
> >with a centralized network service for all encryption and decryption.
> >As described, it also has good potential to have severe scaling
> >problems.
> >
> 

First the dual server system can handle about 2-4000 transactions
per second.  Each transaction allows a authorized user to encrypt/decrypt
up to about 4 GB of data.  Second the scaling problem for server bottle
necks has been solved by others.  Novell has done it with their 
replication service for NDS.  Something similar, but more concious
of security, is applied here.

> The built in key recovery is why the unrestricted export license was 
> granted.  No keys are escrowed with the government or third party 
> agencies (unlike TIS's solution).  This is very powerful stuff.  Any 
> company in the world, except for places like Iraq, can buy the system
> and keep their keys to themselves.  Key recovery is at their own 
> discretion, not forced upon them by the US government.
>
>I'm not certain how this works.  But let me shoot down a strawman.
>
>Suppose that this system did indeed use a true one-time pad.  A customer
>would be shipped N copies of a CD-ROM of true-random bits -- about 4800M
>of them.  The purpose of the server, then, would be to allocate chunks
>of the bitstream to clients, ensuring that no portion was ever reused
>(remember Venona?).
>
>Such a system would be a theoretician's delight and a practical nightmare.
>
>The problem is that you have to maintain perfect security on *every*
>copy of the CD-ROM.  If one of the N is stolen (or the machine with it
>hacked), all past, present, and future conversations are compromised.
>And the probability of that happening is exponential in N.  In other
>words, it doesn't scale at all.
>
>It's also obvious that 4800 Mbits doesn't last very long -- less than
>an hour at T-1 speeds.  So you'd have to switch CD-ROMs -- simultaneously;
>everyone needs to be playing off the same score -- and safeguard all of
>the old CD-ROMs as well.
>

These problems are solved.  The use of a central secure server and
attaching a seal, containing all information necessary to allow access,
to a document (or to a communications stream) has made it possible.

>Key recovery, of course, is simple in such a scheme:  you turn over
>the CD-ROM to the government on demand.
>

Unfortunately it can be too simple.  Efforts have to be made to
ensure that this cannot be done on a whim.  This system requires
two or more authorized key recovery officials to decrypt an 
encrypted document or communications stream.

>In all seriousness, DES in OFB mode is likely to be more secure in
>practice.  IDEA or CAST-128 in OFB mode would be even better; they
>have a key size of 128 bits.
>
>Of course, this scheme is clearly not a true one-time-pad.  The real
>question is how the key stream is generated from the keying material.
>Is it a published algorithm?  If not, I'm very unlikely to trust it
>even if the Web page were not misleading.

I don't blame you at all for this healthy skepticism.  However think 
carefully.  Given that memory is plentiful, that you can have lots 
of microprocessors, and that good network connections are everywhere.
Now, how would you design a brand new cipher?

>	 
> As for scaling, I guess if you can exceed 2 thousand requests per server
> per second, then you've got a problem.  It ships as a dual server 
> system.  This sure beats the hell out of Public Key implementations 
> which can't do more than 10 per sec.
>
>10 per second *per machine communicating*.  And public key systems can
>set up a secure channel even if the KDC is unreachable; this scheme can't.
>

To date every public key system fielded has proven impractical, witness 
the struggles of the SET system or the SNMP security efforts.  We've 
have been over this ground before, so let's not reiterate old arguements.

I would hope that you, as one of the leading members of the Internet
community, will seriously investigate this new security possibility and 
see if it can be of any use in solving our problems with Internet 
security.

- Alex
--
Alex Alten
Andrade@Netcom.Com
P.O. Box 11406
Pleasanton, CA  94588  USA
(510) 417-0159



Follow-Ups: References: