Cryptography-Digest Digest #412, Volume #10 Thu, 14 Oct 99 17:13:04 EDT
Contents:
Re: Factoring public keys attack? (Bob Silverman)
Re: Factoring public keys attack? (Bob Silverman)
He is back...new "improved" code ("Dan Fogelberg")
Re: speed and secure level (Jerry Coffin)
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column (Bob
Silverman)
Re: Perfect Shuffle Algorithm? (Kevin Buhr)
SafeGossip (Pete Chown)
Re: He is back...new "improved" code (Tim Tyler)
Re: need LFSR information (Scott Nelson)
Re: Using PGP as a source of random numbers (Kevin Buhr)
Re: Feistel ciphers (Anton Stiglic)
Re: where to put the trust (Tim Tyler)
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column ("Roger
Schlafly")
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column (David A
Molnar)
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
(DJohn37050)
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column (Mok-Kong
Shen)
Performance questions (Mok-Kong Shen)
Re: where to put the trust ([EMAIL PROTECTED])
Re: He is back...new "improved" code ("Dan Fogelberg")
----------------------------------------------------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Factoring public keys attack?
Date: Thu, 14 Oct 1999 15:32:40 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Jerry Coffin) wrote:
> In article <6A2K3.5359$[EMAIL PROTECTED]>, richard-
> [EMAIL PROTECTED] says...
> You can't really even count on that though: it's perfectly reasonable
> to use two factors that differ in length by a couple of bits or so,
Reasonable, yes, from a mathematical point of view. But various
STANDARDS mandate equal length primes. (ISO, IEEE, X9, PKCS)
--
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: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Factoring public keys attack?
Date: Thu, 14 Oct 1999 15:44:14 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Jerry Coffin) wrote:
> In article <19991013151854.334$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> says...
>
> [ ... ]
>
> > At most, wouldn't that only double the number of primes to examine?
> >
> > So 10^74 would become 2*10^74 or 10^74.3? And the combinations would
> > be 10^148.6?
>
> If you add one more bit in each direction, that should (unless I'm
> missing something) roughly double the number of possible factors.
You need to be careful with language here. You add one bit to one
prime, but substract one bit from the other.
If the modulus length is fixed at (say) 1024 bits, then
the number of moduli which are the product of 512-bit primes is
about [(sqrt(2) * 2^511)/log( sqrt(2) * 2^511)]^2 ~ 7.1e302
The number which are the product of a 511 and 513 bit prime is about
(sqrt(2)*2^510) * (sqrt(2) * 2^512)/log(...)log(...) ~ 5.1e302
You don't quite double the keyspace by allowing 511*513 in addition
to 512*512
But I ask:
Why does anyone think that 7.1e302 keys are not enough???
--
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: He is back...new "improved" code
Date: Thu, 14 Oct 1999 10:55:44 -0500
A couple of days ago I posted a question regarding a friend of mine who
challenged me to crack his code generation program. I was sure it was
elementary and it was...thanks to all who helped (especially JPeschel and
John Savard).
Well he is back and this time he is giving me even less ciphertext (225
bytes) and won't tell me anything about his "secret" algorithm. The
description of the plain text was "It is English and punctuation has been
ignored." Here is my preliminary analysis...
He gave it to me in a wierd format, instead of a binary file, it looked like
this:
94 98 51 83 11 33 91 94 15 27 92 51 27 42 93 65
I assumed those were byte values and converted them accordingly 65=A etc
-- length of file after conversion 225
-- byte values range from 11 - 98
-- 25 byte values in the range are not used
I ran Kappa, chi-sq, entropy, kasiski etc and can tell nothing from the
output :-). Not even sure what it was supposed to tell me. I tried vcrack
and it produced gibberish. Any ideas?
Thanks.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: speed and secure level
Date: Thu, 14 Oct 1999 09:56:54 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> Is there a encryption faster than DES with the same secure level?
Most of the AES finalists are at least believed to be substantially
more secure than DES (though nobody can prove it) and I believe all of
them are substantially faster than DES.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Thu, 14 Oct 1999 17:07:03 GMT
In article <[EMAIL PROTECTED]>,
"Brian Gladman" <[EMAIL PROTECTED]> wrote:
>
> The arguments for multiple AES winners cannot be dismissed so easily.
Yes it can. By one word. The word is:
interoperability.
By allowing multiple algorithms you are certain to guarantee that there
will be some users who can't talk to others.
There
> are at least three reasons for wanting more than one winner: (1) to
provide
> a degree of choice in dedicated, closed applications, (2) to provide a
> degree of diversity in open applications
Why does everyone use TCP/IP?
Repeat after me:
A Standard allows interoperability.
--
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: [EMAIL PROTECTED] (Kevin Buhr)
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: 14 Oct 1999 12:16:59 -0500
[EMAIL PROTECTED] (Herman Rubin) writes:
>
> In article <[EMAIL PROTECTED]>,
> Lynn Killingbeck <[EMAIL PROTECTED]> wrote:
[ . . . ]
> >I don't know your definition(s) of 'thoroughly' and 'instantly', but you
> >might find the comments in volume 2 of Knuth, starting with the
> >paragraph at the bottom of page 145 of the 3rd edition, of interest.
> >Partial quote "...cannot possibly generate more than..." Even with just
> >13 cards, the common random number generators based on 2^32 values can
> >not generate all shuffles.
>
> If you do it right, it can.
I think you're missing the point. As I understand it, when Knuth
refers to the "common random number generators based on 2^32 values",
he means an pseudo-RNG with a 32-bit seed and, therefore, an PRNG
capable of producing only 2^32 distinct pseudorandom sequences of
binary digits, once a seed has been chosen and set.
A card shuffling algorithm, no matter how complicated, is ultimately a
deterministic function from the set of random seeds to the set of card
orderings. Since 2^32 is around 4.29e9 while 13! is around 6.23e9, a
32-bit PRNG can, at best, produce only a fraction of the possible
shuffles of 13 cards, no matter how it is used.
I imagine you read the "based on 2^32 values" as meaning that the
generator happened to output 32 bits at a time.
Kevin <[EMAIL PROTECTED]>
------------------------------
From: Pete Chown <[EMAIL PROTECTED]>
Subject: SafeGossip
Date: Thu, 14 Oct 1999 17:31:48 GMT
I have just made SafeGossip available for download. SafeGossip is an
implementation of RFCs 2487 and 2595 which describe IMAP, POP and SMTP
over TLS/SSL. There is also an implementation of the FTP draft, and
there will shortly be one of the telnet draft. SafeGossip is a proxy
server, so you don't have to use any particular clients or servers to
make use of it. Redistribution terms are GPL and the home page is:
http://www.skygate.co.uk/safegossip/
Currently SafeGossip is at a late alpha stage. I think you could almost
use it in a production environment, but it is currently rather difficult
to set up, and some important functionality is missing such as logging.
I would be very interested in the opinions sci.crypt readers have about
SafeGossip, especially if any security issues come to mind.
======================================================================
phone +44 (0) 20 8542 7856, fax +44 (0) 20 8543 0176, post:
Skygate Technology Ltd, 8 Lombard Road, Wimbledon, London, SW19 3TZ
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: He is back...new "improved" code
Reply-To: [EMAIL PROTECTED]
Date: Thu, 14 Oct 1999 17:23:50 GMT
Dan Fogelberg <[EMAIL PROTECTED]> wrote:
: A couple of days ago I posted a question regarding a friend of mine who
: challenged me to crack his code generation program. I was sure it was
: elementary and it was... [...]
: Well he is back and this time he is giving me even less ciphertext (225
: bytes) and won't tell me anything about his "secret" algorithm. The
: description of the plain text was "It is English and punctuation has been
: ignored."
If you're evaluating security for his system, you should at the very
/least/ be able to persuade him to give you the algorithm.
When examining the strength of a cypher using cryptanalytic attacks, it's
a pretty standard assumption that the opponent has full access to
/everything/ *except* the key(s) - i.e. including the cyphermachine and
the plaintext of large volumes of output.
There are good reasons for these assumptions - as they frequently hold
in real life situations where cyphers are deployed.
>From the quality of your friend's efforts so far, you /may/ succeed in
cracking his challenge again - despite the piddling quantity of
information, the lack of any plaintext, complete ignorance about the
cypher machine, etc - but it all seems a trifle ridiculous ;-/
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
That's right... pretend it's a lollipop.
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: need LFSR information
Reply-To: [EMAIL PROTECTED]
Date: Thu, 14 Oct 1999 17:46:53 GMT
On Wed, 13 Oct 1999 10:35:10 -0700, Philip Koopman <[EMAIL PROTECTED]>
wrote:
>[EMAIL PROTECTED] wrote:
>
>>Where can i find a table of LFSR coefficients with maximum
>>length period.
>
>http://www.ices.cmu.edu/koopman/lfsr
>
I wrote a program to calculate maximal length LFSR's,
using "that chordic nonsense." After 32 bits, it
can only find "probable" polys. The list of Probable
polys include all maximal length LFSR's but might include
a few less-than maximal length polys as well.
Hardly the best way to find LFSR's, but it's faster than
straight out brute force, and the code's already done.
On my Pentium 166, it takes 23 seconds to find all 16 bit LFSR's.
For those interested, there's a copy (with source) on my ftp site
ftp://helsbreth.org/pub/helsbret/random
Or if you have trouble getting it,
you can email me for a copy.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (Kevin Buhr)
Subject: Re: Using PGP as a source of random numbers
Date: 14 Oct 1999 12:59:27 -0500
nosehat <[EMAIL PROTECTED]> writes:
>
> I'm making a OTP for communication between just two parties. So I need
> lots (several CDs) of random numbers. Could I get these by encrypting
> very large files with PGP's conventional encryption, then grabbing big
> chunks out of the middle of these files?
There's some irony in using PGP's convenient secret-key encryption
facility to produce a key for one of the most inconvenient and
cumbersome encryption schemes available.
I haven't seen anyone else make this obvious point: assuming you've
made the decision to use OTP because you feel it provides a slight
security advantage over a convential encryption algorithm, then it
makes no sense whatsoever to use a convential encryption algorithm,
which you don't trust to encrypt your data, as a source of data for
your OTP key.
In practice, OTP is generally less secure than conventional
algorithms, since while one can easily memorize a 128-bit IDEA key
using simple mnemonic devices, one generally can't memorize CDs worth
of OTP keys, and safeguarding the CDs can be problematic.
Am I missing something? Maybe you have some other reason for choosing
OTP? True, it's easy to implement, but if you're going to be shipping
CDs around anyway, why not just pass around copies of PGP?
Kevin <[EMAIL PROTECTED]>
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Feistel ciphers
Date: Thu, 14 Oct 1999 14:01:16 -0400
Adam Durana wrote:
> P1 and P2 are blocks from a plain text.
>
> P1 is split into two parts making L1, and R1.
> P2 is split also giving you L2, and R2.
> Key1 and Key2 are sub keys of Key.
>
> So encrypting P2 would be done by...
>
> L2 = R1
> R2 = L1 xor F(R1, Key2)
>
It's almost that. You start with just *one* block, P, wich
you split in two (L_0, R_0).
You then do as you say:
L_1 = R_0,
R_1 = L_0 xor F(R_0, K_1), where K_1 is as you said.
It is better to index the way I did, cause it's simpler,
L_1 and R_1 is now the result of computations of
round 1, using key K_1.
In the general case, the in the i th round you do:
L_i = R_(i-1),
R_i = L_(i-1) xor F(R_(i-1), K_1).
DES, for example, is a feistel ('par excellence'), having
16 rounds. Luby came up with a theorem for pseudo-random
permutations that is interesting. If you start out with random plaintexts,
then the function FP3 equivalent to doing 3 rounds of feistel is
is a pseudorandom permutation (using F: any one way function).
For 2 rounds, and 1 rounds, it's not a PRPG.
Anton
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: where to put the trust
Reply-To: [EMAIL PROTECTED]
Date: Thu, 14 Oct 1999 18:06:05 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: And BTW for all we know, we can test ciphers for fundamental flaws. We can
: assume [for example] that RC5 is relatively strong because many people have
: seen it, attacked it, and still the best attack is o(2^53).
You may have your wired crossed here:
o(2^53) means exactly the same as o(1).
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Bad RNG: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4.33e+67, 1, 1, 1, 1, 1...
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Thu, 14 Oct 1999 10:37:12 -0700
Brian Gladman <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> The arguments for multiple AES winners cannot be dismissed so easily.
There
> are at least three reasons for wanting more than one winner: (1) to
provide
> a degree of choice in dedicated, closed applications, (2) to provide a
> degree of diversity in open applications (a well established practice),
and
> (3) to meet requirements that benefit from the sequential application of
> different encryption algortithms (again an established practice).
You are just saying that one algorithm won't be good enough for
some reason. But what is the reason? Why is diversity/choice
good?
If NIST decides that algorithm A is best, but algorithm B is
also very good, then you want NIST to give its blessing to
people who disagree with NIST and prefer to use algorithm
B. This doesn't make any sense to me. If someone thinks
he is smarter than NIST, and NIST's analysis was wrong,
and he wants to use algorithm B, then he can do it no
matter what NIST says.
There is diversity in practice because there is disagreement
about what is best. If it turns out that the five finalists are all
more or less equally good, then there may never be a consensus
about what to use unless someone like NIST declares one to
be the standard. A lot of people like standards. Those who
don't can do whatever they want anyway.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: 14 Oct 1999 18:00:33 GMT
Derek Bell <[EMAIL PROTECTED]> wrote:
> What kind of research is there into combatting side-channel attacks?
> Granted, an adequate form of protection might be too un unwieldly for a smart
> card, but it might help in other contexts.
What I've seen is specialized depending on the kind of side-channel you
want to defend. So there are papers and such on tempest (see Ross
Anderson's Soft Tempest for example) and how to shield you equipment,
papers on timing attacks and how to get around them, and so on.
CRYPTO '99 had an interesting paper on defeating power analysis which
suggested that the computation be fixed such that revealing partial info
during the computation doesn't reveal enough to infer what the key is. The
authors were primarily concerned with power analysis attacks, but I think
their methods could apply to other "side channels" as well. as long as the
side channel isn't ALSO leaking the plaintext or something else evil.
Not sure what you'd do about failure analysis than the obvious (and
expensive) approach of investing in self-destructing hardware...
-David
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: 14 Oct 1999 19:05:44 GMT
Here is 2 slightly different scenarios;
A) NIST chooses ONE AES algorithm. A few years from now, it is discovered to
be somewhat weaker than at first thought. A few years after that, it is
discovered to be much weaker. Now what?
B) NIST chooses a small number of AES algorithms. For those systems without
much limitations, they do all the algs. For those systems that are
constrained, they choose one. Now an algorithm is found to be weaker than
thought. Everyone starts to migrate away from it to another of the AES algs.
The systems that use multiple algs, this is a matter of negoritiation of which
to use, etc.
For systems with one alg, they switch over over time.
I know that I MUCH prefer the possibilities of scenario B.
Don Johnson
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Thu, 14 Oct 1999 21:12:37 +0200
Anonymous wrote:
>
> Could you please explain what you mean by multiple algorithms or
ciphers. Are you refering to chaining or using different ciphers
on different blocks. How would that work? Would you use alternate
ciphers onm alternate blocks, or maybe a sequential set of ciphers
on alternate blocks...
>
> I am assuming that all the ciphers must use the same blovk size...
>
> Or would you randomely select a cipher from a set on each
consecutive block...
In my humble opinion it 'suffices' for the purpose of discussion of
the present thread to make the simplest assumptions about using
multiple algorithms, i.e. avoiding as many issues as possible that
could bring in unnecessary complications without essentially
contributing to the question of comparative merits of multiple
algorithms against single algorithm as such. Thus I would assume
(1) n cipers are selected, n = constant, (2) these are ordered,
(3) these have the same block size, (4) each block is sequentially
enciphered by the n ciphers, (5) there is no chaining.
As you have certainly noticed, each of the five items above
can be dropped/varied. Doing so would lead to results favouring
the use of multiple algorithms in my humble opinion.
M. K. Shen
==========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Performance questions
Date: Thu, 14 Oct 1999 21:12:31 +0200
A couple of questions of ignorance:
1. What is the performance comparison between hardware DES and 3DES?
2. I suppose one can implement DES with FPGA. What is the performance
comparison between FPGA and a specially designed hardware of DES?
Thank you in advance.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: where to put the trust
Date: Thu, 14 Oct 1999 19:10:04 GMT
In article <7u4k25$a6c$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Patrick Juola) wrote:
> In article <7u3nmd$u6e$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]>
wrote:
>>Again, you can check to see if a plane flies most of the time, or
>>whether a chip correctly computes most of the time. A cipher can
>>suffer a catastrophic failure of a global scale and we cannot really
>>test against that.
>
>A "catastrophic failure of a global scale?" I'm not sure I understand
>what you mean by this. Cryptographic systems don't fail all by
>themselves; it's a difficult task, requiring a fair amount of
>expertise and skill, to make a (properly used) cryptosystem fail.
If a standard cryptographic primitive fails, then all systems that use
it might be in deep trouble. Cryptography will be the basis of the
information society of the future and if, after 50 years, somebody
finds a way to break the AES with two known plaintexts and 1 second of
a PC, or if there is a mathematical breakthrough with problems we use
as the basis of public key cryptography, then, if unprepered, we would
probably have a sudden, mayor and global disruption in our hands.
Frankly nothing comparable can happen because of a bad automotive
design. I agree with you though, that it is possible to increase
security on the system level. One good idea is not to depend too much
on one primitive. This might be achieved, for example, by using
multiple symmetric ciphers in series, or multiple key exchange
algorithms in parallel.
>>(...) Now, it is not really
>>imaginable that something will happen in the next 50 years that will
>>make most bridges of the world crash down at the same time, or make
>>most plains stop flying, or most computer chips stop working.
>
>Obviously, you've never heard of the EMP bombs? Or, heck, the Y2K
>bug? Bridges, being a little bit lower tech, are more likely to
>withstand EMP bombing, but they're really sensitive to earthquakes.
They taught me about EMP in '75. Actually I know quite a bit about the
dangers of nuclear war (one of the reasons I moved to Costa Rica was to
prepare for such an event happening). That danger has not completely
disappeared and obviously the disruption caused by a global
thermonuclear war would be horrendous. The fact that we still live with
that latent danger does not mean we should not think about other
serious dangers that may lurk in the future use of cryptography.
Now, we who participate in this group can do very little about nuclear
war, or a big asteroid hitting the earth, or a virus out of the jungle
wiping out the human race. But we can educate less knowledgeable people
about the dangers of the technology we expound and try to guide its use
in a way that mitigates these dangers. There are practical ways to
prepare against the worst case scenario. After the Y2K error, we all
should agree that over-confidence is not a good idea.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Dan Fogelberg" <[EMAIL PROTECTED]>
Subject: Re: He is back...new "improved" code
Date: Thu, 14 Oct 1999 14:16:20 -0500
Let me put it this way. He is illogical, but beyond that, it is the joy of
proving him wrong. I wnet over it with him about the algorthm etc but he
says it is uncrackable because nobody will know what it is blah blah blah.
He is kind of in the Steganography mode, if he only knew what that was.
Tim Tyler <[EMAIL PROTECTED]> wrote in message
> From the quality of your friend's efforts so far, you /may/ succeed in
> cracking his challenge again - despite the piddling quantity of
> information, the lack of any plaintext, complete ignorance about the
> cypher machine, etc - but it all seems a trifle ridiculous ;-/
> --
------------------------------
** 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
******************************
