Cryptography-Digest Digest #30, Volume #11 Tue, 1 Feb 00 12:13:01 EST
Contents:
Re: Pencil & paper cipher question ("Tony T. Warnock")
Re: Private-key RSA (David A Molnar)
Re: NIST, AES at RSA conference (Terry Ritter)
Re: Does the NSA have ALL Possible PGP keys? (James Felling)
Re: Does the NSA have ALL Possible PGP keys? ("John Galt")
Jaws Technologies' L5 Data Encryption Algorithm? ([EMAIL PROTECTED])
Re: Does the NSA have ALL Possible PGP keys? ("Dorsey Bolliard")
Re: What is the status of AES? (Helger Lipmaa)
Re: NIST, AES at RSA conference (Terry Ritter)
Re: How to password protect files on distribution CD (Alan J Rosenthal)
----------------------------------------------------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Pencil & paper cipher question
Date: Tue, 01 Feb 2000 07:36:27 -0700
Reply-To: [EMAIL PROTECTED]
Sorry guys.
It was Gillogly not Ritter.
Both do good work however.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Private-key RSA
Date: 1 Feb 2000 14:30:21 GMT
[EMAIL PROTECTED] wrote:
> Hi,
> Surely if you encrypt using RSA, but both the public-key and exponent
> are kept secret (i.e. not widely published), the cryptanalyst has a
> nigh on impossible job?
That's an interesting question. Given a message encrypted with RSA (or
some other cryptosystem), can you identify the public key used to
encrypt?
Note that this has implications beyond the security scenario you
are suggesting. In particular, consider an anonymous remailer with reply
blocks pointing to a public newsgroup. The remailer encrypts with the
final recipient's public key and posts the message. If an adversary can
determine what the public key of a given message is, he can monitor
when that key gets mail.
There was also a thread here a while back (started by Gilaad Mayan?) which
suggested that users could be "fingerprinted" by issuing them different
public keys.
If you can guess the exact plaintext with RSA, then you can certainly
_check_ whether a candidate public key is the key which encrypted this
message. Simply encrypt the plaintext and see if it matches the
ciphertext. You need to have a candidate public key in order to do this,
though, which you wouldn't have in your scenario.
In a randomized scheme, like RSA with optimal asymmetric encryption
padding, or ElGamal, it seems that you can't "guess the exact
plaintext" anymore. It would be neat to prove this somehow.
First we need a definition of what it means to be unable to "determine the
correct public key." A while back I was playing with something like this :
(informally stated, but can be made more formal if you want)
Let's say our adversary is given a ciphertext C, and the corresponding
plaintext P. He has two public keys K_1 and K_2. He knows that C is
the encryption of P under either K_1 or K_2 (he's managed to narrow
it down to these two somehow).
So he knows that C = K_1(P) OR C = K_2(P) .
Now he must tell which one.
We might say that a cryptosystem is "recipient-hiding" if the probability
of the adversary for successfully distinguishing K_1(P) from K_2(P) in
polynomial time is negligible. On the other hand, we might call a
cryptosystem "recipient-leaking" or "recipient-advertising" if the
adversary can _always_ distinguish K_1(P) from K_2(P) in polynomial time.
A recipient-hiding scheme seems to be something useful for anonymous
protocols in which encrypted messages are seen by an adversary. The
advantage of a recipient-leaking or recipient-advertising scheme might
be in offering an easy way to store and search encrypted messages,
depending on their destination.
I'm not sure if this has been considered before; I'm sure it has
somewhere. Any sightings, pointers, etc. appreciated.
I think RSA with OAEP is recipient-hiding, because it seems you would
need to guess the random value usd to pad in order to get the plaintext
fed to the RSA function. I don't know how to rule out other means of
determining the public key, though. I also think that Elgamal encryption
is recipient hiding, since it seems guessing the correct key would
also require guessing the correct random value used to encrypt.
These are just conjectures right now, though.
> Maybe even if he has a quantum computer (as there are an infinite
> number of Public(so-called)-keys)?
No, there is a finite number of public keys. About phi(n) of them,
actually. No idea how that helps/hurts a quantum computer
Thanks,
-David
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: NIST, AES at RSA conference
Date: Tue, 01 Feb 2000 15:24:21 GMT
On 31 Jan 2000 22:47:08 -0800, in
<875vhc$8eq$[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (David Wagner) wrote:
>In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>> But it is also correct that multiple ciphering is provably strong*er*
>> in the sense of not allowing known-plaintext and defined-plaintext
>> attacks on individual ciphers.
>
>BTW, I don't understand what you mean. There's a counterexample to the
>natural interpretation (multi-ciphering inherently prevents known- and
>chosen-plaintext attacks on the component ciphers), so maybe you mean
>something else.
>
>If we consider one round of DES, one of Blowfish, plus one of Serpent,
>the result is extremely insecure, and known-plaintext attacks on any of
>the rounds may be mounted using merely known texts for the whole
>construction -- so clearly in this degenerate case, multi-ciphering does
>not prevent such attacks.
Generally, unless we can solve all levels actually *simultaneously*,
one level must be solved first. Breaking some layer first is the
effort of a single "cipher," and the additional effort for the
remaining layers is *additional* effort beyond the original break.
But, since a single Feistel round does not change half the block, I'm
not sure that a single round of a Feistel cipher is a realistic model
of a "cipher." Using three levels of stream cipher probably would
also be a bad idea.
The real degenerate case is that of the unity transformation, which we
can apply n times and still have plaintext. Since the plaintext *is*
the ciphertext, having one gives us the other, although that would
hardly be called a "known-plaintext attack." But normally we try to
create ciphers which are quite unlikely to produce the unity
transformation.
Given reasonable ciphers, unless we can solve all three levels
actually *simultaneously*, the first layer being solved cannot be
attacked by known-plaintext, because either plaintext or ciphertext or
both are obscured by other cipher layers.
>> >Anyway, one would still need to support
>> >this position with evidence that diversity is more cost-effective than
>> >other means at our disposal.
>>
>> Hardly. What is needed is to show that the currently-accepted
>> approach -- having some sort of "contest" and then claiming some small
>> number of ciphers are secure enough to use -- is more risky in various
>> ways than using multiple ciphers.
>
>Well, I don't agree that this is enough.
>
>Let's suppose that, for the same performance cost, I can use either
>(1) Triple-DES, or (2) DES/FEAL/MMB. This scenario probably isn't too
>far off. Now, you seem to suggest that (1) is inherently preferable to
>(2). Why? This is the claim that needs evidence.
I do not so claim.
>Sure, using multiple ciphers probably adds security, at least in the
>trivial sense that it increases the total number of rounds, if in no
>other way -- but it's not at at clear to me that if you compare with
>an equivalent number of "rounds"/"complexity", the diversity-based
>construction will fare better than the homogenous one. It's plausible
>that it could go either way, but far from obvious to me which way
>it'll go.
But in Feistel ciphers, increased rounds *is* increased security.
Indeed, the power of attacks on Feistel ciphers is often *measured* in
the number of rounds which can be surpassed. Adding rounds is one of
the clearest measures of additional strength that one might mention.
That is hardly a "trivial sense"; instead, it is clear evidence of the
advantage.
Normally one would think that using different ciphers would be even
worse. Our experience in cryptanalysis is evidence that no single
technique (other than brute force, of course) breaks all ciphers. So
if we have different ciphers, we are likely to need different
techniques to break each layer. That seems likely to be even more
effective than having more rounds.
>> It is clear, for example, that in the contest between cryptographer
>> and opponent, it is far more cost-effective to make and use new
>> ciphers than it is for opposing cryptanalysts to keep up and break
>> those ciphers. Indeed, this is probably the only tool we have that
>> can strike at the resources of our unknown opponents.
>
>I have to disagree here, too.
>Let's assume that the attacker can spend far more resources on
>cryptanalysis than we can spend on design. Fair enough? WWII history,
>etc., seems to support this view, anyway.
>If you buy into that assumption, then it seems like the best thing
>we can do is pick something really simple -- ideally, so simple that
>it's *obvious* that there's nothing you can do to attack it, but in
>practice, simple enough that we can hope to mostly understand its
>properties within our resources -- rather than to use a bunch of
>half-understood ciphers, and leave the adversary the opportunity to
>find new properties we didn't expect in some of them.
Let me say first that you are not really disagreeing as much as you
are pontificating your point of view, and you have given little or no
basis for a belief which is not sustainable on its face.
I do assume that the attacker has far more resources.
As for having a cipher which is so simple that it is *obvious* that
there is no attack, that is yet another way of saying that we would
all like to have provable security. Yes, if we had such a thing we
would not worry about the massive resources of our opponents. But we
do *not* have such a thing, and in my view are quite unlikely to get
it. So *every* serious cipher we have *is* a "half-understood"
cipher; we have none of the other kind.
*Absent* provable security, we are left to use ciphers which may be
insecure, and if they are insecure, we do not expect to know. So we
*can* put all our eggs in that basket, but we *cannot* watch it.
If we forever use the same cipher, we do not cause our opponents any
increased investment. They can concentrate on one cipher. They can
use all our academic insights, provide some of their own, build a
single breaking machine, and so on. That is quite different from
having to perceive, acquire, analyze and break a continuing flow of
new ciphers. If we can force our opponents into spreading their
resources, we have reduced their ability to dig deep into any one
cipher. So if the original cipher is now deeper than they can dig, it
*is* made "stronger" by having many brothers.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Crossposted-To: comp.security.pgp,misc.survivalism
Subject: Re: Does the NSA have ALL Possible PGP keys?
Date: Tue, 01 Feb 2000 09:30:15 -0600
Anonymous wrote:
> There are a couple of interesting threads on talk.politics.crypto
> originating from a cryptographer with www.filesafety.com. They
> purport that the NSA has ALL POSSIBLE keys for PGP and that all PGP
> encrypted netmail has been "transparent" for at least two years to
> the NSA and certain elements of the military and FBI. The
> cryptographic basis for this alleged total compromise of PGP is
> discussed.
>
> This is a low-traffic NG and I should like to see serious analysis of
> these claims by those who are more technically qualified to discuss
> them.
>
> Take a look, and be sure to cross-post your comments here.
The only way the NSA could have "all possible PGP keys" is if the RNG
used is hobbled so as to produce only a subset of the truly huge number
of possible values. If the RNG is not hobbled there is not enough space
on earth to store the data, much less an efficient lookup algotithim to
acccess said data( The database would be of truly ridiculous size -- it
would take trilions of years for the entire computing power of the planet
to even just increment the pointers through the database) . Many people
have examined the PGP source code, and seen no evidence of such a defect
in the generator, thus it is my opinion that this poster is distributing
FUD, and not telling it like it is.
------------------------------
From: "John Galt" <[EMAIL PROTECTED]>
Crossposted-To: comp.security.pgp,misc.survivalism
Subject: Re: Does the NSA have ALL Possible PGP keys?
Date: Tue, 01 Feb 2000 15:32:50 GMT
"Anonymous" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> There are a couple of interesting threads on talk.politics.crypto
> originating from a cryptographer with www.filesafety.com. They
> purport that the NSA has ALL POSSIBLE keys for PGP and that all PGP
> encrypted netmail has been "transparent" for at least two years to
> the NSA and certain elements of the military and FBI. The
> cryptographic basis for this alleged total compromise of PGP is
> discussed.
>
This idiot (filesaftey) is peddling snake oil. He is trashing PGP in an
attempt to make his junk sell. Ignore the fuck head.
------------------------------
From: [EMAIL PROTECTED]
Subject: Jaws Technologies' L5 Data Encryption Algorithm?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 01 Feb 2000 16:10:45 GMT
Can anyone tell me whether or not the claims from Jaws Technologies
respecting their "Jaws Technologies' L5 Data Encryption Algorithm" are valid?
Has it been broken, and if so, what was the time required to perform the
break, and what equipment was used. Whenever I see claims for a proprietary
algorithm I tend to view them with a very jaundiced eye, and this is one of
those cases...
Thanks in advance,
Bob
R.S. (Bob) Heuman - Willowdale, ON, Canada
===================================================
<[EMAIL PROTECTED]> or <[EMAIL PROTECTED]>
Copyright retained.
My opinions - no one elses...
If this is illegal where you are, do not read it!
------------------------------
From: "Dorsey Bolliard" <[EMAIL PROTECTED]>
Crossposted-To: comp.security.pgp,misc.survivalism
Subject: Re: Does the NSA have ALL Possible PGP keys?
Date: Tue, 1 Feb 2000 11:42:50 -0500
Call me suspicious, but the more I hear encouraging people not to use PGP,
the more I suspect that the government has not been as successful as it
would like in breaking it.
My suspicion (admittedly without solid basis) is that the government
probably has people working day and night on the problem, and undoubtedly
has algorithms that CAN break encoded messages in finite time, but that the
time involved is still sufficiently long so as to make the routine intrusion
into every pgp message prohibitively costly. Of course, if there are
relatively few messages being encoded, they can make the assumption that
anyone using PGP must have something to hide and subject them to their
intrusive scrutiny. This is why I encourage everyone to use PGP to encode
every message, regardless of how inconsequential or banal. There are few
enough ways open to us to thwart government intrusion. We ought to avail
ourselves of every one.
db
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: What is the status of AES?
Date: Tue, 01 Feb 2000 19:02:33 +0200
Sandy Harris wrote:
> [posted and mailed]
>
> [EMAIL PROTECTED] (Ed Pugh) spake thus:
>
>
> >Also
> >is there a web site that details comparitive strengths and weaknesses
> >of the different ciphers being considered for the AES or one which
> >lists high-speed chip implementations?
>
> There's data at the Block Cipher Lounge, on pages reporting timing results
> from Brian Gladman and Helger Lipmaa. I've no URLs to hand.
http://home.cyber.ee/helger/aes
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: NIST, AES at RSA conference
Date: Tue, 01 Feb 2000 17:05:20 GMT
Unfortunately, I did not get the Savard article...
On 31 Jan 2000 22:57:13 -0800, in
<876049$8ff$[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (David Wagner) wrote:
>In article <[EMAIL PROTECTED]>,
>John Savard <[EMAIL PROTECTED]> wrote:
>> But the point he was trying to make, using "tripling" instead of a
>> detailed description of your multi-ciphering proposal, would be that
>>
>> if the mathematical condition of unprovability is _itself_ cause for
>> concern
This statement begins a logical "complex question" which cannot be
answered correctly as either "yes" or "no." The logical problem is
the word "concern," because there *is* *no* *one* concern.
Unprovable security is indeed the *fundamental* concern, in that *if*
we had provable security, that would solve the problem. But since we
do *not* have provable security, we necessarily have *other* concerns.
>> then no technique that does not yield a provably secure cipher removes
>> the cause for concern.
The correct answer is: "yes and no."
Yes, the *fundamental* issue of provable security exists no matter
what we do. But since we do not have provable security, we also have
*other* concerns.
Not having provable security does not mean that we cannot improve our
situation. In fact, not having provable security means that we *must*
concern ourselves with other things. And that is precisely what the
common wisdom has *not* done.
>> If the mathematical condition of unprovability is *not* cause for
>> concern by itself,
If we mean by concern "the most important goal," then of course the
unprovability of security has crushed that.
If we mean by concern "of serious interest," then we try to live with
the unprovability of security and institute measures to increase
whatever security we may have.
>> then what *other* arguments do you have for being out of step with
>> everyone else, by refusing to see the light and acknowledge that the
>> five AES finalists are all more secure than anyone could possibly
>> need?
The argument being improperly posed a complex question, thus admitting
no one answer, that is what you get:
It is not me who is primarily concerned with proven security.
Instead, I represent the side which has accepted that we can have no
such thing, and has moved on to see what can be done in this
unfortunate situation.
On the contrary, proven security is the issue dominating
*conventional* wisdom, as failed ad-hoc attacks are casually used as
arguments for the strength of the target cipher. That is clearly
improper logic and wrong. Yet I see the structure of AES as promoting
the delusion of a certification which cannot be supported by logic or
science. It is the conventional wisdom which says "what is wrong with
that?"
>Thank you, John. That is exactly the argument I was trying to get at,
>although as usual, you stated it better than I.
If that is really your argument, you need to re-think your logic.
It is not myself but the conventional wisdom which argues that failed
ad-hoc attacks can be extrapolated into proven or at least "good
enough" security. But that argument has no basis in logic or science.
My position is that while we cannot trust any cipher, we *can*
innovate techniques to improve the effective strength of possibly-weak
ciphers and reduce the risk of loss in case of cipher failure. We can
reduce the risk of single-point failure, protect ciphers from the
most-effective attacks, and cause our opponents to spread their finite
resources. The conventional wisdom says "why bother?" But that
answer implies that we have "good enough" security, which is something
cryptanalysis simply cannot assure.
>BTW, I think this discussion is interesting even outside of the context
>of the AES.
>
>> But there are responses. One of which might be to note that except for
>> MARS, we're dealing with ciphers using a single type of round.
>
>Yup.
>
>As an occasional would-be cryptanalyst, I can certainly agree that
>ciphers with multiple round-types often tend to be much more frustrating
>to find attacks on. But this cuts both ways: I can never quite convince
>myself whether this is because they inherently are more secure; or merely
>because complex ciphers are harder to analyze in general, and thus might
>be susceptible to serious attacks that are simply harder to find than
>would otherwise be the case.
That is of course the reason for using multiple independent ciphers
instead of simply adding "rounds" of different construction in the
same cipher. Independent ciphers can be tested independently under
various attacks. We do not use a cipher which succumbs, and if one of
our ciphers later does, we could use something else. Of course to be
able to change ciphers implies that we have multiple ciphers.
>I've certainly seen a number of real-life examples where "gratuitous"
>complexity made attacks harder to describe, but not at all harder to
>implement. This is the worst-case scenario for complex ciphers.
Yet the main goal of cryptanalysis is *not* the production of a single
"break any cipher" technique. Real cryptanalysis is targeted on
particular classes of cipher, and actual breaking generally requires
the details of a particular cipher.
If cryptanalysis would be more effective by adding a cipher to the
cipher being attacked, we would see that proposed as an attack
technique. We do not see that.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
Crossposted-To: alt.security.pgp,comp.security.unix
From: [EMAIL PROTECTED] (Alan J Rosenthal)
Subject: Re: How to password protect files on distribution CD
Date: 1 Feb 2000 16:01:56 GMT
[EMAIL PROTECTED] (Vernon Schryver) writes:
>Modern computers have more than enough unique bits to generate a globally
>unique signature that can be used instead of a value from a dongle.
But those are typically too volatile. E.g. replacing your hard disk will
alter a lot of the obvious "signatures".
Heck, you might replace your entire computer. With the dongle method,
you just move the dongle to the new computer. It's a closer match for the
protection the vendor is trying to implement than is the signature scheme.
Besides the fact that a vendor can sell you a CD and a dongle and just give
them to you, whereas in your scheme the user has to compute this signature and
send something back to the company which then has to send something out.
This is not to say that I approve of dongles, but I don't think the
licence-manager type schemes are better. (And I really wish I had heard
about those "I hate FlexLM" T-shirts in time to buy one.)
Incidentally, I really object to this use of "globally unique" (not your
term I know). If it is unique, it's just unique by chance. There is no
actual mechanism which causes the signatures to differ, unless they're
based on something which really is unique because of some allocation scheme
(such as a MAC address). (In which case it's simpler just to use that MAC
address.)
------------------------------
** 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
******************************
