Cryptography-Digest Digest #927, Volume #8 Mon, 18 Jan 99 14:13:04 EST
Contents:
Re: Cayley-Purser algorithm? (Jerry Leichter)
Re: SSL - How can it be safe? ([EMAIL PROTECTED])
Re: Some Non-Random DES Characteristics ([EMAIL PROTECTED])
encryption and electronic banking ("Despontin M.")
Re: General (but detailed enough) description of RC4... (Doug Stell)
Re: SSL - How can it be safe? (Doug Stell)
Re: General (but detailed enough) description of RC4... (Casey Sybrandy)
Re: HIGH ENTROPY ENCRYPTION IS A MUST!! (Markus Kuhn)
Re: Why does the GOP hate encryption? [no PGP content] (Anonymous)
Re: On the Generation of Pseudo-OTP (Jim Felling)
----------------------------------------------------------------------------
From: Jerry Leichter <[EMAIL PROTECTED]>
Subject: Re: Cayley-Purser algorithm?
Date: Mon, 18 Jan 1999 10:14:11 -0500
| > > Sorry. Once the method has been published, it CAN NOT be patented
| > > in the US.
|
| > You have up to one year to file after initial publication. There
| > was a big stink made about the Diffie-Hellman patent because it was
| > filed over a year past initial publication.
|
| I have been through 2 patent applications in the last 6 months. And
| will probably go through 2 more in the coming year.
|
| You MUST file at least a provisional application before publishing.
| Once you file a provisional application you have a year to file the
| full application. But you can not publish first.
Sigh. This has already started all kinds of silly responses.
*Traditionally*, *US* law gave you one year after publication to file.
No provisional application was necessary; in fact, I don't recall ever
hearing the term before. Just about every other country in the world -
perhaps, indeed, *every* other country - required filing before the
first publication. (In any case, publishing before filing in the rest
of the world would have been a very stupid move: While the US rule has
been that the patent goes to the "first to invent" a thing, in the rest
of the world, it went to the "first to file". Someone who read your
publication and filed a couple of minutes before you did would end up
with the patent on your work.)
Over the last couple of years, US intellectual property law has changed
in significant ways in an attempt to "harmonize" it with IP law in the
rest of the world. There was a push to go to the "first to file"
system, though I believe it was turned back - other adjustments (mainly
in the term of patents) were made instead. I haven't really kept up
with this. I have no idea what's happened with publication. I'm
skeptical that the law would have changed so drastically, but you never
know. If Mr. Silverman's lawyers are telling him he can't publish
before a provisional application, they presumably know what they are
talking about - though you'd have to find out exactly *why*. It's
possible they are concerned about non-US rights; it's possible that US
law still gives you one year to file after publication, but gives you a
longer patent term if you file first. It could be none of these, but
simple prudence.
In any case, even if the law changed, it would have no effect on the
validity of US patents already granted under the old US rules.
-- Jerry
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: SSL - How can it be safe?
Date: Mon, 18 Jan 1999 15:20:38 GMT
In article <[EMAIL PROTECTED]>,
fungus <[EMAIL PROTECTED]> wrote:
> It invents a new key for each connection.
I have often wondered how this works. I hope someone could answer this for
me.
Scenario
========
1. User goes to website to buy something with browser (that supports SSL)
2. The browser is sent the website's public key (correct)?
3. The browser generates a random session key then encrypts it with the
public key.
4. The server gets the msg, decrypts it with its private key and then uses
the newly received key for the SSL session (maybe replies saying it has been
received).
5. The user enters their credit card information and such then hits submit.
The browser encrypts the data with the session key and sends it to the server
who then decrypts it.
Is this correct? How is the session key not crackable? I assume the public
key stuff is 40/128bit (depending on version user has).
Granted breaking the session key would only give you the session info, but
isn't that enough (ala credit card #)? How is the session key generated
(conceptually)?
As a side note, what happens in step #2 if someone else sends them their
public key instead (man in the middle)?
Thanks...
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Some Non-Random DES Characteristics
Date: Mon, 18 Jan 1999 15:24:47 GMT
In article <77thag$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Gregory G Rose) wrote:
> In article <77ietq$rh0$[EMAIL PROTECTED]>,
> <[EMAIL PROTECTED]> wrote:
> >
> >
> > Some Non-Random DES Characteristics
>
> There's a logical flaw in some of your argument
> (although many of your points remain valid).
Gregory:
Thanks for your review. In fact, you bring a most valuable distinction to the
table, but one which can be easily resolved as I comment below. Yet, it will
need an addition to the text, to make it clear.
>
> Using arguments based on 1.2 to 2 bits of entropy
> per character in English text, you get 3 to 300
> "english like" plaintexts which need to be
> disambiguated.
Yes, and I understand you agree with that. The text so summarizes it, in item
(e) of Section 2:
|Therefore, comparing with the total number of 2^64 possible plaintexts, I
|expect (on average) to have to disambiguate the correct text from a very
small |number of false English-looking plaintexts, in the range of 3 ~ 300.
> You then claim these can be
> distinguished based on things like digraph and
> trigraph frequencies. This is incorrect... because
> it is exactly things like the digraph frequencies
> which reduce the entropy of english text from the
> 5 bits per character if you simply have
> equiprobably alphabetic characters.
>
You are correct about the entropy of English text and indeed the analysis done
in item (e), which I quote above, is based on it and thus must include the
statistical influence of all unigrams, digrams, trigrams, etc.
However, that claim which you question is made on item (f) and is distinct in
form and substance from the one in item (e), albeit it is coherent with it (as
it must). Let me discuss form and substance in separate.
FORM: Item (e) uses the entropy of English-text to obtain a statistical
estimate of the number of *all* English-looking sentences that have an 8-byte
length -- however, we can neither detect any such English-looking sentence by
using the results from item (e) nor can we expect all such sentences to exist
in English. That task is taken up in item (f), which coherently uses the same
information that was used to derive the entropy used in item (e), but now
being used byte-by-byte -- so that, given a detection threshold, I can now
detect whether an 8-byte string is English-looking or not. I can also
introduce a dictionary search in order to validate any English-looking word
and this becomes also part of the detection threshhold. I call attention to
the need to define a *detection threshhold* in item (f), which is a detection
problem, whereas the same need is absent in item (e) -- which just integrates
*all* possibly expected occurrences, on average.
The question now, as you very well pose it, is why should we expect *less*
occurrences from counting *all* detected English-looking sentences in item (f)
as compared with the statistical estimate for *all* occurrences of
English-looking text?
The answer, which needs to be explained in that item, is that item (e)
introduces a detection threshold -- which must be specified. This is better
explained in the companion text http://www.mcg.org.b/unicity.txt -- in section
9:
|Given the cost of a false detection, the cost of a miss, and their
|probabilities, which can be translated in detection theory in terms of
accuracy |and reliability [Ger98], one can calculate the best threshold (in
terms of |number of letters, digrams, trigrams, and so on frequencies,
dictionary entry |confirmation, known plaintext confirmation, etc.) that will
minimize |cost.
Thus, in other words, the result given in item (e) is an average that counts
as valid any occurrence of 8-byte words such as "IN NO IS", "LAT WHEY",
"CRATICT ", "FROURE B", "PONDENOM", "REPTAGIN", etc. as given by Shannon
[Sha48] -- that ALL contain valid unigram, digram and trigram English
statistics. But, in item (f) we need to (and, we can) introduce a detection
threshold for the probability of occurrence of a *valid* 8-byte string --
which may be 0.5 or 0.2 or whatever we may obtain from our linguistic model
over a dictionary of actual words and word sequences which were pre-selected
(given the cost of a miss, etc.).
The (attacker chosen) detection threshhold is therefore that which reduces
all occurrences as *estimated* by entropy in item (e) to a (possibly) lesser
number of "all detected occurrences" as measured in item (f).
Which leads to the substance difference:
SUBSTANCE: item (f) concerns itself with the practical question of finding
8-byte English-looking texts from a set of 2^56 8-byte strings -- which is
solved as a detection problem by defining a threshhold minimum probability
and resorting to probability tables of unigram, digram, trigram, words, etc.
and even expected plaintext as explained later on (magic numbers, etc.). On
the other hand, item (e) uses the entropy to otain an average estimate for a
larger set -- the set of *all* possible English-looking 8-byte strings.
One can view item (e) as providing a theoretical estimate of the problem`s
complexity and item (f) as providing a practical tool to solve it. Which
practical tool has a "control knob" given by the detection threshhold.
> In other words, your selected candidates will, by
> definition, pass the digraph and trigraph
> frequency tests, and any other such tests.
>
Yes, but with different probabiliites -- which are then either accepted or
rejected by comparison with the detection threshhold which is defined in item
(f). Which reduces the number of final occurrences as a funtion of the
detection threshhold -- higher threshhold, less occurrences.
Thank you for calling attention to an alternate reading of the text -- which I
need to disambiguate.
The relevant new text for item (e) is now:
Therefore, comparing with the total number of 2^64 possible plaintexts, I
expect (on average) to have to disambiguate the correct text from a very
small number of false English-looking 8-byte plaintexts, in the range of 3 ~
300. I note that this number includes 8-byte plaintexts which are not
English-valid, even though they are English-looking, such as "IN NO IS", "LAT
WHEY", "CRATICT", "FROURE B", "PONDENOM", " REPTAGIN", as given by Shannon
[Sha48], as they all contain valid unigram, bigram and trigram English
statistics.
And, the new item (f) is:
f. Thus, DES decipherment under brute-force assumptions has been
reduced to a simple English plaintext selection problem -- even when
text compression is used before encipherment. As Shannon [Sha49]
showed 50 years ago, this can be done using standard English letter
frequencies, digram and trigram frequencies, dictionaries and even
known plaintext -- in what is essentially a detection problem. This
introduces the need to define a detection threshhold, which defines
the minimum probability that an acceptable 8-byte string must have
under the language model defined by the attacker. This chosen
detection threshhold reduces the number of possible plaintext messages
from the total value given in item (e) above to a possibly much lesser
value; given the cost of a false detection, the cost of a miss, and
their probabilities, which can be translated in detection theory in
terms of accuracy and reliability [Ger98], one can calculate the best
threshold (in terms of number of letters, digrams, trigrams,
and so on frequencies, dictionary entry confirmation, known plaintext
confirmation, etc.) that will minimize cost. For example, the known
result in [Sha49] is that one should need an average of 5-characters
to disambiguate one English message -- this is the unicity distance
for plaintext English. Since we have 8-characters in a DES block,
Shannon [Sha49] showed thus that we should expect no large
difficulties to disambiguate one correct English message from the set
of all possible English-looking 3 ~ 300 samples. However, if not one
but even all 3 ~ 300 messages are left, this would already allow the
corresponding 3 ~ 300 keys to be directly used to decipher just one
more block as considered next, with large benefit.
f. Thus, DES decipherment under brute-force assumptions has been
reduced to a simple English plaintext selection problem -- even when
text compression is used before encipherment. As Shannon [Sha49]
showed 50 years ago, this can be done using standard English letter
frequencies, digram and trigram frequencies, dictionaries and even
known plaintext -- in what is essentially a detection problem. This
introduces the need to define a detection threshhold, which defines
the minimum probability that an acceptable 8-byte string may have
under the language model defined by the attacker. This chosen
detection threshhold reduces the number of possible plaintext messages
from the total value given in item (e) above to a possibly much lesser
value; given the cost of a false detection, the cost of a miss, and
their probabilities, which can be translated in detection theory in
terms of accuracy and reliability [Ger98], one can calculate the best
threshold (in terms of number of letters, digrams, trigrams,
and so on frequencies, dictionary entry confirmation, known plaintext
confirmation, etc.) that will minimize cost. For example, the known
result in [Sha49] is that one should need an average of 5-characters
to disambiguate one English message -- this is the unicity distance
for plaintext English. Since we have 8-characters in a DES block,
Shannon [Sha49] showed thus that we should expect no large
difficulties to disambiguate one correct English message from the set
of all possible English-looking 3 ~ 300 samples. However, if not one
but even all 3 ~ 300 messages are left, this would already allow the
corresponding 3 ~ 300 keys to be directly used to decipher just one
more block as considered next, with large benefit.
Comments?
Cheers,
Ed Gerck
______________________________________________________________________
Dr.rer.nat. E. Gerck [EMAIL PROTECTED]
http://novaware.com.br
--- Meta-Certificate Group member -- http://www.mcg.org.br ---
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "Despontin M." <[EMAIL PROTECTED]>
Subject: encryption and electronic banking
Date: Mon, 18 Jan 1999 16:45:59 +0100
Hi,
I am looking for easy-to-understand information in English, German, Dutch or
French, not too technical, about encryption used for electronic banking.
Kind regards,
Nele.
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: General (but detailed enough) description of RC4...
Date: Mon, 18 Jan 1999 16:55:05 GMT
On Mon, 18 Jan 1999 16:01:33 +0100, Bartosz /Lakomiec
<[EMAIL PROTECTED]> wrote:
>
> Hi, everybody,
>
> I'm not interested in RC4 pseudo/source code and inner workings
> but I would like to learn its 'external' specifications that
> are needed from the cryptography implementators' point of view:
>
> - input data formatting required (if any)
Simply octets. RC4 generates a stream of octets, which it XORs with
the data octets.
> - key size
Variable, up to 2048 octets. Any key you provide is simply used
repeatedly until 2048 octets are input to the key setup function.
> - key generation method
This is external to RC4. RC4 does have an internal key setup function
that turns the key into 256 octets of "state."
> - encryption/decryption synchronization method
This is external to RC4. Both encryption and decryption instances of
RC4 must a) use the same key and b) must have process the same number
of octets since the key setup function was last run. Otherwise, your
states are out of sync.
Remember that for stream ciphers you must never encrypt twice with the
same key/state. If you do, the plaintext can be recovered from the XOR
of two plaintext/ciphertext streams and then the RC4 stream can be
recovered, even without knowing the key or the state.
Also, remember that you can not use an appended error detection scheme
with stream cipher. If you do, message extension attacks are
possible.
> During last several months I browsed tens cryptography sites
> but there is no word about this algorithm anywhere.
> I know that RSA published technical report on RC4 (TR-401, 1992)
> but I can't find it on-line.
> If you could point out any Web resource on RC4 I will be incredibly
> grateful.
Try Rivest's own web page.
> I'm working on a Point-to-Point Protocol encryption extension
> and (apart from block ciphers) I would like to consider RC4
> as an example of a stream cipher. As I know this is the only stream cipher
> that is found in several serious networking products.
It's used in this context, because of its great speed. I worked on one
of those products. That product's synhronization method simply dropped
the connection and renegotiated the shared key, if it detected that it
was out of cryptosync.
A stream cipher can also be built out of any block cipher. Contrary to
the opinion of one loon in this newsgroup, this method does not
"suck."
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: SSL - How can it be safe?
Date: Mon, 18 Jan 1999 17:07:03 GMT
On Mon, 18 Jan 1999 15:20:38 GMT, [EMAIL PROTECTED] wrote:
>In article <[EMAIL PROTECTED]>,
> fungus <[EMAIL PROTECTED]> wrote:
>
>> It invents a new key for each connection.
>
>I have often wondered how this works. I hope someone could answer this for
>me.
>
>Scenario
>--------
>
>1. User goes to website to buy something with browser (that supports SSL)
>
>2. The browser is sent the website's public key (correct)?
Correct. The public key is contained in a certificate and the CA's
key, used to verify the certificate, is known to the browser a priori.
>3. The browser generates a random session key then encrypts it with the
>public key.
Correct, assuming an RSA key transport mechanism. SSL does permit
other key agreement methods, such as Diffie-Hellman.
>4. The server gets the msg, decrypts it with its private key and then uses
>the newly received key for the SSL session (maybe replies saying it has been
>received).
Correct, assuming an RSA key transport mechanism. This key is the
master key and session keys for the encryption and integrity functions
in each direction are derived from the master key by repeatedly
hashing it with various constants.
>5. The user enters their credit card information and such then hits submit.
>The browser encrypts the data with the session key and sends it to the server
>who then decrypts it.
Correct.
>Is this correct? How is the session key not crackable? I assume the public
>key stuff is 40/128bit (depending on version user has).
No, it is the data encryption key that is 40/128 bits. The public key
used for master key transport or agreement is much longer, 512/1024
bits. The international version is limited to a 512-bit key by the
U.S. export regulations.
>Granted breaking the session key would only give you the session info, but
>isn't that enough (ala credit card #)?
You get only what's encrypted under that one session.
> How is the session key generated (conceptually)?
Hashing of a randomly generated master key in the RSA method or the
output of the key agreement computation in the D-H method.
>As a side note, what happens in step #2 if someone else sends them their
>public key instead (man in the middle)?
That's where signed certificates come in. The MITM must have a
certificate issued by a CA that the browser trusts. The user must
trust the name that is in that certificate.
------------------------------
From: Casey Sybrandy <[EMAIL PROTECTED]>
Subject: Re: General (but detailed enough) description of RC4...
Date: Mon, 18 Jan 1999 11:54:09 -0500
Input formatting: that would depent on you. The algorithm does not have any
set requirement for the formatting of the input. Theoretically, you can have a
256 character key and RC4 can use it.
Key generation: PRNG's, enrypting dummy plaintext, etc. There are no
specifications for key generation for RC4.
Synchronization: you would have to syncrhonize each end yourself. RC4 is just
a simple block cipher designed to run in OFB all the time, thus it cannot
synchronize itself.
As for anything else, it's fast, it resists most attacks I think. The only
attack I've really seen published against RC4 was a related key attack, I
think. Hope this helps.
Bartosz /Lakomiec wrote:
>
> Hi, everybody,
>
> I'm not interested in RC4 pseudo/source code and inner workings
> but I would like to learn its 'external' specifications that
> are needed from the cryptography implementators' point of view:
>
> - input data formatting required (if any)
> - key size
> - key generation method
> - encryption/decryption synchronization method
> - ...
>
> During last several months I browsed tens cryptography sites
> but there is no word about this algorithm anywhere.
> I know that RSA published technical report on RC4 (TR-401, 1992)
> but I can't find it on-line.
> If you could point out any Web resource on RC4 I will be incredibly
> grateful.
>
> I'm working on a Point-to-Point Protocol encryption extension
> and (apart from block ciphers) I would like to consider RC4
> as an example of a stream cipher. As I know this is the only stream cipher
> that is found in several serious networking products.
>
>
> -------------------------------------------------------------------------
> Bartek Lakomiec
> [EMAIL PROTECTED]
> -------------------------------------------------------------------------
------------------------------
From: [EMAIL PROTECTED] (Markus Kuhn)
Subject: Re: HIGH ENTROPY ENCRYPTION IS A MUST!!
Date: 13 Jan 1999 11:27:22 GMT
[EMAIL PROTECTED] writes:
|> What I mean by perfect encryption. Perfect encryption
|> is such that the total entropy is added to the entropy
|> of the data in the best way possible. Note the total
|> entropy of data and encryption can never exceed that
|> of the total message being encrypted. Also note
|> the entropy added can never exceed the key length that
|> is used to represent the state of the file. Which
|> for IDEA for example is 128.
Some Claude E. Shannon has already been there fifty years
ago (see the nice introduction to the relationship between
information theory and cryptography in intro crypto
textbooks such as Douglas R. Stinson: Cryptography -
Theory and Practice, CRC Press, 1995, 448 pages,
ISBN 0-8493-8521-0.
Entropy is a pretty lousy concept for measuring
security of crypto parameters, a very commonly
made mistake:
Consider the following key generator: 50% of the
keys are a 1024-bit string of all zeros, the other
50% are uniformy distributed truely ramdom 1024-bit
strings. The entropy of this key generaor is
obviously
sum p*log_2(1/p) = 0.5 * log_2(1/0.5) +
2^1024 * 0.5 * 2^-1024 * log_2(2 * 2^1024) =
0.5 * 1 + 0.5 * 1025 = 513 bit
A key with 513 bit entropy sounds pretty secure, yet you can
easily break 50% of all messages by guessing that they
have been encrypted with the all zero key. Entropy is
somewhat irrelevant here, the maximum probability
(or minimum decision content) of every possible key
is of much more concern for security.
Similar conclusions also apply to the plaintext, on which
your discussion was focussing. It is better not to talk
about entropy unless you have fully understood what it
means.
Markus
--
Markus G. Kuhn, Computer Laboratory, University of Cambridge, UK
Email: mkuhn at acm.org, WWW: <http://www.cl.cam.ac.uk/~mgk25/>
------------------------------
Date: 18 Jan 1999 17:38:46 -0000
From: Anonymous <[EMAIL PROTECTED]>
Subject: Re: Why does the GOP hate encryption? [no PGP content]
> Does anyone actually believe that the Republican party is any more
> sympathetic to the cause of popular encryption than the Dems? Come
> on, gimme a break. I don't give a rat's ass about Clinton's current
> troubles, what bothers me is the way he and Gore backpeddaled on
> this issue. Long criticized for co-opting republican ideas, he did
> the same with this one. Anti-encryption/pro law enforcement in this
> regard is a totally Republican agenda. Clinton sold us out on this
> one. The Republicans will be the ones to just slam this door shut on
> privacy.
Governments fear what they cannot control. And what a government cannot
control it feels compelled to destroy.
Citizens are tolerated only becuase they generate income for the
government in the form of taxes and fees. This is why they can't
arrest EVERYbody; there'd be no one left to guard the prisoners
and no one to pay the politicians' salaries. But They need only
arrest a few "ringleaders" to "send a message" to the public as
to which behavior is allowed and which is not.
Steve
------------------------------
Date: Mon, 18 Jan 1999 12:09:55 -0600
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: On the Generation of Pseudo-OTP
"R. Knauer" wrote:
> On Fri, 15 Jan 1999 16:18:34 -0600, Jim Felling
> <[EMAIL PROTECTED]> wrote:
>
> >The only reason I mentioned that condition is that we are effectively
> >limited to sampling a limited(if rather large) subset of such a number,
> >and therefore must be concerned with the properties of that subset, and
> >not of the system as a whole.
>
> Somewhere along the way I lost what you were trying to get across. If
> you feel it is important to this discussion, please restate it.
> Thanks.
>
> <snip signature>
What the above comment is in response to is:
I had said that if a 'real' number such as pi is used as a OTP source it
must be evaluated as to its statistical behavior in the 'locality' that the
data is drawn from as it is guaranteed to have good statistical properties
only over the whole of its decimal expansion and not over any finite
subregion however large. Someone then brought up the excellent point that
this is also true of a TRNG. My above comment is in response to that
point.We must (due to our computing methods) evaluate it over a large and
finite subset, and thus should take pains to assure ourselves that that
subset has appropriate statistical behaviors. With a TRNG we are
effectively sampling from a continuous spectrum and thus avoid the problem
of potential analysis of the 'space' from which we draw our numbers. Were we
able to chose in a repeatable way a completely arbitrary starting point in
the number being used and generate digits from that point we would be free
of that, but we possess no such algorithm( we possess a digital expansion
algorithm, but it will balk at giving us digits starting at an arbitrary
2^(2^(2^1000)) digit number simply due to the amount of storage such a
humongeous number will entail. Continuous processes are free of this limit
and therefore in my opinion do not need to comply to a condition specifying
'good behavior' in the subset being evaluated.
------------------------------
** 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
******************************
