Cryptography-Digest Digest #434, Volume #10 Wed, 20 Oct 99 19:13:04 EDT
Contents:
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column ("Trevor
Jackson, III")
Re: Strengthening passwords against dictionary attacks ([EMAIL PROTECTED])
Re: detecting backdoor in prime generator (Tom St Denis)
Re: detecting backdoor in prime generator (Tom St Denis)
Re: detecting backdoor in prime generator (Tom St Denis)
Re: detecting backdoor in prime generator (Bob Silverman)
Re: How to go about decoding this? ("Dan Fogelberg")
Re: Amazon.com Crypto contest ("Dan Fogelberg")
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column ("Brian
Gladman")
Re: Bruce Schneier Proves That Secure Cryptography is Impossible
([EMAIL PROTECTED])
Re: detecting backdoor in prime generator (Anton Stiglic)
Re: Help! How can i decrypt text? ("Dan Fogelberg")
Re: Key Hidden Encryption (John Savard)
Re: detecting correlated pairs? ([EMAIL PROTECTED])
----------------------------------------------------------------------------
Date: Tue, 19 Oct 1999 23:38:11 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
DJohn37050 wrote:
> Jerry, you have a GREAT reason to have more than one AES winner, in a
> satellite, the cost of more than one is small, but the cost of another
> satellite is huge.
>
> I am certain there are other examples like this.
>
> And what is the US government supposed to do if their only pick breaks? Hurry
> up and certify another algorithm? Guess and pick a non-certified one? It is
> clear to me that for SOME scenarios, it is mandatory to have more than one AES
> winner.
Let's consider this in a bit more detail. What would happen if a suspicion were
cast over "the" single AES winner? Not a catastrophic break, but, say, a
non-constructive proof that a weakness of such-and-such work factor existed. We'd
want to activate a backup.
I just came from a Personal Protection course where, among other things, one
learns the rules of various forms of fighting. Rule #1 of a gunfight is "Have a
gun."
To activate a backup on must "have a backup". If NIST's contest results were
presented using a win/place/show ranking system we could use the "place" cipher as
a secondary or backup mechanism to be deployed only in mission-critical systems.
For truly serious systems, like NASA's man-rated systems criteria, we could
provided a tertiary cipher with the "show" entry.
This proposal suggests that NIST apply a _ranking_ to the ciphers rather than a
binary accept/reject result. Given a clear "winner" most of the
simplicity/cost/interoperability/standardization arguments disappear. We'd _have_
a winnner. But we'd also have alternates. Backups. Options in case of disaster
or better optimization for particular applications.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Strengthening passwords against dictionary attacks
Date: Wed, 20 Oct 1999 04:07:39 GMT
In article <[EMAIL PROTECTED]>,
Anton Stiglic <[EMAIL PROTECTED]> wrote:
...
> > be mounted against the file. Thus I still contend that SPEKE or
it's
> > variants do not cure the problem. SPEKE is great when two -people-
are
> > interacting however.
> >
>
> And what would be the key to decrypt the file?
> If the server encrypts "easy" with 3DES, how do you think you will
> do a dictionnary attack on this? You need the 3 56 bit keys?
> Of cours someone needs to start the program, but that person doesn't
> need to stay for the SPEKE protocol.
Maybe I'm not getting but I still don't think SPEKE will work. Even if
you use 3DES or any other strong algorithm, the mostly likely way to
protect the encrypted file is with a password. If the encrypted
password is stored anywhere on the computer it is subject to off line
dictionary attack. Are you suggesting that the person starting the
server side will type in 3 56 bit keys from memory?
The 3DES key is 3 64 bit keys BTW, the other are 8 bits are used for a
parity check or thrown away depending on the implemenation. See AC for
the details.
Also, in the example of a stand alone Win NT box, who would be starting
the SPEKE session? The OS itself? If that is the case then the
pasword must be on the computer somewhere.
--Matthew
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: detecting backdoor in prime generator
Date: Wed, 20 Oct 1999 11:45:33 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Jerry Coffin) wrote:
> I suspect what's really being suggested here is a level of
> predictability in the "random" numbers that are chosen as candidates
> to test for primality. If the group of candidates that will be
> generated is small, then the number of possible keys generated is
also
> small, and it becomes relatively easy to test among this limited set
> of possibilities.
>
> In this sort of situation, the primes themselves are basically
> irrelevant -- even if you could prove that all of them were "strong"
> primes, if the program could really only produce a few million
> different possible keys, there'd be no reason to deal with factoring
> the key at all; it'd be much simpler and quicker to exhaustively test
> against all the keys the program would produce. Of course,
generating
> keys is slow enough that most people will never attempt to generate
> millions of them to find that they start getting the same keys far
> sooner than they really should.
>
> Of course, all of the above is purely speculation about what people
> really meant. AFAIK, it doesn't apply to PGP, and obviously it's
> meaningless except with respect to a particular product, since it
> really has nothing to do with the encryption algorithms involved.
You know your posts comes up every 2 months or so right? Do you know
the prime number theorem? Suggesting that only a million primes exist
in say 512 bit numbers is very stupid.
I would suggest you read the source for PGP and stop wasting time
here. There is alt.security.pgp (or something like that) for your very
sort of nonce.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: detecting backdoor in prime generator
Date: Wed, 20 Oct 1999 11:48:21 GMT
In article <[EMAIL PROTECTED]>,
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> A backdoor for RSA is what interests me.
>
> More specificaly, there is a way to produce p and q, that are primes
> (and I beleive enven strong primes), such that n= pq is easy to factor
> by someone who doesn't know p, q, but knows the algorithm that
> generated p and q. It's based on an idea that if p and q are
identical
> for about half of the most significant bits, n=pq can trivialy be
> factored. With some modifications, you can pick p' = ap, and
> q' = bq, for some small constants a, b, such that p' and q' are primes
> (possibly strong primes), but don't have the common bits, such that
> n' = p'q' is easy to factor. It's something my thesis director
(Claude
> Crepeau) came up with (it's has been said that people know about it,
> but no articles have been published).
> I remember hearing about an article talking about a protocol that
> verifies that a generator of RSA modulus has no back door (if I
> remember correctly) I'd like to see if it works in this case.
May the buzzword be with you.
The number field sieve (for numbers over 130 digits) can factor
composites comprised of strong primes just as easily as joe blow
primes. Therefore your point there is moot. If p and q are random
then there is no correlation to exploit (other then the fact its a
composite) in pq.
I would suggest to read the source, post in alt.security.pgp and stop
wasting time here.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: detecting backdoor in prime generator
Date: Wed, 20 Oct 1999 11:50:31 GMT
In article <[EMAIL PROTECTED]>,
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
>
> > What theoretic? You make up a random number and test it for
> > primailty. If you are suggesting that one scheme may let composites
> > thru you can always use two algorithms. The chances of both of them
> > letting it thru is squared (if you maintain an equal probable
> > proportion between the two algorithms. I.e one scheme may need k
runs
> > to get 2^-k proof and the other 2^-4k ..etc)
>
> I'm not talking about a prime number generator, I'm talking about an
> RSA modulus generator with a back door.
>
The chances of being a backdoor in two random primes n=pq, are about
the same as your house suddenly picking up and flying to alaska.
RSA has been out for a long time now, it's been attacked by probably
every cryptographer out there. For properly constructed primes and
encryption/decryption exponents, RSA is pretty much very secure.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: detecting backdoor in prime generator
Date: Wed, 20 Oct 1999 13:52:08 GMT
In article <7ujhq2$p0m$[EMAIL PROTECTED]>,
"Vedat Hallac" <[EMAIL PROTECTED]> wrote:
> >generated p and q. It's based on an idea that if p and q are
identical
> >for about half of the most significant bits, n=pq can trivialy be
> >factored. With some modifications, you can pick p' = ap, and
> >q' = bq, for some small constants a, b, such that p' and q' are
primes
> >(possibly strong primes), but don't have the common bits, such that
> >n' = p'q' is easy to factor. It's something my thesis director
(Claude
> Sorry, but it seems I am missing something. How can p' and q' be
primes if
> they are a*p, and b*q? Are a and b real numbers?
The basic idea was correct, but the presentation was not rigorous.
Let p be a 512 bit prime chosen uniformly at random from the set of
512 bit primes.
Let q be another 512 bit prime *very* close to alpha * p where alpha
is a rational number which is the ratio of two relatively small
integers. e.g. q ~ 227/160 p or q ~ 140/163 p etc...
pq is then easily factored. This gives a backdoor for constructing
deliberately weak RSA keys.
Note however, that q was NOT randomly generated even though p was.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Dan Fogelberg" <[EMAIL PROTECTED]>
Subject: Re: How to go about decoding this?
Date: Wed, 20 Oct 1999 08:52:11 -0500
Where is this challenge located on Amazon???
JUzarek <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "CDJ" [EMAIL PROTECTED] wrote
>
> >I was sent the following cipher today, and am wondering what a good way
to
> >go about decoding is:
> >
> >038-097-34-64-242-335-51-377-183-168
> >038-097-34-64-380-330-115-289-273-189-56
> >068-486-42-23-87-434-10-468-151-345-150-494-376-415-426
> >038-549-53-15-1-193-121-29-109-66-28-160-106
> >047-111-70-99-24-21-25-12-53-22-56-8
> >
> >Though I'm curious about the actual cipher, I'm more interested to know
how
> >one goes about the decoding process.
> >
>
> That message is the amazon.com crypto challange. Don't think anyone is
going
> to do the all work so you to win the prize without raising a finger.
------------------------------
From: "Dan Fogelberg" <[EMAIL PROTECTED]>
Subject: Re: Amazon.com Crypto contest
Date: Wed, 20 Oct 1999 09:04:51 -0500
First 10 digits are book numbers. Beyond that I have not a clue
Eric Hambuch <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Trevor Jackson, III" wrote:
> >
> > Does anyone know why residents of Quebec are excluded?
> >
> > Bruce Schneier wrote:
> >
> > > FYI. I know nothing about the contest.
> > >
> > >
http://www.amazon.com/exec/obidos/subst/promotions/crypto/crypto-contest.htm
l/ref%3Dgw%5Fm%5Fce%5Fbo%5F4/002-8211936-5204257
>
> Does anyone have any idea how to solve it ?
>
> Eric
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Wed, 20 Oct 1999 15:18:14 +0100
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Brian Gladman wrote:
> >
> > I do not think it is unreasonable to seek an AES outcome that
accommodates
> > both these requirement domains.
>
> Very well said. Nothing in the world, not even AES, can fit all.
Thank you for your kind words.
> > But I would have thought that such constraints might be removed if
> > necessary. In the limit, if RC6 and MARS are not available as 2nd and
3rd
> > place AES algorithms, we then have Rijndael, Serpent and Twofish since
these
> > are not IPR constrained. Not necessarily a bad outcome.
>
> Has anybody made serious thought of the possibility of extracting
> some of the good ideas from each submitted AES candidate and doing
> some variations (to avoid patent problems) and putting in some
> proper ideas of one's own to arrive at a new design? I mean one
Although its quite possible that a better cipher might be constructed by
combining the techniques used in the AES algorithms in different ways, I am
rather uncertain that those who have the knowledge to do this would want to
repeat the process of algorithm development just undertaken for AES all over
again.
Moreover, as an outsider to the field of cipher design, I have the
impression that the problem here is not so much how to jumble things up but
rather that of knowing whether the result is secure. I hence suspect that
more work on the cryptanalysis of the five AES finalists in their current
form may be more effective in improving algorithm security than the
synthesis of new algorithms right now.
But on a related point, while a block cipher can be turned into a stream
cipher in a number of ways, will a better stream cipher result if one is
designed from scratch as a stream cipher? And, if the answer is yes, why is
there not an AES effort towards a standard stream cipher? Are they less
amenable to standardisation?
Brian Gladman
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Bruce Schneier Proves That Secure Cryptography is Impossible
Date: Wed, 20 Oct 1999 15:18:47 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Johnny Bravo) wrote:
> On Tue, 19 Oct 1999 16:26:53 GMT, [EMAIL PROTECTED] wrote:
>
>>Plain English is close to 1 bit entropy per character. I have
>>published a list of 4096 common and short English words (see
>>www.tecapro.com/makepass.html); if you randomly choose words from that
>>list you get a little over 2 bits of entropy per character and can
>>build shorter pass phrases.
>
>Or to be precise, you get 12 bits per word. Unless you end up with a
>valid english sentence, in which case you should select another
>passphrase.
Right. Each word in the list has 6 characters or less.
>>A related problem is: how do you produce a normal English phrase?
>>Picking one out of a book won't do because there are not 2^128 phrases
>>printed.
>
>It certainly would do. Even though there might not be 2^128 printed
>phrases, your attacker would have to use a dictionary of every book
>ever printed to begin a dictionary attack against you. The limitation
>here would be the storage requirement and the trouble of scanning
>every book ever printed into the database to begin with, and there is
>nothing that says that you can't change a word. What if your phrase
>was one of those book phrases with a random word at the beginning, or
>in the middle, or at the end. With a few minor changes, you
>can easily end up with 2^128 possible phrases. Even something as
>simple as a deliberate misspelling of a single word would render the
>entire dictionary useless.
I agree: picking a phrase from a book *and* modifying it can achieve
2^128 bits of entropy. But then it will be more difficult to memorize.
The trick is to find a way to produce entropy that is as easy to
memorize as possible. Ultimately, this is a question of human
psychology.
The whole matter may become moot shortly. Perhaps in a few years time,
when most people do understand the importance of security, hardware
producers will be motivated to include a fingerprint scanner (or a
voice analyzer) as standard input device in most computers (or even
home appliances) they build.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: detecting backdoor in prime generator
Date: Wed, 20 Oct 1999 11:55:29 -0400
Patrick Juola wrote:
> Mr. Stiglic is suggesting a broken generator that doesn't select
> "random" primes.
Yes! Thanks for understanding me! :)
Anton
------------------------------
From: "Dan Fogelberg" <[EMAIL PROTECTED]>
Subject: Re: Help! How can i decrypt text?
Date: Wed, 20 Oct 1999 15:02:38 -0500
If it is basic text then a simple frequency analysis will help. Beyond that
there are utilities that will help that are available. I believe one is
called CryptAid or maybe it was Crypt-Aid. Either that or post part of the
encrypted text here and someone may help you.
dfg <[EMAIL PROTECTED]> wrote in message
news:7ueni4$eau$[EMAIL PROTECTED]...
> My task is to decrypt encrypted text and find the encryption key.
>
> It's basic encryption character is only swaped with one other char.
> example:
> ABCDEF...
> BEFGJK....
> i need to find that key!
>
> plz help
>
>
>
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Key Hidden Encryption
Date: Wed, 20 Oct 1999 20:56:50 GMT
[EMAIL PROTECTED] (Chad Hurwitz) wrote, in part:
>I'm attempting to make an executable file that calls an encryption procedure
>with a "user unknown" key as input. The program will output an encrypted
>message, also unknown to the user. I.E. there is user A and user B and
>program C. I want program C (run by user A) to send a secure message to
>user B. program C and user B would know the Key and user A can not.
>Is it possible for a program to encrypt a message with out revealing the
>key? or How can you keep the key hidden enough within the source so a
>user would have a great deal of trouble trying to find out the key from
>looking at the dissasembled program?
>Is there a field label for this cryptology problem? (besides impossible :)
That is doable. Public-key cryptography methods, like RSA, let a user
know a public key, with which he can encrypt messages. But that key
doesn't decrypt any messages encrypted with it; the private key, known
only to the legitimate reciever, who created the public/private key
pair, is the only key that can be used to decrypt those messages.
Will that do what you want?
Or do you want to prevent the user from forging messages, not reading
them?
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.math
Subject: Re: detecting correlated pairs?
Date: Wed, 20 Oct 1999 21:17:23 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> [EMAIL PROTECTED] wrote:
> >
> > I'm testing weak pseudorandom functions with a couple thousand
output
> > digits. I'd like to know whether some pair of digits is strongly
> > correlated.
> >
> > Is there a way to do this that doesn't involve checking each of the
> > n(n-1)/2 pairs of digits individually?
> >
> > - Bob Jenkins
> >
> > Sent via Deja.com http://www.deja.com/
> > Before you buy.
>
> I'd be tempted to treat the numbers as evenly spaced data samples, and
> throw it data points into an FFT or similar transform to see if there
is
> some noticeable lower frequency component.
>
> By the way, I can't make any sense of your 'pair of digits is strongly
> correlated.' Do you perhaps you have something in mind like Figure 8
in
> Knuth's 'The Art of Computer Programming', vol. 2, section 3.3.4? Or,
> perhaps you are looking to detect actual repetition of a short-period
> generator (in which case, exercise 3.1-7b might be of interest to
you).
>
> Lynn Killingbeck
>
Looks like I didn't phrase that well.
An equivalent question: I have a type with thousands of attributes and I
want to know which attributes are correlated. Can this be done without
examining each pair of attributes over lots of instances of the type?
Or, a little more general, I have a block cipher. I want to test that
for every input bit, for every set of n output bit positions,
f(input, key) xor f(input xor bit, key)
is uniformly distributed in those n output bit positions. Is there a
way to test this without checking each subset of n output bits one at a
time?
I think the answer is no. I don't have a proof though. (The more
general problem is why I gave up on writing a block cipher a few years
back. Such a subset of output bit positions could be used to deduce the
key. Showing that the zillion subsets I'd tested didn't have the flaw
said nothing about the zillions of subsets I hadn't tested.)
For the special case of a type with attributes that are almost always
identical, there is a shortcut: for one or a few instances, hash the
attributes by value and ignore any pairs of attributes that don't have
the same value. Sorting works for attributes that are always almost
identical.
- Bob Jenkins
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
