Cryptography-Digest Digest #390, Volume #11 Wed, 22 Mar 00 15:13:01 EST
Contents:
Re: Card shuffling (John Myre)
Re: new Echelon article (Paul Koning)
Re: multiple encryption (Johnny Bravo)
Re: pgp key collision (Lutz Donnerhacke)
Re: More weapons for Mallory against Quantum Encryption (Mike Rosing)
Re: root mod a prime? (Mike Rosing)
Re: ecc equation (Mike Rosing)
Re: Hashing Algorithms. (basic newbie question) (John Myre)
NIST publishes AES3 papers (David Crick)
Re: Non-doublespending offline digital money? (Tony L. Svanstrom)
Re: 2048 Bit Encryption? (James Felling)
Hashes! (newbie question) ("Simon Johnson")
Re: Gray Code like (Mike Rosing)
Re: key distribution/management ("Lyalc")
Re: Factoring Large Numbers - I think I figured it out! ("Richard Anthony Hein")
----------------------------------------------------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Card shuffling
Date: Wed, 22 Mar 2000 10:49:59 -0700
Mok-Kong Shen wrote:
>
> John Myre wrote:
> >
> > Mok-Kong Shen wrote:
> >
> > > ... Can
> > > one give a function f(P) with range [0.0, 1.0] that characterizes
> > > in some reasonable way (i.e. not contrary to some common sense
> > > or intuition and hence be acceptable to the common people) the
> > > 'disordering' of P relative to S?
> >
> > Well of course. But what use would it be? Any number of facts
> > concerning random numbers and probability are counterintuitive
> > "to the common people". What would you use f(P) for?
>
> In that case please give one such f for n=4, for example, so that
> we can see whether is reasonable for most people.
Not my point. The way you design a function should be based on
its purpose. I imagine I could think up a function that would
convince some people that it measures disorder. I also think
that better mathematicians could think up better functions. I
remain convinced that such an exercise is pointless without
specifying more carefully everything the function is for.
> The second point
> of yours is certianly not true. Probability theory stems from study
> of gambling. The original concept of defining probability to be the
> frequency of occurences of events came from that and remains to be
> generally accepted by all people.
And average people don't lose money on sucker bets. In case this
is not clear, I mean to say that intuitive measures of randomness
are quite often wrong. This is the principle on which professional
gamblers, and gambling houses, make money: even when average
people know there is a trick, they don't figure out what it is.
The *concept* of probability may be generally accepted by all
people, but only a minority understand the details.
> As to use of f(P), one is what
> is clearly to be seen from the original post of mine concerning
> card playing. One can namely use it to test how well a person
> shuffles a deck with the purpose of introducing disorder into it.
"How well" in what sense? All I can see is "convincing to an
ordinary person that it is disordered, so that they trust that
it is fair".
If you intend to create an f(P) that *really* measures fairness,
Douglas Gwyn has already pointed out that this is impossible:
only the *process* is relevant. One *cannot tell* from a single
shuffle whether the process that generated it is fair.
>
> M. K. Shen
John M.
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: new Echelon article
Date: Wed, 22 Mar 2000 12:49:15 -0500
John Savard wrote:
>
> On 19 Mar 2000 06:31:13 -0800, [EMAIL PROTECTED]
> (David A. Wagner) wrote, in part:
>
> >It's a shame, given this mission, that the NSA has been such
> >a force for _in_security in, e.g., the design of the US cellular
> >telephony infrastructure.
>
> And, of course, cell phones are one of the very few areas in which one
> might be able to support the idea that something like the Clipper chip
> had a legitimate role. One has, at least, the precedent of laws that
> forbid all forms of encryption over the radio without special
> licensing, and the fact that a cell phone is itself a piece of
> (somewhat) expensive hardware, not, say, an existing net-connected PC
> that can encrypt quite well, thank you, without buying a special chip
> to do the job.
No, I think cell phones are a very nice argument *against* Clipper.
As for "laws that forbid ... encryption" -- what laws are those?
There are of course regulations that disallow encryption of ham
radio signals, but that doesn't carry over to other radio services.
> And the Clipper chip, for its flaws, would be considerably more secure
> than what we have now, even in digital cell phones.
Perhaps so. Note, though, that there wasn't any reason why
cellphones couldn't have used a competently designed cipher.
There were plenty around when the work was done, including
ciphers with small enough hardware requirements.
paul
------------------------------
From: Johnny Bravo <[EMAIL PROTECTED]>
Subject: Re: multiple encryption
Date: Wed, 22 Mar 2000 12:46:15 -0500
On 22 Mar 2000 13:35:37 GMT, [EMAIL PROTECTED] (Mark Wooding)
wrote:
>Johnny Bravo <[EMAIL PROTECTED]> wrote:
>
>> Without the meet in the middle attack, you can add ln(x) bits to the
>> encryption, where X is the number of different encryptions used, when
>> compared to a brute force attack. 40 different keys adds roughly 5
>> bits, 8 bits for 64 keys. It only ramps down from there, you are
>> better off using a stronger cipher if possible.
>
>I must be having a really bad day today, because this sounds like
>rubbish to me.
It's not you, it's me posting without any sleep. I was confusing the
original multiple encryption question with multiple hashing to extend a
smaller key into a larger keyspace. One paper I have talks directly about
extending a 40 bit key into a 56 bit DES keyspace, ugh. I still haven't
slept. My apologies for the above rubbish. :)
--
Best Wishes,
Johnny Bravo
"The most merciful thing in the world, I think, is the inability
of the human mind to correlate all it's contents." - HPL
------------------------------
From: [EMAIL PROTECTED] (Lutz Donnerhacke)
Subject: Re: pgp key collision
Date: 22 Mar 2000 16:20:18 GMT
* Paul Koning wrote:
>> Key generation tooks s few minutes for the first ones. The last example
>> required four hours computing to modify the fingerprint to the current date
>> and time. SHA-1 Fingerprints are as easy to fool.
>
>Say what?
KeyIDs MUST NOT be considered unique.
>I don't see what the pgp output you show has to do with the
>comment about "deadbeef" attacks. And last I heard, SHA-1
>fingerprints couldn't be fooled in reasonable time, that's
>after all what it means to be a cryptographic hash function.
I can do it. The output demonstrated it. No, it's not a fake:
=====BEGIN PGP PUBLIC KEY BLOCK=====
Version: 2.6.3in
mQEQAzaekxACzAEIAKCMRhza5p7f9eCzOCbeog9mmct7qJweWG5ICJK8SyPNcg1d
IDbcWOGKJGgmmhLGalPO3pYHDTmIf6g6j5NZuQ0YcKISEZPQ1IzmKC3N2sYRDbk7
R7NfKMyqGSGqoLj1hfyacBvZ3voI1lJWjvJ3xpkkcvtTOr00QE6gTX5SJpxnX3Z4
4P7D8dKwU0RqlvVde/u0AZaUjw2AoQ89l/0I0Bkg9IrwwjLs42sgOA5frpmkKrCp
xmYEiQgAVlid39q7dCQP+dUs5YkQRoz/m6pL0SGrEYoeO44kMG2Jz7a1uFoKGsZr
+OQFE2JvFGQwWFooeV9ivFYEHp3WaJbuyhmZAQEAHisIQXe0U1Jvb3QgQ0EgZGVz
IEluZGl2aWR1YWwgTmV0d29yayBlLlYuIDxpbi1jYUBpbmRpdmlkdWFsLm5ldD4g
KFNJR04gRVhQSVJFOjIwMDAtMTItMzEp
=U7OE
=====END PGP PUBLIC KEY BLOCK=====
>Can you exhibit a key that has a fingerprint (NOT key ID) ending
>in a particular 32 bit value? Say, "deadbeef"? If so, you'd have
>a significant discovery in hand...
Yep.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: More weapons for Mallory against Quantum Encryption
Date: Wed, 22 Mar 2000 12:18:42 -0600
[EMAIL PROTECTED] wrote:
> If I know what bits are going to be checked, I let them pass. The
> others I put myself in the middle, getting 50% of them. I will then
> know 75% of the bits!! (25% in the man-in-the-middle, 50% in the
> checking)
All bits are attempted to be checked. Since they are individual
photons,
you can't always get one.
> I didn't understand this! Which protocol?
The Mitre one, which started this thread (I may be spelling it wrong).
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: root mod a prime?
Date: Wed, 22 Mar 2000 12:30:51 -0600
Tom St Denis wrote:
> I found 1000 or so hits on google with the same string. Could you just
> please email [or send via usenet] the url of the websites you found?
I only got 2 today. Sheesh! This was a good one:
http://mosaic.math.tamu.edu/~Doug.Hensley/modsqrt.txt
> Thanks for the help. I hope to write some primitive ECC code [i.e find
> points, add them, double, multiply by scalars]... :)
Cool. Best way to learn :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: ecc equation
Date: Wed, 22 Mar 2000 12:26:35 -0600
Tom St Denis wrote:
> What is the diff between Trace(a) = 1, or 0?
The order of the curve. For some curves you get a large prime on Tr(a)
= 0,
and others you get a large prime on Tr(a) = 1. If Tr(a) = 0, embedding
points
on the curve is slightly faster. Not really important now that we've
got
1 GHz processors tho!
>
> For GF(p) what considerations should I make? What other types of
> polynomials exist? I think I saw
>
> y^2 + xy = x^3 + ax + b
No, that's not quite right. For GF(p) you want y^2 = x^3 + ax + b.
> 'a' must be negative for the real number set. Not for GF(p).
I see. Yeah, you don't get a bubble out in front, so it's hard to get
3 points on a real line (everything would be imaginary otherwise).
Hmmm.... I wonder what elliptic curves over the complex plain could
do for crypto :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Hashing Algorithms. (basic newbie question)
Date: Wed, 22 Mar 2000 11:26:52 -0700
>
> Why are there no hashing algorithms using Pseudo-Random number generators?
>
> Why not perform a simple little digest on the message and use it to seed a
> random number generator, then produce a random stream of 160bits?
>
> How secure is this approach?
There is nothing wrong with this concept. In the end, however, to
really get a good hash you have to use a good digest, not a "simple
little digest". We would like for a good hash function to have
various properties. One is that you shouldn't be able to figure out
the input (message) given only the output (hash). Your scheme might
do that, if the random number generator was strong.
As another poster pointed out, however, we also need to prevent
someone from computing a second message producing a hash, given
the first one. In this case, we have the first one, so we have
the result of the "simple little digest", which is input to the
random number generator. If the "simple little digest" is weak,
we can get a second message that produces the same digest, which
would (of course) produce the same "random" numbers.
This fails if the digest is short; indeed, anything less than the
hash size itself (160 bits in your example) means the hash is not as
strong as it looks. That is, even if the simple digest output (and
thus the random number seed) were 128 bits, and the digest were strong
(say, it is MD5), then we really don't have 160 bits of strength. We
have 128 bits of strength. This might be enough, but it is less than
the 160 bit output would imply. You can see that if the intermediate
were really short (say, 32 bits), that the final result is insecure.
John M.
P.S.
An interesting construction along these lines is Panama (by Craig
Clapp and Joan Daemen; the latter also helped create Rijndael, one
of the AES finalists). It is claimed to be usable as either a
stream cipher (essentially a random number generator) or as a
hash function. Two important factors in their approach are that
(1) the internal state is quite large, and (2) you iterate a mixing
function a lot in between input and output. The structure is simple,
in mathematical terms, but I don't think it can be called a "simple
little digest". Oh well.
------------------------------
From: David Crick <[EMAIL PROTECTED]>
Subject: NIST publishes AES3 papers
Date: Wed, 22 Mar 2000 18:38:22 +0000
http://csrc.nist.gov/encryption/aes/round2/conf3/aes3papers.html
------------------------------
From: [EMAIL PROTECTED] (Tony L. Svanstrom)
Subject: Re: Non-doublespending offline digital money?
Date: Wed, 22 Mar 2000 19:50:45 +0100
Niklas Frykholm <[EMAIL PROTECTED]> wrote:
> Proton Systems (www.protonworld.com) has developed a system along these
> lines. It is used by most banks and retail stores in Sweden (and in many
> other countries too), but customer response has been rather cold. After
> all, if it is used just like cash, if it can be stolen just like cash then
> what exactly is the advantage over cash?
True, but the that system uses traditional smartcards... I'm not saying
that they are easy to fool, but I feel that if a system can't be trusted
with 100'000 USD then why should I trust it with 100 USD...
BTW, I'm from Sweden to so I've got one of those cash-cards (as a part
of my VISA), but I don't use it. I put some money on it just to
demonstrate that reader-thing for an american company, but I never had
any use for it so I never initialized it on my new VISA-card.
/Tony
--
/\___/\ Who would you like to read your messages today? /\___/\
\_@ @_/ Protect your privacy: <http://www.pgpi.com/> \_@ @_/
--oOO-(_)-OOo---------------------------------------------oOO-(_)-OOo--
DSS: 0x9363F1DB, Fp: 6EA2 618F 6D21 91D3 2D82 78A6 647F F247 9363 F1DB
---ôôô---ôôô-----------------------------------------------ôôô---ôôô---
\O/ \O/ ©1999 <http://www.svanstrom.com/?ref=news> \O/ \O/
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: 2048 Bit Encryption?
Date: Wed, 22 Mar 2000 12:47:47 -0600
Anthony Stephen Szopa wrote:
> [EMAIL PROTECTED] wrote:
> >
> > Even with the NSA's new holographic computer technology?
> >
> > see -> http://www1.ekstrabladet.dk/VisArtikel.iasp?PageID=43390
> >
> > On Tue, 21 Mar 2000 21:41:55 -0800, Anthony Stephen Szopa
> > <[EMAIL PROTECTED]> wrote:
> >
> > >[EMAIL PROTECTED] wrote:
> > >>
> > >> Can the NSA break a 2048 bit encrypted email message? If they can,
> > >> is there anything out there that they can't break?
> > >
> > >I don't think they can break OAP-L3
> > >
> > >http://www.ciphile.com
>
> Let's start to address this point by asking this question:
>
> What is your wildest upper estimate as to how fast such a computer
> might be?
>
> Can it perform, maybe, 1E12 operations per second? Perhaps 1E24
> operations per second? How about 1E100 operations per second?
> Even 1E1000 operations per second?
>
> Even if this holographic computer can perform at 1E1000 operations
> per second (or faster), it will still be ineffective in cracking
> messages encrypted with OAP-L3 if the key were simply made long
> enough. And this key would not be difficult to process by a user
> of OAP-L3.
>
> OAP-L3 is not susceptible to factoring attacks.
Nor is any other stream cypher (the family of cyphers that OAP-L3 fals
into). OAP-L3 has never been subject to any formal reviewal process, and its
algorithim has not been subjected to a public examination to determine its
quality. There are many other stream cyphers of which this is true.
> If you want to
> crack OAP-L3 encrypted messages you must guess a key, process
> it to generate OTPs, then attempt to decrypt the message using
> these OTPs.
> This is quite a computationally intensive process
> for each and every possible key.
Assuming you are attacking OAP-L3 by brute force, as opposed to a more
rational attack such as cryptoanalisys. Calling the bitstream it generates
an "OTP" is a misnomer. A stream cypher may have an exceptionally long
period, but it can and does repeat, and even if it does not have repeating
values there will be characteristics of the stream that prevent it from
generating truly random data( an absolute necessity in an OTP -- calling a
stream cypher an OTP is like calling a rusted out chevy with no wheels up on
blocks with a cracked engine block and no seats a car -- they are related
entities, and may look similar to the untrained eye, but one does the job,
and the other does not. )
>
>
> If the OAP-L3 key length provides a security level of 1E100000
1E100000 what? bits? possible keys?
> and
> this holographic computer can perform 1E1000 operations per second
> then at a minimum it would take 1E99000 seconds to just generate all
> possible keys (not to mention all the time it would also take to
> generate the OTPs from each of these keys, etc.)
Anyone worth their salt won't generate all keys, they will attack the
algorithim. In addition just because there are X many possible keys doesn't
mean that the algorithim used in key generation will select randomly from
that space -- attacks based on the fact that most people want a
password\phrase that is shorter than the Declaration of Independence will
limit that to a much smaller amount in practice, and that is assuming that
such a phrase is of good quality.
>
>
> If you are a US or Canadian citizen currently residing in the US or
> Canada and your ISP is physically located in the US or Canada, you can
> get the OAP-L3 Shareware Version 4.1 via email. Go to
> http://www.ciphile.com and go to the Pricing and Ordering web page.
> Click on the blue underlined "email" anchor tag in the third paragraph.
> Send us this email.
>
> Or you can go to the web site and directly download the OAR-L3 random
> number generation software directly.
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Hashes! (newbie question)
Date: Wed, 22 Mar 2000 19:00:04 -0000
Could you use a PRNG for creating a hashing algorithm?
If the period of the PRNG was greater than 160-bits ( the length of the
digest i wish to generate ) then it should be just as secure as MD5 or
SHA-1, shouldn't it?
Thanxs
Simon Johnson
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Gray Code like
Date: Wed, 22 Mar 2000 13:11:27 -0600
[EMAIL PROTECTED] wrote:
>
> My excuses in advance if this is not a valid question in this group.
>
> I have encountered a form of encoding that's very similar to Gray Code,
> but isn't quite the same. In Gray Code only a single symbol at a single
> position may change when you move to an adjecent code word. What I'm
> looking at here is a list of code words where a new symbol is shifted in
> from the right when you move to the next code word and all codewords are
> unique.
>
> An example:
>
> 000
> 001
> 010
> 101
> 011
> 111
> 110
> 100
I don't like one step. 000, 001, 010, then 100. Why 101?
If you are alternating 0 or 1 to rotate in, then the next
step to 011 doesn't fit. An LFSR will give you a "random"
looking sequence and go thru all possible combinations.
(It's not random, just messed up.)
Patience, persistence, truth,
Dr. mike
------------------------------
From: "Lyalc" <[EMAIL PROTECTED]>
Subject: Re: key distribution/management
Date: Thu, 23 Mar 2000 06:23:28 +1100
Add to the list:
Key issuing methods
Key transport and storage methods
Key processing environments
and it get pretty well rounded out if applied to both symmetric and
assymetric keys
Doug Stell wrote in message <[EMAIL PROTECTED]>...
>On Tue, 21 Mar 2000 22:19:46 -0500, stanley trepetin
><[EMAIL PROTECTED]> wrote:
>
>>Hi, I'm a graduate student at MIT. I'm writing an in-depth paper on key
>>distribution and management issues with email applications. Can someone
>>give me advice (or references to papers or people) on the most
>>interesting questions in this space? Technical, economic, or public
>>policy questions would all be relevant.
>>
>>For example, I see considerable variety in current email encryption
>>implementations. Hushmail.com automatically exchanges keys necessary to
>>open up sent messages. Interosa.com forces you to contact your partner
>>to securely exchange keys before opening messages. Microvault.com allows
>>the sending of mail, and packages the keys with the note, to
>>automatically secure a reply without special software. (PGP does a
>>flavor of this as well). The GTE CyberTrust Accelerator Program installs
>>PKI on top of existing email desktop programs without the need for
>>proprietary email programs at all -- like adding a PKI layer on top of
>>the email system! There is also considerable incompatibility when email
>>clients use different encryption algorithms or different key lengths.
>>
>>I'd like to understand the variety of implementations which exist today
>>based on the issues/problems of key distribution/management. What are
>>the important questions to ask?
>
>The U.S. Government has a variety of key management systems, some
>centralized, some decentralized. However, it would be very difficult
>to obtain information on these systems, unless you actually work on
>them. NIST runs the FPKI program and it has lots of data available.
>
>You might collect some Certification Practices Statements, as they
>will address many of the issues in a manner unique to the
>infrastructure for which they were written.
>
>Some issues you might consider are the following:
>
>Key recovery (not totally a bad idea, it has its place)
>Revocation and compromise
> Efficiency, timeliness, recovery
> Subscriber & infrastructure compromise
>Infrastructure versus organizational structures
>Trust relationships within an infrastructure
>Trust relationships between infrastructures
>Interoperability
>Cross-certification between infrastructures
>Cross-certification within an infrastructure
>Reverse certification within an infrastructure
>Subscriber initial authentication
>Delegation
>Group or organization certfication
>Traceability within a group or organization
>Infrastructure disaster recovery
------------------------------
From: "Richard Anthony Hein" <[EMAIL PROTECTED]>
Subject: Re: Factoring Large Numbers - I think I figured it out!
Date: Wed, 22 Mar 2000 14:26:51 -0500
A method does not always have an algorithm that can be modeled. For
example, using DNA to factor is a method. However there is no way to
currently model that method using classical computers. Same thing applies
to quantum computation. The method in quantum computation utilizes the
method of superimposing both the on and off states of a bit, thus making a
qubit. Shor's algorithm would make use of this methodology. However, try
to use that method on a classical computer and you'll find that it's
impossible - at least it seems to be impossible.
I would like to comment one more time on the commercial value of a method
that can be used with today's technology:
When the idea of quantum computers was conceived, no one really thought that
it would be much more than a really fast computer. There really wasn't much
interest except by academics to try to actually MAKE one of these machines,
because it would take a long time, and lots of work, and money to build one,
and it might be impossible to do it.
However, when Shor's algorithm was introduced, people realized the potential
of a quantum computer and now they are working their collective butts off to
try to build one. They obviously believe there is commercial value now, all
because of Shor's algorithm. I think I made my point on this issue, at
least.
Richard Hein
"Bob Silverman" <[EMAIL PROTECTED]> wrote in message
news:8b8ilq$oh0$[EMAIL PROTECTED]...
> In article <MuOB4.5485$[EMAIL PROTECTED]>,
> "Richard Anthony Hein" <[EMAIL PROTECTED]> wrote:
> > It's not an algorithm Bob. It's a methodology. It would eventually
> become
> > a microchip specific to the task. Right now, it's like a vacuum tube
> (no,
> > it doesn't look like a vacuum tube - it's at that level of tech
>
> You really don't know what you are talking about. If it is a
> "method" implementable on a microchip then it is equivalent to some
> finite state machine and hence HAS A DESCRIPTION AS AN ALGORITHM.
>
> Everytime you open your mouth you look more like a crank.
>
> If you want to establish that you are not a total kook, then I suggest
> you factor the number I provided. (or one of the other RSA challenge
> numbers)
>
> I think it would also be useful if you went back to school to learn
> some mathematics and some computer science.
>
>
> --
> 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.
------------------------------
** 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
******************************
