Cryptography-Digest Digest #189, Volume #12 Mon, 10 Jul 00 03:13:01 EDT
Contents:
Re: Advanced Cryptography FAQ (S. T. L.)
Re: Proposal of some processor instructions for cryptographical ("Douglas A. Gwyn")
Re: A thought on OTPs ("Douglas A. Gwyn")
Re: computer program: extract consonants/vowels from input ("Douglas A. Gwyn")
Re: Any crypto jokes? (potentially OT) ("Douglas A. Gwyn")
Re: Efficient algorithm to determine relative primality? ("Scott Fluhrer")
Re: Proposal of some processor instructions for cryptographical applications
(Benjamin Goldberg)
Re: Compression & Encryption in FISHYLAND (Kurt Shoens)
Re: A thought on OTPs (Bryan Olson)
Re: Using CRC's to pre-process keys (Scott Nelson)
Re: Efficient algorithm to determine relative primality? (David Blackman)
Re: A thought on OTPs (Bryan Olson)
Re: Using CRC's to pre-process keys (Mack)
Re: Random Numbers (Scott Nelson)
Re: Advanced Cryptography FAQ (Mack)
$10,000.00 Reward for Paytv / cash card, smart card decryption! (Justice403911)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (S. T. L.)
Subject: Re: Advanced Cryptography FAQ
Date: 10 Jul 2000 04:39:32 GMT
<<2. What is wrong with it?
The current state of encryption these days have an inherent weakness
in that they are based on static keylength, static operators and
operations (algorithms), and a static symbol set (base).>>
That's freaking crap. You go break IDEA, lamer, and then talk to us. Which
means don't talk to us.
-*---*-------
S.T.L. My Quotes Page * http://quote.cjb.net * leads to my NEW site.
Now **108** reviews of my 169 science books. Other pages up:
Review of the _Foundation_ series, Jet Fighter Paper Airplane page,
LASTLY Shrine, Files for Download!
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Mon, 10 Jul 2000 00:43:42 -0400
Dennis Yelle wrote:
> That is not a very good example,
Well, I didn't want to code up an actual stream cipher.
The example was a simple one to illustrate the convenience
of direct bit access from the HLL.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: A thought on OTPs
Date: Mon, 10 Jul 2000 00:47:04 -0400
Mok-Kong Shen wrote:
> The chi-square test can be used to test how well the hypothesis
> that the die is unbiased, i.e. there is a test for the adequacy of
> the model. There is no parallel in the case of independence of
> random variables (there is no test).
Sure there is. Since lack of independence implies correlation,
one simply tests for correlation. In fact chi-square can be used.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: computer program: extract consonants/vowels from input
Date: Mon, 10 Jul 2000 00:51:13 -0400
JPeschel wrote:
> The case for W as a vowel is probably made because
> the letter was originally a double-u, written as
> VV. The case is a weak one, so you're better
> of treating Ws as consonants.
In the examples given, W was a consonant, but in my last name
the W is a vowel, even though one might guess otherwise. We
know that because it originated in Wales, where W is a vowel.
The symbol for W did indeed originate in a doubled Roman V
(which is actually the same as modern U), which is also why
it is called "double-u". I suppose this leaves a vacwm of
some sort.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Any crypto jokes? (potentially OT)
Date: Mon, 10 Jul 2000 00:54:04 -0400
rosi wrote:
> [snip]
Thanks, that was one of the biggest jokes yet.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Efficient algorithm to determine relative primality?
Date: Sun, 9 Jul 2000 21:46:16 -0700
Bryan Olson <[EMAIL PROTECTED]> wrote in message
news:8kalho$a2h$[EMAIL PROTECTED]...
> ChenNelson wrote:
>
> > Would someone know an efficient algorithm for determining whether
> > numbers x and y are relatively prime, without havng to necessarily
> > calculate gcd(x,y) using Euclid's method? Calculating the gcd of two
> > numbers using Euclid's method is too slow for crypto-size (100+digits)
> > numbers. Thanks.
>
> I don't think any significantly faster algorithm is known.
>
> Euclid's algorithm* is blazingly fast. The usual
> implementation is quadratic in the number of digits,
> and much faster than exponentiation.
And, if it isn't fast enough, there are extensions that are applicable to
large (crypto-size) numbers that speed it up by a factor of 5 or so. The
basic idea (by D. H. Lehmer) is that you several rounds of the normal
Euclid's algorithm on the leading digits, and then apply those results to
the full numbers. By doing most of the work on small (32 or 64 bit)
numbers, you avoid most of the multiprecision arithmetic. Reference: Knuth,
algorithm 4.5.2L (first edition, sorry, that's what I have in front of
me...)
--
poncho
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical applications
Date: Mon, 10 Jul 2000 05:10:45 GMT
Mok-Kong Shen wrote:
[snip]
> I should appreciate comments and suggestions of further
> processor instructions that are useful for encryption purposes
> and that are, hopefully, not inefficient for hardware
> realizations.
Is it possible to make a single instruction, which does a lookup
in an 8x8 fixed sbox, in the amount of time that, eg, addition to
a constant would take? This wouldn't be something used in general
purpose machines, obviously, but for encryption on a limited-memory
device.
A related, but possibly off-thread, question is: When we say that
algorithm X only uses Y bytes of RAM, do we include the key? We're
only worried about memory considerations when it's limited, and
that *usually* is when we're talking about things like smartcards
(or maybe encryption chips): Since smartcards don't change keys
often [if at all, once the card is made], wouldn't it make sense
for the key to be in ROM, or retrieved/indexed by a single
instruction like my first question, or even have the key values
unrolled right into the code?
------------------------------
From: [EMAIL PROTECTED] (Kurt Shoens)
Subject: Re: Compression & Encryption in FISHYLAND
Date: 9 Jul 2000 23:18:43 -0700
In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
>There are practically no algorithms which are known to be secure against
>known plaintext attacks. All we can usually say is that we don't
>currently know of any such attacks. Since I don't know what attacks my
>opponent is aware of, I would avoid providing him with clues such as
>known plaintext unnecessarily, wherever possible.
Agreed that there's no proof of security against known
plaintext attacks. If you're really concerned about avoiding
known plaintext, you can always avail yourself of the various
chaining modes, which will do a better job of camouflaging the
plaintext.
Suppose as a simple example, you pick a random 16-byte value, prepend it
to your plaintext and XOR it with each succeeding plaintext block.
Voila! No known plaintext to worry about. Of course, if pre-whitening
is a good idea, then it should be incorporated into the underlying
encryption algorithm ... as it is in some.
If you don't use some sort of IV + chaining then the plaintext worries
are back, even when using 1-1 compression. Perhaps your adversary
can trick you into compressing and encrypting a known message.
Another tack: if encrypting unmodified plaintext worries you, then
why not jump into the multiple encryption game discussed at length
here a few weeks ago? If encrypting once is good, surely encrypting
twice, three times, or N-times is better? The resulting combination
is still an encryption algorithm, though. Perhaps it's vulnerable
to a known plaintext attack ....
And further: if we don't know how a cryptosystem will be attacked,
then how do we defend it? Maybe 1-1 compression makes some unknown
attack easier!
>Why is brute-force necessarily infeasible? I've previously enumerated all
>manner of cases where the keyspace can be reduced through bugs, theft,
>torture, carelessness, espionage, and so forth - and having better halting
>criteria can help, especially with relatively short messages.
OK, good point. Sometimes brute force will be feasible. When it is,
how much extra security does 1-1 compression provide? In a short
message, the attacker need only decrypt a few blocks. If the plaintext
was random before compression, you're in great shape ... and the
compression was unnecessary. Otherwise, the key space is expanded
by a few bits at most. If brute force works, your messages are
probably compromised.
>8-bit keys can be quite satisfactory - *if* both you and the opponent
>know you're only ever likely to want to send 256 different messages.
>In essence, you can number the messages, and then use a OTP.
If you can use a one-time pad, none of this is worth worrying about.
>These measures can help defend against the possibility that the office
>the messages are sent from is being bugged, or a huge number of other
>possible security leaks.
1-1 compression doesn't help in these cases. If my office is bugged,
why can't They (you know, Them) get the plaintext or at least the
whole key?
Let me ask you, what would you give up to use 1-1 compression? Would
you accept a smaller key size? What you choose to use ECB mode?
Would you use a less-studied algorithm? Accept a poorer random
number generator? Forego some time outside on a nice day?
In reality, there's no need to give up any of these things; I'm
wondering how you rank 1-1 compression relative to all the other
available security measures. You've pointed out that errors
in implementation or operation can leave one exposed. I say let's
focus our efforts on the correct use of known good techniques
rather than diverting our attention to measures that don't really
help.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: A thought on OTPs
Date: Mon, 10 Jul 2000 06:13:16 GMT
Mok-Kong Shen wrote:
>
> Bryan Olson wrote:
>
> > So the answer yet again: there is no test that will
> > always find dependence when it exists.
>
> My point has been that it is an interesting fact that,
> while there is no generally applicable test for
> independence
Now you say your point has included the answer to
the question on which you claimed to have received
no definite answer?
> (a correlation test can be
> considered a pre-test to screen out unnecessary test candidates) in
> practice, one nonetheless in quite a number of places of applied
> statistics makes assumption of independence of random varaibles (and
> deduces results, which are certainly theoretically interesting, but
> .....).
And many results of great practical significance.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Using CRC's to pre-process keys
Reply-To: [EMAIL PROTECTED]
Date: Mon, 10 Jul 2000 06:23:38 GMT
On 8 Jul 2000 18:33:25 -0700, [EMAIL PROTECTED]
(David A. Wagner) wrote:
>In article <[EMAIL PROTECTED]>,
>Scott Nelson <[EMAIL PROTECTED]> wrote:
>> ... the SHA-1 hash of a 128 bit key isn't likely
>> to contain the full 128 bits, due to collisions.
>
>I don't think that's quite right.
>Assuming SHA1 is secure, it comes close enough that
>I claim the difference is pretty irrelevant.
>
If we assume that the hash is completely unbiased
within the 128 bit space, hashing all possible 128 bit
keys would result in approximately 1/e values being
missed, and 1/e single hits, with the rest being
hit multiple times. Effectively reducing the key
space by less than 3 bits, which I agree is pretty
irrelevant in most cases. It's not 0 though,
so this is an advantage that CRC has over SHA1.
I wouldn't say it's enough to overcome the disadvantage
of the hash not being secure, but it is an advantage.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: Efficient algorithm to determine relative primality?
Date: Mon, 10 Jul 2000 16:23:37 +1000
Scott Fluhrer wrote:
> > ChenNelson wrote:
> >
> > > Would someone know an efficient algorithm for determining whether
> > > numbers x and y are relatively prime, without havng to necessarily
> > > calculate gcd(x,y) using Euclid's method? Calculating the gcd of two
> > > numbers using Euclid's method is too slow for crypto-size (100+digits)
> > > numbers. Thanks.
>
> And, if it isn't fast enough, there are extensions that are applicable to
> large (crypto-size) numbers that speed it up by a factor of 5 or so. The
> basic idea (by D. H. Lehmer) is that you several rounds of the normal
> Euclid's algorithm on the leading digits, and then apply those results to
> the full numbers. By doing most of the work on small (32 or 64 bit)
> numbers, you avoid most of the multiprecision arithmetic. Reference: Knuth,
> algorithm 4.5.2L (first edition, sorry, that's what I have in front of
> me...)
>
> --
> poncho
Isn't there an algorithm using only shift, mask and subtract that runs
in N ** 2 time? Asymptotically that would be quite a bit faster than
Euclid's which is around N ** 3 using long division, and maybe (N ** 2)
* (lg(N) ** 2) or similar nonsense if you can get away with FFTs for
modulus (and i'm not sure you can). I think shift/mask/subtract would be
faster in practice for crypto sized numbers as well.
I'd expect some of the big number libraries out there to use this
algorithm, but i'm too lazy to check if they do.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: A thought on OTPs
Date: Mon, 10 Jul 2000 06:34:58 GMT
Douglas A. Gwyn wrote:
> Bryan Olson wrote:
> > So the answer yet again: there is no test that will
> > always find dependence when it exists.
>
> And there is also no test that will always find
> independence when it exists. What statistical
> tests *do* is provide a measure of support for
> or against a hypothesis; the measure can never
> be certain unless the enitre population is sampled.
The fact that when a test rejects the result is not
certain (in the sense of probability = 1) is relatively
unimportant in practice. We simply construct the test
so that the probability of failure for a source that
does fit the hypothesis is negligible.
The significant issue is that the "for" and "against"
sides are no where near equally convincing. A test
may definitely show that two generators are not random
and independent, but it cannot show that they are.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Using CRC's to pre-process keys
Date: 10 Jul 2000 06:47:56 GMT
[EMAIL PROTECTED] (David A. Wagner) wrote:
>In article <[EMAIL PROTECTED]>,
>Mack <[EMAIL PROTECTED]> wrote:
>> >What's not clear is why this is at all relevant to the application of
>> >hashing entropy sources to get key material. I don't know about you,
>> >but the number of keys _I_ have ever generated falls far short of 2^80...
>>
>> Since the original post was about ASCII text key processing I am
>> not sure it is.
>
>Er... huh? Sorry, I don't know how to read your comment. Are you
>suggesting that you might want to generate more than 2^64 keys in your
>life?
>
No I am not sure that the hashing of entropy sources is relevant to
the original post since it was ASCII text. Although I have used
CRCs for compressing entropy for non-crypto purposes.
I don't see any reason not to use the for crypto purposes if you
can be 'certain' that your entropy source isn't being influenced.
And that is a very important assumption.
This is one place that the speed of the CRC would definitely
be an advantage. ie. if you must generate huge amounts of random
data from a relatively low entropy source.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Random Numbers
Reply-To: [EMAIL PROTECTED]
Date: Mon, 10 Jul 2000 06:52:21 GMT
On Mon, 10 Jul 2000, "David Hyde" <[EMAIL PROTECTED]> wrote:
>
>"David Hyde" <[EMAIL PROTECTED]> wrote in message
>news:8kac12$nk2$[EMAIL PROTECTED]...
>> Does anyone know how to convert a random bit stream into random 16-bit
>> numbers with uniform distribution?
>>
>>
>
>Sorry I left out some detail about the random bit stream. The bit stream
>has been generated from a white noise source I built from a zener diode, a
>couple of op-amp stages and a comparator. Although the bits produced are
>independent of each other, there is a bias that can't be removed by
>adjusting the dc mean level of the noise. Therefore I was asking if there
>is a way of processing the bit stream to produce 16-bit random numbers with
>a uniform distribution?
>
In other words, you have a (probably) biased source of bits,
and you want to make them unbiased.
Despite the theoretical perfectness of Von Neumann's approach,
(http://www.helsbreth.org/random/removing_bias.html)
it's only perfect if the data is uncorrelated (unlikely in
the extreme) so the best thing to do is to hash the bits.
If you're doing that in software, then collect up
a large amount and apply a secure hash.
You might want to take a look at a Yarrow,
http://www.counterpane.com/yarrow.html
since it's publicly available (free) and avoids
a lot of nasty problems that you might not have thought of.
If you want to do it in hardware, then a simpler hash is probably
in order. I like taking the output and clocking it into a CRC
generator chip like the 74LS401, though you can build your own
out of discrete easy enough. This can often replace a buffer
chip so the part count might not even go up.
Note that hashing doesn't technically remove bias and dependance,
it just reduces them. If the source is almost unbiased now,
then it doesn't take that much to reduce it to lower than
measurable levels. However, as mentioned elsewhere,
there is probably a lot more bias and dependance than you think,
so it's a good idea to use massive overkill.
I'd say at least 256 clocks per 16 bits of output data.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Advanced Cryptography FAQ
Date: 10 Jul 2000 07:06:22 GMT
><<2. What is wrong with it?
>
>The current state of encryption these days have an inherent weakness
>in that they are based on static keylength, static operators and
>operations (algorithms), and a static symbol set (base).>>
>
>That's freaking crap. You go break IDEA, lamer, and then talk to us. Which
>means don't talk to us.
>
>-*---*-------
>S.T.L. My Quotes Page * http://quote.cjb.net * leads to my NEW site.
>Now **108** reviews of my 169 science books. Other pages up:
>Review of the _Foundation_ series, Jet Fighter Paper Airplane page,
>LASTLY Shrine, Files for Download!
>
>
>
You have got it wrong he isn't a lamer because he thinks that static
keylength and static operators are wrong.
He is a lamer because he is trying to sell his spreadsheet or whatever it
is. And to make matters worse he really doesn't understand the
concept of chosen plaintext attack. I would say pure Snake Oil.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Justice403911)
Subject: $10,000.00 Reward for Paytv / cash card, smart card decryption!
Date: 10 Jul 2000 07:09:40 GMT
Dear Sir/ Madam,
Our company is posting a contest for anyone that can create an automated script
or program or machine or both, in order to decode any smart card for United
States Based Paytv and Cash card systems.
If you think you can, email us for more information. All correspondence is
strictly confidential. The first one that succeeds will receive $10,000.00 USD
NO JOKE!
This contest is for educational purposes only.
If You decode it today, you are paid tomorrow. Interested persons should send
inquiries to [EMAIL PROTECTED] SERIOUS ENQUIRIES ONLY.
Thanking you in advance for your anticipated cooperation.
JUSTICE403911.
------------------------------
** 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
******************************
