Cryptography-Digest Digest #723, Volume #13 Tue, 20 Feb 01 14:13:01 EST
Contents:
Re: New unbreakable code from Rabin? (Erwin Bolwidt)
Question about RSA excryption... (Taylor Francis)
Re: Question about RSA excryption... ("Jeff Moser")
Re: New unbreakable code from Rabin? (Steve Portly)
Re: A different concept for email encryption ?? (Paul Crowley)
Re: Password authentication with symmetric key exchange (Paul Crowley)
Re: Is there an algorithm to sequentially enumerate all transcendental numbers?
(Paul Crowley)
Re: CipherText patent still pending (Benjamin Goldberg)
Re: Super strong crypto (Benjamin Goldberg)
Re: Question about RSA excryption... (Benjamin Goldberg)
Re: Key expansion. ("Cristiano")
Re: MQV implementation (Mike Rosing)
Re: Question about RSA excryption... ([EMAIL PROTECTED])
Re: New unbreakable code from Rabin? (Mok-Kong Shen)
Anonymous web surfing? (Mok-Kong Shen)
Re: Password authentication with symmetric key exchange ("Henrick Hellstr�m")
Re: Key expansion. ("Cristiano")
Re: Fast DES-crypt question ("Didier F.")
----------------------------------------------------------------------------
From: Erwin Bolwidt <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: Tue, 20 Feb 2001 16:52:59 +0100
Hard wrote:
[...]
>
> You can fit a stack of common DVD disks (4GB - very conservative) 18
> of them to an inch in the space a human man would stand (six stacks at
> 72 inches each) and have eight hours worth of this stream.
>
> Now it is true that most individuals or groups of individuals could
> not keep up with this, but I'm *sure* the NSA could if it would mean
> being able to chew through a significant portion of encrypted traffic.
>
> The adversary does not appear to be helpless. But again, one of you
> is probably going to clue me in as to why Dr. Rabin's scheme is
> provably impossible to crack.
>
> BTW, thanks for the post, Mr. Schlafly.
I wonder why this method should be considered 'practical'. The NY Times
article talks about some source of the random data, like a satelite
broadcasting a random data stream at an extremely fast rate.
I don't really see how launching a satelite for your private
communications is more practical than sending a One-Time Pad on a set of
DVD's to another party. Well-funded terrorist groups, drug traffickers,
military organizations and other well-funded people could probably do
both with a reasonable guarantee of success.
A One-Time Pad could have been intercepted or copied while it was being
sent to the receiver, and a satelite can also be tampered with before
launch or perhaps even after launch if the adversary has enough
technology.
Using a 'random data source' that you don't control is even worse, since
you have no guarantee at all then that it is really random. The easiest
way to crack this scheme seems to me to make sure that the random data
source (like the satelite) is instead a good PRNG that can be repeated
by an attacker that knows the seed of the generator.
But that's just what I think after reading the NY Times article, I'd
hope that Rabin has something better.
Erwin
------------------------------
From: Taylor Francis <[EMAIL PROTECTED]>
Subject: Question about RSA excryption...
Date: Tue, 20 Feb 2001 10:53:14 -0600
Admittedly, I'm a beginner, but the RSA method, seems to produce the
same ciphertext for the same plaintext. Despite the prime numbers and
difficultites of factoring, doesn't this just produce a simple
substitution cipher?
How is this difficulty overcome?
------------------------------
From: "Jeff Moser" <[EMAIL PROTECTED]>
Subject: Re: Question about RSA excryption...
Date: Tue, 20 Feb 2001 12:06:57 -0500
> same ciphertext for the same plaintext. Despite the prime numbers and
> difficultites of factoring, doesn't this just produce a simple
> substitution cipher?
No,
p = 1234567891
q = 9876543211
N = pq = 12193263122374638001
e = 65537
d = 12191402595354763373
Encrypting the message "111222" yields: 4883125278959820367
Encrypting the message "222111" yields: 9586466168913275336
As you can see, the encrypted values are quite different. If you send the
same message over and over.. consider adding "salt" of random bits to the
front of a message.
Jeff
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: Tue, 20 Feb 2001 12:20:27 -0500
Erwin Bolwidt wrote:
[...]
>
>
>
> Using a 'random data source' that you don't control is even worse, since
> you have no guarantee at all then that it is really random. The easiest
> way to crack this scheme seems to me to make sure that the random data
> source (like the satelite) is instead a good PRNG that can be repeated
> by an attacker that knows the seed of the generator.
> But that's just what I think after reading the NY Times article, I'd
> hope that Rabin has something better.
It sounds as though you believe that the output of a good algorithmic PRNG
is less likely to be biased then the output of a hardware RNG. You are
probably correct in many cases. Some of the hardware RNGs I have seen
tested had ridiculous bias. With a hardware RNG design performance can vary
depending on individual component quality whereas an algorithm does not.
The PRNG I am currently using has at least a bias of about 1/65000.
Although it would take a fair amount of cipher text to exploit a bias this
small, it is still food for thought.
------------------------------
Subject: Re: A different concept for email encryption ??
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Tue, 20 Feb 2001 17:45:55 GMT
Paul Rubin <[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] (Rob Warnock) writes:
> > Let's see... Only 72 characters of what looks like a 26+10 = 36-element
> > alphabet, or ~372 bits. Even using the full 6-bit MIME BASE64 set, at *best*
> > that's only a 432-bits RSA key. In either case, way too small, sorry.
> >
> > But it was a cute idea...
>
> It's workable for elliptic curve public key algorithms (good security
> at 160 bits). But those email addresses are still impractical.
Under some circumstances PK-based identifiers make sense; see SPKI.
If you need them to be shorter, hash them and truncate all but, say,
the first 96 bits of the hash; you don't have to worry about birthday
attacks against the hash function, only second preimage attacks, which
are much more expensive.
With MIME-style 8-into-6 encoding, 96 bits is 16 characters:
[EMAIL PROTECTED]
which I think is pretty practical.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
Subject: Re: Password authentication with symmetric key exchange
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Tue, 20 Feb 2001 17:46:07 GMT
"Henrick Hellstr�m" <[EMAIL PROTECTED]> writes:
> > Yes, what you've done is much closer to the Right Thing than the
> > common behaviour you describe. But ultimately, snake oil is any
> > medicine that looks just like the real thing but doesn't work. I sigh
> > because you probably will get buyers, simply because so few buyers
> > have the faintest idea how to distinguish good cryptography from bad.
>
> You could say that about a lot things. There is a lot of unsecure "security"
> software using proprietary or badly implemented algorithms without any
> mention about it. We, on the other hand, clearly state the status of our
> products.
After reflection (and further correspondance in private email), I
agree that the term "snake oil" is too strong. Not all ineffective
medicine is snake oil. I still have a lot of misgivings about the way
you're approaching security consultancy and cipher design, but I don't
think anyone who gives a clear and unambiguous description of what
they're doing, and conducts themselves as civilly as you do without
overblown bragging, can be described as a snake oil vendor, and I
retract that description with apology.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
numbers?
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Tue, 20 Feb 2001 17:45:59 GMT
jtnews <[EMAIL PROTECTED]> writes:
> Is there an algorithm to sequentially enumerate
> all possible transcendental numbers?
No, but it is possible to sequentially enumerate all possible
non-transcendental numbers.
Well, of course many of them have an infinitely long decimal
expansion, so you'll have to choose an interesting output format, but
there are countably many polynomials with integer coefficients, and
each polynomial only has finitely many solutions (bounded by the
degree). So there are only countably many non-transfinites.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: CipherText patent still pending
Date: Tue, 20 Feb 2001 18:04:08 GMT
John Myre wrote:
[snip]
> > Although there were a number of problems with it, there was a paper
> > (less than a year ago, IIRC) which claimed you could solve some type
> > of NPC graph problem in O(N^6) time.
> <snip>
>
> If that claim is true, then the paper has the proof that
> P = NP, by definition. Therefore, I suspect the paper
> (or your recollection) is wrong.
Yes, I believe that the paper was intended to be a proof-by-construction
that P = NP. However, as I said, there were a number of problems with
it. People who tried to implement it said that in some cases, the
algorithm went into an infinite loop. Whether this was due to a flaw in
the idea, or in how it was written in the paper, I don't know. In a
number of places, the author used his own terms to refer to things for
which standard terminology exists. Also, I believe there was some
indication that the author's primary language was not English (the paper
was written in English).
If the paper/algorithm could be fixed...
--
A solution in hand is worth two in the book.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Tue, 20 Feb 2001 18:12:56 GMT
Mok-Kong Shen wrote:
>
> "Douglas A. Gwyn" wrote:
> >
> > Bryan Olson wrote:
> > > Is "natural lifetime" some property of a key?
> >
> > No, it's a property of the encryption method.
> > Surely you know? that real symmetric-key systems
> > require the key to be changed at intervals calculated
> > to resist cryptanalysis. That is a given; what I
> > am particularly interested in is, *assuming a correct
> > assessment of that property*, is there appreciable
> > actual weakness that could be exploited in practice,
> > caused by piggybacking the distribution of additional
> > key material on the existing channel? This is not an
> > academic exercise about unrealizable infinities; it's
> > an important cryptoengineering issue that is relevant
> > for certain kinds of communication systems. It would
> > be useful to definitely know the answer.
>
> With the reasonable assumption that the keys are at
> least as 'random' as the plaintext being processed,
> there is no reason to expect that a scheme with frequent
> key changes can be weaker than one employing a constant
> key, I believe.
This can be easily assured. Simply make a hash of all plaintexts and
ciphertexts which have been processed since the last key change, add
your random bits to the hash context, and use that as your new key.
If your random bits aren't as entropic as one would like, it's not a
horrible weakness, since we have all the entropy of the last key used
mixed in, too.
--
A solution in hand is worth two in the book.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Question about RSA excryption...
Date: Tue, 20 Feb 2001 18:32:09 GMT
Taylor Francis wrote:
>
> Admittedly, I'm a beginner, but the RSA method, seems to produce the
> same ciphertext for the same plaintext. Despite the prime numbers and
> difficultites of factoring, doesn't this just produce a simple
> substitution cipher?
>
> How is this difficulty overcome?
Tt's true that using pure RSA to encrypt two identical plaintexts
produces two identical ciphertexts. However, we generally do not use
pure RSA encryption for sending messages. We generate a random string
r, encrypt r using RSA, then encrypt our actual message using some block
cipher with r as the key. The recipient uses RSA to decrypt r, then the
block cipher and r to decrypt the rest of the message. Since r is long
and random, now two actual messages are ever sent using the same r, and
no two RSA encryptions produce the same ciphertext (since they always
have different plaintexts).
--
A solution in hand is worth two in the book.
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: Re: Key expansion.
Date: Tue, 20 Feb 2001 19:30:01 +0100
> > I have a password constituted from few characters and I want to expand
it
> > (to at least 128 bits) for use it like session (secret) key for an
algorithm
> > to symmetrical key (e.g. rijndael).
> > How could I do?
> Why expand it? Run it through a one way hash algorithm.
If I want to use 192 or 256 bits how would I do?
There are problems if I withdraw only 128 bits instead of 160 (I don't want
to use MD5)?
Cristiano
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: MQV implementation
Date: Tue, 20 Feb 2001 12:35:17 -0600
Alexander Schmitt wrote:
>
> > Use the NIST 233 curve. Change out the integer math from the book a
> "real"
> > integer math package. Use the inversion routine from chapter 11 instead
> of
> > from 4. Those changes should give you an order of magnitude improvement
> with
> > no problem.
>
> Now, I have tried to use the chapter 11 inverse routine instead of the
> chapter 4 routine.
> But it will be hangs on the program in an endless loop in the onb_inv
> routine. Any hints what could be gone wrong at my adaptation? I have used
> the routine nearly 1:1 from the book.
> With the normal ONB inversion routine it works.
>
> Are there any math libs which can be suggested for a fast implementation of
> the big integer maths?
Which compiler are you using? some people have had problems with signed
vs unsigned variables and the shift (>>) instruction. If it's a signed shift
the upper bits will all be set and it never clears (so you get an infinite loop).
Check out GMP, MIRACL or freelip for large integer routines. Peter Gutmann and
Wei Dai also have nice crypto libraries which include large integer math routines.
so lots to choose from!
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Question about RSA excryption...
Date: 20 Feb 2001 13:50:46 -0500
Taylor Francis <[EMAIL PROTECTED]> wrote:
> Admittedly, I'm a beginner, but the RSA method, seems to produce the
> same ciphertext for the same plaintext. Despite the prime numbers and
> difficultites of factoring, doesn't this just produce a simple
> substitution cipher?
Well, yes. If you use E=M^e mod n
where n is the modulus and e the public exponent then all you have to
do is write down a table for the simple substitution
of M-->substitutes to E.
Just write down the 2^1024 different entries in this table and you
have done it! Unfortunately, just trying to put one number on each atom
a billion done each second ... well, the universe will burn out
well before you even get started (that is a very, very large number).
To avoid traffic analysis (noting the same encrypted text and deciding
that whatever was sent last week - the same message is sent this week)
one actually encrypts a random number using RSA and encrypts the real
message using that variable (random) number as key using another cipher.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: Tue, 20 Feb 2001 19:54:19 +0100
John Savard wrote:
>
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>
> >There is a problem that needs to be clarified, I suppose.
> >How 'random' should the publicly visible stream of random
> >bits be? (Could they e.g. stem from PRNGs?)
>
> Only the case where they are really random, and not from a PRNG, would
> be considered in the proof. (Note that if they could come from a PRNG,
> they wouldn't need to be public! So one could use public really random
> bits, and XOR them with a PRNG for greater security - but since this
> scheme is already supposed to be 'perfect'...)
So one has a huge public (truly) random bit sequence
and it is the starting point of the segment which is
used to encrypt (xor with plaintext) a particular message
that is the shared secret of the communication partners.
Do I understand that correctly? But then, as someone
already commented, a very resourceful opponent could try
all starting points. Thus the security seems to rest on
the assumption that the opponent is unable practically to
perform this bruteforcing, I guess.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Anonymous web surfing?
Date: Tue, 20 Feb 2001 19:54:33 +0100
The German news magazine Spiegel in its recent issue
(19th Feb) reports that a software firm Safeweb sales a
product named Triangle Boy that enables one to surf on the
internet anonymously without leaving any traces. Does
anyone have experience with that software or can tell
the principles of its functioning? I can't yet imagine
that surfing from a fixed location couldn't be recorded
and analysed for finding out which sites (at least some
of them) one has visited. Thanks.
M. K. Shen
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: Password authentication with symmetric key exchange
Date: Tue, 20 Feb 2001 20:00:19 +0100
"Paul Crowley" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
> After reflection (and further correspondance in private email), I
> agree that the term "snake oil" is too strong. Not all ineffective
> medicine is snake oil.
No, of course not. But should I understand this as if you are implying that
Steak doesn't work (period), or just that you are mispleased with the
documentation and consequently don't know if it works or not?
> I still have a lot of misgivings about the way
> you're approaching security consultancy and cipher design, but I don't
> think anyone who gives a clear and unambiguous description of what
> they're doing, and conducts themselves as civilly as you do without
> overblown bragging, can be described as a snake oil vendor, and I
> retract that description with apology.
Thanks!
--
Henrick Hellstr�m
StreamSec HB
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: Re: Key expansion.
Date: Tue, 20 Feb 2001 19:54:03 +0100
> > I have a password constituted from few characters and I want to expand
it
> > (to at least 128 bits) for use it like session (secret) key for an
> algorithm
> > to symmetrical key (e.g. rijndael).
> > How could I do?
> You'll still only have "a few characters" of entropy, so brute force
sounds
> like a big problem here :)
You're right.
For set remedy to this type of attack I have thought to make it slower
possible: to use the elliptic curve.
I multiply the (public) base point for the inverse of my password modulo the
prime order of the base point: s=(pwd^-1 mod n)*P. s will be my actual
password. In this case the brute force attack will takes long time.
Could it be a valid system?
Cristiano
------------------------------
From: "Didier F." <[EMAIL PROTECTED]>
Subject: Re: Fast DES-crypt question
Date: Tue, 20 Feb 2001 19:05:41 GMT
Matthew Kwan <[EMAIL PROTECTED]> wrote in message
news:96i0fk$f6d$[EMAIL PROTECTED]...
> "Didier F." <[EMAIL PROTECTED]> writes:
>
> >Hi everyone,
> >Where can i get the latest - fastest version of crypt? I have some
> >source code based upon Eric Young's method, but that's from 1993.
> >So before i convert it to assembler, i would like to know if there
is
> >a newer version and where i can find it.
> >Also if someone wrote assebler code for crypt on a x86 (586 would
do)
> >where can i get it?
>
> >Thanks.
>
>
> Depends what you need - linear speed or throughput. Parallel
bitslice
> gets the most encryptions per second, but it's slower if you just
want
> to do one encryption.
>
> More details on bitslicing at http://www.darkside.com.au/bitslice,
> which includes a link to John the Ripper, a password cracker with
> optimised crypt code.
>
> Can't help with regular crypt code, however.
>
>
> mkwan
Sorry for the delayed reply, but i found what i needed from a link on
that page and it did give me a lot of reading.
Thanks for the link.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
