Cryptography-Digest Digest #646, Volume #10 Mon, 29 Nov 99 12:13:02 EST
Contents:
Re: brute force versus scalable repeated hashing (Juergen Thumm)
compact encryption in javascript ("Eike Kock")
Question about CSS (Matthieu Brunet)
Re: US stupidity ("Tim Wood")
Re: Why Aren't Virtual Dice Adequate? ("james d. hunter")
Re: ENIGMA verification (David Hamer)
Re: smartcard idea? ([EMAIL PROTECTED])
Re: "Compressible Encryption" - Is it an oxymoron? (John Savard)
Re: NSA should do a cryptoanalysis of AES (Bruce Schneier)
Elliptic Curve Public-Key Cryptography (Bruce Schneier)
----------------------------------------------------------------------------
From: Juergen Thumm <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc
Subject: Re: brute force versus scalable repeated hashing
Date: Mon, 29 Nov 1999 13:08:12 +0100
Bill Unruh wrote:
> Why are you assuming an 8 byte passphrase? Why not a one character
> passphrase? That is eaven easier to crack. Ie, you passphrase MUST
> contain as much "entropy" as you want your key to have. This is very
> well known, and if it does not, you are in trouble.
i had to select something as a base for security estimation.
8 characters is a realistic average for security-aware everday use.
i gave some raw number how long it may take to crack,
and users using more or less entropy in their keys can then decide
themselves how much tradeoff or increase in resistance they want.
> And is still susceptible to dictionary lookup. The enemy can simply
> prehash all of your 8 character pass phrases, and do a lookup when he
> gets your message. 8 characters is too little, no matter how you massage it.
good idea, let's follow this:
the attacker would have to store 36**8 == 2.82e+12 patterns,
with 16 bytes each, makes 4.51e+13 bytes,
or a 41 Terabyte lookup table.
today's largest machines work in the gigabyte range.
this may change within one or two decades,
especially with the development of holographic storage,
but at least today, a table-based attack still requires
massive investment and should be limited to well-equiped
secret services only.
to encounter this, one solution may be to create no 16-bytes
output in the hashing loop but, for example, 128 bytes
and combine this with the random block, to build the input
for the final symmetric key. any comments?
> Well, there is also the difference in stupidity between teh encryptor
> and the attacker. You assume a stupid encryptor. In that case, there are
> loads of attacks available to the attacker, most of which do not involve
> breaking the crypto engine.
not quite. my calculations are based on full 36**8 possible key patterns,
that is, a random combination of a-z and 0-9 characters,
like "1xk5wr8". whoever uses such difficult passwords would already
be a highly security-aware user.
whoever uses, in contrast, a passphrase like "martha75", also uses
8 characters but has a massive resistance tradeoff.
the optimum for open bcrypt lies in passphrases like
"martha 19.7 went to woody 17.9" - still relatively easy to remember,
but human language-based dictionary attacks should fail
due to the numbers. except for very tricky attacker algorithms
which use a combined dictionary/random scheme...
passphrase entropy theoretics surely are a big subject -
maybe someone has a good link about it?
greetings,
Juergen Thumm
--
[jthumm(@)lycosmail.com]
address altered to deflect spam.
------------------------------
From: "Eike Kock" <[EMAIL PROTECTED]>
Subject: compact encryption in javascript
Date: Mon, 29 Nov 1999 14:33:22 +0100
Hi!
I am looking for a compact public-key-based encryption algorithm I can
easily implement using javascript in less than 10 lines of code. Anyone know
of something like this.
Thank you in advance,
Eike
------------------------------
From: Matthieu Brunet <[EMAIL PROTECTED]>
Crossposted-To: alt.video.dvd
Subject: Question about CSS
Date: Mon, 29 Nov 1999 14:26:24 +0100
I have a question about the technical aspect of CSS protection which is
not explained in the DVD FAQ:
It seemed to me that there was a unique scrambling (i.e. cyphering)
private key, known by the DVD player to decipher the content. It would
be this key which was found by hackers on the Xing player and used in
DeCSS.
This scheme is not what I have read in articles. In [1], we are told:
"Descrambling requires a pair of keys(...). The keys are stored on the
lead-in area of the disk, which is generally only read by compliant
drives."
In case this is true which I believe, I don't see what prevents a
non-compliant (though legal) drive from reading every part of the disc
(no patent should forbid this, right?) in order to make a perfect copy
of the DVD.
I don't either see what is the role of the universal CSS key found on
Xing player.
Thanks for your time,
Matthieu
[1] Bloom et al., "Copy Protection for DVD Video" in Proceedings of the
IEEE, Special Issue, July 1999.
------------------------------
From: "Tim Wood" <[EMAIL PROTECTED]>
Crossposted-To: us.politics,talk.politics.crypto
Subject: Re: US stupidity
Date: Mon, 29 Nov 1999 13:58:14 -0600
SCOTT19U.ZIP_GUY wrote in message <81hl8q$140u$[EMAIL PROTECTED]>...
>In article <81gd2c$hh8$[EMAIL PROTECTED]>, "Tim Wood"
<[EMAIL PROTECTED]> wrote:
>>Should this thread be crossposted to sci.crypt?
>>
> It already is so don't worry about it.
>I put it there so WHAT?
>
>
>David A. Scott
>--
i'm not sure it's within the mandate of the group, but then this isn't
either.......
------------------------------
From: "james d. hunter" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Why Aren't Virtual Dice Adequate?
Date: Mon, 29 Nov 1999 09:39:40 -0500
Reply-To: [EMAIL PROTECTED]
John Savard wrote:
>
> On Sun, 28 Nov 1999 22:11:04 -0500, "james d. hunter"
> <[EMAIL PROTECTED]> wrote:
>
> > It's been proven that the only type of processes are physical ones.
>
> It's true that the phenomenon of the execution of a computer program
> is physical. However, computers are designed to behave in a
> predictable manner; the ordinary rolling of a real physical die, on
> the other hand, derives from inputs that are not controllable or
> predictable. The initial state of a computer program almost can't help
> being controllable and predictable, given the design of present-day
> computers and operating systems.
Ordinary dice are also designed to behave in a predictable manner.
And they do. When you go to a casino, you will usually see someone
with a gun by the door, watching over the local Wayne "QM" Newtons,
to make sure that don't "interpret" their way out of paying their real
physical debts.
>
> >It's been noticed that none of "pseudo-random", "random", or "truly
> >random" or "quantumly random" exist.
>
> Just because some people have made such assertions hardly means that
> they are true.
>
> >So virtual dice, since they are also
> >physical dice, are adequate.
>
> Thus, your conclusion is false (and is disproven in practice in any
> case).
Well, lucky in philosophy always did imply unlucky at cards.
------------------------------
Date: Mon, 29 Nov 1999 10:13:15 -0500
From: David Hamer <[EMAIL PROTECTED]>
Subject: Re: ENIGMA verification
One well know example is to be found in the article: "The
Turing Bombe: Was it Enough", Deavours, C.A. & Louis
Kruh, Cryptologia XIV(4), pp 331-349, 1990.
Additionally, you may download a 'demo' version of two
different Enigma variants from:
<http://www.eclipse.net/~dhamer/csg/index.html>
...or from the other CSG sites. Each simulation has been
rigorously checked against original ciphertext/decrypt
pairs from the Bletchley Park archives and also against
input/output from actual machines - and may confidently
be used as a yardstick if you wish to do so.
[EMAIL PROTECTED] wrote:
> I am looking for a few "authentic" ENIGMA intercepts/messages to test a
> simulator I have written.
DHH
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
David Hamer The Crypto Simulations Group
[EMAIL PROTECTED] http://www.eclipse.net/~dhamer
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: smartcard idea?
Date: Mon, 29 Nov 1999 16:04:58 GMT
>Daniel James wrote
>You can't use an IP address for this, as many dial-up internet services
>provide the user with a variable IP address, chosen from a pool of
available
>address at connection time. Such a user's IP address will vary from
>connection to connection.
I didn't go into detail on this. Recording the client IP address to
lock the session is all that would be required. If the client becomes
disconnected midstream they would be required to login again. The only
time an authorized user would get locked out is if their one time pad
gets out of sync with the server. This could only happen in the rare
case that an intruder was able to break a one time pad and access the
server before the authorized user. Keeping track of the last IP used
would help catch intruders. Static IP address may be more common if and
when IPV6 is implemented.
>I'm not at all sure that storing the authorization data on card is
feasible,
>either. If the cardholder communicates with many online vendors the
card will
>run out of space to store this stuff.
Current costs for flash memory are under $5 a Megabit. The amount of
data necessary to do a proper authorization is small, you really only
need Account number, name, pin data perhaps only a few hundred bytes per
account. To protect 100 bytes of account data you would need to store
200 additional bytes of random pad per account in flash memory between
logins. This is because one time pad systems are prone to plain text
attack, so you need to be able to combine several in a manner that
allows you to encrypt and exchange them. (I am not going into detail
about the algo here but I am sure it is well known). Keeping the
encryption transmission short reduces the time that an intruder would
have to steal any given one time pad. You could use pads and data of
only a few bytes in length using several new pads every second. The
bandwidth required to exchange many small pads is not much larger than
that to exchange one large one.
This system doesn't require an expensive processor since it is really
only providing a simple slide rule function to combine and remove OTP
from data. This makes it very inexpensive solution.
The major advantage for this system is that the server side creates all
of the onetime pads that will be used. This would mean that proper law
enforcement warrants could be easily carried out server side with the
permission of the owner. If this were not possible this system would
probably not be allowed since one time pads are unbreakable. This is a
simple system and obviously has been thought up before my question is
who owns the patent for this system?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: "Compressible Encryption" - Is it an oxymoron?
Date: Mon, 29 Nov 1999 16:20:47 GMT
[EMAIL PROTECTED] (Paul Hsieh) wrote, in part:
>[EMAIL PROTECTED] says...
>> Microsoft's "Compressible Encryption" isn't, apparently, but that
>> doesn't mean that compressible encryption is *impossible*. One could
>> first compress the input, encrypt it securely, then output it in a
>> compressible form. Except for steganography or armor, I can't imagine
>> why anyone would bother, but it exists as a _theoretical_ possibility.
>Uhh ... well I thought that the entropy of the message was kind of what
>you are trying to protect. In any event, doesn't it make more sense to
>compress first, then encrypt?
Of course it does.
I was just noting that one *could* perform secure "compressible
encryption"; the simplest way is to compress first, then encrypt, then
pad to allow compression to take place afterwards. Naturally, the
padding plus second compression is a waste of effort. Yet, this might
be useful so that storage requirements on a compressed volume would be
more predictable.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: NSA should do a cryptoanalysis of AES
Date: Mon, 29 Nov 1999 16:20:35 GMT
On Wed, 24 Nov 1999 19:33:57 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>> It is also possible that we can get the NSA information under FOIA,
>
>Not likely, since FOIA has an exemption for imformation classified
>in the interest of national security.
According to the various FOIA experts I've spoken with, there is some
precedent for denying that exemption because AES is a civilian
standard, and not a military one. I'm not optimistic, mind you, but
it's certainly worth trying.
Bruce
**********************************************************************
Bruce Schneier, Counterpane Internet Security, Inc. Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Elliptic Curve Public-Key Cryptography
Date: Mon, 29 Nov 1999 16:30:07 GMT
(This is reprinted from the November Crypto-Gram newsletter.)
In September of this year, nearly 200 people using 740 computers
managed to crack a message encrypted with 97-bit elliptic curve
cryptography. The process took 16,000 MIPS-years of computing, about
twice as much as used by the team that recently cracked a 512-bit RSA
encryption key. Certicom, the company who sponsored this challenge,
has offered this result as evidence that elliptic curve cryptography
is stronger than RSA.
Let's take a look at this claim a little more closely.
All public-key algorithms, whether for key exchange, encryption, or
digital signatures, are based on one of two problems: the factoring
problem or the discrete logarithm problem. (There are other
algorithms in academic circles, but they're too unwieldy to use in the
real world.) The security of RSA comes from the difficulty of
factoring large numbers. Strong RSA-based systems use 1024-bit
numbers, or even larger.
The security of most other public-key algorithms -- ElGamal, DSA, etc.
-- is based on the discrete logarithm problem. The two problems are
very similar, and all of the modern factoring algorithms can be used
to calculate discrete logarithms in the multiplicative group of a
finite field. To a rough approximation, factoring a number of a
certain size and calculating the discrete logarithm of numbers the
same size takes the same amount of work. This means that for a given
key size, RSA, ElGamal, DSA, etc. are approximately equally secure.
(This isn't strictly true, but it's a good enough approximation for
this essay.)
All of these algorithms require the use of something called an
"algebraic group." When public-key cryptography was invented, the
algorithms were all implemented in the simplest algebraic group: the
numbers modulo n. For example, RSA encryption is m^e mod n, and a
Diffie-Hellman public key is g^y mod n. As it turns out, any
algebraic group will do. Elliptic curves are simply another algebraic
group.
In elliptic curve cryptography, public keys and private keys are
defined as points along a mathematical object called an elliptic
curve. (Don't worry; it doesn't really matter what that means.)
Addition is an operation that combines two points and produces a third
point. The algorithms look the same, but the detailed math is very
different.
But if any algebraic group will do, why is anyone bothering with
elliptic curves? It turns out that for discrete-logarithm elliptic
curve algorithms, perhaps we can get by with smaller keys. (This is
not true for RSA, which is why you never see elliptic curve RSA
variants).
All of the fastest algorithms for calculating discrete logs -- the
number field sieve and the quadratic sieve -- make use of something
called index calculus and a property of the numbers mod n called
smoothness. In the elliptic curve group, there is no definition of
smoothness, and hence in order to break elliptic curve algorithms you
have to use older methods: Pollard's rho, for example. So we only
have to use keys long enough to be secure against these older, slower,
methods. Therefor, our keys can be shorter.
And they can be significantly shorter. In the wake of the recent
break, Certicom recommends 163-bit keys. Compare this to the
recommended key lengths for conventional discrete-logarithm
algorithms, which are at least 1024 bits.
Whether this recommendation makes sense depends on whether the faster
algorithms can ever be made to work with elliptic curves. The
question to ask is: "Is this lack of smoothness a fundamental
property of elliptic curves, or is it a hole in our knowledge about
elliptic curves?" Or, more generally: "Are elliptic curves
inherently harder to calculate discrete logs in, or will we eventually
figure out a way to do it as efficiently as we can in the numbers mod
n?"
If you believe the former, elliptic curves will always be more secure
-- for the same key lengths -- than the numbers mod n. If you believe
the latter, it's only a matter of time before they are broken.
Certicom very much wants you to believe the former. They say things
like: "Elliptic curves as algebraic/geometric entities have been
studied extensively for the past 150 years, and from these studies has
emerged a rich and deep theory." They conclude that because of this,
we can gain good confidence that new algorithmic advances won't be too
devastating.
To me, this is a lot of wishful thinking. It would be nice if we had
150 years of work on the cryptographic properties of elliptic curves.
But we don't; instead, we have 150 years of work on the properties of
elliptic curves that mathematicians care about, almost all of it only
incidentally touching on what cryptographers care about. Elliptic
curve cryptography was invented only in 1985, and has only been really
studied seriously for a few years.
Even today, most of the work on elliptic curves in the typical
university math department is pretty irrelevant to us cryptographers.
Sure, some of their results might occasionally help us understand the
strength of elliptic curve algorithms; but that's almost never been
the goal of the mathematicians' research studies. This is changing
now, but slowly.
Furthermore, work on efficient algorithms for elliptic curves is very
new. The whole notion of efficient algorithms didn't even appear until
about the 1960s or 1970s, and algorithmic number theory has only
become popular in the past two decades. It just wasn't relevant
before computers.
The real answer to the question is "we don't know." We don't know if
there are efficient ways to calculate discrete logarithms in elliptic
curve groups. We don't know if there is a definition of smoothness
that will allow us to apply the number field sieve to elliptic curves.
We don't know if, in the long run, you can use shorter keys with
elliptic curve algorithms.
In the short run, Certicom's recommendations are reasonable. Today,
we can't calculate discrete logs in elliptic curves as efficiently as
we can in the numbers mod n. Systems can use shorter keys with
elliptic curves. But in the long run, we don't know.
There are other differences to consider, too. Checking elliptic curve
signatures is still a big pain compared to checking RSA signatures.
And all users of an elliptic curve system have to share the same
curve. (If you don't do this, you lose most of the size benefits of
the elliptic curve keys.) This has security implications: it is
easier to break a key of a random user on a system than it is to break
a specific user's key. I'd like to see more analysis of this aspect
of elliptic curve systems.
My recommendation is that if you're working in a constrained
environment where longer keys just won't fit -- smart cards, some
cellphones or pagers, etc. -- consider elliptic curves. If the choice
is elliptic curves or no public-key algorithm at all, use elliptic
curves. If you don't have performance constraints, use RSA. If you
are concerned about security over the decades (almost no systems are),
use RSA.
Realize, though, that someday -- next year, in ten years, in a century
-- someone may figure out how to define smoothness, or something even
more useful, in elliptic curves. If that happens, you will have to
use the same key lengths as you would with conventional discrete
logarithm algorithms, and there will be no reason to ever use elliptic
curves.
Postscript: This same analysis applies to factoring (and the basic
discrete log problem). RSA Security, Inc. likes to talk about the
long mathematical history of the factoring problem, and how that gives
us confidence about the security of RSA. Yes, it has been studied for
centuries, but only recently has that study been even remotely related
to cryptography. Moreover, working on factoring hasn't been a
respectable area of study until very recently; before that, it was
considered an eccentric hobby. And efficient algorithms for factoring
have only been studied for the past couple of decades. We really have
no idea how hard factoring truly is.
The truth is that companies have a tendency to advertise their
products. Before making a decision about cryptographic algorithms,
customers should try to get a variety of independent opinions (from
parties not financially involved in the outcome of the decision) about
what they are buying.
News on the recent elliptic curve cracking effort:
http://www.computerworld.com/home/news.nsf/all/9909282ellip
http://www.certicom.com/press/99/sept2899.htm
An excellent mathematical introduction to elliptic curves:
http://www.certicom.com/ecc/enter/index.htm
An excellent discussion on comparative key lengths, including RSA and
elliptic curves: http://www.cryptosavvy.com
**********************************************************************
Bruce Schneier, Counterpane Internet Security, Inc. Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
