Forwarded: Request for Comments on primality testing

2007-01-24 Thread Steven M. Bellovin
From: Elaine Barker [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: Request for Comments on primality testing
Date: Tue, 23 Jan 2007 16:18:59 -0500
X-Mailer: QUALCOMM Windows Eudora Version 6.2.3.4

NIST received many comments when Draft FIPS 186-3 was posted for public
comment during the spring of 2006 (see Note above). Several comments
concerned the number of tests required for primality testing. In
response, NIST surveyed the latest literature available on this topic
and is providing alternatives for your consideration (see
http://csrc.nist.gov/CryptoToolkit/tkdigsigs.html). Please provide
comments to [EMAIL PROTECTED] by February 23rd, 2007, inserting
_Comments on FIPS 186-3 Primality Testing_ in the subject line. NIST is
particularly interested in comments relating to the security of the new
proposal versus the values currently used in Draft FIPS 186-3.

Elaine Barker
National Institute of Standards and Technology
100 Bureau Drive, Stop 8930
Gaithersburg, MD 20899-8930
301-975-2911

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: more on NIST hash competition

2007-01-24 Thread Ivan Krstić
Perry E. Metzger wrote:
 http://www.csrc.nist.gov/pki/HashWorkshop/index.html

I'm completely unfamiliar with the way NIST operates, but I've been
wondering for years why they haven't organized this competition already.
Do we have a list veteran who can shed some light on why it took them
this long? My curiosity demands to know.

-- 
Ivan Krstić [EMAIL PROTECTED] | GPG: 0x147C722D

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: analysis and implementation of LRW

2007-01-24 Thread Peter Gutmann
David Wagner [EMAIL PROTECTED]
Jim Hughes writes:
 The IEEE P1619 standard group has dropped LRW mode. It has a vulnerability
 that that are collisions that will divulge the mixing key which will reduce
 the mode to ECB.

Peter Gutmann asks:
 Is there any more information on this anywhere?  I haven't been able to find
 anything in the P1619 archives (or at least not under an obvious heading).

Alexander Klimov replies:
Probably http://grouper.ieee.org/groups/1619/email/msg00962.html

Huh.  Was that the reason?  I suspect there may have been more to it than
that.  

Actually there's a lot more to it than that, the original analysis was posted
by Quantum crypto guy Matt Ball (that's the drive manufacturer Quantum, not
quantum crypto) in late 2005:

  http://grouper.ieee.org/groups/1619/email/msg00558.html

with a followup in early 2006:

  http://grouper.ieee.org/groups/1619/email/msg00588.html

So it's not a case of google is your friend, it's 'knowing which magic
incantation to type into google to find what you're looking for' is your
friend.

Anyway, it's a pretty detailed analysis, well worth reading.

Peter.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Private Key Generation from Passwords/phrases

2007-01-24 Thread Bill Stewart



 With 4K possible salts, you'd need a
 very large password file to have more than a very few collisions,



Definition of very large can vary. (alliteration intended).[...]
UCSD has maybe 60,000 active users.  I think very large is very common
in the University environment.


Different decade, different threat models, different scales.
It was probably pretty rare to have more than a
couple of hundred users on a PDP-11,
but even at 60-70 you're in birthday-collision range with a 12-bit salt.
But a website could easily have a million users in its password files,
and some systems like Yahoo and Hotmail have hundreds of millions,
though obviously they're not all separate Unix userids.
Sometimes it matters if they get stolen, sometimes not -
I don't care if someone discovers that
my New York Times web password is password,
but I'd be really annoyed if my online banking password got cracked.

Salt is designed to address a couple of threats
- Pre-computing password dictionaries for attacking wimpy passwords
These become harder to do online, pushing a dictionary of
e.g. a million words to 4 billion, or ~32GB,
an unreasonably large database for ~1975 crackers,
though obviously you could use a manageable stack of tapes.
Today that fits in my iPod, though it's still impractical
to store an unsalted full-56-bit DES password dictionary.
- Detecting password collisions within systems, and between systems
Testing a known password against 4096 salts
took a long time at 0.5 MIPS, but it's faster at 4000 MHz.
Large systems will have internal collisions,
and the web makes it even more likely that somebody
will have logins on insecure systems
that might have the same password as their secure logins.
- Annoying then-hypothetical hardware DES crackers
That's still useful against some designs today,
though many designs, especially software,
are table-driven in ways that aren't annoyed much.

There are probably times that salt is useful, and that password files
using hashes are useful, but I'd think that if you're going to do that
today you might as well use 64 or preferably 128 bits of salt,
and of course you might want a hash other than MD5 or SHA-1.


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: analysis and implementation of LRW

2007-01-24 Thread Peter Gutmann
David Wagner [EMAIL PROTECTED] writes:

That is indeed an interesting requirement, and one that seems to legitimately
rule out a number of existing modes of operation for IEEE P1619.

From reading through the followup discussions, I think there's a strong desire
to not standardise something that's very brittle (think RC4).  For example in
a later followup the same person who pointed out the LRW issues thought that
one widely-deployed implementation, TrueCrypt, might have fallen into this
trap.  Luckily it didn't, but it was a sign that LRW may be just a bit too
brittle to safely deploy, particularly when the intended audience is embedded
systems and ASIC engineers and not cryptographers.  So the current
recommendation is to go to XTS (sometimes, confusingly, referred to as XEX),
which can be implemented using existing IP blocks developed for AES-GCM.
There are already several vendors shipping IP for AES-XTS.

Peter.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


OT: SSL certificate chain problems

2007-01-24 Thread Travis H.
Hi,

This is not really typical of the traffic on this list, hence the OT.

I send it because I think this is one of the few places where I'll
find some people with deep understanding of SSL certs.

Recently I had an issue where Google checkout would not accept an
SSL certificate because Apache didn't present the entire hierarchy,
just the site certificate itself.  The CA was Thawte.  What Google
said was that many browsers supply missing certs as needed, but
apparently their software did not.

The fix would seem to be easy; just put the right CA root cert in the
SSLCACertFile directive. or point to the directory with SSLCACertPath.
However, I've tried over and over with various root CA certs
downloaded from Thawte, and with one intermediate CA cert, and various
combinations thereof, but with no sucess.

The troubleshooting command line Google gave us was:

openssl s_client -connect www.domain.com:443 -showcerts  /dev/null

Hi,

This is not really typical of the traffic on this list, hence the OT.

I send it because I think this is one of the few places where I'll
find some people with deep understanding of SSL certs.

Recently I had an issue where Google checkout would not accept an
SSL certificate because Apache didn't present the entire hierarchy,
just the site certificate itself.  The CA was Thawte.  What Google
said was that many browsers supply missing certs as needed, but
apparently their software did not.

The fix would seem to be easy; just put the right CA root cert in the
SSLCACertFile directive. or point to the directory with SSLCACertPath.
However, I've tried over and over with various root CA certs
downloaded from Thawte, and with one intermediate CA cert, and various
combinations thereof, but with no sucess.

The troubleshooting command line Google gave us was:

openssl s_client -connect www.domain.com:443 -showcerts  /dev/null

Which shows:
depth=0 /C=US/ST=California/L=Los Angeles/O=Company, LLC/OU=COMPANY, 
LLC/CN=www.domain.com
verify error:num=20:unable to get local issuer certificate
verify return:1
depth=0 /C=US/ST=California/L=Los Angeles/O=Company, LLC/OU=COMPANY, 
LLC/CN=www.domain.com
verify error:num=27:certificate not trusted
verify return:1
depth=0 /C=US/ST=California/L=Los Angeles/O=Company, LLC/OU=COMPANY, 
LLC/CN=www.domain.com
verify error:num=21:unable to verify the first certificate
verify return:1
CONNECTED(0003)
---
Certificate chain
 0 s:/C=US/ST=California/L=Los Angeles/O=Company, LLC/OU=COMPANY, 
LLC/CN=www.domain.com
   i:/C=ZA/O=Thawte Consulting (Pty) Ltd./CN=Thawte SGC CA
-BEGIN CERTIFICATE-
[...]
-END CERTIFICATE-
---
Server certificate
subject=/C=US/ST=California/L=Los Angeles/O=Company, LLC/OU=COMPANY, 
LLC/CN=www.domain.com
issuer=/C=ZA/O=Thawte Consulting (Pty) Ltd./CN=Thawte SGC CA
---
No client certificate CA names sent
---
SSL handshake has read 1396 bytes and written 340 bytes
---
New, TLSv1/SSLv3, Cipher is DHE-RSA-AES256-SHA
Server public key is 1024 bit
Compression: NONE
Expansion: NONE
SSL-Session:
Protocol  : TLSv1
Cipher: DHE-RSA-AES256-SHA
Session-ID: 0DD3301C8B8AF7BD3706A991475B22580AA32FCF85A141D753E2F051A691ED86
Session-ID-ctx:
Master-Key: ...
Key-Arg   : None
Start Time: 1169584627
Timeout   : 300 (sec)
Verify return code: 21 (unable to verify the first certificate)
---
DONE

I can't seem to get that certificate chain to have any contents other
than what you see above, no matter what I do, and hence can't get rid
of the Verify return code: 21... does anyone have any advice on what
to do next?  URLs or references to other mailing lists welcome.
-- 
``Unthinking respect for authority is the greatest enemy of truth.''
-- Albert Einstein -- URL:http://www.subspacefield.org/~travis/


pgpOnPmmhdFCX.pgp
Description: PGP signature


Re: analysis and implementation of LRW

2007-01-24 Thread David Wagner
Thanks to everyone who responded with more information about IEEE
P1619.  Here are some of the additional links, with my reactions:

Andrea Pasquinucci points to:
 http://en.wikipedia.org/wiki/IEEE_P1619#LRW_issue

Ben Laurie points to:
 http://grouper.ieee.org/groups/1619/email/msg00558.html

Wikipedia points to two concerns with LRW: (1) LRW isn't secure if you use
it to encrypt part of the key; (2) something having to do with collisions.
For these reasons, Wikipedia says that IEEE P1619 is moving to XEX-AES.

I think (1) is a valid concern and a legitimate reason for IEEE P1619
to move to another mode.  XEX-AES is a great mode and this seems like a
solid move for IEEE P1619.  XEX-AES rests on solid foundations, and there
are good grounds for confidence in its design.  I would add one caveat,
though.  I am not aware of any proof that XEX-AES -- or any other mode,
for that matter -- is secure when used to encrypt its own key.  This is
not a flaw in XEX-AES, but rather a generic property of standard models
of security for symmetric-key encryption.  So I wouldn't be inclined to
get too comfortable with the idea of encrypting the key under itself.

I'm not 100% certain I follow what (2) is trying to get at, but it
sounds to me like a non-issue.  One interpretation of (2) is that the
concern is that if part of the key is chosen in a non-uniform way (say,
as a password), then LRW is insecure.  Of course, you should not use any
mode in that way, and I don't know of anyone who suggests otherwise.
The remedy is straightforward: crypto keys should be truly uniform.
This is standard advice that applies to all modes of operation.

Another possible interpretation of (2) is that if you use LRW to encrypt
close to 2^64 blocks of plaintext, and if you are using a 128-bit block
cipher, then you have a significant chance of a birthday collision,
which may leak partial information about the plaintext or key.  That's
absolutely true, though it is pretty much a standard feature of any mode
of operation based on 128-bit block ciphers.  Standard advice is to change
keys long before that happens, and that advice doesn't seem terribly
hard to follow.  (See, e.g., my prior post on this subject for evidence
that this doesn't seem likely to be a serious problem for current disk
encryption applications.  That's fortunate for narrow-block cryptography,
because otherwise none of the solutions would be acceptable.)  So it
sounds like concern (2) is a bit of a red herring, and LRW is still ok
for applications that won't be used to encrypt the key or any material
derived from the key.

The good news out of IEEE P1619 is that a number of excellent modes of
operation are coming out of that effort, and other applications should
be able to take advantage of the good work that P1619 is doing.  This is
good stuff.

Disclaimer: Of course, LRW is of personal interest to me, so I'm sure
I'm biased.  Form your own opinions accordingly.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Attacking the hash (WAS: Private Key Generation from Passwords/phrases)

2007-01-24 Thread Allen

Hi gang,

As an outsider, sort of, looking in I had an interesting thought 
about this. Since insider threats are the biggest problem, what 
vector could an insider use against password hashes to gain root 
password access?


The problem with Rainbow tables is that they would be too massive 
when the salt was 4096 to be practical unless you had the power 
of NSA or an equivalent supporting your efforts.


However, what about attacking the salt? How good is the PRNG for 
the salt? Is it at all predictable?


Here is one approach that might work. Keep entering the same 
password(s) and collecting the resultant hashes until you get 
several duplicates. Then analyze the results to see if there is a 
pattern to the repetition that would allow for a birthday attack 
against the salt that would allow an attack against the root 
password hash or other administrative rights password hashes that 
could be collected.


I suspect this would be somewhat difficult to code but once done 
almost the entire attack could be done off-line on a machine that 
uses the same password hash creation mechanism so you wouldn't 
trigger an IDS or similar audit process on the network under attack.


Given the long history of industrial espionage in the corporate 
world I'm sure that there are probably small teams working to 
collect information that have somewhat more resources than an 
individual or outsider group might have, making the effort 
required feasible.


Thoughts?

Best,

Allen

Leichter, Jerry wrote:

| ...One sometimes sees claims that increasing the salt size is important.
| That's very far from clear to me.  A collision in the salt between
| two entries in the password file lets you try each guess against two
| users' entries.  Since calculating the guess is the hard part,
| that's a savings for the attacker.  With 4K possible salts, you'd need a


[snipped]

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]