Cryptography-Digest Digest #182
Cryptography-Digest Digest #182, Volume #12 Sun, 9 Jul 00 07:13:00 EDT
Contents:
Re: Using CRC's to pre-process keys (Mack)
Re: computer program: extract consonants/vowels from input ("Douglas A. Gwyn")
Re: Using CRC's to pre-process keys (Mack)
Re: A thought on OTPs (Bryan Olson)
Re: Using CRC's to pre-process keys (Mack)
Re: Using CRC's to pre-process keys (Mack)
Re: MD of large data-sets (Bryan Olson)
Re: Using CRC's to pre-process keys (Simon Johnson)
Re: Using CRC's to pre-process keys (Simon Johnson)
Re: Concepts of STRONG encryption using variable base http://www.edepot.com/phl.html
([EMAIL PROTECTED])
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: A thought on OTPs (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: Concepts of STRONG encryption using variable base (Mok-Kong Shen)
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Using CRC's to pre-process keys
Date: 09 Jul 2000 07:48:32 GMT
SHA-1 is a 160-bit hash function. I don't understand what you mean by
"isn't likely to contain the full 128 bits, due to collisions". I assume
you are refering to 128 bits of entropy. And the part about collisions
doesn't make any sense because if SHA-1 suffers from it, then CRC will to.
There are collisions in both cases. Any time you take N bits and compute a
hash value of M bits, and N is greater than M there will always be
collisions. And in some cases depending on the hash function there will be
collisions even when N is less than or equal to M. Also if what you say
about a 128-bit CRC of a 128 value having the same entropy is true, then
there is no reason to use CRC since you aren't gaining anything by doing it.
- Adam
I believe what he was trying to say is that if you take a SHA-1 for example
and produce a 128 bit value (pick your method of reducing it) from a 128
bit input you will have some collisions. By the birthday paradox 1
collision after 2^64 inputs. With a CRC for a fixed 128 bit input length
you will never get a collision unless you reuse an input.
Is this any clearer?
Mack
Remove njunk123 from name to reply by e-mail
--
From: "Douglas A. Gwyn" [EMAIL PROTECTED]
Subject: Re: computer program: extract consonants/vowels from input
Date: Sun, 09 Jul 2000 03:50:37 -0400
Darren New wrote:
Whether a letter is more correctly classified as a consonant or
as a vowel is, as you observe, context dependent.
I want to know whether the "P" in "pneumonia" is a consonant or a
vowel.
Usually it is said to be "silent", but it's still a consonant.
--
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Using CRC's to pre-process keys
Date: 09 Jul 2000 08:11:27 GMT
Mack [EMAIL PROTECTED] wrote in message
news:[EMAIL PROTECTED]...
Normally keys are preprocessed with MD5 or SHA-1
I assume that you mean, "when translating from a human memorizable key
phrase into a key for a private key encryption system with a fixed key
length, normally MD5, SHA-1 or some other secure hash is used".
It is designed for ASCII keys. Not nessessarily input by humans at the
stage it is used.
There are other ways to generate private keys (eg. through a public key
mechanism) where the issues are quite different. And, of course, there are
private key systems (eg. RC4) that can accept quite long keys directly, and
so there's little point in doing a hash first.
RC4 leaves residual correlations that requires discarding the first 512 bytes
of
output if used with ASCII text. Not perfect but respectable. Of course the
original design did not include this. As for public key mechanisms they
genrally
don't include ASCII text.
These tend to be a bit slow. And also a bit of
overkill if the cipher is secure.
Slowness is not an issue. Look at the problem statement: we input the key
phrase from the user and then convert it. The first part (inputting from
the human) is so slow that the few microseconds taken to do a secure hash is
irrelevant.
See above.
And, some people (including me) like massive overkill if it is cheap enough.
How cheap is cheap enough???
I am proposing pre-processing with an appropriate
length CRC. ie. CRC-64, CRC-128 or CRC-256
depending on the required key. This effectively
reduces the key length of an ASCII key and
provides balanced output.
The obvious problem with a CRC is that collisions are easy to compute -- it
would be trivial to compute two key phrases that correspond to the same
private key. Now, how that can be used by an attacker is not at all
obvious. However, that is a
Cryptography-Digest Digest #185
Cryptography-Digest Digest #185, Volume #12 Sun, 9 Jul 00 16:13:01 EDT
Contents:
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Q: Hadamard transform (Mok-Kong Shen)
Yet another uncommon number system (Mok-Kong Shen)
Re: Quantum Computing (Was: Newbie question about factoring) (Jerry Coffin)
Re: Using CRC's to pre-process keys (Jerry Coffin)
Re: Concepts of STRONG encryption using variable base http://www.edepot.com/phl.html
("tok")
Re: A thought on OTPs (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Samuel Paik)
Advanced Cryptography FAQ ([EMAIL PROTECTED])
Re: Proposal of some processor instructions for cryptographical (Samuel Paik)
Re: computer program: extract consonants/vowels from input (JPeschel)
Re: Proposal of some processor instructions for cryptographical("Trevor L.
Jackson, III")
From: Mok-Kong Shen [EMAIL PROTECTED]
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Sun, 09 Jul 2000 20:18:06 +0200
Kasper Pedersen wrote:
"Mok-Kong Shen" [EMAIL PROTECTED] wrote
I implicitly assume a common processor, e.g. what people normally
have access to, e.g. a PC.
Aren't we already talking specialty items? Maybe people _will have_, but
they certainly don't _have_
I mean crypto software that is to be used by common people, i.e.
without requiring them to purchase any special hardware.
The problem is with the size of the look-up table and quite probably
also the efficiency incurred thereby in case the permutation is
dynamically
determined so that one has to recompute the look-up table frequently.
Which is acceptable on fixed perms. A 32:32 mapping can be done in 4 clks on
a modern CPU, the 16 kbit memory for the table the limiting factor as we
assume 1 load per clock. But - that memory isn't much bigger than the 32:32
switch matrix on the silicon, and it's a lot more powerful.
Dynamically changing perms of this kind are fun - but you can probably find
something that's more cryptographic value for the cost.
Well, if I don't err, for a given particular permutation one has to
have a look-up table of 2^32 words as an array. Isn't that fairly huge?
And one has to compute the contents of these, even if done only once
in a key dependent way.
Perhaps I misunderstood you. But it is not a matter of formal formulation,
it is a matter of implementation (with processor instructions).
Which is why he's talking FIR filters. DSPs have special instructions for
those, optimized to such a degree that they sometimes take up most of the
silicon. Take the sample C code below
for (i=0; in; i++)
{
acc+=data[p1+base_p1]*data[p2+base_p2];
p1=(p1+1) mod size_p1;
p2=(p2+1) mod size_p2;
}
A typical low-cost DSP will do the above loop in 1+n clock cycles. The above
{...} is one instruction in the CPU, and the for(;;) is free (typically 1
clk setup).
And with a little headache, it can be implemented in 3DNow! at 1 clock/round
v. 32*32, for those running K6-x or K7's.
Notice how well it moves bits around?
The context in the above case was computing the parity. Does
Data[index] of your code refer to a single bit? Thanks.
M. K. Shen
--
From: Mok-Kong Shen [EMAIL PROTECTED]
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Sun, 09 Jul 2000 20:23:10 +0200
Thomas Womack wrote:
"Mok-Kong Shen" [EMAIL PROTECTED] wrote
Transposition is one of the basic operations in cryptography.
Is it, any more? Having a look at the AES candidates, most of them carefully
refrain from calling for bit transpositions simply because they're rather
hard to implement.
Given that, I think that one should get hardware support for transpositions.
If you want byte transpositions, Altivec has a vector-permute instruction
which considers one 128-bit register as a list of 16 bytes A[0..15],
considers the lower bit of each byte as an index into a second register B
(also considered as a set of 16 bytes B[0..15]), and sets C[i] = B[A[i]]. I
don't know how long this instruction *takes* on a current G4, but someone in
comp.arch surely does.
Anyway, byte transposition in memory is always supported, if I don't err.
The bit scatter/gather technique you suggest seems to go very against the
RISC philosophy by having a single instruction require hundreds of memory
operations; I think you have to stick with permutations that can fit in a
register, though there's nothing stopping you from suggesting a
super-Altivec using 256-bit vector registers.
Actually I don't think that a general bit permuation instruction is very
extravagant. There is, if I don't err, normally a translate instruction that
Cryptography-Digest Digest #186
Cryptography-Digest Digest #186, Volume #12 Sun, 9 Jul 00 18:13:00 EDT
Contents:
Re: Efficient algorithm to determine relative primality? (Bryan Olson)
Re: Proposal of some processor instructions for cryptographical (Terje Mathisen)
Re: Using CRC's to pre-process keys (David A. Wagner)
Re: Advanced Cryptography FAQ (James Pate Williams, Jr.)
Re: Proposal of some processor instructions for cryptographical(Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Iain McClatchie)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical(Helger Lipmaa)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
CP algorithm ("Theophilus Samuels")
Re: Advanced Cryptography FAQ (John Savard)
Re: Proposal of some processor instructions for cryptographical applications (John
Savard)
From: Bryan Olson [EMAIL PROTECTED]
Subject: Re: Efficient algorithm to determine relative primality?
Date: Sun, 09 Jul 2000 19:58:55 GMT
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.
(*) I assume we're talking about the modern version of
Euclid's algorithm, based on
for x != 0, GCD(x, y) = GCD(x, y mod x).
As I understand things, the ancient Greek version
reduced the problem using
GCD(x, y) = GCD(x, y-x)
which would be slow.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
--
From: Terje Mathisen [EMAIL PROTECTED]
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Sun, 09 Jul 2000 17:36:25 +0200
Mok-Kong Shen wrote:
Terje Mathisen wrote:
Since future crypto algorithms will work with a minimum block size of
128 bits, this instruction would at the very minimum be capable of
working with half that size, i.e. 64-bit registers. A generalized
bit-shuffle operation would then need something like 64 * 6 = 384 bits
of shuffle index data. (This could theoretically be limited to the
number of bits needed to encode 64!, but I would not like to try to
dynamically split this at runtime. :-()
I think that 64-bit PCs are in the coming, and the price of 64-bit
workstations are going down to be affordable to those having serious
encryption jobs that justify higher expenses. For a 128-bit algorithm,
64-bit permutation is not too bad, I suppose, noting that for a Feistel
cipher one splits the block into two halves. Could you please explain
why you need 384-bit permutations for a 128-bit algorithm? Thanks.
Please re-read my post above: If each output bit can come from any of
the 64 possible input locations, then it will need a 6-bit number
(0..63) to specify that relationship.
Doing the same for all 64 input/output bits would then require 6*64 =
384 index/routing bits.
So, do you want something like a fixed 6-register block, where the first
register to be used is specified as part of the instruction, or do you
want to have a 384-bit immediate operand to the opcode?
Terje
--
- [EMAIL PROTECTED]
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
--
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Using CRC's to pre-process keys
Date: 9 Jul 2000 13:13:02 -0700
In article [EMAIL PROTECTED],
Mack [EMAIL PROTECTED] wrote:
If the 160-bit hash is reduced to 128 bits (again pick your method of
reducing it) collicions occur after 2^64 inputs. When you reduce your
key to produce 128 bit output the birthday paradox applies to the
reduced value not the original value.
Yes, quite right.
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?
--
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: Advanced Cryptography FAQ
Date: Sun, 09 Jul 2000 20:34:31
Cryptography-Digest Digest #187
Cryptography-Digest Digest #187, Volume #12 Sun, 9 Jul 00 20:13:01 EDT
Contents:
Re: Random Numbers (John Savard)
Re: Proposal of some processor instructions for cryptographical (David A. Wagner)
Re: Proposal of some processor instructions for cryptographical applications
("Stephen Fuld")
Re: Proposal of some processor instructions for cryptographical applications
("Stephen Fuld")
www.curious.4ears ("rosi")
Re: Proposal of some processor instructions for cryptographical (Roger Schlafly)
Re: Random Numbers ("David Hyde")
Re: Random Numbers (John Savard)
Re: Advanced Cryptography FAQ ("Trevor L. Jackson, III")
Re: Random Numbers (Nicol So)
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Random Numbers
Date: Sun, 09 Jul 2000 22:15:41 GMT
On Sun, 9 Jul 2000 18:17:16 +0100, "David Hyde"
[EMAIL PROTECTED] wrote, in part:
Does anyone know how to convert a random bit stream into random 16-bit
numbers with uniform distribution?
As others have noted, taking 16 (or 15, if you only want to generate
positive integers) bits at a time from the random bit stream, if it is
genuinely random, will do just fine.
Is it random, but biased? Is it pseudorandom, and with correlations
between the bits? As the other replies have noted, one needs to know
what other factors make this other than a truly trivial question.
Of course, if one wants to produce random integers with a uniform
distribution that range between some other set of limits than 0 and
32,767 or 0 and 65,535; say, from 0 to 999, then one does need special
techniques. They're doubtless explained somewhere on the web, but here
they are anyways, since it isn't clear what keywords to use to find
them:
Let's say you want to convert a stream of bits into uniformly
distributed numbers from 0 to 999.
Then, you start by taking the bits 10 at a time to give you a number
from 0 to 1023. If that number is less than 1000, you've got a number.
Otherwise, subtract 1000 from the number, to give you a number from 0
to 23. Treat that as a base-24 digit, and introduce it into another
accumulator (acc = acc*24 + new_digit) that holds numbers up to 24^3,
or 13824.
When this has happened three times, if the number in the accumulator
is from 0 to 12999, take the last three digits as your number.
If you want, you can take the first few digits, as a number from 0 to
12, and therefore a base-13 digit, and save them in an accumulator;
and, if you get a result you can't use, a number from 13000 to 13824,
you can subtract 13000 and save that result as a base-824 digit.
Where you want to stop, and just throw away unusable results, depends
on how efficiently you want to convert the random bit stream to a
random digit stream.
John Savard (teneerf -)
http://www.ecn.ab.ca/~jsavard/crypto.htm
--
From: [EMAIL PROTECTED] (David A. Wagner)
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: 9 Jul 2000 15:17:57 -0700
Iain McClatchie [EMAIL PROTECTED] wrote [excerpts only]:
Why bother supporting cryptography in the CPU?
- Hardware implementations of the speed-critical cyphers are _tiny_.
- Popularly-used cryptographic algorithms change very slowly.
- Connection speeds are increasing. Software encryption can keep
up with a 56 Kb/s modem just fine, but a 10 Mb/s cable modem is
a problem,
- Popular cryptographic algorithms now appear to be exportable.
Those are good points. Still, there's a definite cost, and I wonder
how compelling a need there is for hardware crypto.
Until the AES is chosen, there's no obvious single candidate for hardware
implementation. Each crypto protocol has a different favorite cipher
(SSL - RC4; IPSEC - DES; SSH - IDEA). That will likely change some
years after after the AES is chosen, but even so, I'm not convinced
there's a compelling need for hardware implementation. No matter which
AES candidate is chosen, it is likely to run at about 20 cycles/byte,
so encrypting at even 10 Mb/s should take only something like 4% of the
CPU speed, if I'm not mistaken. Is that a significant enough burden to
justify hardware implementation?
If there is no utterly compelling need for hardware crypto, do you think
the advantages of hardware implementation will still outweigh the costs?
I'm truly interested in your thoughts.
--
From: "Stephen Fuld" [EMAIL PROTECTED]
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical applications
Date: Sun, 09 Jul 2000 22:29:41 GMT
"Douglas A. Gwyn" [EMAIL PROTECTED] wrote in message
news:[EMAIL PROTECTED]...
Thomas Womack wrote:
"Mok-Kong Shen" [EMAIL PROTECTED] wrote
Transposition is one of the basic operations in cryptography.
Is it, any more? Having a look at the AES candidates, most of them
carefully refrain from calling for bit
