Cryptography-Digest Digest #266, Volume #9 Mon, 22 Mar 99 18:13:03 EST
Contents:
Re: Symmetric vs. public/private (Mordido)
Re: Common Modulus Attack ([EMAIL PROTECTED])
Re: Test Vectors (Anonymous)
Re: Is TEA Algorithm safe???? ([EMAIL PROTECTED])
Re: RC4 file encryptor (please take a look) (Bryan G. Olson; CMSC (G))
Re: Splitting privtae keys (Bryan G. Olson; CMSC (G))
Analysing (Werner Lang)
Re: Newbie, what a stupid term... (John Bailey)
Re: Does PGP use salt when hashing passphrases? (Robert Munyer)
To break a5 ("Adam Rostek")
Re: Testing Algorithm (hash) (David A Molnar)
Re: Self-executing encryption program ([EMAIL PROTECTED])
Re: How "safe" is SafeGuard Easy for WinNT by Utimaco? (Bart Symons)
ULK (Uncontrollably Long Key) Ciphers (John Savard)
AES Cndidate - Alpha (Wojciech Laskowski)
Re: Random Walk ("karl malbrain")
----------------------------------------------------------------------------
From: Mordido <[EMAIL PROTECTED]>
Subject: Re: Symmetric vs. public/private
Date: Mon, 22 Mar 1999 16:24:08 GMT
I've read your post and I see that you understand "shared-keys". Please
consider this--
"To create a reply block, first choose some passphrases for shared-key,
conventional encryption with ``pgp -c''. Suppose you want your message
encrypted first with your nym's public key, then with shared key
``passphrase_b'', then with shared key ``passphrase_a''. Create a
remailer message like this:
::
Anon-To: [EMAIL PROTECTED]
Latent-Time: +0:00
Encrypt-Key: passphrase_a"
*The above in quotes is an excerpt from the subject line, Creating a
Reply Block.
What is a "shared-key"?
*I'd appreciate your reply. In advance, thank you.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Common Modulus Attack
Date: 22 Mar 99 17:52:42 GMT
_DEFAULT <[EMAIL PROTECTED]> wrote:
> I was reading Bruce's book where he talked about Common Modulus Attack on
> RSA:
> c1 = m ** e1 mod n
> c2 = m ** e2 mod n
> e1 and e2 are relatively prime, the cryptanalyst knows n, e1, e2, c1, and
> c2.
> The extended Euclidean algorithm can find r and s:
> r * e1 + s *e2 = 1
> assume r is negative, extended Euclidean algorithm can be used to find c1
> ** -1, then
> [(c1 ** -1) ** -r] * [c2 ** s] = m mod n
Well, one could use (c1**r), but one of r,s is negative ... this is just
to use positive integers.
> My question is: does c1 ** -1 always exist?
It had better! If not (this is the inverse mod n), then the GCD(c1,n)>1
and this factors n! (once you factor n, you can find the private keys for
the public keys and then be able to decode this and all messages sent in
either public key). The percentage of numbers (from 1 to n) that are
relatively prime to n is phi(n)/n (phi=Euler's Totient) and for n=pq (say
for RSA), this is (1-1/p)(1-1/q). For p,q large (say over 200 bits) this
is on the order of 1-2/p ... or only 2/p (as a fraction ... say about
2**(-200)) of the "messages" are NOT relatively prime to n! Very few ...
if EVER you send such a message one can use it to factor your modulus (and
then decode EVERY message you send!) (of course, this is like "guessing" a
factor of n .. the odds against it are on the order of 2**200:1).
> If the cryptanalyst knows c1,
> why does he need to use extended Euclidean algorithm to find c1 ** -1 ?
c1**(-1) is the inverse of c1 MODULO n (c1**(-1) is the number, d with
d*c1=1 mod n)
> tried to use the following number but I can't recover the message m:
> m = 13, e1 = 2, e2 = 3, n = 5
Well, that is not very secure as a cipher. Since n is PRIME, anyone can
find the secret exponent). NOTE: e1 is NOT relatively prime to phi(n)!
(the map from x-->x^2 is not one-to-one, for example, 4^2=1^2=1 mod 5 ...
so if you use e1=2 and get the secret message "1" did the sender send the
message "1" or "4" originally?) (there are ways around that, such as
sending two bits of extra info in the case that n=pq to determine which
solution is the original message).
Second m is larger than n!!!
NO GOOD. The encryption (in RSA) encrypts messages 1<=m<=n ONLY
(if e is relatively prime to phi(n) and n is square free, then the map
from 1<=m<=n m|-->c=m^e mod n is one to one and has inverse (one can solve
for m given c) m=c^d mod n where ed=1 mod phi(n) (actually, lambda(n)
instead of phi(n) suffices where lambda(n) is the Carmichael function ...
the LeastCommonMultiple of (p_i-1) where n=PRODuct(p_i) (no repeated
factor for n being square free)).
Take, for example, n=85=5*17, phi(n)=4*16=64 (lambda(n)=LCM(4,16)=16) and
e1=5, e2=3 (NOT e1=2 for RSA), m=7 [I am using 7 instead of 13, since for
m=13, I believe c1 happens to come out equal to m!] (here e1,e2 are
relatively prime to phi(n)). We need d1 d2 (decrypting exponents) with
d1*e1=1 mod 16 (this suffices ... don't need mod 64, actually) or d1=13,
d2=11. These suffice as private keys (one could use larger values with
d_i*e_i=1 mod 64, but these smaller decrypting exponents work).
---
Let's check that these decrypting exponents work in this example:
for c1=m^e1=7^5 mod 85=62 mod 85
and if we try to decode, we get c1^d1 mod 85=62^13 mod 85 = 7 mod 85, just
m (the original message) again (decrypting works here)
(62^13 mod 85 = 62^12*62 mod 85 = (62^4)^3*62 mod 85
=21^3*62 mod 85=81*62 mod 85 = 7 mod 85)
for c2=m^e2 = 7^3 mod 85 = 3 mod 85
decoding would give c2^d2 mod 85=3^11 mod 85 = 7 mod 85).
----
Now suppose someone only sees c1, c2 and knows e1, e2 and n.
c1^(-1) (the multiplicative inverse of c1) is the number d with
d*c1=1 mod 85 or 62*d=1 mod 85 ... let's see:
62*48-85*35=1, so 62*48=1 mod 85 (62^(-1) mod 85 = 48 mod 85)
This is c1**(-1) (the multiplicative inverse mod n) (I used a continued
fraction expansion of 85/62 to get this ... that is just the (extended)
Euclidean Algorithm).
We need:
r*e1+s*e2=1 (5r+3s=1 with r<0 ... 5*(-1)+3*2=1 so r=-1, s=2 work).
so m=m^1=(m^e1)^r*(m^e2)^s=c1^r*c2^s=(c1^-1)^(-r)*(c2)^s mod n is one way
to find m knowing only c1, c2, e1, e2 and n (after calculating
c1^(-1) mod n and r,s): Let's see if this works in this example:
Now ... assume we only know the public keys (e1,n) (for Ralph, say) and
(e2,n) (for Betty, say) and the n's are the same and see the original
message "m" (somehow we know that this is the same message -- say, Jane
sends the same message to Ralph and Betty who have the same modulus in
their public keys) sent to Ralph and Betty, so we see c1 and c2. We know
e1, e2, n and c1, c2. We DON'T know either d1 or d2 (the private keys for
Ralph or Betty).
Just knowing e1 and e2 (NOT KNOWING d1 OR d2!) we can find r,s. We know c1
and c2 so we can calculate (c1^-1)^(-r)*c2^s mod n just from knowing c1,c2
(the encrypted messages) and n (need n, since c1^(-1) is the
multiplicative inverse of c1 MODULO n). This ((c1^(-1))^(-r)*c2^s mod n)
comes out (in this example) as:
(c1^-1)^(-r)*c2^s=48^(-(-1))*3^2=48*9=7 mod 85. This recovers the original
message, 7! So we could decode without knowing either of the private keys
(if we know the public keys; they have the same modulus and the same clear
text is encrypted in both those keys and we get both encrypted versions).
------------------------------
Date: Mon, 22 Mar 1999 18:51:36 +0100 (CET)
From: Anonymous <[EMAIL PROTECTED]>
Subject: Re: Test Vectors
>Not sure if this might be a good idea but a group (say
>sci.crypt.Test.vectors) specifically for test vectors. It something that
>people (including myself) are after every now and then when they try new
>code.
>Could also keep some longer binary tests there without annoying people.
>
>Anyone else want it?
>
>(PS if this has be talked about before or already exists just ignore me)
a webpage which gets included into the FAQ would be more useful as the
test vectors wouldn't have to be reposted every week or so.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Is TEA Algorithm safe????
Date: Mon, 22 Mar 1999 18:42:30 GMT
> Or, am I hopelessly mistaken and you gain no extra security at all no
> matter how you chain blocks together? If so, expect many followups to
> correct me. (-: I'm just thinking out loud here...
If you chain (CBC or PCBC) you increase the difficulting of analyzing the data
without the key. If you simply use ECB similar blocks can be analysed.
BTW, I thought the weakness (according to the paper) involves 2 related keys
and 2^32 plaintexts?
BTWx2, are there any 16-bit versions of TEA? Using 16-bit registers?
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Bryan G. Olson; CMSC (G))
Subject: Re: RC4 file encryptor (please take a look)
Date: 22 Mar 1999 19:51:10 GMT
[EMAIL PROTECTED] wrote:
Bryan Olson had written:
: > I dislike the method. First, I don't see why anyone would want to
: > throw out password entropy, as the get_public_key function does.
: >
: > Second, we can easily derive a session key from the
: > passphrase and a one-time salt, so there's no motivation for
: > the non-portable and inconvenient mouse-based randomness
: > generator.
: If you (for example) hash your password and use that as a salt, you provide
: another method of checking for valid passwords. You should really hash
: something else. The mouse was the best easy idea I cam up with.
I don't think you've thought through the attacks. In the method
you use, you generate a random vector and send its cleartext
along with the message. I'm saying you can replace the random
salt with a one-time salt, such as timestamp. Either way the
salt is transmitted in the clear.
The passphrase exhaustion attack works against either method. The
adversary doesn't care if the salt was generated randomly or not,
since he sees it in the clear.
The one class of attack that may work against the one-time salt
and not against the random salt is "related salt" attacks. We
can defend against such attacks by using a hash function to
generate the session key from the master key (pass phrase) and
salt.
--Bryan
------------------------------
From: [EMAIL PROTECTED] (Bryan G. Olson; CMSC (G))
Subject: Re: Splitting privtae keys
Date: 22 Mar 1999 20:17:56 GMT
Scott Fluhrer ([EMAIL PROTECTED]) wrote:
: >[EMAIL PROTECTED] wrote:
: >> I am trying to find a way to divide a large private key (e.g. 1024 )
: >> into one large piece and another small piece (e.g. 128), such that the
: >> owner of the key holds the small piece, and some other party holds the
: >> large piece. When the key is needed, the 2 pieces are recombined on the
: >> owner machine to a complete key.
[...]
: If the size differential is too large to make this practical, then you
: can pick a symmetric encryption algorithm (eg. DES), make the small piece
: a random DES key, and the large piece the real key encrypted with that
: key.
Given the statement of the problem, I think that's the solution.
Be sure to use a symmetric algorithm that's at least as strong as
public key system. DES is probably not adequate.
--Bryan
------------------------------
From: [EMAIL PROTECTED] (Werner Lang)
Subject: Analysing
Date: Mon, 22 Mar 1999 21:40:50 +0100
Hi there
is there a group, who
test cryptographic algorithm for free.
Thanks J.Lang
------------------------------
From: [EMAIL PROTECTED] (John Bailey)
Subject: Re: Newbie, what a stupid term...
Date: Mon, 22 Mar 1999 21:07:31 GMT
On Sat, 20 Mar 1999 23:31:42 -0500, Brandt <[EMAIL PROTECTED]> wrote:
> I would like to know the best place to start to learn
>cryptography. To learn the the vocab and the math skills. Also
>where to learn the concept of Unix password encryption.
To Start to learn crypto, a place to start (underline for emphasis)
is the man files of a good Unix system. Your question stimulated me
to think of a cgi script which lets me read my service provider's man
pages.
I immediately logged on to my service provider, a Unix system, and
tried the command: man crypt. It worked (painfully). The second time
I typed the command: man crypt > man_crypt.txt and put the result in a
file on my crypto web directory.
I left the result in
http://www.frontiernet.net/~jmb184/interests/cryptography/man_crypt.txt
for your reference.
Thanks for a helpful question.
John
------------------------------
From: [EMAIL PROTECTED] (Robert Munyer)
Crossposted-To: comp.security.pgp.discuss
Subject: Re: Does PGP use salt when hashing passphrases?
Date: 22 Mar 1999 15:08:20 -0600
In article <[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> Lincoln Yeoh ([EMAIL PROTECTED]) wrote:
> : Was wondering if using salt for hashing/encrypting passphrases
> : be a good idea.
>
> Maybe it would be for some purposes. But it isn't used by PGP,
> because it couldn't be used the way it is set up.
No, salt works fine with the way PGP is set up. See RFC 2440
("OpenPGP Message Format"), section 3.6 ("String-to-key (S2K)
specifiers"). Here is section 3.6.2, verbatim:
Implementations SHOULD use salted or iterated-and-salted S2K
specifiers, as simple S2K specifiers are more vulnerable to
dictionary attacks.
http://info.internet.isi.edu:80/in-notes/rfc/files/rfc2440.txt
> In PGP, you want to be able to decode a key file or a conventionally
> encrypted file knowing ONLY the passphrase. If salt were used to
> produce the key from the passphrase, you would have to know the
> salt value too.
That's no problem. The program can just save the salt, unencrypted,
in the headers of the encrypted file or message.
-- Robert Munyer <[EMAIL PROTECTED]>
------------------------------
From: "Adam Rostek" <[EMAIL PROTECTED]>
Subject: To break a5
Date: Mon, 22 Mar 1999 22:08:48 +0100
I'm interested in software attack to a5 (a3, a8).
Does anyone know anything about it?
Please send me e-mail.
[EMAIL PROTECTED]
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithm (hash)
Date: 22 Mar 1999 21:03:08 GMT
> If AC captures your imagination, then you will simply have to buy
> Handbook
> of Applied Cryptography by A.J.Menezes, P.C.van Oorschot &
> S.A.Vanstone.
> This book is harder to get into but contains far more detail than
> AC2.
It's worth noting at this point that some libraries can be persuaded
to buy such books for you, thereby saving money at the cost of waiting
for the book to come in. You may even meet people this way, as you end
up discovering that someone *else* checked out the only copy...
-David
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Self-executing encryption program
Date: Mon, 22 Mar 1999 21:23:14 GMT
Mycroft wrote:
> Sundial Services wrote:
[...]
> > Do you know how long it actually takes to dismantle the
> > PKZip stream cipher?
[...]
> Hmmmm....I don't recall the original poster asking for a "fool proof"
> self-extracting encrypted executable, just an example of ANY self-extracting
> ecrypted executable. If you have a better example, then post it. If not...
Cursed be he who places a stumbling block before the blind.
If one _knows_ a system has been broken, then suggesting it without
mentioning that fact is irresponsible. If one does not know that
it has been broken, then the fact that it has (by Eli Biam and Paul
Kocher incidentally) is important news here on sci.crypt.
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Bart Symons <[EMAIL PROTECTED]>
Subject: Re: How "safe" is SafeGuard Easy for WinNT by Utimaco?
Date: Mon, 22 Mar 1999 21:35:28 +0000
In addition, the encryption key can be a randomly generated key, not
even known by the user himself. It can be different for every PC in your
organisation (although this will mean you have to do a manual
installation on every PC).
Also, to answer a FAQ: when the user changes his password, this doesn't
require a new encryption round of the hard disk. The disk encryption key
remains the same, only the password used to recover this key is changed.
The mechanisms SG Easy uses are identical for all supported OS (Windows
3.x, Windows 9x, Windows NT4 and OS/2).
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: ULK (Uncontrollably Long Key) Ciphers
Date: Mon, 22 Mar 1999 21:51:41 GMT
The following concept is *not* a way for U.S. software developers to get
around key length restrictions, since programs for export are individually
examined, and "dodges" around the restrictions, such as the long key setup
time of Blowfish, are specifically disallowed.
I suppose, though, that foreign countries that only grudgingly signed on to
the modifications to Wassenaar could turn a blind eye to this sort of
thing.
However, I think this technique may have *practical* application entirely
in the absence of any political limitations on cryptography.
Let us take a cipher, which must be a stream cipher with a *large* internal
state, and which must be an autokey.
Then, supposing an implementation of such a cipher accepted a short
password as the key. One could still use, say, a paragraph of text as the
real key as follows:
Enter password.
Start enciphering.
First, encipher your key paragraph.
Then, encipher your message.
Then, throw away the first bit of the message prior to transmission: the
part corresponding to the key paragraph.
The reciever first enciphers the key paragraph to get the missing first bit
of the file, and then deciphers the whole file.
One could make the procedure simpler if one is enciphering only straight
text and uses a cipher which is reciprocal.
John Savard (teneerf is spelled backwards)
http://members.xoom.com/quadibloc/index.html
------------------------------
From: Wojciech Laskowski <[EMAIL PROTECTED]>
Subject: AES Cndidate - Alpha
Date: Mon, 22 Mar 1999 23:47:57 +0100
Can you give me any information, where can I get K. Almquist's paper
"AES Candidate Performance on the Alpha 21164 Processor"?
Thanks,
Wojciech Laskowski
------------------------------
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: Random Walk
Date: Mon, 22 Mar 1999 14:53:37 -0800
R. Knauer wrote in message <[EMAIL PROTECTED]>...
>Consider this news item from the AP:
> (HOUSTON) -- Hospitals in Houston are sending out letters to
>former patients who may have been exposed to Hepatitis C in blood
>transfusions as far back as 11 years ago. Some of those who could have
>picked up the virus in the transfusions may not show signs of illness.
>(...)
>It looks like people who had money for expensive operations got
>transfusions and therefore got zapped by hepatitus, whereas people who
>could not afford luxury operations did not get transfusions and were
>spared.
Thank you for bringing this DISCOURSE back to the question of
PRIORITIZATION. Making Health Care free does NOT necessarily lead one to
greater COST overall. Professionals must re-take TRIAGE-ability across the
needs of the community as a whole, and historically this occurs only after
ORGANIZATION is built.
>>That is total BULLSHIT. The mechanics of MATHEMATICS have been widely
known
>>since HUNTER-GATHERORS became FARMERS, 5K or so years ago.
>
>Are you suggesting that hunter-gatherers were doing tensor calculus on
>their clay tablets? Please, gimme a break willya.
Sorry, but I don't give BREAKS here. I make the claim that EACH and EVERY
new thing is ALWAYS based, somewhere, on existing things. I believe, from
an ANALYSIS of HISTORY, that tenders of the NILE and TIGRIS valleys dealt in
TENSOR CALCULUS to get anywhere.
>I have read similar books on the "law of unintended consequences" and
>they make for enjoyable reading. But that does not mean that the
>people in Caersar's day could break the Caesar cipher easily.
My point here is to GROUND both cryptography and cryptanalsys in the same
frame of reference under prioritization.
>One day we will be able to factor the product of large prime numbers
>with quantum computers. When that finally happens, it is not correct
>to look back and say that we were enabled earlier because the
>machinery was there to do it and all we had to do was put the pieces
>together correctly.
Again, the point is: IF YOU CAN SAY IT, YOU CAN DO IT defines the
TIMEFRAME, not CONSTRUCTIONISM.
>The worldview espoused by existential metaphysics demands the concrete
>actualization of a potential act for it to be real.
Sorry, but I come pre-subscribed to BOLSHEVISM. Good luck with metaphysics,
however!
Karl_M
------------------------------
** 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
******************************
