Cryptography-Digest Digest #85, Volume #13 Fri, 3 Nov 00 12:13:01 EST
Contents:
Re: RSA vs. Rabin (Bob Silverman)
Rijndael Security ("ajd")
Re: 3-dimensional Playfair? (Daniel)
Re: Calculating the redudancy of english? (Roger Gammans)
Re: Crypto Export Restrictions (Terry Ritter)
Re: srp-1.7.0 released w/TLS Telnet security, X11 forwarding support (Jeffrey Altman)
Re: Give it up? (Eric Lee Green)
Re: Rijndael Security (Eric Lee Green)
Re: Crypto Export Restrictions (James Felling)
Re: Calculating the redudancy of english? ("Douglas A. Gwyn")
Re: Is RSA provably secure under some conditions? ("Douglas A. Gwyn")
Re: ECC choice of field and basis (DJohn37050)
Re: index of coincidence of Spanish/Turkey ("Douglas A. Gwyn")
Re: Beale Cypher ("Douglas A. Gwyn")
Re: is NIST just nuts? ("Douglas A. Gwyn")
Re: Rijndael Security ("Douglas A. Gwyn")
Re: Give it up? (Tom St Denis)
----------------------------------------------------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: RSA vs. Rabin
Date: Fri, 03 Nov 2000 14:37:08 GMT
In article <8tsl7m$pu4$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> > Is this little difference the reason why Rabin is provably as
> secure
> > as factorization?
>
> Yes. If you can find square roots, i.e a^2 = b^2 mod N (a != b) then
> you can factor N. Thus solving the square root (well I think this is
> how the proof goes, of course Bob will correct me) is as difficult as
> factoring.
Somewhat simplified, but essentially correct. But you also need
a != -b mod N as well as a != b mod N
>
> The question remains: Is factoring hard?
>
> > 2. RSA with low exponents is found insecure today.
Nope. Wrong. Thank you for playing.
Please explain where you heard this and why you think your statement
is correct.
> Rabin is insecure for various other reasons I would imagine.
Oh? Please tell us why you think this, and what these other reasons
might be. If you can't then you have no business making such a
statement.
R-W is subject to a known ciphertext attack which can reveal the key
(and not just the plaintext or signature!). But correct padding
destroys the attack.
> RSA is more convenient as well. You can easily perform either
> operation and you can do signatures, etc..
Rabin-Williams with e = 2 is 50% faster than RSA with e = 3
(and faster still than RSA with larger e) for verifying signatures.
I therefore ask why you think RSA is "more convenient"?
> RSA is conjectured to be as hard as taking the discrete logarithm
> modulo a composite (and with sufficient twisting as hard as
factoring).
>
> However, there is no proof that you need to factor to solve the RSA
> problem. In the case of Rabin it has been proven that you need to
> factor to take the square root.
This is almost, but not quite correct. What would be correct is
saying that finding square roots modulo a composite is polynomially
equivalent to factor. You don't NEED to factor to take the square
root. You could find the square root by direct search without
factoring. However, once you have done so, you can factor the modulus
easily.
--
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: "ajd" <[EMAIL PROTECTED]>
Subject: Rijndael Security
Date: Fri, 3 Nov 2000 10:05:35 -0000
How secure is Rijndael when given (most of) the plaintext and the cipher
text? For example if I encrypt a bitmap (and somehow the interceptor
knows its a bitmap), the interceptor then knows that the first block will
decrypt to
42 4D ** ** ** ** 00 00 00 00 36 00 00 00 28 00
where bytes 0-1 are the bitmap identifier
2-5 are the file size (which the interceptor doesn't *quite* know as my
encrypted file will be a multiple of the block size, and vthe plaintext file
may not be)
6-9 reserved and always zero
10-13 is the offset to beginning of bitmap data
14-17 is th header size
Given this information about the plaintext, and given the encrypted text,
can the interceptor work out the key? It seems to me like we are giving away
a bit too much information. Is there a standard to get around this problem?
regards
andrew
------------------------------
From: [EMAIL PROTECTED] (Daniel)
Subject: Re: 3-dimensional Playfair?
Date: Fri, 03 Nov 2000 14:58:13 GMT
On Thu, 02 Nov 2000 19:48:04 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>
>
>Daniel wrote:
>>
>> The largest problem to overcome will be the size of the CT (= 2 times
>> the length of the PT - this is the case for a typical Playfair).
>
>I suppose you erred. Playfair encodes a couple of characters
>to another couple via the matrix, thus preserving the length.
>
>M. K. Shen
Indeed, I mixed up with Nebel's/Painvin's system. But my previous
remarks still have a point, though.
regards,
Daniel
------------------------------
From: [EMAIL PROTECTED] (Roger Gammans)
Subject: Re: Calculating the redudancy of english?
Date: Fri, 03 Nov 2000 14:59:29 GMT
In article <8ts7mu$1ifq$[EMAIL PROTECTED]>, David C. Barber wrote:
>"Bill Unruh" <[EMAIL PROTECTED]> wrote in message
>news:8tq2bf$2dt$[EMAIL PROTECTED]...
>> In <8tkosd$84d$[EMAIL PROTECTED]> Simon Johnson <[EMAIL PROTECTED]>
>writes:
>>
>> > How does one calculate the redudancy of english?
>>
>> Then you have to decide, are you going to take a typical passage (in
>> which many words occur far far far more frequently than others) or a
>> dictionary ( where all words occur equally-- once).
>
>What about a Dictionary with definitions (e.g. the Webster available at
>Project Gutenberg)? Would analysis there yield useful data?
I was wondering about the shannon alogrithm posted earlier.
It might be interesting to see if on could train a large enough neural
network from a (random and representative) subset of Project Gutenberg, then
go back and measure it it a differemt subset.
Unfortuantely just a quick thought reveals the following weaknesses in
this as a plan:-
1. Lack of a estimate for 'large enough' neural net.
2. How do find your two independent random and representative
subsets. How do make sure this is what you've got.
3. Network overtraining.
TTFN
--
Roger
Think of the mess on the carpet. Sensible people do all their
demon-summoning in the garage, which you can just hose down afterwards.
-- [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Crossposted-To: talk.politics.crypto,talk.politics.misc,alt.freespeech,alt.hacker
Subject: Re: Crypto Export Restrictions
Date: Fri, 03 Nov 2000 14:59:37 GMT
On Thu, 02 Nov 2000 22:03:15 -0800, in
<[EMAIL PROTECTED]>, in sci.crypt David Schwartz
<[EMAIL PROTECTED]> wrote:
>
>Matthew Montchalin wrote:
>>
>> On Thu, 2 Nov 2000, David Schwartz wrote:
>> |Its algorithmic principles are quite sound. WebMaster's RNG is based
>> |upon it, and it's achieved independent certification by TST. The
>> |primary source of raw entropy is clock skew between independent
>> |oscillators as well as inherent randomness in processes that interact
>> |with human beings.
>>
>> Like the time between keypresses?
>
> Yes, like the time between keypresses measured to an accuracy of better
>than a millionth of a second.
That is extremely deceptive.
Keypress events from an ordinary PC keyboard are quantized by a
relatively-slow (probably tens of milliseconds) keyboard scan process.
A key can only be reported after it has been detected by the scan.
The scan itself, the report queue and handshake timing are all
deterministic.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Jeffrey Altman)
Crossposted-To: comp.security.unix,comp.os.linux.security
Subject: Re: srp-1.7.0 released w/TLS Telnet security, X11 forwarding support
Date: 3 Nov 2000 15:11:51 GMT
In article <[EMAIL PROTECTED]>,
Paul Rubin <[EMAIL PROTECTED]> wrote:
: I'm missing something--what's the point of using SRP in conjunction
: with TLS? If you believe the TLS certificates, then TLS stops MITM
: attacks so you can send the password in the encrypted TLS stream.
TLS does not have to be used with certificates. TLS can be used
with an anonymous cipher suite. The MITM attack on the TLS negotiation
is then detected by SRP.
Even when using encrypted connections such as TLS or SSH you never
want to send your password to the host you are connected to. The
use of TLS or SSH does not protect the host computer from becoming
compromised. When compromised to first thing that is often done
is to replace sshd, telnetd, ... in order to capture end user passwords.
A password that is valid on one machine is often valid on another one.
There are three reasons that we want to use TLS with Telnet:
. The encryption provided by TLS is more secure than that
provided by Telnet ENCRYPT
. TLS is an IETF standard and is used throughout the industry on
almost every platform and with many other protocols. New ciphers
such as the AES candidate (Rijndael) will be added to TLS. There
is no reason to duplicate the effort for a single protocol such
as Telnet. (Future versions of TLS may also be designed with
wireless sessions in mind.)
. Support for TLS provides the ability for Telnet to take advantage
of X.509 server and client certificates that may already be in use
for HTTP sessions. When client certificates are in use there is
no need to use SRP or Kerberos 5 for login.
Jeffrey Altman * Sr.Software Designer
The Kermit Project * Columbia University
612 West 115th St * New York, NY * 10025 * USA
http://www.kermit-project.org/ * [EMAIL PROTECTED]
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: Give it up?
Date: Fri, 03 Nov 2000 08:32:11 -0700
Mok-Kong Shen wrote:
> Tom St Denis wrote:
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > A good test for a block cipher is given a ciphertext block C and (let's
> > say this is an AES cipher) and 127 bits of P (the plaintext) you cannot
> > guess the last bit faster then brute force without the key.
>
> But known-plaintext attack (the zero bytes mean that
> part of the plaintext is known) is one of the commonly
> considered attacks, isn't it?
That is why you do not use a block cipher in straight ECB mode.
If you're using it in CFB mode, the first thing encrypted is a random salt
value. This basically means that as prior block's cryptotext is EOR'ed with
the current block's crypto-text, each subsequent block has a seemingly-random
value EOR'ed with it, which should resolve any known-plaintext attack
problems. (Yes, I know that it's not quite THAT simple, but for sake of
discussion this should suffice).
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer "The BRU Guys"
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: Rijndael Security
Date: Fri, 03 Nov 2000 08:36:44 -0700
ajd wrote:
> How secure is Rijndael when given (most of) the plaintext and the cipher
> text? For example if I encrypt a bitmap (and somehow the interceptor
> knows its a bitmap), the interceptor then knows that the first block will
> decrypt to
>
> 42 4D ** ** ** ** 00 00 00 00 36 00 00 00 28 00
>
> Given this information about the plaintext, and given the encrypted text,
> can the interceptor work out the key?
Supposedly not. Nevertheless, you'd be well advised to use a cipher block
feedback mode in order to "hide" any plaintext patterns. See any good text on
the field for descriptions/sample code.
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer "The BRU Guys"
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,talk.politics.misc,alt.freespeech
Subject: Re: Crypto Export Restrictions
Date: Fri, 03 Nov 2000 10:05:44 -0600
Scott Craver wrote:
> Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote:
> >CiPHER wrote:
> >>
> >> *waggles fingers* OoooOOOooo! 'Nasty person'! lol
> >>
> >
> >Thank you for your intelligent input.
> >
> >Like we really need more of this.
>
> ...," he says, posting a follow-up.
>
> Have you posted the algorithm yet for your pseudorandom
> number generator, or is it still just the "help files?"
> IIRC people could not gleen exactly how the algorithm
> worked by reading those files, and thus could not subject
> it to analysis.
>
As someone who has attempted to understand Mr. Szopa's algo in the past,
unless he has changed or adjusted things, how it works is via lots and
lots and lots of user intervention. There are any number of
inneficiencies in the algorithim, and to generate a useful ( i.e.
potentially secure) key you must spend at least 15min to 1/2 hour typing
your "keying data" in.
He probably achieves a fairly good RNG iff you are willing to work hard
at setup, and have a good understanding of how it works, and permutative
math. OTOH almost any ARCFOUR/RC4 implementation will blow the doors
off of it as far as speed to setup, ease of avoiding weak keys, and
should be comparable as to speed.
I have estimated that (assuming no better attacks vs. his RNG are found
than those that I have observed in the short time in which I examined his
math/algo) his algorithim uses about an order of magnitude more keying
than RC4 to achieve the same results. In general, I wouldn't bother with
it. PGP, or any other reputable crypto program will achieve results that
are as good (if not substantially better) , with much less time and
effort upon the user's part.
>
> By the way, since your PRNG uses permutations, it uses
> "mathematical equations." If you don't think it involves
> math because it uses compositions of permutations rather
> than products of large integers, then you need to read some
> abstract algebra textbooks. And your customers need to
> _know_ that you need to read some abstract algebra textbooks.
>
It is my considered opinion that Mr. Szopa is self taught, and unawqare
of some of the more sophisticated elements of permutation theory.
>
> You don't need to give out the source code, but something
> like pseudocode for the generator part would be ideal.
>
> -S
>
>
Pseudo code for the generator part is ugly. Here is a rough version -- I
am not at my notes to make certian that this is 100% accurate, and I only
have e-mail access on the PC I am at presently so I cannot verify it at
the website.
Step1 :Generate mix files
For i=1 to 3
A)Start with a file F(i) containing an ordered list of all permutations
of {0123456789}
B)User chooses a method, inputs required data(methods are simple
permutations of File F)
C)File is permuted accordingly.
D) GO back to 1B if user feels inclined to.
next i
Now you have the three mix files
Generation involves
n=1
Take the three F(i)'s and chose nth digit from each( notational F(i,n)=
nth digit of file i) then A) K=100*f(1,n)+10*f(2,n)+f(3,n)
if K>= 3*256 then n=n+1 go to A
Output K mod 256
goto A
There may be some steps missing, but this is very close to the skeleton
of the system.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Calculating the redudancy of english?
Date: Fri, 3 Nov 2000 15:14:43 GMT
JPeschel wrote:
> Simon Johnson [EMAIL PROTECTED] writes:
> >How does one calculate the redudancy of english?
> Use the index of coincidence.
No.
For a correct answer see Shannon's paper.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Is RSA provably secure under some conditions?
Date: Fri, 3 Nov 2000 15:22:04 GMT
Jan Fedak wrote:
> I wonder are there any conditions under which RSA is provably secure?
You would need to define your term "secure", but certainly
RSA can in principle be broken in principle, given sufficient
(modest) amount of ciphertext (assuming considerable
redundancy exists in the plaintext), by searching the
deciphering-key space for a value that converts the ciphertext
to a highly redundant (testable) output (putative plaintext).
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: ECC choice of field and basis
Date: 03 Nov 2000 16:37:10 GMT
NSA wears 2 hats. In this case, in speaking to NIST, they are wearing their
infosec hat, that is, goodness is the goal.
Don Johnson
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: index of coincidence of Spanish/Turkey
Date: Fri, 3 Nov 2000 15:38:10 GMT
[EMAIL PROTECTED] wrote:
> Do you know the IC of Spanish and Turkey?
> Are my values correct?
> german IC=0.0762
> english IC=0.0658
> french IC=0.0778
You're actually asking about the characteristic kappa values.
Delta IC by definition is around 1 for flat-random and > 1 for
a typical natural language.
If you have a collection of documents in the languages you
can compute their kappa yourself.
I'm not sure why you care. Since kappa is dependent on
alphabet size, it's not of much use.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Beale Cypher
Date: Fri, 3 Nov 2000 15:40:29 GMT
Set'em up Joe wrote:
> Looking for current opinions of ng on Beale, real vs. hoax.
There is information at the Crypto Drop Box at the ACA's
Web site http://www.und.nodak.edu/org/crypto/crypto/
My own opinion is that the available evidence is insufficient
to settle the question.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: is NIST just nuts?
Date: Fri, 3 Nov 2000 15:42:54 GMT
Greggy wrote:
> But wouldn't you agree that your assumption is that we know the best
> known attack? While the NSA knows all we know, we know nothing that is
> secret to them. So extra rounds are called for (assuming that you want
> to hide your traffic from EVERYONE).
That is a non sequitur. If NSA knows how to efficiently crack
Rijndael, it could crack any similar system with a comparable
amount of work. Adding rounds would accomplish nothing.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Rijndael Security
Date: Fri, 3 Nov 2000 15:53:01 GMT
ajd wrote:
> How secure is Rijndael when given (most of) the plaintext and the cipher
> text?
Well, one can then recover (most of) the plaintext.
> Given this information about the plaintext, and given the encrypted text,
> can the interceptor work out the key? It seems to me like we are giving away
> a bit too much information. Is there a standard to get around this problem?
This isn't a standards issue. You're basically just describing
the conditions suitable for what we call a "known plaintext"
attack on the system, which has the goal of recovering the key.
Practical cryptosystems need to be impervious to such attacks.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Give it up?
Date: Fri, 03 Nov 2000 16:53:26 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > >
> {snip]
> > > Another poster has already answered to this point. Do
> > > you agree that this known information does render the
> > > chance of analysis a bit higher, even if in practical
> > > cases that chance may still not be sufficient to effect
> > > a break? Note that DES has been broken by brute force,
> > > not by sophisticated, theoretically interesting,
> > > techniques in practice, as far as I know.
> >
> > Technically... well sure it would "help" but practically is a
different
> > story. With only 2^20 blocks from an AES cipher you do not have
enough
> > information to mount any form of attack (or on the full cipher
anyways)
> > which means brute force is still the only way to go. Sure you now
have
> > a method to test your key, but that doesn't matter.
>
> Remember we were discussing in the general context of
> whether compression CAN aid encryption. We were not assuming
> that one has a sufficiently strong encryption algorithm
> such that any 'aid' is superfluous from the very beginning
> and consequently the goal of discussion becomes vacuous.
> So if compression does helps to reduce the chance of
> the opponent in some attacks, that could be interesting,
> isn't it? We are discussing in this regard so to say
> 'theoretically' and not considering practical cases. In
> fact, strong adherents of AES would consider having that
> algorithm solves all security problems till eternity and
> would totally ignore anything else, whether compression
> or not.
Aw, but the benefit in terms of security is next to negible.
> Your sentence regarding OTP shows in my view that you have
> not properly understood the term 'perfect security' as
> defined by Shannon. Your arguments in some previous posts
> emphasize the practical security, claiming that opponent
> can't do certain things if the work is too large, and now
> you are arguing the theoretical security, claiming that
> almost anything can be broken. Isn't there a fundamental
> disparity? Anyway, I am done with this thread and I leave
> others to examine whether what you wrote above is sensible
> or that I am mistaken.
No, this shows you have to read my postings carefully. I said I could
guess an OTP key *(and never know it)*. Hence, in reality I could at
some point have read the real plaintext, I just can't determine it from
any other message.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
