Cryptography-Digest Digest #586, Volume #13 Mon, 29 Jan 01 14:13:01 EST
Contents:
Re: RSA: Finding the private exp instead of factoring (Bob Silverman)
Re: Between Silk and Cyanide (Derek Bell)
Re: RSA: Finding the private exp instead of factoring (Paul Schlyter)
Re: Security of Centrinity's FirstClass Product (John Savard)
Re: security of cd-rw erasure? (John Savard)
Re: Security of Centrinity's FirstClass Product ([EMAIL PROTECTED])
(Off) UDP port 49152 on Macintosh (OS 9) (Erich)
Recommendations on simplest way to add client/server encryption (Rob Yampolsky)
Re: Security of Centrinity's FirstClass Product (Jim Gillogly)
A Password Protocol (John Savard)
Re: Security of Centrinity's FirstClass Product (Jim Gillogly)
Re: RSA: Finding the private exp instead of factoring (DJohn37050)
----------------------------------------------------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: RSA: Finding the private exp instead of factoring
Date: Mon, 29 Jan 2001 14:16:23 GMT
In article <951dto$eje$[EMAIL PROTECTED]>,
"The Death" <[EMAIL PROTECTED]> wrote:
> Isn't it easyer sometimes to encrypt a message, and try finding the
private
> exponent.
> The procedure is:
> 1) Encrypt a message
> 2) Decrypt by private exponent X
> 3) Is the decrypted message the same as the original?
> * Yes - You found the Private Exponent!
> * No - Increase X by 1 and go back to (2)
I suggest that you count the number of private exponents.....
--
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/
------------------------------
From: Derek Bell <[EMAIL PROTECTED]>
Subject: Re: Between Silk and Cyanide
Date: 29 Jan 2001 14:42:07 -0000
Roger Peniston-Bird <[EMAIL PROTECTED]> wrote:
: At this point I am left wondering how, given the original sequence of
: letters - from having cracked the cypher - and having got the sequence as
: encrypted, it is possible with basic fiddly maths to determine the two
: transition keys. So could someone please explain this or tell me where I
: might find the answer? Then I could try and work out the second key for
: myself.
David Kahn revied a book on French resistance during WW2 which
describes a very similar cipher. (Marks mentions the double transposition
system used was similar to one used by the Free French.)
The review was in Cryptologia, Vol 4, Issue 3, page 173.
It doesn't describe any mathematical techniques to break it,
but knowing the poem gives a cryptanalyst a chance to work out both
keys.
Derek
--
Derek Bell [EMAIL PROTECTED] |"Usenet is a strange place."
WWW: http://www.maths.tcd.ie/~dbell/index.html| - Dennis M Ritchie,
PGP: http://www.maths.tcd.ie/~dbell/key.asc | 29 July 1999.
|
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: RSA: Finding the private exp instead of factoring
Date: 29 Jan 2001 15:07:58 +0100
In article <951dto$eje$[EMAIL PROTECTED]>,
The Death <[EMAIL PROTECTED]> wrote:
> Isn't it easyer sometimes to encrypt a message, and try finding the private
> exponent.
> The procedure is:
> 1) Encrypt a message
> 2) Decrypt by private exponent X
> 3) Is the decrypted message the same as the original?
> * Yes - You found the Private Exponent!
> * No - Increase X by 1 and go back to (2)
>
> In practical needs of decrypting messages of others, isn't this better?
No -- it's much much much much much much much much much much much much
much much much much much much much much much much much much much much
much much much much much much much much much much much much much much worse!
Suppose you use N-bit RSA keys. You know that the modulus n (note
that n and N are different numbers) has two factors where the
smallest factor is no larger than sqrt(n), i.e. it has at most N/2
bits. A naive approach to find the factors would be:
0. Divide out any eventual factors of 2 (in real moduli there aren't any)
1. Start with factor=2
2. Try divide n with factor,
3. If the remainder=0 you've found a factor! Divide n by factor to
find the other factor, and the RSA key is cracked.
3. Increase n by 1, then go back to step 2. until factor > sqrt(n)
4. If you've reached factor>sqrt(n) without finding a factor, n is prime
and the RSA key cannot be valid.
There are much faster factoring algorithms, however this naive algorithm
may have to perform 2**N/2 dividions before finding a factor or
concluding n is prime.
Now, let's compare that with your approach where you basically will
have to try 2**N different private exponents, and in each such try
compute a modular exponent. Thus is MUCH MUCH MUCH MUCH MUCH MUCH
MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH
MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH
MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH MUCH
slower, because:
1. You'll have to do 2**N rather than 2**N/2 operations. This is
2**N/2 times more operations. If N is 768 (which today is
considered the minimum size of a safe RSA key), this means some
1.5E+116 times more operations!
2. In your case, each operation would have to be a modular exponent,
while in the naive factoring algorithm, each operation would have
to be an ordinary division, which is MUCH faster!
Suppose a division takes 0.1 milliseconds while a modular exponentiation
takes 50 milliseconds. Then cracking a 768-bit RSA key by factoring
with the naive factoring algorithm above would take some 4E+111 seconds
which is 1E+92 trillion years. Your approach to try every possible
exponent would take some 8E+229 seconds which is 2E+210 trillion years.
Next, suppose that computers somehow became 4E+120 times faster than
today. Then the naive factoring algorithm would execute in one
nano-second, while your exhaustive key search still would require
2E+109 seconds, which is 5E+89 trillion years !!!!!
As a comparison: the age of the universe is approximately 1E+10 years
or 10 billion years, which is 3E+17 seconds.
Finally, the factoring method has another advantage over your exhaustive
key search method for cracking RSA keys: the factoring method allows
you to crack the RSA key even if you have no plaintext/ciphertext
pair available!
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Security of Centrinity's FirstClass Product
Date: Mon, 29 Jan 2001 15:25:11 GMT
On Mon, 29 Jan 2001 08:49:57 GMT, [EMAIL PROTECTED] wrote, in
part:
>Can anyone PLEASE RE-ASSURE ME or WARN me...
Well, there probably isn't someone out there who can tell you
something based on specifically knowing what encryption method is in
the product.
To claim that they need to keep the algorithm secret for 'security
issues', when dissasembling a program is essentially trivial compared
to the effort it takes to perform cryptanalysis of a modern block
cipher, certainly would seem to be a bad sign.
That does not mean the product is necessarily lacking in security. And
pretty well any encryption program running on your computer depends on
your computer being secure, so I don't think the criticism levelled in
another post is too serious a flaw. But in general, one would _prefer_
to use an encryption program whose operation one could validate
oneself.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: alt.comp.periphs.cdr
Subject: Re: security of cd-rw erasure?
Date: Mon, 29 Jan 2001 15:39:46 GMT
On 28 Jan 2001 21:53:49 -0800, Paul Rubin <[EMAIL PROTECTED]>
wrote, in part:
>Anyone know if it's possible to recover any info from a cd-rw disc
>after it's been reformatted? Is there some way to look at the actual
>bits under a conventional microscope, or do you need infrared?
>Yeah, this is OT for sci.crypt, but I figure some of the right people to
>ask might be here.
Right off the top of my head, my guess would be that it is _much_
easier to do this than it would be to recover, say, previously
overwritten data from magnetic media (which _is_ possible).
For that matter, the article a friend mentioned to me - about data
being recoverable as much as ten rewrites ago - was from back in the
days of IBM 2311 removable disk packs. The much higher densities of
todays hard drives may mean there is less extra "room" on the media
for traces of old information.
A dye can be changed from a reflective state to an absorptive one, and
vice versa, by intense laser beams in CD-Recordable media.
Two things might give away previously recorded data. Possibly the
previous pattern of dye states might remain along one edge of the
groove, if there was variation in the alignment of the laser. Also,
there is the chance there might be slight marks on the polycarbonate
of the disk itself from the previous writing processes.
Visible light gives a better resolution than infrared, and will likely
be as effective. But any traces of previous writes will be difficult
to see.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Security of Centrinity's FirstClass Product
Date: Mon, 29 Jan 2001 15:52:19 GMT
You said:
> beware snake oil.
Thanks... thats the impression I got too. Anything else? I need to give
a more "tangable" assessment of this product from a security point of
view, to a few who have not read 'The snake-oil FAQ'.
Cheers
GW
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Erich <[EMAIL PROTECTED]>
Subject: (Off) UDP port 49152 on Macintosh (OS 9)
Date: Mon, 29 Jan 2001 17:12:42 GMT
Hello!
After some thinking about it, and as this has been published since 1999, I
have decided to provide this information:
Some versions of Open Transport on Macintosh computers constantly listen on
UDP port 49152 for incoming connections. I personally have absolutely no
intentions to spread silly rumors that might harm Apple (I'm a Macian) and
I'm not particularly paranoic as well, but this doesn't get out of my mind.
Fact is, this port is listening intentionally, because there was a denial of
service attack on this port that has been fixed according to an official
technote by Apple. But the fixed version still listens on this port.
There are most probably unjustified rumors that this is the default port a
realtime monitoring system (in use by e.g. the NASA) uses as well. But it's
the first so-called "private" port anyway, so this is certainly a pure
incident.
Afaik, Apple has not commented on this port, neither officially nor
inofficially. Is there some insider or expert that has some plausible ideas
what this port could have been used for? Maybe some idea that stops these
silly rumors?
I just don't want my computer to listen on ports without knowing why!
Thanks,
Erich
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Rob Yampolsky <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc
Subject: Recommendations on simplest way to add client/server encryption
Date: Mon, 29 Jan 2001 12:34:48 -0500
Hi. I'm trying to add encryption to my client/server app, and am
looking for suggestions as to the easiest way to do it in an 'acceptably
secure' manner. The client runs on Windows, and the server on Unix
(AIX or Linux). I'd also like to control whether encryption happens at
all from the server at connection time. I'm also (somewhat) concerned
about the code size on the client side. My client app is only 350KB -
I'd hate to quadruple the size just to get encryption.
So far, I'm looking at OpenSSL and another free library called
libmcrypt. Libmcrypt seems to provide the same basic encryption
algorithms without doing the SSL handshake for you. Haven't found any
good code samples yet, but it sure sounds like SSL makes things more
complicated. Would it be reasonable to implement a simple handshake for
key exchange and just do encryption in the app (via libmcrypt)? Or is
'simple handshake for key exchange' an oxymoron?
And of course sample code would be greatly appreciated.
Thanks,
Rob Yampolsky
[EMAIL PROTECTED]
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Security of Centrinity's FirstClass Product
Date: Mon, 29 Jan 2001 10:29:26 -0800
[EMAIL PROTECTED] wrote:
>
> You said:
> > beware snake oil.
>
> Thanks... thats the impression I got too. Anything else? I need to give
> a more "tangable" assessment of this product from a security point of
> view, to a few who have not read 'The snake-oil FAQ'.
If you're giving an <honest> assessment of the security of the product,
you'll have to say that you can't. No matter how good the designer of
their proprietary crypto algorithm is, it has evidently not gone through
the kind of public gauntlet and thrashing that other algorithms have.
Now that you know it's a stream cipher you can look at their white papers
and such to see whether they make the obvious stupid play (i.e. using the
same key for more than one message), and perhaps run some tests on the
software itself to see whether other stuff is being obviously exposed,
but there's no way you'll be able to assess the actual security of the
product from a black box analysis.
--
Jim Gillogly
7 Solmath S.R. 2001, 05:37
12.19.7.16.12, 11 Eb 15 Muan, Eighth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: A Password Protocol
Date: Mon, 29 Jan 2001 18:22:31 GMT
I suspect this password protocol isn't new, but as I don't recall
offhand anything like it, I thought I would describe it here.
Scenario:
User: Knows a password.
Host: A general purpose computer; files it has on its disks may be
read by an adversary, but its computations are assumed to be secure.
Security Computer: This computer is secure, but it's connected to the
host over an insecure network, so both passive and active attacks on
its link to the host are possible.
I had hoped to avoid the use of public-key techniques, but if an
adversary is impersonating the host, without such techniques, a user
can be successfully impersonated (although an alarm would sound,
because no genuine user could be successfully verified); but I only
use them once, between the host and the security computer.
This is my solution to the problem.
The Security Computer keeps a table containing:
User ID; Hash of the user's password; User Master Key
The Host keeps a table containing:
User ID; Hash of the user's password after that password has been
encrypted with the user master key.
a) When the user logs in, the user first transmits his user ID to the
host computer.
b) The host computer then passes the user ID and a random session key
*encrypted with the security computer's public key* to the security
computer.
c) The security computer transmits a challenge vector to the host
computer.
The challenge vector has the following form: it consists of the
concatenation of the user master key, the session key, and a random
value, and is then encrypted with the hash of the user's password.
(To obtain the session key, the security computer needs to use its
private key.)
d) The host transmits the challenge vector to the user.
e) The user enters his password, and the user's computer does the
following:
1) The hash of the user's password is calculated: H(PW).
2) The challenge vector is decrypted: D(CV,H(PW)) -> ( MK, SK, R )
3) The master key is used to produce the hash of the user's password
that the host computer posesses. H(E(PW,MK))
4) This hash is used as the key to encrypt the challenge vector, and
the result is hashed.
5) This result is then encrypted by the session key, and the result is
hashed, and this hash is transmitted to the host computer.
f) The host computer, knowing H(E(PW,MK)) and the session key, can
repeat the calculation applied to the challenge vector, and verify the
user's identity.
The security of this protocol rests on the fact that the session key
is not available to an attacker.
I was hoping to obtain security from the fact that the master key is
not available to the attacker, but with the impersonator using
modified software, a bogus security computer can issue an invalid
challenge vector, and then the impersonator can simply encrypt that
challenge vector using H(E(PW,MK)) obtained from the disk of the host
directly. One needs to know H(PW) to issue good challenge vectors, so
even without using public-key methods to protect the session key, an
impersonation attempt will cause the system to fail.
With protected session keys, however, the steps in this protocol
relying on the master key become unnecessary, and it can be
simplified:
a) When the user logs in, the user first transmits his user ID to the
host computer.
b) The host computer then passes the user ID and a random session key
*encrypted with the security computer's public key* to the security
computer.
c) The security computer transmits a challenge vector to the host
computer.
The challenge vector has the following form: it consists of the
concatenation of the session key and a random value, and is then
encrypted with the hash of the user's password.
(To obtain the session key, the security computer needs to use its
private key.)
c) The host transmits the challenge vector to the user.
d) The user enters his password, and the user's computer does the
following:
1) The hash of the user's password is calculated: H(PW).
2) The challenge vector is decrypted: D(CV,H(PW)) -> ( SK, R )
3) The session key is used as the key to encrypt the challenge vector,
and the result is hashed, and this hash is transmitted to the host
computer.
e) The host computer, knowing the session key, can repeat the
calculation applied to the challenge vector, and verify the user's
identity.
Essentially, the host generates a session key in secret, and it is
first transmitted to the security computer guarded by the security
computer's public key, and then it is transmitted to the user's
computer, guarded by the direct hash of the user's password, which is
not kept on the host computer.
Once the extraneous steps are removed, perhaps it isn't all that
original...
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Security of Centrinity's FirstClass Product
Date: Mon, 29 Jan 2001 10:42:16 -0800
[EMAIL PROTECTED] wrote:
> Thanks... thats the impression I got too. Anything else? I need to give
> a more "tangable" assessment of this product from a security point of
> view, to a few who have not read 'The snake-oil FAQ'.
Let me add one more obvious observation: if you're lucky you can prove
it has poor security -- that is, if they do something clearly bone-headed --
but you can't have good confidence that it has good security without being
able to see the workings of the product itself. Even if you have access to
the home-brew algorithm itself, you're not likely to be able to find a flaw
in it unless you're a strong cryptanalyst. If you <are> a strong cryptanalyst,
failing to find a flaw won't give you much confidence that Biham or Coppersmith
couldn't have found one.
--
Jim Gillogly
7 Solmath S.R. 2001, 05:37
12.19.7.16.12, 11 Eb 15 Muan, Eighth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 29 Jan 2001 18:53:40 GMT
Subject: Re: RSA: Finding the private exp instead of factoring
I suggest Paul's explanation be posted in the crypto FAQ. It is simple to
understand.
Don Johnson
------------------------------
** 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
******************************
