Cryptography-Digest Digest #757, Volume #10 Fri, 17 Dec 99 18:13:01 EST
Contents:
Re: Enigma - theoretical question (Johnny Bravo)
Re: The 20 years periods did apply to 2 of the 3 patents. Why not for RSA ? (wtshaw)
Re: I was just thinking about a potential Cipher system... (Jim)
Re: Enigma - theoretical question (Jim)
Re: DES key safety (Scott Nelson)
SHA-1 hash (was Re: ARC4 cipher...) ("Andrej Madliak")
Re: More idiot "security problems" (Eric Lee Green)
Re: More idiot "security problems" (Eric Lee Green)
Re: First step in finding primes (Johnny Bravo)
Re: Are thermal diodes as RNG's secure (Bill Unruh)
Re: I was just thinking about a potential Cipher system... (SCOTT19U.ZIP_GUY)
Re: Reducing Key Sizes (Scott Nelson)
Re: Skytale? (UBCHI2)
Re: discrete logorithm reduction to factoring (Bill Unruh)
RSA, how to calculate big numbers ("Bart Peeters")
Re: discrete logorithm reduction to factoring (DJohn37050)
Re: Prime series instead (Re: Pi) (Matthew Montchalin)
Re: Breaking a cipher. ("Markus Eiber")
Re: RSA, how to calculate big numbers ("Markus Eiber")
Re: First step in finding primes (Eric Bach)
DES as pseudo random number generator ("Markus Eiber")
Re: discrete logorithm reduction to factoring (Jerry Coffin)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: Enigma - theoretical question
Date: Fri, 17 Dec 1999 15:10:48 GMT
On 17 Dec 1999 17:53:22 GMT, [EMAIL PROTECTED] (UBCHI2) wrote:
>If you are going to use the enigma software that you can download off the
>internet, you should rewire the rotors to a custom pattern. The wiring of the
>rotors can be an important secret.
Given that and the other conditions he used above, like not putting
three test letters repeated twice at the start of every message, and
not putting known plain text at the start of every message, it should
be pretty secure for short messages. Much more secure than the actual
Enigma as the Germans used it, since they broke all the above rules on
a regular basis.
Best Wishes,
Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Crossposted-To: alt.security.pgp
Subject: Re: The 20 years periods did apply to 2 of the 3 patents. Why not for RSA ?
Date: Fri, 17 Dec 1999 14:29:22 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> The 3 most known patents in the encryption area are :
>
> Name Number Filed Expires
> ----------------------------------------------------------------
> Diffie-Hellman 4,200,770 Sept. 6, 1977 Sept. 6, 1997
> Hellman-Merkle 4,218,582 Oct. 6, 1977 Oct. 6, 1997
> RSA 4,405,829 Dec. 14, 1977 Sept. 20, 2000
>
> The 20 years periods did apply to 2 of the 3 patents.
> Why it is not applicable to the last one ?
*Contributions*
--
Pbashgngvf znyrqvpgvf, synzzvf npevohf nqqvpgvf.
------------------------------
From: amadeus @DELETE_THIS.netcomuk.co.uk (Jim)
Subject: Re: I was just thinking about a potential Cipher system...
Date: Fri, 17 Dec 1999 20:22:58 GMT
Reply-To: Jim
On Thu, 16 Dec 1999 17:22:51 -0600, "Pipian" <[EMAIL PROTECTED]> wrote:
>I was thinking that a polymorphic cipher would be fairly secure (well it's
>the same as a one-time pad, I guess) when I came upon an idea...
>
>How secure would a cipher like this be?
>
>There would be 26 Enigma-like mechanisms, theoretically labeled A-Z...
>According to a certain keyword/words, you would switch between the machines
>containing the letters of the keyword... (Sounds similar to a Vigenere
>cipher on top of Enigma) This, I would think, would be fairly secure, but
>which of these methods for rotation of the scramblers would be most secure?
>Rotation of scramblers in all machines when one letter is encoded? Or
>rotation only on the machine the letter is encoded on?
Don't think you'd need to do this. The Enigma machine is secure enough
if you change the rotor wiring, plugboard, ringstelle and rotor start
positions with each message. Extremely easy to do with a PC!
------------------------------
From: amadeus @DELETE_THIS.netcomuk.co.uk (Jim)
Subject: Re: Enigma - theoretical question
Date: Fri, 17 Dec 1999 20:22:58 GMT
Reply-To: Jim
On 17 Dec 1999 17:53:22 GMT, [EMAIL PROTECTED] (UBCHI2) wrote:
>If you are going to use the enigma software that you can download off the
>internet, you should rewire the rotors to a custom pattern. The wiring of the
>rotors can be an important secret.
Yes. But surely with a computer you can change the rotor wirings
at intervals, or even with each message?
Don't forget to change the plugboard too!
It's secure enough for the stated purpose, if a bit cumbersome.
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: DES key safety
Reply-To: [EMAIL PROTECTED]
Date: Fri, 17 Dec 1999 20:27:23 GMT
On Fri, 17 Dec 1999 "Tom Pedersen" <[EMAIL PROTECTED]> wrote:
>Hi
>Is DES safe towards the key? I mean if you have the cleartext and the
>ciphertext could you derrive the key? Theory and practise is two different
>issues, so actually I'm asking two questions.
>
There are some theoretical attacks on DES that
involve large amounts of chosen plain-text that
are in some sense, easier than brute force, but
since DES keys can be recovered in less than 3 days
through brute force, it's not a very interesting
result anymore. (see http://www.eff.org/DESCracker/
for more details)
No, DES is not safe towards the key.
Brute force is sufficient to recover it.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: "Andrej Madliak" <[EMAIL PROTECTED]>
Subject: SHA-1 hash (was Re: ARC4 cipher...)
Date: Fri, 17 Dec 1999 21:12:24 +0100
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
Hi!
SHA-1 is one of the hashing algorithms PGP uses (the other one is
MD5). I think it's stated in the header because of the
(in-)compatibility with older clients - i think (but I'm nut sure)
that the 2.6.x versions can use only MD5-hash.
Andrej
r.e.s. wrote in message <83dud2$jk8$[EMAIL PROTECTED]>...
>"Andrej Madliak" <[EMAIL PROTECTED]> wrote ...
>: -----BEGIN PGP SIGNED MESSAGE-----
>: Hash: SHA1
>[...]
>: -----BEGIN PGP SIGNATURE-----
>: Version: PGPfreeware 6.5.2 for non-commercial use
><http://www.pgp.com> : Comment: Quis custodiet ipsos custodes?
>:
>: iQA/AwUBOFnpUoaZUlJQw2ggEQKzGQCfaQL39a/dK7wji1gsahd66YjMhYQAoNwf
>: FUkdYax6qXlYJZcv1Cpec0CV
>: =hUzp
>: -----END PGP SIGNATURE-----
>
>Sorry to butt in, and off-topic at that, but I have to ask...
>What is the significance of the "SHA1" at the top of your post?
>(I know SHA1 is a hashing algorithm, but if PGP uses SHA1, why
>mention it? Obviously I am not much acquainted with PGP ;-)
>
>--
>r.e.s.
>[EMAIL PROTECTED]
>
>
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 6.5.2 for non-commercial use <http://www.pgp.com>
Comment: Quis custodiet ipsos custodes?
iQA/AwUBOFqLF4aZUlJQw2ggEQKPzwCeKXWyXUNp2tCOaFAKx9RHO5ZHgaMAoN/E
xqgEwjEydgjSmcJMVOZSNbua
=P4OG
=====END PGP SIGNATURE=====
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: More idiot "security problems"
Date: Fri, 17 Dec 1999 13:46:25 -0700
JPeschel wrote:
> I think you're glamorizing your childhood code-cracking glory-days a tad. :-)
>
> Stepping through and editing snippets of code, or applying a patch, won't
> work if the the password checking algorithm, usually a one-way hash,
> is secure.
Agreed. That's what I use in a couple of different places in a next-generation
product that I designed for my employer, as well as public key algorithms. On
the other hand, we're not talking about one-way hashes for internal
authentication purposes. We're talking about an encrypted IMAP password. An
IMAP password is useless if stored as a one-way hash, because you must decrypt
it back to plain text in order to send it to the IMAP server, and by
definition you're not going to decrypt a one-way hash :-).
If a) the stuff is being stored somewhere, b) the stuff is being decrypted to
plain text, and c) you're not typing any kind of password or passphrase to
decrypt it, then obviously the password or passphrase is being generated
internal to the program. Meaning that you can thus reverse-engineer the
program and pull out the password or passphrase.
If Netscape could have stored the EMAIL password as a one-way hash, we
wouldn't be having this discussion. Alas, most POP3 servers out there require
a plain-text password to be transmitted to them, meaning that it just isn't
possible to store the EMAIL password as a one-way hash.
Finally: Applets run via a browser should not be able to get outside of their
"sandbox" and access your system's internals. If they do, that's an error in
the implementation of the "sandbox" or in the operating system itself, because
your system is then inherently compromisable. (Yes, I know about ActiveX, and
view it as an inherent security flaw -- I would filter out all ActiveX
controls at the firewall if I were a sensible network administrator). I have
that basic complaint about executable attachments too -- if my company were
not running Linux on the desktop, I would filter out executable attachments at
my EMAIL server, because they are inherently insecure.
Unfortunately, it appears that a) people are stupid and will run anything that
comes into their mailbox, and b) people care more about their own convenience
than about security, thus commercial OS vendors similarly care more about
convenience than about security. If there's any lesson to be gained from all
of this, it's that Netscape should never have stored that password ANYWHERE
but, rather, should have required the user to always type in his EMAIL
password. That's the same reason my brother never clicks the "Save Password"
box in the Windows Internet connection widget but, rather, always types in the
password by hand -- because this way, even if one of his kids breaks into his
computer, they can't connect to the Internet and post spam under his name :-).
But then, my brother has enough brains so that his head doesn't echo...
-Eric Lee Green [EMAIL PROTECTED]
http://members.tripod.com/e_l_green
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: More idiot "security problems"
Date: Fri, 17 Dec 1999 13:51:27 -0700
Xcott Craver wrote:
> >And I'm not a so-called "security expert". No wonder I have nothing but
> >disdain for the "security expert" who discovered this "security problem".
>
> That makes you the third person I've seen on this group going to
> the trouble to use double-quotes and so-calleds whenever referring
> to known security experts.
There are security experts who are worthy of the name. I would hire Bruce
Schneir or David Wagner in a moment, for example (and may end up doing so, my
network stuff DOES need an audit to make sure I didn't make any stupid
mistakes).
My complaint is about "security experts" who come out with rash statements
intended to scare people for purposes of publicizing their "security firm"
(usually one-man operations operating out of rented offices in Podunk,
Kansas). The NSA Key scare was one such, and this Netscape Key thing is yet
another one. That's how I can tell the difference between a security expert
and a "security expert" -- a REAL security expert doesn't need to scare people
with rash statements in order to drum up business.
-- Eric Lee Green [EMAIL PROTECTED]
http://members.tripod.com/e_l_green
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: First step in finding primes
Date: Fri, 17 Dec 1999 16:09:47 GMT
On Fri, 17 Dec 1999 17:11:31 GMT, Tom St Denis <[EMAIL PROTECTED]>
wrote:
>In AC he suggests dividing by primes upto 256 which would give you
>1.12/lnx or ~79.8% of all odd composites.
Checking for the first 54 primes (those less than 256), eliminates
79.93% of all odd composites. Checking the first 1028 primes (those
less than 8192), eliminates 87.55% of all odd composites.
As you can see the law of diminishing returns sets in, you do 1900%
as much work for an ~9% increase in results. You have to balance the
work required for further testing against the work required to check
against large numbers of primes. Depending on how much computation
your primality checking uses, you might be better off doing many more
checks vs primes than the 256 figure, it all depends on your program.
Best Wishes,
Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Are thermal diodes as RNG's secure
Date: 17 Dec 1999 21:22:25 GMT
In <[EMAIL PROTECTED]> Tim Tyler <[EMAIL PROTECTED]> writes:
>The comparison with pseudo-random number generators still seems
>appropriate to me:
>PRNG output has a lower entropy than a real random stream. The entropy of
>the stream is only that of the original seed.
>Similarly, hashes based on pseudo-random functions - rather than genuinely
>random ones - will not do as good a job of concentrating the entropy as
>they could do.
>The original data is patterned (that's why we're using a hash in the
>first place - to introduce more randomness).
No, it is NOT why we use the hash. We use the hash to take say 150 bits
of input which however only have 128 bits of entropy to produce an
output of 128 bits which still has that same 128 bits of entropy. The
hash function is NOT assumed to introduce any randomness whatsoever. It
is just assumed to not destroy entropy in th einput. Now, hashes
obviously do destroy entropy as well. A 150 bit input with 150 bits of
entropy will produce a 128 bits of output with 128 bits entropy.
A has is a many to one function. The question is whether the many to one
mapping has any correlation with the regularities in the data. For
example one could imagine a hash which took 256 bits of input with 128
bits of entropy and produced that same output for all of th epossible
inputs. This would be perfect correlation between the input and the
hash. However the probability that say MD5 is correlated with the biases
in the output of a zener diode is negligible.
>The hash itself is also patterened (as it's made up of a relatively small
>function, rather than a huge random LUT). If the types of pattern happen
>to be anything other than completely orthogonal, that might cause
>problems for the ability of the hash to concentrate the entropy from the
>message.
Yes, but are those "patterns" of any relation to the "patterns" in the
data being distilled? (Ie, is the hash a valid theory for the biases in
the noise source.)
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: I was just thinking about a potential Cipher system...
Date: Fri, 17 Dec 1999 22:13:14 GMT
In article <[EMAIL PROTECTED]>, Jim wrote:
>On Thu, 16 Dec 1999 17:22:51 -0600, "Pipian" <[EMAIL PROTECTED]> wrote:
>
>>I was thinking that a polymorphic cipher would be fairly secure (well it's
>>the same as a one-time pad, I guess) when I came upon an idea...
>>
>>How secure would a cipher like this be?
>>
>>There would be 26 Enigma-like mechanisms, theoretically labeled A-Z...
>>According to a certain keyword/words, you would switch between the machines
>>containing the letters of the keyword... (Sounds similar to a Vigenere
>>cipher on top of Enigma) This, I would think, would be fairly secure, but
>>which of these methods for rotation of the scramblers would be most secure?
>>Rotation of scramblers in all machines when one letter is encoded? Or
>>rotation only on the machine the letter is encoded on?
>
>Don't think you'd need to do this. The Enigma machine is secure enough
>if you change the rotor wiring, plugboard, ringstelle and rotor start
>positions with each message. Extremely easy to do with a PC!
>
Why go to the trouble to use an Enigma type of machine when its just as
easy to code up somthing like GVA.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Reducing Key Sizes
Reply-To: [EMAIL PROTECTED]
Date: Fri, 17 Dec 1999 21:42:45 GMT
On Fri, 17 Dec 1999 "Adam Pridmore" <[EMAIL PROTECTED]> wrote:
>Does anyone know if there are any security issues in symmetric algorithms if
>the key size is reduced (eg making the last x bits of the key constant),
>other than reducing the number of available keys. (ie Brute force is still
>the easiest way to break it).
>
>Could this be very dependant on the algorithm chosen?
>
Yes, and Yes.
Most modern ciphers don't have much problem with it.
(other than the obvious problem that a smaller key size
is easier to brute force.) I.e. there's no (publicly)
known way to break IDEA with the top 64 bits being set
to 0 that's easier than brute force.
However, many other, less practical attacks do become
possible with reduced key size. For example, it's
usually not reasonable to pre-calculate all possible
encryptions of a particular block, but if the key-size
is small enough, then it might be. So 32 bit DES is
not only crackable in a under an hour with a modern PC,
it's also possible to do a chosen cipher-text attack
on it that will crack it in a few milli-seconds.
It's also conceivable with a bad algorithm that reducing
the key size will have a disproportionate result.
3DES normally has about 112 bits of "strength,"
(2/3 of 168), but reducing 168 bit 3DES to 64 bit keys
_might_ result in a cipher with only 33 bits of strength.
It depends on which bits you leave out.
As a general rule, it's better to duplicate a
short key into the unused bits, rather than set
them to 0. Or use something like SHA1 or nbitCRC
( http://www.helsbreth.org/random/nbitcrc.html )
to convert the user key space to the cipher key space.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (UBCHI2)
Subject: Re: Skytale?
Date: 17 Dec 1999 21:44:39 GMT
Seems that if you had a water inflated bladder of a rod's length, you would
have universal cracking device for this encryption!!! Just add water until the
bladder rod expands to a width that reveals the plaintext.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Crossposted-To: comp.theory
Subject: Re: discrete logorithm reduction to factoring
Date: 17 Dec 1999 22:00:38 GMT
In <8373h1$7vb$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>Is it true that discrete log reduces to factoring ?
Yes. THis is the whole basis of Shor's quantum result in factoring. What
Shor really did was to solve the discrete logs, and then show that this
also solved factoring.
------------------------------
From: "Bart Peeters" <[EMAIL PROTECTED]>
Crossposted-To: alt.security
Subject: RSA, how to calculate big numbers
Date: Fri, 17 Dec 1999 23:32:54 +0100
I have to calculate:
(32567023914^367151)%40000399997
How can I do that?
--
Bart Peeters
E-mail:
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: discrete logorithm reduction to factoring
Date: 17 Dec 1999 22:26:48 GMT
My understanding that is that if you can solve DL, you can also solve IF. This
means DL may be stronger than IF (or of equal strength). As if you can solve IF
you may not be able to solve DL.
Don Johnson
------------------------------
From: Matthew Montchalin <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Prime series instead (Re: Pi)
Date: Fri, 17 Dec 1999 14:21:21 -0800
| > > Is there any practical value to the number derived from using primes
| > > instead of odds in that formula? E.g.,
| > >
| > > N = 4(1 - 1/3 + 1/5 - 1/7 + 1/11 - 1/13 + 1/17 ... )
| >
| > You forgot one.
SDpikachu wrote:
| Yes, but 1 isnt a prime,
Unless we make it an honorary prime, like the 2 is an honorary prime.
| so it should have been:
|
| N = 4(1/2 - 1/3 + 1/5 - 1/7 + 1/11 - 1/13 + 1/17 ... )
|
| That was a completely pointless post... why do I bother?
But is there any practical value to the resulting number? Any of those
numbers, whether 2 is replaced by 1, or included with 1?
------------------------------
From: "Markus Eiber" <[EMAIL PROTECTED]>
Subject: Re: Breaking a cipher.
Date: Fri, 17 Dec 1999 23:31:10 +0100
Tom St Denis schrieb in Nachricht <83dqi1$82$[EMAIL PROTECTED]>...
>In article <01bf488c$5a2ec8a0$1c488bca@pc001>,
> "jim" <[EMAIL PROTECTED]> wrote:
>> I'm only a newbie to the world of cryptography and I was wodering
>about
>> breaking a cipher. Is it a hard task, or is it just reversing the
>cipher
>> and using as many keys as possible?
>
>A cipher is said to be broken when it no longers works as claimed.
>This can be because of a short key (40 bit keys for example) or because
>of some statistical/algebraic bias in the algorithm.
>
>RC5 was [for example] broken with differential analysis, but requires
>2^53 blocks [that's 2^56 bytes or 2^36 MB of data] of data and is
>hardly pratical. So is the cipher insecure? Not really.
That's interesting!
How was the number of block's needed to break RC5 calculated?
I think nobody could encrypt 2^53 blocks.
Is there a measure like the unicity distance in order to decide whether a
cipher is practical secure or not? Where could I get information to this
topic?
>
>My point being, a broken cipher is not always insecure.
>
>Tom
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
------------------------------
From: "Markus Eiber" <[EMAIL PROTECTED]>
Crossposted-To: alt.security
Subject: Re: RSA, how to calculate big numbers
Date: Fri, 17 Dec 1999 23:41:04 +0100
Bart Peeters schrieb in Nachricht <83ecpe$749$[EMAIL PROTECTED]>...
>I have to calculate:
>
>(32567023914^367151)%40000399997
>
>How can I do that?
>
Use modular arithmetics:
Note the following example:
m^9 mod n = (((((m^2 mod n)^2 mod n))^2 mod n) *m) mod n
applied to your specific problem:
calculate ((m^367150 mod n) *m) mod n
>--
>Bart Peeters
>E-mail:
>
>
>
------------------------------
From: [EMAIL PROTECTED] (Eric Bach)
Subject: Re: First step in finding primes
Date: 17 Dec 1999 22:43:47 GMT
If you want to think quantitatively about trial division
as a preliminary step in prime testing, you should take a
look at Exercise 9.12 in E. Bach & J. Shallit, Algorithmic
Number Theory I, MIT Press, 1996. (I do not believe that
is the only source for this but it is one I know well.)
Eric Bach
[EMAIL PROTECTED]
------------------------------
From: "Markus Eiber" <[EMAIL PROTECTED]>
Subject: DES as pseudo random number generator
Date: Fri, 17 Dec 1999 23:55:42 +0100
Hi there!
As you know one-time-pad is a cipher with perfect secrecy.
How about a one-time-pad using a DES generated pseudo random number
sequence?
Note the following example for a stream cipher:
I will get a seed by a real random process (e.g. thermic noise) and will
create a pseudo random number sequence by DES in CFB mode. Then I will
encrypt my message by this using an XOR operation.
The seed and DES key will be transmitted secure to the recipiant of the
message and he may decrypt the message after creating the identical pseudo
random number sequence by adding it to the cipher.
The security of this cipher depends only on the quality of the pseudo random
number sequence.
How secure is it?
Markus Eiber
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Crossposted-To: comp.theory
Subject: Re: discrete logorithm reduction to factoring
Date: Fri, 17 Dec 1999 15:58:14 -0700
In article <83ebq6$lgc$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> In <8373h1$7vb$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>
> >Is it true that discrete log reduces to factoring ?
>
> Yes. THis is the whole basis of Shor's quantum result in factoring. What
> Shor really did was to solve the discrete logs, and then show that this
> also solved factoring.
No -- it's the opposite. Factoring can always be reduced to a
discrete log problem, but the reverse may not be true.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
** 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
******************************
