Cryptography-Digest Digest #180, Volume #12 Sat, 8 Jul 00 20:13:00 EDT
Contents:
Re: Quantum Computing (Was: Newbie question about factoring) (Jerry Coffin)
Re: Using CRC's to pre-process keys (S. T. L.)
Re: Using CRC's to pre-process keys ("Adam Durana")
Re: Using CRC's to pre-process keys ("Scott Fluhrer")
Re: Concise Programming, Attn: Tom St. D & All (Rebus777)
Re: Quantum Computing (Was: Newbie question about factoring) (Roger Schlafly)
Re: Missing nuclear secrets found behind Los Alamos copy machine (Gregory Greenman)
Re: Any crypto jokes? (potentially OT) (Darren New)
Concepts of STRONG encryption using variable base http://www.edepot.com/phl.html
([EMAIL PROTECTED])
Re: Suggestions for crypto for constrained-memory/CPU computers? (Paul Rubin)
Re: Proposal of some processor instructions for cryptographical applications
("Stephen Fuld")
Re: DES Analytic Crack ("Douglas A. Gwyn")
Re: computer program: extract consonants/vowels from input ("Douglas A. Gwyn")
Re: Hash and Entropy ("Douglas A. Gwyn")
Re: Proposal of some processor instructions for cryptographical ("Douglas A. Gwyn")
Re: Concepts of STRONG encryption using variable base ("Douglas A. Gwyn")
Re: Using CRC's to pre-process keys ("Adam Durana")
Re: computer program: extract consonants/vowels from input (Darren New)
Re: Concepts of STRONG encryption using variable base (Benjamin Goldberg)
----------------------------------------------------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Crossposted-To: comp.theory
Subject: Re: Quantum Computing (Was: Newbie question about factoring)
Date: Sat, 8 Jul 2000 13:10:48 -0600
In article <8k4amk$eb1$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> 7 is seems doubtful. In this month's Physics Today,
> D. Mermin poses a useful problem for only one qubit
> (which he calls a Q-bit for some defiant reason);
> to determin the millionth bit of the binary expansion
> of sqrt(2+x). That would be big news.
>
> But I've not heard of even one qubit being exploited to
> do anything of that nature, so is it really seven ?
An announcement was recently made claiming 7 qubits. I, of course,
can't personally vouch for the accuracy or veracity of the
annoucement, but I didn't notice anyything that made it seem
particuarly likely to be inaccurate.
Keep in mind as well that while quantum computing can reduce the
number of operations necessary to do particular tasks, that quantum
computers that have been built have carried out the individual
operations _extremely_ slowly -- to the point that a conventional
computer is a LOT faster, even though it requires more operations.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (S. T. L.)
Subject: Re: Using CRC's to pre-process keys
Date: 08 Jul 2000 19:12:15 GMT
<<I.e. the SHA-1 hash of a 128 bit key isn't likely
to contain the full 128 bits, due to collisions.>>
Show me a SHA-1 collision, lamer.
-*---*-------
S.T.L. My Quotes Page * http://quote.cjb.net * leads to my NEW site.
Pages up: 419 Quotes, 52 reviews of 169 science books, and a review of
the Foundation series. Newest Page: S.T.L.'s Files for Download!
------------------------------
From: "Adam Durana" <[EMAIL PROTECTED]>
Subject: Re: Using CRC's to pre-process keys
Date: Sat, 8 Jul 2000 15:15:58 -0400
> >Normally keys are preprocessed with MD5 or SHA-1
> >These tend to be a bit slow. And also a bit of
> >overkill if the cipher is secure.
> >
> Speed is rarely an issue, but another problem
> with secure hashes is they aren't easily extensible
> to larger bit sizes. (It can be done, but it's
> not obvious how to do it.) They're also not
> guaranteed to fill the key space completely.
> I.e. the SHA-1 hash of a 128 bit key isn't likely
> to contain the full 128 bits, due to collisions.
> A 128 bit CRC of a 128 bit key _is_ guaranteed to
> have the same entropy.
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
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Using CRC's to pre-process keys
Date: Sat, 8 Jul 2000 12:39:33 -0700
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".
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.
> 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.
And, some people (including me) like massive overkill if it 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 potential weakness that the secure hash does
not share.
The whole point of the translating step is to convert the entire key phrase
into a key in such a way that as much entropy as possible in the key phrase
is present within the secret key. The ideal is that every possible key
phrase should correspond to a separate secret key. Practically speaking, a
secure hash does meet that ideal, in that collisions do exist, but we have
no way of finding them. A CRC does not.
>
> Another proposal involves a fixed non-linear table
> substitiution as the first step. An 8-bit bijective table
> with the properties that it have good avalanche
> characteristics and at least some non-linearity.
>
> The second step would be to run the output bytes
> in a CRC-like manner. ie. the bytes are
> processed so that each bit location within a byte
> is CRCed with the corresponding bits in the other bytes.
>
> For both of these methods the key is limited to 255 bytes.
> The byte 0xff and the length are then prepended to the key
> before processing. Then the final key is complemented.
What's the point to complementing the key?
> For the second method the length would be substituted but
> the byte 0xff would not.
>
> A more technical description will be released if response
> is positive.
>
> Benefits of this method over a true hash are that it allows
> mapping of weak keys to the true input and the speed
> gained.
A better way to avoid weak keys: choose an encryption algorithm with no
(known) weak keys. They do exist (for example, all of the AES finalists).
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Rebus777)
Subject: Re: Concise Programming, Attn: Tom St. D & All
Date: 08 Jul 2000 19:59:08 GMT
>
>http://radsoft.net/bloatbusters/
>
>I was directed to this site in another News Group
>and as I read the pages I thought of some of you
>in sci.crypt that are ANTI_BLOATWARE.
>
>Have a look and help fight for the cause!
This site seems to navigate as several pages one after the other. Click the
MORE button at the end of each page to progress.
-RSC
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Crossposted-To: comp.theory
Subject: Re: Quantum Computing (Was: Newbie question about factoring)
Date: Sat, 08 Jul 2000 14:14:08 -0700
Jerry Coffin wrote:
> An announcement was recently made claiming 7 qubits. I, of course,
> can't personally vouch for the accuracy or veracity of the
> annoucement, but I didn't notice anyything that made it seem
> particuarly likely to be inaccurate.
Like this?
Up to now, proposed "quantum error correction" schemes have shown
merely how to preserve the state of qubits. Now, Los Alamos
researchers (Raymond Laflamme, 505-665-3394) have developed an
algorithm for carrying out reliable calculations on a "qubyte"
made of 7 entangled qubits while accounting for the possibility
that one of the qubits is corrupt (upcoming paper in Phys Rev Lett).
http://www.aip.org/enews/physnews/1996/physnews.293.htm
It seems they developed an algorithm, not a computer or
actual physical qubits.
------------------------------
From: Gregory Greenman <[EMAIL PROTECTED]>
Crossposted-To: alt.war.nuclear
Subject: Re: Missing nuclear secrets found behind Los Alamos copy machine
Date: Sat, 08 Jul 2000 21:26:01 GMT
Michael Kagalenko wrote:
> Gregory Greenman ([EMAIL PROTECTED]) wrote
> ]> Heck, I have a satellite dish at home that has
> ]> encryption, after a fashion.
> ]
> ]That encryption is not of sufficient strength to protect data as
> ]sensitive as this. I would posit that any encryption scheme that
> ]is simple enough that a set-top box can decode it in real time, albeit
> ]with a known decoding algorithm; is insufficiently secure to stand
> ]up to a cryto-analytic attack of any great length of time.
>
> That statement is false. A set-top box has enough computing power to
> implement an algorithm like Skipjack or Blowfish, which have been
> extensively attacked by the best cryptographers.
Michael,
Do you know if Skipjack and/or Blowfish encryption is approved to
safeguard classified data of the Secret Restricted Data variety?
Dr. Gregory Greenman
Physicist
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Any crypto jokes? (potentially OT)
Date: Sat, 08 Jul 2000 21:30:54 GMT
Boris Kazak wrote:
> > Isn't that WOM memory.
> > AKA, Write Only Memory
> A very well-known device, usually called "sink" or "null-device".
> You direct all software trash towards it.
Actually, there are some versions of plasma displays that don't need to be
refreshed, but the machine can't read what's being displayed. That would be
a WOM also.
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"We have large financial earlobes."
------------------------------
From: [EMAIL PROTECTED]
Subject: Concepts of STRONG encryption using variable base
http://www.edepot.com/phl.html
Date: Sat, 08 Jul 2000 21:27:24 GMT
We all know that encryption these days are weak. Weak in the sense
that they are static and can be brute force searched by permutating
through the keyspace of the encyption key.
One of the most revolutionary concepts of encryption that I have
come up with is dynamic encryption and the use of dynamic algorithm
and "keys".
Using the concepts of dynamic encryption as well as dynamic bases,
one can achieve one-time-pad security without the inconveniences
of using it.
For more information on BASE Encryption, read it up
here http://www.edepot.com/phl.html
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Suggestions for crypto for constrained-memory/CPU computers?
Date: 8 Jul 2000 22:24:33 GMT
In article <[EMAIL PROTECTED]>,
John Doe <[EMAIL PROTECTED]> wrote:
>I'm trying to protect sensitive data stored on a range of
>constrained-memory/CPU devices (handhelds, etc.). The data would never
>actually be *encrypted* on the device - larger/faster computers would handle
>that - the little guy must be able to decrypt reasonably fast though.
>
>I've seen algorithms that do the opposite: fast/easy encryption, intensive
>decryption, but what I need is just the opposite. Any pointers and
>suggestions would be much appreciated!
If you're thinking of public key algorithms, all the ones I know of
are slower at decryption than low-exponent RSA is at encryption.
However, on most current handheld PDA's (e.g Palm Pilot), you can still
do public key decryptions fast enough for reasonable interactive use.
If you're trying to make a decryption token, lots of smart card cpu's
that are otherwise much slower than a PDA already have public key
accelerators so you can also do decryption fairly fast.
If you can say exactly what you're trying to do (what application and
what hardware), you may get specific advice here.
------------------------------
From: "Stephen Fuld" <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical applications
Date: Sat, 08 Jul 2000 22:31:28 GMT
"Terje Mathisen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Mok-Kong Shen wrote:
> >
> > Transposition is one of the basic operations in cryptography.
> > However, it is in my view poorly supported currently by processor
> > instructions at the bit level at which all modern block ciphers
> > operate. For, while there are AND, OR and SHIFT/ROTATE
> > instructions to realize any arbitrary permutations of the bits
> > of a computer word, it can be very cumbersome and hence
> > inefficient to do so. Thus I like to suggest that future
> > processors will have an instruction to facilitate implementation
> > of encryption algorithms that employ arbitrary, eventually
> > dynamically determined, permutations of bits. Such an
> > instruction will naturally need two operands, one referencing
> > either a register or memory word and the other an arrary of
> > bytes/words that specify the target positions of the individual
> > bits. Since this very general instruction may be comparatively
> > costly in execution time, I think that the following two
> > special instructions could be desirable in addition:
>
> 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. :-()
>
> As the regulars here (or Deja) can confirm, I'd love to have an opcode
> like this, but I really don't see it as very likely. This is an awful
> lot of hw to dedicate to a very specialized task, unless you want to use
> the same hw to implement a single-bit latency full mesh 64x64 switch
> matrix.
>
> More reasonable would be a way to combine a couple of
> lower-level/smaller shuffle opcodes, the Motorola Altivec has afaik got
> the most useful version of this today.
>
> Terje
>
> --
> - <[EMAIL PROTECTED]>
> Using self-discipline, see http://www.eiffel.com/discipline
> "almost all programming can be viewed as an exercise in caching"
>
While I agree with Terje that new interesting instructions are fun to figure
out and give a "eureka" like feeling when you see how they speed up some
useful task, I think the trend in cryptography algorithms is away from this
kind of requirement. Look at the requirements for AES (The US Government's
replacement for DES as a federal standard). One of the requirements was
efficient implementation on current generation 32 bit systems (and also on 8
bit smart card type processors). If you look at the actual submissions, as
a result, they tend not to require this kind of thing. Some don't even
require a multiply instruction or data dependent rotates.
--
- Stephen Fuld
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: DES Analytic Crack
Date: Sat, 08 Jul 2000 18:48:40 -0400
Volker Hetzer wrote:
> The problem is not to hold them in RAM but to solve them.
Actually, up until that point the discussion had been about
whether the DES enciphering equation itself was too big.
> You can try to solve the equation for the key bits or you
> could try to find bits that make the equation true.
There is no difference between solving for the key bits and
finding the key bits that make the expression true.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: computer program: extract consonants/vowels from input
Date: Sat, 08 Jul 2000 18:52:16 -0400
Whether a letter is more correctly classified as a consonant or
as a vowel is, as you observe, context dependent. Unfortunately,
no small set of rules suffices to make a correct determination in
all cases. There are technical methods that will do a good job
*on average*, but they are unlikely to work well on such a short
sample as a person's name.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Hash and Entropy
Date: Sat, 08 Jul 2000 18:58:39 -0400
Mark Wooding wrote:
> * `cleave' means both `separate' or `cut', ...
Why did you give the scissors to Junior?
Because Mommy's little baby loves shortening bread!
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Sat, 08 Jul 2000 19:04:13 -0400
Mok-Kong Shen wrote:
> Transposition is one of the basic operations in cryptography.
> However, it is in my view poorly supported currently by processor
> instructions at the bit level ...
To the contrary, a general bit-set transformation requires a large
number of bits to describe it, which might as well be organized in
a lookup table: transformed = table[input]; // very speedy.
This method is used in virtually every fast implementation of block
ciphers. Limiting the architectural support to simple shuffles of
the bits rather than general transformations seems pointless.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Concepts of STRONG encryption using variable base
Date: Sat, 08 Jul 2000 19:07:04 -0400
[EMAIL PROTECTED] wrote:
> We all know that encryption these days are weak. Weak in the sense
> that they are static and can be brute force searched by permutating
> through the keyspace of the encyption key.
What planet are you from?
------------------------------
From: "Adam Durana" <[EMAIL PROTECTED]>
Subject: Re: Using CRC's to pre-process keys
Date: Sat, 8 Jul 2000 19:30:01 -0400
"S. T. L." <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> <<I.e. the SHA-1 hash of a 128 bit key isn't likely
> to contain the full 128 bits, due to collisions.>>
>
> Show me a SHA-1 collision, lamer.
If you weren't such an idiot and anxious to flame someone you would have
thought a little bit more before you posted. Collisions exist in ALL hash
functions. You can't represent X-bits of information with Y-bits, where Y
is less than X without collisions existing. But that's probably over your
head.
- Adam
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: computer program: extract consonants/vowels from input
Date: Sat, 08 Jul 2000 23:49:32 GMT
> 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.
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"We have large financial earlobes."
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Concepts of STRONG encryption using variable base
Date: Sat, 08 Jul 2000 23:53:27 GMT
Douglas A. Gwyn wrote:
>
> [EMAIL PROTECTED] wrote:
> > We all know that encryption these days are weak. Weak in the sense
> > that they are static and can be brute force searched by permutating
> > through the keyspace of the encyption key.
>
> What planet are you from?
I think he's from Venus.
------------------------------
** 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
******************************
