Cryptography-Digest Digest #181, Volume #12 Sun, 9 Jul 00 03:13:01 EDT
Contents:
Efficient algorithm to determine relative primality? (ChenNelson)
Re: Using CRC's to pre-process keys (David A. Wagner)
Re: Using CRC's to pre-process keys (David A. Wagner)
Re: Using CRC's to pre-process keys (David A. Wagner)
Re: Concepts of STRONG encryption using variable base http://www.edepot.com/phl.html
(David A. Wagner)
Re: Concepts of STRONG encryption using variable base ("Trevor L. Jackson, III")
Re: Proposal of some processor instructions for cryptographical (Nicol So)
Re: Using CRC's to pre-process keys (Nicol So)
Re: Proposal of some processor instructions for cryptographical ("Trevor L.
Jackson, III")
Re: Suggestions for crypto for constrained-memory/CPU computers? (Shawn Willden)
Re: Efficient algorithm to determine relative primality? (John Savard)
Re: Efficient algorithm to determine relative primality? ("ben handley")
Re: Using CRC's to pre-process keys (David A. Wagner)
Re: SafeIT - Untrusted encryption program. (Arturo)
Re: Is this random? (Shawn Willden)
Re: Proposal of some processor instructions for cryptographical (Terje Mathisen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (ChenNelson)
Subject: Efficient algorithm to determine relative primality?
Date: 09 Jul 2000 01:17:46 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
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.
Sincerely,
Nelson Chen
=====BEGIN PGP SIGNATURE=====
Version: PGP for Personal Privacy 5.5.2
Comment: For public key, go to key server with key ID 0xD28C0DD9
iQA/AwUBOWfTw21ACZTSjA3ZEQK0MgCgptg6AqA89Qsobp19qAaQ4mPV4SAAn2wx
V2doE1iqRMhp4hQ5XbyNb2rt
=fOR2
=====END PGP SIGNATURE=====
==========================
To earn $0.05 per clickthrough from your web page, please go to
http://www.3wmart.com/ and sign up for our button banner program.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Using CRC's to pre-process keys
Date: 8 Jul 2000 18:30:26 -0700
In article <[EMAIL PROTECTED]>,
Mack <[EMAIL PROTECTED]> wrote:
> Normally keys are preprocessed with MD5 or SHA-1
> These tend to be a bit slow.
You preprocess enough keys that the speed of SHA1 is problematic?
Are you sure? I would be very surprised.
> And also a bit of overkill if the cipher is secure.
That's not at all clear. Ciphers are analyzed under a model where
the key is chosen uniformly at random. If you take non-uniform keying
material and pass it directly to the cipher (without pre-hashing), the
security warranty has been voided, and all bets are off.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Using CRC's to pre-process keys
Date: 8 Jul 2000 18:33:25 -0700
In article <[EMAIL PROTECTED]>,
Scott Nelson <[EMAIL PROTECTED]> wrote:
> 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.
I don't think that's quite right.
Assuming SHA1 is secure, it comes close enough that
I claim the difference is pretty irrelevant.
(Unless you are hashing 2^64 keys....!)
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Using CRC's to pre-process keys
Date: 8 Jul 2000 18:37:21 -0700
In article <8k811u$j8f$[EMAIL PROTECTED]>,
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> 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.
This kind of attack looks more problematic when you consider that,
if you're pre-processing lots of input data to try to accumulate enough
entropy for your key material, then there's a reasonable chance that the
attacker may be able to control at least some of those inputs -- and the
linearity of the CRC leaves some real concerns that the attacker may be
able to exploit this problem.
Note that there is a CRC-like construction that is provably secure (when
the parameters are large enough), but one must choose the feedback polynomial
uniformly at random and keep it utterly secret and never re-use it. (The
relevant result is called the Leftover Hash Lemma.) This is of some
theoretical interest, but probably not of much help in the real world.
The constraints seem unlikely to be fulfilled in practice; if you can choose
such a feedback polynomial, you can probably just use it as your key.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Concepts of STRONG encryption using variable base
http://www.edepot.com/phl.html
Date: 8 Jul 2000 18:38:57 -0700
In article <8k86bl$q9p$[EMAIL PROTECTED]>, <[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.
Nonsense. It is trivial to ensure that brute-force attacks are utterly
infeasible. I suggest that you read up a little bit further on the
state of the art in cryptology before doing any more design work.
------------------------------
Date: Sat, 08 Jul 2000 22:42:22 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Concepts of STRONG encryption using variable base
[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.
No they cannot. Use your virtual calculator to figure out how long it would
take you to _count_ up to 2^256. Then figure out how much slower trial
decryption is compared to counting. A 256-bit key cannot be searched.
>
>
> 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".
This concept is older than some written languages.
>
>
> Using the concepts of dynamic encryption as well as dynamic bases,
> one can achieve one-time-pad security without the inconveniences
> of using it.
No.
>
>
> For more information on BASE Encryption, read it up
> here http://www.edepot.com/phl.html
Massive confusion site. Now, if you created a diffusion site, people could
use your web sites as cryptographic primitives.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Sat, 08 Jul 2000 22:53:41 -0400
Reply-To: see.signature
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...
>
> [Proposal for two new instructions: "swapping" & "mirroring", omitted]
Instead of adding specialized instructions to the instruction set that
don't have much use outside of a small class of programs, a better
approach would be to couple a processor with a reconfigurable device,
something akin to an FPGA.
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Using CRC's to pre-process keys
Date: Sat, 08 Jul 2000 23:09:44 -0400
Reply-To: see.signature
"David A. Wagner" wrote:
>
> In article <8k811u$j8f$[EMAIL PROTECTED]>,
> Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> > 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.
>
> This kind of attack looks more problematic when you consider that,
> if you're pre-processing lots of input data to try to accumulate enough
> entropy for your key material, then there's a reasonable chance that the
> attacker may be able to control at least some of those inputs -- and the
> linearity of the CRC leaves some real concerns that the attacker may be
> able to exploit this problem.
This runs counter to my intuition. Do you have a specific workable
attack in mind?
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
Date: Sat, 08 Jul 2000 23:32:11 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
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:
>
> (1) Swapping. This instruction needs an operand that specifies
> the level at which the swapping is to be done. At the first
> level, the word (register or memory) is divided into two halves
> that are exchanged in positions. At the second level, the
> swapping is done separately on each half of the word.
> Analogously for the higher levels.
Many CPUs have these kinds of instructions.
> (2) Mirroring. This also has levels similar to swapping. At the
> first level, the bits of the word referenced are exchanged by
> mirroring about the central axis. At the second level, the
> mirroring is done separately on each half of the word.
> Analogously for the higher levels.
This is called bit reversal. It is common in digital signal processing.
All of these transforms can be efficiently implemented as lookup tables
(LUT). Given a LUT you can perform arbitrary and data-dependent
transformations (because a LUT can expressed the full potential of unique
mappings from input to output). Given Ritter's Dynamic Substitution you can
customize the transformation such that each byte (or other element) of a
stream is uniquely transformed.
> Another processor instruction that I think is desirable is
> to obtain the parity of groups of bits (e.g. 4, 8, etc.) from
> consecutive words in memory and accumulate these into a word.
> This could be useful to so to say distill the entropy out of
> a given bit sequence.
This is a kind of convolution. It can be efficiently expressed as a finite
impulse response (FIR) filter.
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: Suggestions for crypto for constrained-memory/CPU computers?
Date: 08 Jul 2000 21:48:03 -0600
"John Doe" <[EMAIL PROTECTED]> writes:
> 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!
Triple DES is used extensively on smart cards with 4-bit
microcontrollers, 256 bytes (not Kbytes) of RAM and a few KB of ROM,
and provides quite acceptable performance for encrypting or decrypting
small amounts of data, even when the DES implementation is in software
(which is the norm). Actually the performance bottleneck is the
9600kb data link between the card and the host system, not the
encryption engine.
The AES ciphers promise to be far better for small software-based
devices than DES.
If you need public key crypto, rather than symmetric, it's a little
tougher. Smart cards, for example, don't have enough horsepower to do
RSA reasonable amount of time, and so we have to add hardware large
integer math coprocessors. Even then, it's a bit slow. You mentioned
handhelds, though, which generally have 10Mhz or faster CPUs in them.
There should be no problem with software implementations in these
devices.
To summarize: I think you don't have a problem.
Shawn.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Efficient algorithm to determine relative primality?
Date: Sun, 09 Jul 2000 05:33:24 GMT
On 09 Jul 2000 01:17:46 GMT, [EMAIL PROTECTED] (ChenNelson) wrote, in
part:
>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.
Actually, Euclid's method is better than polynomial time, and you
won't find one much faster. It would take a time proportional to the
logarithm of the number of digits in the number if the time for
addition and subraction were constant, and this is very good speed.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "ben handley" <[EMAIL PROTECTED]>
Subject: Re: Efficient algorithm to determine relative primality?
Date: Sun, 09 Jul 2000 18:06:21 +1200
> Actually, Euclid's method is better than polynomial time, and you won't
> find one much faster. It would take a time proportional to the logarithm
> of the number of digits in the number if the time for addition and
> subraction were constant, and this is very good speed.
Hmm, are you sure of this? I thought it was proportional to the logarithm
of the numbers, i.e. proportional to the number of digits. Are you saying
that you can find the gcd of two 1000 digits in order 10 iterations?
ben
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Using CRC's to pre-process keys
Date: 8 Jul 2000 23:16:57 -0700
In article <[EMAIL PROTECTED]>, Nicol So <see.signature> wrote:
> "David A. Wagner" wrote:
> > if you're pre-processing lots of input data to try to accumulate enough
> > entropy for your key material, then there's a reasonable chance that the
> > attacker may be able to control at least some of those inputs -- and the
> > linearity of the CRC leaves some real concerns that the attacker may be
> > able to exploit this problem.
>
> This runs counter to my intuition. Do you have a specific workable
> attack in mind?
Well, here's one. It's not a good example, because it requires a
funny assumption, favorable to the cryptanalyst and highly unrealistic.
But it's the best I can come up with at the moment.
Consider a continuous system that has a bunch of inputs (mouse, timer,
network, hard disk timings, ...) and will generate a key on demand by
sampling all its input ports and computing the CRC of its inputs,
whenever requested. Suppose the attacker has control over one of
those inputs. Suppose also that the attacker can cause new keys to
be generated whenever he likes, and can get chosen plaintexts encrypted
under those keys.
Then the attacker can try the following attack: ask for a key K to be
generated, then tweak the one input he controls by xor-ing it with a
known difference D, then ask for a new key K' to be generated. If the
attacker is lucky, maybe none of the other inputs changed in between
the two requests. If that is so, the linearity of the CRC ensures that
K,K' will have a known difference D', where D' = CRC(D). In other words,
we can predict that K' = K xor D will hold, even though we don't know
K or K' directly.
But now, on some otherwise-secure ciphers, this relation between the two
keys allows for related-key attacks that compromise the cipher. For
example: three-key triple-DES can be broken with a carefully chosen D
(choose D so that D' flips some bits in just the third key but not in
the first two keys).
The above seems pretty far-fetched.
In practice, what is perhaps more worrisome is that the structure in
the inputs might interact badly with the linearity of the CRC to cause
some entropy to be lost. For instance, we know that XOR-ing all the
inputs is bad, because if all the variability is in the least significant
bit of each of N inputs, then the XOR will have only 1 bit of entropy,
even though the concatenation of the inputs has N bits of entropy.
Similarly, what if the feedback polynomial of the CRC causes bit positions
in the different inputs to line up so that they cancel in a similar way?
If the feedback polynomial were independent from the inputs, then this
would probably not be a concern, but since the feedback polynomial is
known and chosen ahead of time and fixed for all time, one can hardly
make any reliable independence assumptions here.
In any case, we know that none of this funny business can happen if
we use a secure hash, so unless we think we understand the phenomena
here really well, the conservative choice seems to be to just hash
everything. No?
Am I missing something? Maybe I've just got unjustified paranoia on
the brain. If so, I hope you'll let me know.
------------------------------
From: [EMAIL PROTECTED]=NOSPAM (Arturo)
Subject: Re: SafeIT - Untrusted encryption program.
Date: Fri, 07 Jul 2000 08:06:10 GMT
On Thu, 06 Jul 2000 17:15:51 GMT, [EMAIL PROTECTED] wrote:
>Hi there tekkies.
>
>I have come across a company that sells an encryption program which
>primary function is to encrypt email. The company is Softnet Security
>and they spread knowledge of the products by a studied mouth-to-mouth.
>They are based in Bahamas (to get closer to the us market? yea sure).
>The program costs $10 USD (not much but PGP is for free).
>
>But the thing that make me want to post this all over sci.crypt
>is that the symmetric key algorithm used in their program are a 'trade
>secret'. Sure it's legal to do so, but not acceptable. The users buy
>the program and thinks it's safe, but it might not. It it's safe, prove
>it!
>
Don�t trust them. Either they have found the most thrilling,
attack-resistance crypto algorithm since DES or they are just trying to get
security through obscurity. IMHO, it�s just snake oil.
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: Is this random?
Date: 09 Jul 2000 00:48:37 -0600
"Simon Johnson" <[EMAIL PROTECTED]> writes:
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > I've come across a number generator written in java which claims to be
> > "truly random" number generator (not a PRNG)... Could someone tell me
> > how accurate (or inaccurate) this claim is?
> Inaccurate, a computer is a finite-state, determinsitic
> beast. Eventually, any "truly random number generator" will become
> periodic and therefore predictable. (Unless of course you use
> something attached to you're computer that records random noise or
> something along those lines.)
Yes and no. We certainly like them to be deterministic, but in fact
there is a fair bit of randomness in their operation. Mine has five
different peripherals attached to it, not counting the user interface
and storage media, each of which speaks up at various times, some
fairly predictable, and some pretty random, plus the OS does a lot of
things at different times, which creates a complex, but mostly
deterministic pattern, and then there's me.
All in all, it seems like there's enough randomness there to be useful
cryptographically. Not that the bit of Java code posted looks like a
good way to gather it. The approach taken by /dev/random feels pretty
good.
Shawn.
------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Sun, 09 Jul 2000 08:40:54 +0200
Stephen Fuld wrote:
> 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, you're absolutely right re. AES.
Since I (with 3 others) wrote the asm code for one of the original AES
submissions, I know that the few (2?) submissions that couldn't be
implemented efficiently, preferably with portable C code, got a big hit
against them early in the process.
Since these restrictions still allow for good cryptographic properties,
while allowing a 5 year old cpu to keep up with full duplex 100 Mbit/s
fast ethernet, the need for specialized crypto instructions will not
increase.
The one thing that's missing from the AES code is bignum arithmetic, for
setup/authentication, but this is being adressed anyway.
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
** 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
******************************
