Cryptography-Digest Digest #194, Volume #10 Tue, 7 Sep 99 15:13:04 EDT
Contents:
Re: Linear congruential generator (LCG) (Tony Wingo)
Re: _NSAKey ("karl malbrain")
Re: Ways to steal cookies in HTTP and HTTPS (Nick Kew)
Re: THINK PEOPLE (Frank Gifford)
Re: ECC and smart card (Medical Electronics Lab)
Re: "Simple question" about DES (John Savard)
Re: SQ Announcement ("Kostadin Bajalcaliev")
Re: NSA and MS windows ([EMAIL PROTECTED])
Re: SQ Announcement ("Kostadin Bajalcaliev")
Re: NSA and MS windows ("Trevor Jackson, III")
Re: NSA and MS windows ([EMAIL PROTECTED])
Schoof-Elkies-Atkin implementation ("Michael Scott")
Re: ECC and smart card (Matthias Bruestle)
Re: Beale (was: Mystery inc.) ([EMAIL PROTECTED])
----------------------------------------------------------------------------
Date: Tue, 07 Sep 1999 09:34:28 -0700
From: [EMAIL PROTECTED] (Tony Wingo)
Subject: Re: Linear congruential generator (LCG)
In article <[EMAIL PROTECTED]>, David Goodenough
<[EMAIL PROTECTED]> wrote:
>On Tue, 07 Sep 1999 15:54:04 +0200, Terje Mathisen
><[EMAIL PROTECTED]> wrote:
>
>>Kwong Chan wrote:
>>>
>>> A linear congruential generator is defined as
>>>
>>> x(t)=ax(t-1)+b mod n
>>>
>
>However, on the subject of LCG's, I seem to remember that a certain
>operating system once used a LCG as it's "random number generator"
>(sic), that had a strong tendancy for the lower bits to go in a
>repeating cycle. Is this just a property of that particular poor
>choice of a and b, or is this a problem with all LCG's
Actually, it is a poor choice of n. If n is of the form 2^n, then the low
bit goes 0, 1, 0, 1, 0, 1 ....
If n is prime, the low bits behave much better. I don't have my copy of
Knuth here, so I can't quote chapter and verse. However, Volume 2 will
tell you more than you ever really wanted to know about LCG's.
Keep in mind that even with prime modulus, LCG's are still not the best
choice for applications requiring long period and low serial correlation.
-t
------------------------------
Reply-To: "karl malbrain" <[EMAIL PROTECTED]>
From: "karl malbrain" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: _NSAKey
Date: Tue, 7 Sep 1999 09:51:16 -0700
Trevor Jackson, III <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Microsoft Mail Server wrote:
>
> > good point, the assumtion that the government is vile, devious, sinless,
and
> > above the law has been created from single examples of deviant
individual
> > misbehavior on the part of selected events.
> >
> > the usual attack upon a working system of government is to discredit and
> > find the unremarkable errors that occur in any system that deals with
human
> > irresponsiblities.
STOP TRYING TO TOLERATE IT and take responsibility.
> > comparing one system to another will only yield nothing other than
> > differences that have evolved over years of human squabbling and foolish
> > "pride-mongering".
> >
> > that an individual feels a personal incursion upon their individual
> > "rights", that individual certainly needs to evaluate the need for all
> > other's right's to the same freedoms. (or go find another system that
treats
> > you better!)
> >
> > keep in mind that wars and conflicts are usually precipitated over years
of
> > discontent and malingering stupidities. (and selfish, arrogant familial
> > hierarchy systems)
> >
> > the need for privacy and secrecy goes "out the window" really fast when
> > bullets start whizzing closely past your childrens' faces!
>
> The need for privacy and secrecy becomes a dominating influence in one's
life
> when one expects to mix bullets and one's children.
Try ARMY and NAVAL intelligence for more answers. Karl M
------------------------------
From: [EMAIL PROTECTED] (Nick Kew)
Crossposted-To: comp.infosystems.www.misc,comp.security.misc
Subject: Re: Ways to steal cookies in HTTP and HTTPS
Date: Mon, 6 Sep 1999 15:51:24 +0000
> GET ...
> browser --------------------------------------> intruder
>
> GET ...
> intruder --------------------------------------> server
You missed the point "isoma" already tried to tell you.
* Browser sends server's cookie (if any) to server. Not to intruder.
* Browser sends intruder's cookie (if any) to intruder. Not to server.
Now, what has intruder gained?
> (scheme that looks like a proxy server)
A proxy server sees all the information in transit. If the entire transaction
is going via your "intruder", then a cookie is the least of your problems.
--
Nick Kew
------------------------------
From: [EMAIL PROTECTED] (Frank Gifford)
Subject: Re: THINK PEOPLE
Date: 7 Sep 1999 13:52:34 -0400
In article <7qslrb$5su$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>In article <7qpf08$12hg$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
>> And the same encryption key and program used for all three files.
>> Two of the encrypted files where obtain in tact ( well since you have the key
>> who cares) but the third encrypted file for which the plaintext is missing but
>> is known to be the same except for a small portion in the middle has a 100
>> bytes missing from the end.
>> The point is if you use any of the AES methods with the 3-letter blessed NSA
>> chaining methods. Which have passed the high standards of the NSA so they
>> must be good. You can recover the missing portion of the text. Not so with
>> a program like mine. Becasue I don't use the offical blessed chaining methods
>> since I feel the term "error recovery" is a PR term for Back Door. But these
>> are my feeling only. Go ahead and follow the crytpo gods and continue to
>> worship at the altar of Bill Gates.
>
>With a proper salt method, even if you find 2/3 of the session keys you will
>not find the 3rd, and thus not the 3rd message.
>
>Even still the other 2 users would have to reveal their secret key to get the
>3rd message, and even then your magical crypto-crap will not stand up.
>
>moral: Use a salt for EVERY message so that the same session key is not used.
Do you mean salt in the sense of an Initial Vector (IV)?
Algorithm: Any block cipher of your choice
Chaining: CBC
Plaintext 1:
AAAA...AAAA Your codename is BOB BBBB....BBBB
Key: XXXXXX - This becomes publicly known
IV: Known only to person decrypting (i.e. agreed ahead of time)
Plaintext 2:
AAAA...AAAA Your codename is TIM BBBB....BBBB
Key: XXXXXX - Same as key for message #1
IV: Known only to person decrypting (and different than used for message 1)
Plaintext 3:
AAAA...AAAA Your codename is SAM BBBB....BBBB
Key: XXXXXX - Same as key for messages #1 and 2
IV: Known only to person decrypting (and different than used for message 1 and 2)
Here's the set up:
You send three messages to three different people. All plaintext messages
are 10K in length and are all the same except for a middle portion of about
1K which has specific information to the recipient.
Ahead of time you've worked out an IV that you will use with each of the
recipients, and the IV is different for each person.
You encrypt the messages with your favorite block cipher with CBC. All
messages are encrypted with the same key.
As the messages are being transmitted, your favorite eavesdropper listens
to the enciphered traffic. He intercepts all of message 1 and all of
message 2. Unfortunately (?), he gets all but the last 100 bytes of
message 3.
Due to negligence on your part, the encryption key falls into the hands of
the eavesdropper. He can now attempt to decrypt the messages.
Since he doesn't know the IV of the individual messages, the first block
of each decryption will be mangled and unreadable. However, the second
block and subsequent blocks will be readable. This is the error-correction
property of CBC.
In the case of the third message, he can't decrypt the last 100 bytes,
simply because he doesn't have the encrypted bytes themselves, although he
knows from the message structures that the last 100 bytes are the same
as the other messages.
Now, suppose you instead use a wrapping method where you iterate over the
entire message several times. All the data affect all the other pieces of
the data. Without the last 100 bytes of the third message, you will be
unable to get past the first iteration over the message, since you won't
know what value to pass to the next iteration.
The nutshell version is that an IV, even if never known, is not going to
save you in this case.
-Giff
--
Too busy for a .sig
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: ECC and smart card
Date: Tue, 07 Sep 1999 12:24:29 -0500
ycching wrote:
>
> ECC is said to be more suitable for implementation in smart card. Up
> till now, I haven't come across any implementation using ECC in smart
> card. Can anyone tell me what smart card has used ECC in it? Is there a
> free ECC library for 8051 or any other microcontroller?
It's pretty easy to port my libraries to an 8 bit microcontroller
and a few people have already done it. I don't know if they want
to give it away though :-)
Check out http://www.terracom.net/~eresrch and
http://www.manning.com/Rosing for the documentation.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: "Simple question" about DES
Date: Tue, 07 Sep 1999 18:08:03 GMT
"P.Creveuil" <[EMAIL PROTECTED]> wrote, in part:
>I am trying to understand section 8.1 of FIPS 74, but humbly fail...
>I wish to DES encrypt a string of (say 16) digits to a string of N
>digits, by means of the "mapping a character set onto itself".
You want to use DES to encrypt a string of 16 decimal digits to
produce a result guaranteed to be 16 decimal digits? I wasn't aware
that a standard mechanism to map an _arbitrary_ character set onto
itself was included in the DES standards.
>But the mechanism described in 8.1.1 and its reverse (?) process in
>8.1.2 do not make sense for me. Has anyone an example.
>E.g. :
>text to cipher = 1234567887654321 (this makes 8 octets : 12 34 56 78 87
>65 43 21)
>DES key : 01 02 03 04 05 06 07 08 (I know the parities are not correct)
>then ???
Let us assume all this stuff is in hexadecimal. If you're talking
about conventional DES encryption, not some special mode...
First, we take the DES key, and supply parity for it:
01 02 83 04 85 86 07 08
The first 7 bits of each byte are used as the key (if you specified 01
02 03 04 05 06 07 as your DES key, I'd have assumed those were the 56
bits of the real key; since you're giving an 8-byte key, I'm assuming
standard DES format.)
So the 56 bits used as the DES key are:
0000000 0000001 1000001 0000010 1000010 1000011 0000011 0000100
which is *already* kind of confusing.
Permuted Choice I is the next step, to produce two 28-bit numbers from
this, and then they're shifted, and at each step Permuted Choice II
produces the subkeys.
The text being enciphered first goes into the Initial Permutation.
There's a detailed description of DES on my web site, which *may* be
readable.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Kostadin Bajalcaliev" <[EMAIL PROTECTED]>
Subject: Re: SQ Announcement
Date: Tue, 7 Sep 1999 18:27:20 +0200
OK, one more thing is made clear. In one of your previous post you have
mentioned a part of my thesis where I claim that using P[P[P]] is dangerous.
I must to admit that it was hard for me to define way it is so. One of SQ
variants I have test (the only one) did not pass the statistical tests it,
that variant have P[P[]]. Now it is clear way it was so. Thank you.
David Wagner wrote in message
<7r2693$qgc$[EMAIL PROTECTED]>...
>In article <7quume$[EMAIL PROTECTED]>,
>Kostadin Bajalcaliev <[EMAIL PROTECTED]> wrote:
>> Now technical details: Mr.. Warner claim that SQ has a property to hold
the
>> lsb property.
>
>No, I claimed that a variant of SQ has this property, not SQ itself.
>(At least, that's what I intended to claim. I apologize if I caused
>any confusion.) Namely, if one replaces step {1} of SQ by the following
> {1'} A=P[Sr]; B=P[V[P[A]]];
>then one gets a cipher which has a large class of weak keys.
>
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: NSA and MS windows
Date: 7 Sep 1999 13:41:58 -0400
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> Paul Crowley wrote:
>> Except for one problem: as far as anyone can see, the idea of a backup
>> key is stupid and pointless. I can't see *any* goal that it meets
>> that isn't met by having two copies of the primary key.
> Then you haven't been paying attention. The backup key allows MS
> to get the product certified for export without having to hand over
> their private key.
Does this imply that they did (or may in the future) have to turn over
this secondary private key?
How could a key not known by the government be used for "certification?"
Is the option to give the government access to the OS at the level of
certifying components (which MS may have achieved by providing a secondary
key and thus not have to turn over their primary key) what was necessary
for "certification?"
------------------------------
From: "Kostadin Bajalcaliev" <[EMAIL PROTECTED]>
Subject: Re: SQ Announcement
Date: Tue, 7 Sep 1999 17:58:08 +0200
David Wagner wrote in message
<7r1po2$q7h$[EMAIL PROTECTED]>...
>In article <7quume$[EMAIL PROTECTED]>,
>Kostadin Bajalcaliev <[EMAIL PROTECTED]> wrote:
>> The discussion about SQ1 is starting to look as theory vs. theory. Thanks
to
>> Mr.. Warner I have read the Shannon theory again and I did not find any
>> conflict between "Information Lose" and "Unconditional Security". They
>> address the same subject but clearly from two different points of view.
>> Shannon theory is model what "unconditionally secure" Stream cipher must
be.
>> "Information Lose" theory is "computation security".'
>
>Ahh, good, this helps. I still have questions, but it's an excellent
>start. Thanks for taking the time to explain it to me!
>
>Next I'd like to ask whether you think of the "Information Lose" theory
>as a design principle or as a theorem. Is it a sufficient condition, a
>necessary condition, or an ad-hoc heuristic?
Information Lose in general is a law, If we have not the required
information to run some attack than we can not run it. This is nothing new.
It can be also viewed as a design principle. In my thesis this theory or
principle is not generalazed is explained together with SQ model of Stream
Ciphers. There are some other conditions needed to be satisfied. Each of
tham can be a theme of discusion. Why it is named theory? Because my
intention was to descrube a general templame of stream ciphers and the
theory needed to made tham secure.
About the LFSR they can not be a object of InfoLose implmentation first
because they are too linear and the do not fit in SQ model. However applaing
InfoLose to LFSR make tham harder to analize. But because of the main design
they will not be a significantli securer.
>
>Here's an example which makes me think that the "Information Lose"
>principle must be a heuristic design principle and not a provable theorem.
>Let my try to restate my understanding of the "Information Lose" approach
>and give an example of how to apply you; you can tell me whether I got it
>right.
>
>An attempted restatement of the "Information Lose" principle:
> Suppose the stream cipher outputs a chunk of n bits at a time.
> Then, after each n-bit output is produced, the cipher should
> introduce somehow more than n "new bits" into the internal state
> before the next chunk of n bits of output is produced.
>(The notion of "new bits" is left undefined, and thus this is an informal
>heuristic notion.)
>
You are prety close to my idea but because I am not sure that this two
approaches of info lose are equivalent here is the explenation.
Suppose the stream cipher outputs a chunk of n bits at a time.
The generator output are not all bits produced in than itteration, for
example only n-1 bits are available to the user.
The different is: to discard a whole output value (every second for example)
or to discard part of every ouput value (for example the MSB). I think that
the approach is not secure. For your LSFR it should be somthing as outputing
only 1/2 bit per iteration (theoreticaly).
>
>Of course, this doesn't mean that the "Information Lose" approach is
>useless: heuristic design principles can be extremely useful, even if they
>are not proven or not always a guarantee of success. I'm just trying to
>understand first what is claimed for the approach.
I generally agree with you. Information Lose is not enough to prove that a
system is secure, it must have statistically good behavior at first place.
LFSR are not statistically good. the lost information must be of key
importance to the attacked algorithm. That why it is theory, because some
other approximations must be satisfied. Using Permutation stream ciphers (as
SQ or RC4) we need at least N outputs to recover the permutation state where
N is the length of the permutation. We usually can not prove that the
algorithm design will prevent as to reverse a given iteration but we can
easily construct a "tree of states" to determine how many different
intermediate values can produce the same state after a given step of the
algorithm. For example having P[a+b] there 256 different pairs or a,b (if
they are independent). Doing this for each step we can measure the how many
inputs theoretically can produce the same output. So using Information Lose
we can balance this in such a way that the information needed to reverse the
iteration is at least as the information carried by the output.
------------------------------
Date: Tue, 07 Sep 1999 14:26:47 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: NSA and MS windows
Douglas A. Gwyn wrote:
> "Trevor Jackson, III" wrote:
> > This is an interesting aspect of the situation. Given than an "extra" key
> > exists, whaty other functionality might it have? Any answer to that
> > question is going to be speculation at this point. However, we cannot rule
> > out the possibility that the NSAKEY has capabilities that the main
> > crypto-signing key does not.
>
> Sure we can. Just look at how it is used: it is used to authenticate
> if and only if the main MS key fails to authenticate.
That is one use. Are you claiming that there is proof that there are no other
uses of it?
> The only really interesting thing about this is that it appears that
> somebody at MS decided to add the backup key for a particular purpose
> (to allow export-control evaluation without having to hand over MS's
> private key), but didn't first perform a thorough analysis of the
> modified protocol. As I noted in an earlier posting, whoever has
> possession of the private portion of the backup key can arrange for
> crypto modules that he provides to appear to be "certified" even
> though MS's certification authority is not in the loop. I suspect
> that was not realized by the person(s) who decided to include the
> backup key, or else they realized this but decided the risks were
> less than if Commerce/NSA/whoever were to be given the MS private
> key. They really should have let everybody know about this from
> the outset.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: NSA and MS windows
Date: 7 Sep 1999 13:45:49 -0400
DJohn37050 <[EMAIL PROTECTED]> wrote:
> Here is an obvious reason to have 2 keys, to not put all one's eggs in one
> basket, just as they said: If the first key is broken, then the second key can
> become the new primary key and a new key installed and the broken one taken
> away. After all, what if the first key was broken by someone just guessing a
If the first key is broken, why not use a backup of the first key?
If the first key is revocable or broken the OS will fail unless components
are always certified by both keys.
Are components now certified by both keys?
Giving an attacker two keys, cracking either of which provides
certification authority, does not seem to increase security.
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.research
Subject: Schoof-Elkies-Atkin implementation
Date: 7 Sep 1999 17:26:29 GMT
Reply-To: "Michael Scott" <[EMAIL PROTECTED]>
A free implementation of the Schoof-Elkies-Atkin Algorithm for counting
points on a GF(p) Elliptic Curve is available. This is a prerequisite for
the deployment of Elliptic Curve cryptography (ECC) techniques such as Key
Exchange, Public key Cryptography, and Digital Signature. An alternative is
to use "standard" curves generated by others. Standard curves are published
by the American NIST (www.nist.gov), amongst others.
For full download instructions and instructions for use, download initially
the file
ftp://ftp.compapp.dcu.ie/pub/crypto/sea.cpp
and read the comments at the top of the file.
Windows 'NT/95/98 command prompt executables are available for immediate
use, as well as full source code.
In one test, after sufficient Modular Polynomials were generated, the
points on a random elliptic curve over GF(p) for p the largest 512-bit
prime, were counted. This took 27.5 hours on a 180MHz Pentium Pro with 96Mb
RAM (i.e. relatively modest home computing facilities). This is probably the
largest size of p likely to be of Cryptographic interest (matching the AES
256-bit key size). The Modular Polynomials were generated on the same
hardware.
Elliptic Curves over GF(p) offer many advantages over standard methods such
as RSA.
1. An Elliptic Curve over GF(p) provides an ideal match for the AES
(Advanced Encryption Standard) block encipherment. Using a 256 bit prime
provides the same security as 128-bit AES. Similarly 384 bit ECC matches
192-bit AES, and 512 bit ECC matches 256-bit AES. Note that to offer the
same level of security as 512-bit ECC would require the use of RSA with keys
in excess of 10,000 bits.
2. If using a general random prime p of no special form, the method is not
patented. The performance cross-over with standard methods already occurs
with 160 bit ECC vs 1024-bit RSA/El Gamal. For higher security, ECC is much
faster.
3. The only extra leap-of-faith required is that there exists no
sub-exponential algorithm for solving the general discrete logarithm problem
in ECC.
Mike Scott
=========================================
Fastest is best. MIRACL multiprecision C/C++ library for big number
cryptography
ftp://ftp.compapp.dcu.ie/pub/crypto/miracl.zip
http://indigo.ie/~mscott
------------------------------
From: [EMAIL PROTECTED] (Matthias Bruestle)
Subject: Re: ECC and smart card
Date: Tue, 7 Sep 1999 16:39:57 GMT
Mahlzeit
ycching ([EMAIL PROTECTED]) wrote:
> ECC is said to be more suitable for implementation in smart card. Up
> till now, I haven't come across any implementation using ECC in smart
> card. Can anyone tell me what smart card has used ECC in it? Is there a
> free ECC library for 8051 or any other microcontroller?
There is a 160bit ECC module for the Basiccard from Zeitcontrol.
<www.basiccard.com>
Mahlzeit
endergone Zwiebeltuete
--
PGP: SIG:C379A331 ENC:F47FA83D I LOVE MY PDP-11/34A, M70 and MicroVAXII!
--
Never try to outstubborn a cat.
-- Lazarus Long, "Time Enough for Love"
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Beale (was: Mystery inc.)
Date: Tue, 07 Sep 1999 18:17:54 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> What I have is a typewritten transcript from the Roanoke library,
> which at one time held the original documents. I have reason to
> think there are some errors in the transcription.
I believe the Roanoke transcript you mention is the one written by
George Hart. Hart rewrote the original ciphers to conform to his own
numbering of the Declaration of Independence, so it is not a good
starting point for the Beale ciphers. For many years the Hart
manuscript was the only source available, but a copy of the original
1885 pamphlet, The Beale Papers, by James Ward, was finally discovered
in the late 1970's. This has been reprinted in, The Beale Treasure, A
History of a Mystery, by Peter Viemeister.
More information can be found at the Crypto Drop Box:
http://www.und.nodak.edu/org/crypto/crypto/resources.html
-- Jeff Hill
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
** 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
******************************
