Cryptography-Digest Digest #219, Volume #9 Wed, 10 Mar 99 13:13:05 EST
Contents:
Re: Letter Frequency English (Patrick Juola)
Re: Letter Frequency English (David Hamilton)
Re: Does RC4 have the same problems as OTP? (Steven Markowitz)
Re: Improving POP3/IMAP CRAM authentication (Solar Designer)
Re: Letter Frequency English (R. Knauer)
Re: Does RC4 have the same problems as OTP? (Jim Gillogly)
Re: Are there free RSA Software lib's ? (Rich Wales)
Re: ElGamal vs RSA (DJohn37050)
Where have I seen this? (Dan S. Camper)
Re: in response to RC4 stuff, plus TC1 (Jim Gillogly)
Wordsmithing: prepend/prefix [Re: in response to RC4 stuff, plus TC1] (Jim Gillogly)
Re: Limitations of testing / filtering hardware RNG's (Jim Felling)
Re: Does RC4 have the same problems as OTP? (Jim Gillogly)
Re: Limitations of testing / filtering hardware RNG's (R. Knauer)
Re: Something to think about... ("hapticz")
Re: Does RC4 have the same problems as OTP? (Kent Briggs)
Re: Does RC4 have the same problems as OTP? (Paul Rubin)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Letter Frequency English
Date: 10 Mar 1999 09:10:38 -0500
In article <7c5mpv$f2i$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>Hi
>
>Can anyone spare the time to give a rookie a basic listing of letter
>frequencies in spoken English.
Um.... there are no *letters* in spoken English; there are only letters
in transcriptions of spoken English, and their frequencies will (of
course) vary widely depending on how one chooses to transcribe the
speech.
If you're looking for letter frequencies of spoken-English-mangled-into-
semi-standard-written-English-spelling, get back to me in a few days
if no one's given you what you want. It will look an awful lot like
the standards for written English anyway, so you might as well just
use that.
-kitten
------------------------------
From: [EMAIL PROTECTED] (David Hamilton)
Subject: Re: Letter Frequency English
Date: Wed, 10 Mar 1999 14:17:32 GMT
=====BEGIN PGP SIGNED MESSAGE=====
[EMAIL PROTECTED] wrote:
>Hi
>
>Can anyone spare the time to give a rookie a basic listing of letter
>frequencies in spoken English.
>
>thanks in advance
- From a posting by David Hamer <[EMAIL PROTECTED]> to sci.crypt on 3rd August
1996.
* Comparative Table of Single-Letter Frequencies (%)
English German French Italian Spanish Portuguese
A 7.81 5.0 9.42 11.74 12.69 13.5
B 1.28 2.5 1.02 .92 1.41 .5
C 2.93 1.5 2.64 4.50 3.93 3.5
D 4.11 5.0 3.38 3.73 5.58 5.0
E 13.05 18.5 15.87 11.79 13.15 13.0
F 2.88 1.5 .95 .95 .46 1.0
G 1.39 4.0 1.04 1.64 1.12 1.0
H 5.85 4.0 .77 1.54 1.24 1.0
I 6.77 8.0 8.41 11.28 6.25 6.0
J .23 ..... .89 ..... .56 .5
K .42 1.0 ..... ..... ..... .....
L 3.60 3.0 5.34 6.51 5.94 3.5
M 2.62 2.5 3.24 2.51 2.65 4.5
N 7.28 11.5 7.15 6.88 6.95 5.5
O 8.21 3.5 5.14 9.83 9.49 11.5
P 2.15 .5 2.86 3.05 2.43 3.0
Q .14 ..... 1.06 .61 1.16 1.5
R 6.64 7.0 6.46 6.37 6.25 7.5
S 6.46 7.0 7.90 4.98 7.60 7.5
T 9.02 5.0 7.26 5.62 3.91 4.5
U 2.77 5.0 6.24 3.01 4.63 4.0
V 1.00 1.0 2.15 2.10 1.07 1.5
W 1.49 1.5 ...... ..... ..... .....
X .30 ..... .30 ..... .13 .2
Y 1.51 ..... .24 ..... 1.06 .....
Z .09 1.5 .32 .49 .35 .3
In order of frequency:
English: ETAONISRHLDCUPFMWYBGVKQXJZ
German: ENIRSADTUGHOLBMCFWZKVP (JQXY)
French: EAISTNRULODMPCVQGBFJHZXY (KW)
Italian: EAIONLRTSCDPUMVGHFBQZ (JXKWY)
Spanish: EAOSNIRLDUCTMPBHQGVYJFLZ (KW)
Portuguese: AEORSINDMTUCLPQVFGHBJZX (KWY)
* From: Elementary Cryptanalysis, Helen Fouche Gaines (1939)
End quote from David Hamer's posting.
- From an unattributed source, I have as the frequency per 1000 letters of the
8 most common letters:
E = 125
T = 90
R = 83
I = 76
N = 75
O = 74
A = 72
S = 58
And the 2 sources are different!
David Hamilton. Only I give the right to read what I write and PGP allows me
to make that choice. Use PGP now.
I have revoked 2048 bit RSA key ID 0x40F703B9. Please do not use. Do use:-
2048bit rsa ID=0xFA412179 Fp=08DE A9CB D8D8 B282 FA14 58F6 69CE D32D
4096bit dh ID=0xA07AEA5E Fp=28BA 9E4C CA47 09C3 7B8A CE14 36F3 3560 A07A EA5E
Both keys dated 1998/04/08 with sole UserID=<[EMAIL PROTECTED]>
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>
Comment: Signed with 2048 bit RSA key
iQEVAwUBNuZ71co1RmX6QSF5AQG79wf/bg6aXdXf5kbNIdj3uFnlnU+1NUHeu6Ii
wyyxruoHWdwlWnbyZGsVXQ9XH1wf06NdtZVJR6fufOp9Gj00j75NWJm0FxJNMM2G
b8Bpf3P9caSXyTsrnqo7/ArzUnwQ+OqMSQK6aw+2BmOk1XaC0BItXY75Ven9UOgs
EpXwdgyJ5F9Fw7xWlQnGiNXIfgKdCfVfyatTvzoqyzSmBxuLnT3hSdPRsX7EL/c6
m5plZcr9MdlxfsnTuz7hWua0dTdV5anLh39J4ny7ZJCTAYSOib5r1TC8kPP1fcn5
lZNZ2im6wv/aOj0yBFax+IgD9aKr/HGst0FpDicVrtiKpUr3vd4IPA==
=021n
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Steven Markowitz)
Subject: Re: Does RC4 have the same problems as OTP?
Date: 10 Mar 1999 14:49:00 GMT
In article <[EMAIL PROTECTED]> Kent Briggs <[EMAIL PROTECTED]>
writes:
>[EMAIL PROTECTED] wrote:
>
>> I read that if you use the same key to encrypt two messages that you can
>> weaken the RC4 security? Is that true?
>
>As with all stream ciphers, you need to add SALT to the key so that you
>never produce the same key stream twice. Otherwise, if one plaintext became
>known all plaintexts encrypted with the same key would be known.
With RC4, is it safe simply to append or prepend the salt to the key?
Are there any known related-key attacks that would make it necessary
to hash the salt and key together to be secure?
---- Steve
------------------------------
From: Solar Designer <[EMAIL PROTECTED]>
Subject: Re: Improving POP3/IMAP CRAM authentication
Date: 10 Mar 1999 14:48:44 GMT
In article <7c1nba$huj$[EMAIL PROTECTED]>, Alan DeKok wrote:
> > I've been reading the relatively recent RFCs on POP3 and IMAP protocol
> > extensions designed to support more secure authentication methods. What
> > I was looking for is a simple method (no public key crypto) that would
> > still always be better than plaintext authentication.
>
> They do exist. The problem is finding them, and telling people
> about them.
[...]
> There's almost always something similar in the literature. One of
> the ones I like is:
>
> http://www.sevenlocks.com/papers/authent/bird1.txt
Thanks, I'll read this later.
> > stored at the server:
> > hash = H(H(password))
> > the client needs to know:
> > H(password) (or the password, if entered manually each time)
> > session:
> > S: challenge = unique()
> > C: response = H(H(H(password)), challenge) ^ H(password)
> > S: if (H(H(hash, challenge) ^ response) == hash) auth_ok
>
> The hash at the server is plaintext equivalent: use salts.
Why is it plaintext equivalent? I am storing H(H(P)), while H(P)
is needed to authenticate. The XOR trick I am doing is somewhat
similar to encrypting H(P) with a stream cipher for transmission.
The worst problem (mentioned in my original post) I see with this
approach, is the fact that after a server compromise we're back to
the level of security we would have with plaintext authentication;
just like I've said, other C/R protocols proposed for POP3 or IMAP
don't offer even that.
Speaking of salts, I was going to add them in a real implementation,
as well as a variable iteration count for the inner hash. There're
still a few issues with probing for valid usernames, but I think I
know of a way to get around those.
> My suggestion:
>
> S = Salt
> P = password
> R = random number
>
> Stored by the server as the 'password' (ala 'crypt' and /etc/passwd)
>
> H_S = H(S+P)
>
> Sent by the server to the client on a connection:
>
> S,R
>
> Calculated by the client, and sent to the server:
>
> H(R + H(R + H(S + P)))
>
> Calculated by the server:
>
> H(R + H(R + H_S) = H(R + H(R + H(S + P))) from the client.
I don't see how this is safe from a server compromise: you're storing
H(S+P), and this is the only thing needed for a client to authenticate.
Perhaps when saying about being at least as secure as plaintext
authentication, even after a server compromise, we mean different
things. What I mean is:
1. Passwords are securely hashed on the server. That is, their
hashes aren't easier to brute-force than crypt(3) hashes would be.
2. It is impossible to authenticate with just the stolen hashes.
3. Unfortunately, it may be possible to get a suitable authentication
token for this protocol only (not the plaintext password, which might
be used on another system as well) -- with sniffing -- after the
attacker got access to the server's hashes -- but, just like I've
said, this is no worse than plaintext authentication and crypt(3).
Now, after thinking a bit more and looking up the archives of this
newsgroup of three months ago, I think there's a way to solve even
the remaining problem (plaintext authentication level of security
only, after a server compromise).
Bryan Olson has then pointed out a nice OTP-like C/R algorithm. If
used as described, it would have the following main limitation: the
server would need to update the password database (and probably sync
the write) at each authentication. This is often not acceptable.
However, this algorithm seems excellent for recovering after a server
compromise with my protocol; simply make the inner hash iterated a
variable number of times (which I was going to do anyway, despite
having to solve the username probing issues then), and decrease the
number of iterations when recovering after a compromise. :-)
> See 'Shneier, B., "Applied Cryptography, 2nd Ed."', p. 458, and RFC
> 2107 for information on MAC's.
You probably mean RFC 2104.
--
/sd
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Letter Frequency English
Date: Wed, 10 Mar 1999 15:13:48 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 10 Mar 1999 14:17:32 GMT, [EMAIL PROTECTED] (David
Hamilton) wrote:
>And the 2 sources are different!
The frequency distribution will depend on the kind of text.
Newspaper text is different from school book text, etc.
In Sherlock Holmes' story "The Gold Bug" the distribution used to
break the simple substitution cipher was ETAOINSHRDLU.
IIRC, that is. I memorized that sequence some 45 years ago.
Bob Knauer
"There's no way to rule innocent men. The only power any government
has is the power to crack down on criminals. Well, when there aren't
enough criminals, one makes them. One declares so many things to be
a crime that it becomes impossible to live without breaking laws."
--Ayn Rand
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Does RC4 have the same problems as OTP?
Date: Wed, 10 Mar 1999 08:35:32 -0800
Steven Markowitz wrote:
> With RC4, is it safe simply to append or prepend the salt to the key?
> Are there any known related-key attacks that would make it necessary
> to hash the salt and key together to be secure?
With RC4, if you allow a keyphrase of arbitrary length it's safer to
prefix the salt to the key rather than append (postfix? :) it, since
if the keyphrase is close to the 256-byte limit your salt will not
participate much in the mixing of the state table, leading to similar
key streams. Hashing them together is fine, as long as you're keeping
enough hash to avoid birthday paradox annoyances. 160 bits (e.g.
SHA-1) should be plenty for most applications. If you're not hashing,
the salt should be long enough to make related keys statistically
unlikely. Again, 160 bits should be plenty.
--
Jim Gillogly
18 Rethe S.R. 1999, 16:25
12.19.6.0.3, 11 Akbal 16 Kayab, Third Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Rich Wales)
Subject: Re: Are there free RSA Software lib's ?
Date: 10 Mar 1999 07:20:56 -0800
Bill Stewart wrote:
In the US and Canada, any use of RSA is subject to
RSA's patent.
Do you have a reference for the above claim, as regards Canada?
My understanding has been that the RSA algorithm is patented only in the
US, not Canada -- and that, as a result, residents of Canada are free to
use either RSAREF (which US law allows to be exported to Canada) or a
third-party implementation such as Phil Zimmermann's MPILIB.
Rich Wales [EMAIL PROTECTED] http://www.webcom.com/richw/
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: ElGamal vs RSA
Date: 10 Mar 1999 16:54:48 GMT
I would say that the correct comparison to make is the hard problem each is
based on. There are papers on how to do all these things in good way for all
hard problems.
For ANSI X9.30 defines DSA (DL), X9.31 defines rDSA (RSA and RW sigs) and X9.62
defines ECDSA, all are now ANSI standards. X9.42 defines DL-based key
agreement, X9.44 defines RSA key establishment and X9.63 defines EC key
establishment, all are drafts going thru the standardization process.
IEEE P1363 defines IF (RSA/RW), DL, and ECC signatures and RSA encryption and
DL/ECC key agreement. P1363a is expected to define RSA key agreement and DL/EC
encryption.
ISO DIS 14888-3 defines RSA/RW, DSA and ECDSA signature standards. These are
more general than ANSI, if one meets the ANSI standard then one will meet the
ISO standard, but not necessarily vice versa.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Dan S. Camper)
Subject: Where have I seen this?
Date: Wed, 10 Mar 1999 10:54:50 -0600
All:
Recently I've read -- somewhere -- about a scheme that supposedly allows
you to "reuse" a chunk of random numbers. The algorithm, if I remember
correctly, went something like this:
1) Generate a bunch of random numbers (a pad).
2) Generate random offsets into the pad.
3) When you need a random byte, extract the bytes from
the pad at the offsets and XOR them together to get
a single output byte.
4) Increment all the offsets, wrapping them to zero
in case of overflow.
5) The total key, in this case, becomes the pad and
the original list of offsets. I believe that the
original discussions indicated that the pad could
be reused for many messages and/or users, in which
case only the offsets need to be transmitted as keys.
I spent quite a while crawling through Deja News and a couple of other
archives trying to find discussions about this, with no luck. Does anyone
have any further information about it or can direct me to another source?
Thanks for your time!
DSC
____________________________________________________________________
Dan S. Camper [EMAIL PROTECTED]
Borrowed Time, Inc.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: in response to RC4 stuff, plus TC1
Date: Wed, 10 Mar 1999 08:22:40 -0800
[EMAIL PROTECTED] wrote:
> In article <[EMAIL PROTECTED]>,
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> > Jim Gillogly wrote:
> > > No, you prepend it to the key, ...
> >
> > Please, Jim, "prefix". "Prepend" has a wholly different meaning.
>
> One question do you actually output the salt too? I would think you need too.
Yes, you prefix :) it to the ciphertext as well as to the key.
In older systems (Enigma, M-209) this was called the "message key"
and independently encrypted before prefixing it, depending on the
practices of the communicators using it. This extra encryption is
not considered necessary in most stream cipher implementations of
which I'm aware.
--
Jim Gillogly
18 Rethe S.R. 1999, 16:19
12.19.6.0.3, 11 Akbal 16 Kayab, Third Lord of Night
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Wordsmithing: prepend/prefix [Re: in response to RC4 stuff, plus TC1]
Date: Wed, 10 Mar 1999 08:16:12 -0800
Douglas A. Gwyn wrote:
>
> Jim Gillogly wrote:
> > No, you prepend it to the key, ...
>
> Please, Jim, "prefix". "Prepend" has a wholly different meaning.
Used to: my OED (Oxford English Dictionary) has only one meaning for
it: to weigh mentally, ponder, consider; to premeditate. The meaning
you've argued for before (hang down in front) does not appear in the
OED, so I'm assuming you're trying to create a back-formation from
"prependant", which <is> in the OED. However, etymologically,
"prependant" is formed from "pre" (before) and "pendant" (hanging or
dangling), so verbing it into "prepend" seems to be as unsupportable
a neologism as "prepend" formed by analogy with "append". Since the
only attested meaning of "prepend" (consider, premeditate) was rare
when this OED edition came out, I unilaterally declare the word
abandoned and ripe for re-use. Note that the definition of English
is descriptive rather than prescriptive (unlike French or Icelandic),
and we have the "each man his own etymologist" approach to linguistic
evolution.
Your alternative, "prefix", does indeed have the appropriate meaning
(def. 4), and I grant that it's a more traditional way to say the
same thing. "Prepend", with the meaning I ascribed to it, is common
in the field, and is attested in the On-line Computing Dictionary and
Dictionary.com.
--
Jim Gillogly
18 Rethe S.R. 1999, 15:52
12.19.6.0.3, 11 Akbal 16 Kayab, Third Lord of Night
------------------------------
Date: Wed, 10 Mar 1999 11:27:49 -0600
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Limitations of testing / filtering hardware RNG's
You are still vulnerable at your random source in a physical generator.
Assume for this example it is a radioactive source generator. The detector is
either a single point of failure, or TMR is just testing 3 separate sources, and
will be useless as to detecting failures.(all generators will be flagged very
quickly as candidates for repair). Thus we have a potential source of
uncorrectable propagating error or a simplest target for subversion.
Comments?
"R. Knauer" wrote:
> On 10 Mar 1999 08:18:39 GMT, [EMAIL PROTECTED] (Mark Currie)
> wrote:
>
> >In the real world electronic systems can fail, and they don't always fail in
> >a nice easily detectable way, such as "stuck at 0/1".
>
> One way to circumvent that problem is to employ triple modular
> redundancy (TMR) techniques. TMR is used in mission critical
> applications like space flight and nuclear power plants.
>
> For those who might not be familiar with TMR, simply put it is a
> system which has three identical circuits for every subsystem, and
> these three circuits are constantly moniroted for majority vote. If
> one of the three votes "incorrectly", as measured by the other two
> circuits, the majority vote is taken to be correct, and the subsystem
> is flagged for repair. If there is no majority, as in an analog
> circuit, then the subsystem is shut down.
>
> In such manner, a defective subsystem of a TRNG could be isolated if
> it started behaving incorrectly.
>
> Bob Knauer
>
> "There's no way to rule innocent men. The only power any government
> has is the power to crack down on criminals. Well, when there aren't
> enough criminals, one makes them. One declares so many things to be
> a crime that it becomes impossible to live without breaking laws."
> --Ayn Rand
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Does RC4 have the same problems as OTP?
Date: Wed, 10 Mar 1999 09:28:03 -0800
Kent Briggs wrote:
> 160 bits sounds like massive overkill for salt. Unless you are planning on
> sending more than a trillion messages encrypted with the same key, 40 bits will
> probably do in most situations.
Eek! That means with 1.2 million messages there's a 50% chance you've
picked the same salt twice. That "trillion" ignores the birthday
paradox. For many applications (e.g. IP messages in a router) you
could run up that kind of traffic (1.2 million) in a hurry. I picked
160 so that the square root of it would be substantially bigger than
you want to store for a birthday attack. I grant that for modern
systems 128 bits would be enough, and even 64 bits would be a severe
nuisance to archive enough for a birthday search, but 40 bits is too
close to the hairy edge for my taste. I prefer a little more headroom
on my systems, especially since it's not much more expensive to gather
160 bits than 40.
--
Jim Gillogly
18 Rethe S.R. 1999, 17:16
12.19.6.0.3, 11 Akbal 16 Kayab, Third Lord of Night
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Limitations of testing / filtering hardware RNG's
Date: Wed, 10 Mar 1999 17:32:18 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 10 Mar 1999 11:27:49 -0600, Jim Felling
<[EMAIL PROTECTED]> wrote:
>You are still vulnerable at your random source in a physical generator.
>Assume for this example it is a radioactive source generator. The detector is
>either a single point of failure, or TMR is just testing 3 separate sources, and
>will be useless as to detecting failures.(all generators will be flagged very
>quickly as candidates for repair). Thus we have a potential source of
>uncorrectable propagating error or a simplest target for subversion.
Yes, you are right. Only the classical parts of the system can be made
redundant. That is why it is essential to run periodic offline
diagnostics.
Bob Knauer
"There's no way to rule innocent men. The only power any government
has is the power to crack down on criminals. Well, when there aren't
enough criminals, one makes them. One declares so many things to be
a crime that it becomes impossible to live without breaking laws."
--Ayn Rand
------------------------------
From: "hapticz" <[EMAIL PROTECTED]>
Subject: Re: Something to think about...
Date: Wed, 10 Mar 1999 12:42:38 -0500
well said. often crosses my mind too! i think it's like them having a
"comfort zone" where as long as they know what is being used they feel "in
control", despite being able/unable to actually break the msgs.
suppose it has to do with the maddening grip of power they seem to think
they have!
(see various R. Knauer's msg append for good appraisal of government
mentality)
--
best regards
[EMAIL PROTECTED]
------------------------------
From: Kent Briggs <[EMAIL PROTECTED]>
Subject: Re: Does RC4 have the same problems as OTP?
Date: Wed, 10 Mar 1999 16:42:09 GMT
Jim Gillogly wrote:
> Tom: the "salt" is a suitably long randomly-chosen number that you
> tack on the beginning of the key. It's included in the clear in the
> message so the recipient knows how to modify the key. It should be
> long enough that the chance of accidentally getting the same one
> twice is negligable -- e.g. 160 bits or so. See the CipherSaber
> page for an example: http://ciphersaber.gurus.com .
160 bits sounds like massive overkill for salt. Unless you are planning on
sending more than a trillion messages encrypted with the same key, 40 bits will
probably do in most situations.
--
Kent Briggs, [EMAIL PROTECTED]
Briggs Softworks, http://www.briggsoft.com
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Does RC4 have the same problems as OTP?
Date: Wed, 10 Mar 1999 17:08:35 GMT
In article <[EMAIL PROTECTED]>,
Kent Briggs <[EMAIL PROTECTED]> wrote:
>160 bits sounds like massive overkill for salt. Unless you are
>planning on sending more than a trillion messages encrypted with the
>same key, 40 bits will probably do in most situations.
If the salt is random, make that a million or so messages, not
a trillian. For a trillion, use 80 bits (birthday paradox).
------------------------------
** 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
******************************
