Cryptography-Digest Digest #324, Volume #13 Thu, 14 Dec 00 00:13:00 EST
Contents:
Re: STT stream cipher (update) (Simon Johnson)
Re: Software PRNG.. (Tom St Denis)
Re: YAPRNG (Tom St Denis)
Re: Protocol for computer go (David Schwartz)
Re: 64bit CRC (Paul Schlyter)
Asymettric encryption in VB ("Adam Smith")
Re: Asymettric encryption in VB ("Arnold Shore")
Re: Sr. Cryptographer/mathematician (Paul Rubin)
Re: Unguessable sequence of unique integers? (John Savard)
Embedded Linux System Vs Smart Card (Data)
Re: Custom Encryption Algorithm ("Michael")
Re: MD5 byte order ("David Thompson")
----------------------------------------------------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: STT stream cipher (update)
Date: Wed, 13 Dec 2000 23:26:59 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>
> It's been almost a week and I've tried to discover any
> method of shrinking the keysize, without compromising
> the key strength. I soon gave up, realizing that if the
> key was smaller, then it theoretically would be less
> secure. (fewer bits to brute force).
Yup
> Anyhow, it might be possible to compress the key, although
> after reading comp.compression for a while I realized that
> if the key is truly random (or near random), it wouldn't
> be possible to compress it at all.
Yup
> Also, as you might remember, I stored the STT along with
> the state alphabets (STA), and this produced a key of 132kb.
> Ofcourse, it might seem impossible to brute force such a
> large key, but I still have this strange feeling that there
> is some flaw in my cipherer, but I can't really put my
> finger on it. (I've published the cipher/decipher code here
> before).
> I've also tried to think about if there are any other way
> of storing the information. Like, not storing the STA and
> just store the STT. But this still produce a key of 64kb.
> Any ideas?
>
> I've tried to understand this "phenomenon" that some of
> you guys are referring to; apparently it is possible to
> cipher a stream of data Dn, with some PRNG data Pn, and
> the result is ciphered data Cn. (i.e. Dn + Pn = Cn) But
> what I can't understand is that it is still decipherable.
> Ofcourse, there should be a key in the above "formula".
> Anyone care to explain?
Yeah sure.... Basically, you attack a Stream generator by finding
characterstics of the output that leak some of the input-key data, this
will always happen because the key is less than the plain-text size.
Now, there is a quanitity for stream cipher's called the linear
complexity of the algorithm. If this is low, the cipher is insecure if
it is high it doesn't insure the algorithm's security. A simple
algorithm exists which can reduce any linear feedback functioned stream-
cipher into a LFSR, once these has been found, its all over and the key
can be recovered.
Another way is to look at the differences across the outputs of the
stream generator. Imagine you have a function that computes a useful
difference between one interation of the stream cipher and another, F
(x,y). Now the basic trick to this attack is that these differences are
not usually spread evenly, but there will be a slight frequency peak if
you collect enough output. This peak gives us information about the
key, and it can be used to recover the key faster than brute-force.
This is basically differential cryptanalysis.
Linear cryptanalyis can also be used. Bascially, if you xor one output
against another there may be a probability bias that some of the bits
represent some of the key-bits more than you would expect at random. If
such a bias exists, it can be exploited.
Are these explanations correct?
> Anyhow, I also would like to know how public/private key
> ciphering works. As I've understood it, the private key
> must be uncomputable using the public key. And still it
> should be able to decipher. This seems to me like magic.
> Sorry, but I'm that a newbie to this. Any references
> about this?
>
> BR/jh
>
'Applied Cryptography' and 'Hand-Book of Applied Cryptography' cover
these topics well.
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Software PRNG..
Date: Wed, 13 Dec 2000 23:38:46 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Tom St Denis wrote:
> >
> > In article <[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] wrote:
> > >
> > > Are there any (good) software PRNG's on the net, that is also
free?
> >
> > Well depending on your needs a few programmers in here (including
me)
> > could code you one. There are many types available such as LFGs and
> > LFSRs which are non-patented technology.
> >
> > Tom
>
> Well, I'd rather like to know "how", than get the code from someone
> else. I mean, ofcourse it's cool to use something free, but without
> completely understand it, then it's kind of impossible to truly
> trust it. Also, it would be difficult to know how secure my algorithm
> is..
I admire you. "I'd rather like to know "how"," the sign of a true
scientist!!!
Well there are a lot of texts on it. I am not terribly well versed in
the theory, just the implementations.
A LFSR is a Linear Feedback Shift Register and a LFG is a Lagged
Fibonacii generator (a special form of LFSR). LFSR style math has been
used in CRC generators and various PRNGs.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: YAPRNG
Date: Wed, 13 Dec 2000 23:36:13 GMT
In article <[EMAIL PROTECTED]>,
John Myre <[EMAIL PROTECTED]> wrote:
> David Wagner wrote:
> >
> > If you xor two linear keystream generators together,
> > the result is still linear.
> <snip>
>
> Well, assuming XOR is part of the linear algebra in the
> first place.
>
> Just to be argumentative, suppose that we have LCG, except
> instead of (ax + b) we compute (x^a * b). (I don't mean
> to imply that xor'ing two such streams would be secure, or
> practical, only that the result is not so obviously linear).
Multiplication in Z is a terrible means of making new random outputs.
The state is too small and often degenerative.
And as david pointed out most of the time addition and xor are
cummunatitive (sp?).
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Protocol for computer go
Date: Wed, 13 Dec 2000 15:49:00 -0800
David Wagner wrote:
> Any randomized program can be converted into a deterministic one,
> by throwing 80 random coins before the start of the program, taking
> those 80 bits as secret input (which are also disclosed ahead of time
> to the referee, but kept secret from the opponent until the match is
> over), and expanding them with a pseudorandom generator to generate
> as much "randomness" as is required.
That assumes that the randomness can be found.
> >A serious problem comes from the real-time nature of computer-go:
> >the replay program will run on a different (possibly slower)
> >machine, and thus there is the problem to adjust overtime.
>
> It seems very simple: Either use a machine with the same timings
> (I take it that you are not willing to accept this answer), or else
> define your timings in terms of cycle count instead of wall clock time.
That's just not possible. First of all, computers may have more than
one clock. There's a processor clock, a keyboard clock, and perhaps a
real-time clock with its own oscillator. These various oscillators
create interrupts that the machine has to service. This affects the
relative timings of different tasks the computer is doing.
Consider a machine that starts three tasks at the same time and takes
the results of whichever task produces 'good enough' results first. If
the machine has two processors, how the tasks get distributed to the
processors and how their caches interact may affect the outcome.
As software becomes complex, it can also become fundamentally difficult
to make deterministic.
DS
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: 64bit CRC
Date: 14 Dec 2000 01:26:06 +0100
In article <[EMAIL PROTECTED]>, John Myre <[EMAIL PROTECTED]> wrote:
> Paul Schlyter wrote:
>>
>> In article <[EMAIL PROTECTED]>,
>> Mihai Preda <[EMAIL PROTECTED]> wrote:
>>
>>> I need two independent 32bit fingerprints for a message. I think CRC
>>> would be a good choice (I don't need security).
> <snip>
>>
>> You could also choose
> <snip>
>
> Of course, making a choice depends, not just on what he says
> he doesn't need ("security", whatever that means here), but
> mainly on what he does need. Why would someone need two
> "independant" fingerprints? And of course: "what are the
> requirements on speed, code size, etc., etc.?"
The most straightforward choice would of course to use a hash like MD5
or SHA, and then pick the number of bits you needed, discarding the
other bits. If one tjhink one needs "two independent 32-bit
fingerprints", one can pick 32 bits from the MD5/SHA hash, and then
32 other bits from the same hash. Evne if one "doesn't need the
security", it's still no disadvantage.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: "Adam Smith" <[EMAIL PROTECTED]>
Subject: Asymettric encryption in VB
Date: Thu, 14 Dec 2000 01:26:26 GMT
I need some kind of implementation of a PK system for VB to protect a key
scheme...anyone know of anything I can use? I've tried some RSA
implementation, but as most of you probably know it can't handle the mod
functions (overload)....is my only option an ActiveX control? And if so,
where can I get one? The only half-way decent thing I can find is RSAREF-VB
but it's pretty archaic it seems...in addition all of the RSA documentation
I can find anywhere was written when RSA Labs still had the patent for RSA,
so I can't find any new licensing information...and RSA's site doesn't seem
to be to helpful for this either...
Any ideas or pointers?
Thanks!
Adam Smith
------------------------------
From: "Arnold Shore" <[EMAIL PROTECTED]>
Subject: Re: Asymettric encryption in VB
Date: Wed, 13 Dec 2000 20:40:08 -0500
I'm using one of the available COM objects - in a web/VBScript application.
www.dyncrypto.com . there are others.
Arnold Shore
Annapolis, MD USA
"Adam Smith" <[EMAIL PROTECTED]> wrote in message
news:6lVZ5.172$[EMAIL PROTECTED]...
> I need some kind of implementation of a PK system for VB to protect a key
> scheme...anyone know of anything I can use? I've tried some RSA
> implementation, but as most of you probably know it can't handle the mod
> functions (overload)....is my only option an ActiveX control? And if so,
> where can I get one? The only half-way decent thing I can find is
RSAREF-VB
> but it's pretty archaic it seems...in addition all of the RSA
documentation
> I can find anywhere was written when RSA Labs still had the patent for
RSA,
> so I can't find any new licensing information...and RSA's site doesn't
seem
> to be to helpful for this either...
>
> Any ideas or pointers?
>
> Thanks!
> Adam Smith
>
>
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Sr. Cryptographer/mathematician
Date: 13 Dec 2000 18:19:04 -0800
Tom St Denis <[EMAIL PROTECTED]> writes:
> > - Computaional complexity theory
>
> "Computational" also referred to "Combinatorics"
No.
Computational complexity theory = studying the amount of computational
resources needed to solve different problems (for example, factoring)
> > - Combinatorics
>
> ?hmm repeat?
Combinatorics = study of finite sets, e.g. much of graph theory is
combinatorial.
> > - Number theory
> > - Numerical analysis
>
> These two are the same!
Absolutely not.
Number theory (according to HWL) = study of the positive integers (1,2,3...).
Some people with big attitudes like to call this subject "arithmetic"
and say it is the only "true" mathematics and all the rest of math was
developed in order to further number theory. See the book "Arithmetic"
by J.-P. Serre. Number theory problem: is every even number the sum
of two primes?
Numerical analysis = algorithms for solving numerical problems (very often
centered around differential equations). When these guys program,
they use tons of floating-point operations.
> Well I live in ottawa (Kanata specifically) you can contact me at
> tomstdenis@yahoo if you like.
Take a few math classes first ;-)
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Unguessable sequence of unique integers?
Date: Thu, 14 Dec 2000 01:54:47 GMT
On Wed, 13 Dec 2000 23:39:27 -0000, "Brian Gladman"
<[EMAIL PROTECTED]> wrote, in part:
>If the requested algorithm is 'impossible', this seems to imply that short
>block, long key ciphers cannot have truly secure long keys. I hence
>wondered if this was true.
Well, since a cipher with a 32-bit block is vulnerable to a
chosen-plaintext attack of complexity 2^32, it is 'believed' insecure.
I think the state of the art on this is that we don't have a lot of
results on how secure a cipher is, so if we can find that a cipher is
insecure under very difficult conditions not found in practice, the
cipher is not used.
Also, if just a counter is used - as he proposes - as input into the
block cipher, then the problem is serious. Even if a linear
congruential generator with a random starting point (and maximal
period) is used, one knows that the plaintext blocks have alternating
0 and 1 bits in the LSB positions, so statistical attacks are possible
at the least.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Data <[EMAIL PROTECTED]>
Subject: Embedded Linux System Vs Smart Card
Date: 14 Dec 2000 02:49:43 GMT
Some people said that Embedded Linux System on prototyping board is as
secure as smart card. What do you think? Is it really tamper-resistant as
smart card?
Example of Embedded Linux System:
http://developer.axis.com/hardware/devboard/
-Data
------------------------------
From: "Michael" <[EMAIL PROTECTED]>
Subject: Re: Custom Encryption Algorithm
Date: Thu, 14 Dec 2000 03:27:37 GMT
I have been interested in Cryptanalysis for a while now, and just started
reading this newsgroup a few weeks ago.
By far, the biggest surprise I have found here is that you 'experts' (only
in quotes because I don't really know you) don't have a program that you can
cut and paste these EXTREMELY weak cipher texts into an spit out the plane
text.
Not knowing any better, I thought you would.
I ended up here due to MY quest for such a program.
As I said in one of my first postings, I have written my own (admittedly
weak) algorithm.
Reading this news group makes me less proud of my algorithm, but also feel
like my ciphertext is much much more secure than I though it was.
Your standard answer to the people who post their cipher text is why would I
waste my time decoding it.
Well, this place is all about Cryptanalysis. However, if I email a friend
using my algorithm and the email with the cipher text gets printed out and
left on my friend's desk at work, people as crypto savvy as you guys won't
be there, BUT the 'why should I waste my time' attitude WILL be there.
On another subject, I am very disappointed no one replied to my earlier
posting where I describe a piece of hardware that I want to figure out. I
described the fact that I have the ability to do a Chosen-plaintext attack,
Adaptive-chosen-plaintext attack, Chosen-ciphertext attack, and Chosen-key
attack and I was looking for advice on how to proceed. Not a single reply.
Michael
"Simon Johnson" <[EMAIL PROTECTED]> wrote in message
news:9103ad$bi1$[EMAIL PROTECTED]...
> In article <90vv6m$8rn$[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > In article <90vlam$jjd$[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] (Paul Schlyter) wrote:
> > > In article <90ts4o$ptd$[EMAIL PROTECTED]>,
> > > Tom St Denis <[EMAIL PROTECTED]> wrote:
> > >
> > > > In article <90tq1e$oer$[EMAIL PROTECTED]>,
> > > > Simon Johnson <[EMAIL PROTECTED]> wrote:
> > > >
> > > >> Even though you have not given me an algorithm to work with, i
> can
> > > >> point out some flaws in this cipher just by looking at the
> cipher-
> > > >> text.
> > > >> e.g. You have a row of 9 ones in succession. If this were a good
> > > >> cipher, then you would have an even distribution of digits.
> > However,
> > > >> the probability of a string of nine '1's occuring in a row is
> > 1/10^9
> > > >> or one in a billion.
> > > >>
> > > >> Based on this, I conclude your algorithm isn't very secure.
> > > >
> > > > Your observation is correct however your conclusion is not. A
> valid
> > > > RNG may output a zillion zero bits and still be random.
> > >
> > > In principle true, however if the RNG really is random, it must
> > > output approx 2^a_zillion bits before outputting a zillion zero bits
> > > after one another. Thus it is extremely unlikely that it will
> output
> > > a zillion zero bits after one another in its first few zillion
> output
> > > bits. It's more likely that you e.g. guess a secret RSA key -- and
> > > get it right at the first guess!
> > >
> > > > You observed a bias in his cipher, perhaps due to the fact it's
> > > > probably some sort of simple monoalphabetic substitution mixed
> with
> > > > a Vinegere cipher. Who knows. Just because there are alot of 1's
> > > > doesn't make it weak.
> > >
> > > Among all the ciphertexts containing much more 1's than could be
> > > expected by change, almost all are due to weak ciphers. Only a tiny
> > > fraction will be due to that extremely improbable although not
> > > completely impossible statistical deviation. The chance is much
> > > higher that you'll e.g. die from an airplane crach the next time you
> > > go flying.
> >
> > I agree with what you are saying. My point was that you can't always
> > jump to conclusions. I could look at "twofish" ciphertext and notice
> > something and say "AHA twofish is obviously weak". But that wouldn't
> > be too usefull.
>
> Yes, but the probability of this occuring, with coherent plain-texts,
> is very small indeed. (we could fiddle it and 'decrypt' 111111111 with
> some key, to produce 'Plain-text' that would 'encipher' to non-random
> bit-patterns)
>
> Basically, we are both right in our own ways.
>
> The problem is, we are all playing with black magic here. Since we
> don't know the algorithm and have very little cipher-text.
>
> Simon.
> --
> Hi, i'm the signuture virus,
> help me spread by copying me into Signiture File
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
------------------------------
From: "David Thompson" <[EMAIL PROTECTED]>
Subject: Re: MD5 byte order
Date: Thu, 14 Dec 2000 04:56:30 GMT
Paul Schlyter <[EMAIL PROTECTED]> wrote :
> In article <90iudq$3ui$[EMAIL PROTECTED]>,
> Thomas Pornin <[EMAIL PROTECTED]> wrote:
...
> > Besides, not all computers use 8-bit bytes; for instance, the PDP-11
> > used 9-bit bytes. ...
> > And, last but not least, all PC since the 80386, and including all
> > species of pentium, are bit-adressable, using the instructions bt, btc,
> > btr, bts, bsf and bsr.
>
> Well, sort of, but the so-called "bit address" is split up into a
> byte address plus an index within the byte, instead of a uniform bit
> address. Consider that PDP-11 byte you mentioned above, which has
> 9-bit bytes (and I could add that the DEC-10 had 7-bit bytes and
> 35-bit words, the CDC-6600 series had 6-bit bytes in 60-bit words,
Are you folks on drugs? The PDP-11 had 8-bit bytes,
and was the first DEC machine to be really byte-oriented.
The PDP-6 and -10 had 36-bit words that could be accessed
by the (few, special) byte instructions as bytes of *any* size;
4 x 9-bit, 5 x 7-bit + 1 leftover, and 6 x 6-bit were all common.
The -6/10 byte-pointer was _word_ address plus bit number
(and count) within word.
> and old teleprinters can be said to have 5-bit bytes since they
> encode their characters into only 5 bits each):
Although with no (addressable) storage to make the distinction
matter, they were usually just called "characters".
--
- David.Thompson 1 now at worldnet.att.net
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
