Cryptography-Digest Digest #73, Volume #9 Fri, 12 Feb 99 07:13:03 EST
Contents:
Re: block ciphers
Re: My comments on Intel's Processor ID Number (Gareth Williams)
Re: On a Method of Session Key Generation (revised) (wtshaw)
shuffling hexits (wtshaw)
Tell-Tale DES Byte-Length Encoding (TONY BARTOLETTI)
Factoring Complex Numbers ("Wm. Toldt")
Re: *.EXE files Encryption ("Greg Wright")
Re: Tell-Tale DES Byte-Length Encoding ([EMAIL PROTECTED])
Re: What is left to invent? (TONY BARTOLETTI)
Re: RNG Product Feature Poll ("Trevor Jackson, III")
Re: Factoring Complex Numbers ("Lassi Hippel�inen")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: block ciphers
Date: 12 Feb 99 05:45:03 GMT
Vonnegut ([EMAIL PROTECTED]) wrote:
: Ok, given a cipher w/ block length of n, the odds are pretty good, i.e.
: (n-1)/n that the last bit in the last block is a null. Could this be
: exploited in some way to reveal a part of the key, or is it standard to use
: some character other than an ASCII 0 for the nulls to fill the last block.
: I reallly have no level of experience in this stuff, but I thought I'd ask.
There were standard ways of dealing with this in older ciphers, such as
bisection. With today's ciphers, where a computer does everything before
you see the message, a slightly more elaborate scheme is needed, but it
can still be done.
However, modern block ciphers are strong enough to be impervious even to
chosen-plaintext attacks, and thus the risk of a known-plaintext attack is
not generally considered a concern.
One can either include a length code in the message, and fill with random
bits, or pad with 10000.... and *always* add the 1, even if it means
creating an extra block, the first being a safe way, the second an unsafe
way, of unambiguously indicating the message length in bits. (The length
code, of course, only needs to give the number of bits in the _last
block_). So there are many alternatives, these two being only examples.
John Savard
------------------------------
From: Gareth Williams <[EMAIL PROTECTED]>
Subject: Re: My comments on Intel's Processor ID Number
Date: Fri, 29 Jan 1999 08:35:09 +0000
Bruce Schneier wrote:
>
> I wrote a column on Intel's Processor ID number for ZDNet. You can
> read it at:
>
> http://www.zdnet.com/zdnn/stories/comment/0,5859,2194863,00.html
>
see also Paul Rubin's thread 'Some more technical info on Pentium III
serial number'
which discusses this article:
http://www.eet.com/story/OEG19990127S0011
--
Gareth Williams <[EMAIL PROTECTED]>
** DGW Software Consultants LTD *******************
* Montrose, Ledbury Rd, Ross-on-Wye, HR9 7BE, UK *
* Tel/Fax 01989 563704 *
***************************************************
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: On a Method of Session Key Generation (revised)
Date: Thu, 11 Feb 1999 22:42:36 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
> >The only measure is one of confidence, that the results cannot be
> >anticipated to some degree, and that depends too much on knowledge of the
> >method. The obscurity of resultant series depends on its
> >irreproducability by physical means, or by bulk of data in its initial
> >state, seeds and otherwise.
>
> I do not understand what you have just said, so rather than adding to
> the confusion by trying to second-guess what you might have meant, I
> will ask you to clarify that statement.
OK, confidence is a statistical measure of how sure you are. In some
areas of science, 0.05 level might be OK, which means you are 95% sure
your results are OK. It has lots to do with sampling techniques. When
you say crypto-grade, it should be defined in similiar form, like 0.001.
An error range should also be specified.
Or, did you mean you needed explanation on the second part? I allude to
an OTP and a pRNG in the same way, our wanting to make the series produced
as little likely to be reproduced by some means as possible. If a pRNG is
sufficiently obscure, then an OTP is not necessary. Consider that a pRNG
can be very complex, its initial state including many variables.
>
> >> "The world is filled with violence. Because criminals carry guns,
> >> we decent law-abiding citizens should also have guns. Otherwise
> >> they will win and the decent people will loose."
>
> Most if not all politicians are included in the criminal class in some
> fashion. The term "honest politician" is an oxymoron of the first
> order, as history has demonstrated so clearly.
Be careful, most people have done criminal things, knowingly, or not. A
criminal is only one who has been formally found guilty of a certain type
of offense. This is where some politicians mess up. To go from place to
place and preemptively call someone a criminal without a conviction to
back it up other than within a proceeding to determine such guilt as
spoken by an official accuser is slander. To continue to call someone a
criminal when not convicted is also slanderous. It is best to refer to
the accused.
Being dishonest is not necessarily criminal behavior, not suggested, as it
could be. Honesty should be the best policy, but being too honest, as in
saying things when you shouldn't and at the wrong times is not wise. I
too frequently fault myself in that area.
--
A much too common philosophy:
It's no fun to have power....unless you can abuse it.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: shuffling hexits
Date: Thu, 11 Feb 1999 22:43:02 -0600
I just completed a simple block cipher named Canadian, which converts base
100 to base 36. (Canadian is a river and also a city in Texas at about
100W 36N.) A hexit is just another information unit, like a bit, trit, or
digit; a hexit is a base 6 information unit.
Canadian works because 6^9=10,077,696, slightly more than 10^7. Each
input character in base 100 is valued in the range 00 to 99. An input
group in Canadian is seven characters, which yields 14 digits which are
divided into two 7-digit numbers.
Both seven digit numbers are converted to strings of hexits, 9 each, to
give 18 hexits. The 18 hexits are transposed according to a permuted key
of 18 elements. The new array of 18 hexits is converted to base 36
characters 00 to 55 according to a substitution key. Output groups
consist of 9 characters.
So, a group of 7 input characters gives 9 output characters. The output
set was easy, the lower case alphabet and ten digits.
The keys are THF compatible, as usual, and since the substitution key is
36 permuted characters, and the transposition key is 18 permuted
characters, the longest key this application can use is 54 characters.
Here are the defaults:
Subs(Ca): abcdefghijklmnopqr stuvwxyz0123456789
Trans(Ca): abcdefghijklmnopqr
--
A much too common philosophy:
It's no fun to have power....unless you can abuse it.
------------------------------
From: TONY BARTOLETTI <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Tell-Tale DES Byte-Length Encoding
Date: Fri, 12 Feb 1999 06:49:58 GMT
All,
There is a subtlety to DES message-length encoding that reduces
uncertainty in even a decrypt of a random message by 5-bits,
(that is, a factor of 1/32). It has to do with the way DES
encodes a file's length in the crypt-text. Some implementations
may vary, but this scheme is common among the ones I have seen.
DES LENGTH ENCODING:
====================
Since DES operates on 8-byte blocks, it must output a whole number
of blocks (crypt-text) regardless of whether the input plaintext
is or is not a multiple of 8-bytes in length.
How does DES know the original file length when decrypting?
The typical scheme, with examples to illustrate:
Let L = total number of plaintext bytes.
CASE 1. (L mod 8) <> 0
Example: Plaintext = XXXXYYYYZZZ (L=11)
This is what DES creates (block at a time) as input PRIOR to
encryption:
XXXXYYYY ZZZ????3 (L=16, '?'s are garbage, and
implementation-dependent.)
resulting in, say, crypt-text blocks CCCCCCCC CCCCCCCC.
When DES decrypts the crypt-text, it will output
XXXXYYYY for the first block, because it knows that
there are more blocks to process (1 more in this case.)
When it decrypts the second (and last) block, it checks
to determine if there are any more blocks (there are not,
since its input buffer is empty.) So it will ALWAYS take
the last byte of the decrypted block ZZZ????3 = 3 as the
number of remaining plaintext bytes to output.
Hence the final output is XXXXYYYYZZZ (11 bytes).
CASE 2. (L mod 8) = 0
Example: Plaintext = XXXXYYYYZZZZWWWW (L=16)
What DES creates (block at a time) as input PRIOR to
encryption:
XXXXYYYY ZZZZWWWW ???????0 (L=24)
producing crypttext
CCCCCCCC CCCCCCCC CCCCCCCC (L=24)
Now, as before, it simply outputs the first two blocks
during a decryption, since they are not the last block.
XXXXYYYY ZZZZWWWW
It decrypts the last block, discovers a '0' in the last
byte, and thus knows not to output ANY of this block.
DISCUSSION:
What happens during a "wrong" decryption, in EITHER case?
A wrong-decryption of the last block will cause DES to
uncover a last-byte from the last block, whose value can
range anywhere in 0...255.
Most DES implementations I've seen will test if this value
is between 0 and 7. If so (1 chance in 32) it will stupidly
put out that number of decrypt bytes from the last block
(This is good-stupid.)
But 31 out of 32 times, this value is in 8...255, and most
DES implementations will then announce:
"Error: corrupt file or incorrect key" (Not Good.)
These kinds of implementations reduce ambiguity of output,
even for "random" clear-text, by 5-bits, or a factor of 32.
So, on a brute-force attack, at most 2^51 decryptions need
any further analysis (not 2^56).
(In an exchange with Ed Gerck on the MCG discussion list,
Ed pointed out that if a "useful", statistically random
1000-bit string is DES encrypted, and an attacker decided
to keep ALL of the 2^56 decryptions around to see which one
would be useful in a future, tell-tale context, they would
need to keep about 100,000 Terabytes on hand.
Now, only about 3000 Terabytes need to be stored :)
Seriously, I think a "good" DES should do something
less tell-tale when the last byte is in 8...255, such as
output last number of bytes = (8...255) mod 8, for instance.
Or, simply drop that output block entirely.
Also, one can trivially alter DES code, so that it does not
encode length at all. The caveat: The DES routine must be
"told" ahead of time how many blocks to process.
Dos anyone out there know, offhand, if the message-length
encoding is strictly in the DES specification? Is it a
"violation" to excise it? Is it still DES?
Comments?
___tony___
------------------------------
From: "Wm. Toldt" <[EMAIL PROTECTED]>
Subject: Factoring Complex Numbers
Date: Thu, 11 Feb 1999 23:16:33 -1000
Trevor Jackson, III wrote:
> How do you feel about factoring complex numbers whose terms are
> integral?
(This was in thread "Re: Clarification on PGP. pls")
I never tried that, but here is an example:
x = (2i+3)(11i+13) = 22i^2+26i+33i+39 = 59i-17
y = (23i+31)x = 1357i^2+391i+1989i-527 = 2380i-1884
I do not feel good about this problem. How would I
factor 2380i-1884 or even know is a unique
factorization exists? Maybe there are
several complex factors which give
the same result. Clearly another
factorization exists:
2380i-1884 = 2(1190i-942)
But 59 and 17 are prime numbers in x above.
So a complex number with prime coefficients can be a composite.
This calculation is like a hash function:
it is easy to calculate a composite number from several factors,
but it is not possible to be sure which factors were used to
generate the composite complex number. How can we use this
one way hash capability to our advantage? It is unlike an
RSA composite n=pq where n has unique factors. Maybe
there is some advantage we can find in which
adversaries cannot decrypt using a public
complex composite, but user who knows the
factors can decrypt.
So people can
encrypt using the
composite, but cannot
uniquely decrypt without
knowing the factors. The message
plaintext would be parsed into real
and imaginary words before encryption.
Or maybe encrypt with factors, sign with
composite, and decrypt with factors.
There are other sequences which
may be more useful.
Any ideas on this possibility?
Wm. Toldt
------------------------------
From: "Greg Wright" <[EMAIL PROTECTED]>
Subject: Re: *.EXE files Encryption
Date: Fri, 12 Feb 1999 09:47:23 -0000
You can never stop people from completely reverse-engineering your code.
However FreeESS can help.
www.plugslot.com/FreeESS.hrm
Regards,
Greg
[EMAIL PROTECTED] wrote in message
<79nh2e$i3e$[EMAIL PROTECTED]>...
>I am a beginning C programmer.
>and when I am making for example a program that requires the password to be
>entered, any one can easily see the password by examining the program in
the
>notepad.
>
>Can anyone give me a piece of advice how to get rid of this problem?
>
>Thank'x.
>Alex.
>
>-----------== Posted via Deja News, The Discussion Network ==----------
>http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Tell-Tale DES Byte-Length Encoding
Date: Fri, 12 Feb 1999 10:00:53 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> All,
>
> There is a subtlety to DES message-length encoding that reduces
> uncertainty in even a decrypt of a random message by 5-bits,
> (that is, a factor of 1/32). It has to do with the way DES
> encodes a file's length in the crypt-text. Some implementations
> may vary, but this scheme is common among the ones I have seen.
>
> DES LENGTH ENCODING:
> --------------------
>
> Since DES operates on 8-byte blocks, it must output a whole number
> of blocks (crypt-text) regardless of whether the input plaintext
> is or is not a multiple of 8-bytes in length.
>
> How does DES know the original file length when decrypting?
> The typical scheme, with examples to illustrate:
>
> Let L = total number of plaintext bytes.
>
> CASE 1. (L mod 8) <> 0
>
> Example: Plaintext = XXXXYYYYZZZ (L=11)
>
> This is what DES creates (block at a time) as input PRIOR to
> encryption:
>
> XXXXYYYY ZZZ????3 (L=16, '?'s are garbage, and
> implementation-dependent.)
>
> resulting in, say, crypt-text blocks CCCCCCCC CCCCCCCC.
>
> When DES decrypts the crypt-text, it will output
> XXXXYYYY for the first block, because it knows that
> there are more blocks to process (1 more in this case.)
>
> When it decrypts the second (and last) block, it checks
> to determine if there are any more blocks (there are not,
> since its input buffer is empty.) So it will ALWAYS take
> the last byte of the decrypted block ZZZ????3 = 3 as the
> number of remaining plaintext bytes to output.
>
> Hence the final output is XXXXYYYYZZZ (11 bytes).
>
> CASE 2. (L mod 8) = 0
>
> Example: Plaintext = XXXXYYYYZZZZWWWW (L=16)
>
> What DES creates (block at a time) as input PRIOR to
> encryption:
>
> XXXXYYYY ZZZZWWWW ???????0 (L=24)
>
> producing crypttext
>
> CCCCCCCC CCCCCCCC CCCCCCCC (L=24)
>
> Now, as before, it simply outputs the first two blocks
> during a decryption, since they are not the last block.
>
> XXXXYYYY ZZZZWWWW
>
> It decrypts the last block, discovers a '0' in the last
> byte, and thus knows not to output ANY of this block.
>
> DISCUSSION:
>
> What happens during a "wrong" decryption, in EITHER case?
>
> A wrong-decryption of the last block will cause DES to
> uncover a last-byte from the last block, whose value can
> range anywhere in 0...255.
>
> Most DES implementations I've seen will test if this value
> is between 0 and 7. If so (1 chance in 32) it will stupidly
> put out that number of decrypt bytes from the last block
> (This is good-stupid.)
>
> But 31 out of 32 times, this value is in 8...255, and most
> DES implementations will then announce:
>
> "Error: corrupt file or incorrect key" (Not Good.)
>
> These kinds of implementations reduce ambiguity of output,
> even for "random" clear-text, by 5-bits, or a factor of 32.
> So, on a brute-force attack, at most 2^51 decryptions need
> any further analysis (not 2^56).
>
> (In an exchange with Ed Gerck on the MCG discussion list,
> Ed pointed out that if a "useful", statistically random
> 1000-bit string is DES encrypted, and an attacker decided
> to keep ALL of the 2^56 decryptions around to see which one
> would be useful in a future, tell-tale context, they would
> need to keep about 100,000 Terabytes on hand.
>
> Now, only about 3000 Terabytes need to be stored :)
>
> Seriously, I think a "good" DES should do something
> less tell-tale when the last byte is in 8...255, such as
> output last number of bytes = (8...255) mod 8, for instance.
> Or, simply drop that output block entirely.
>
> Also, one can trivially alter DES code, so that it does not
> encode length at all. The caveat: The DES routine must be
> "told" ahead of time how many blocks to process.
>
> Dos anyone out there know, offhand, if the message-length
> encoding is strictly in the DES specification? Is it a
> "violation" to excise it? Is it still DES?
>
> Comments?
>
> ___tony___
>
This problem does not occur in all modes just some like CBC.
However if one used "wrapped PCBC" like in scott19u then for
all but the very shortest mesages the problem goes away. If you
use it I would recomend 3 passes. You could use a different key
each pass.
David Scott
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: TONY BARTOLETTI <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: What is left to invent?
Date: Fri, 12 Feb 1999 11:04:45 GMT
Trevor Jackson, III wrote:
> > Only Quantum Mechanical phenomena can be proved to be completely
> > indeterminant.
>
> That's a religious statement. The meta-paraphrase goes like this: Even QM is
> not *truly* random because there are hidden variable theories that may make
> QM phenomena dependent on the prior state of the Universe. Since that prior
> state can be manipulated QM phenomena are not only biased but subject to
> manipulation by an adversary.
As I recall, Bell's Theorem demonstrates that for any proposed hidden-variables
theory, one can devise an experiment such that the predictions of that (HV)
theory will differ from values predicted in QM. Thus no such theory can be
a "superset" over QM. If ANY hidden-variables theory is correct, then QM
is not. And if QM is correct, there can be no consistent HV theory.
___tony___
> Now there is one class of phenomena that are, by definition, totally
> indeterminate and impossible to influence (although some charlatans have
> claimed to have influence, their claims are similar to the claims of
> perpetual motion vendors).
>
> There is an extensive literature on this phenomena. Because these phenomena
> orgininate from outside the observable universe they are provably independent
> of any other observable event. These phenomena are called Divine
> Intervention. The only know weakness of the DRNG is the difficulty of
> detecting a sufficient quantity of events to form a useful output rate.
------------------------------
Date: Fri, 12 Feb 1999 06:23:47 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: RNG Product Feature Poll
Dave Knapp wrote:
> R. Knauer wrote:
> >
> > On 11 Feb 1999 09:24:30 -0000, Paul Crowley
> > <[EMAIL PROTECTED]> wrote:
> >
> > >>"Equidistributed" does not
> > >> necessarily mean independent. "Independent" does not necessarily mean
> > >> equidistributed.
> >
> > >unbiased?
> >
> > Equiprobable. Lack of bias is a necessary but not sufficient
> > condition.
>
> There are already a couple of good words for this: "white" and
> "uniform." They have the additional advantage of fewer syllables.
>
> A random uniform generator is what you are looking for.
No, we cannot use the term random because it is too fuzzy. A white, uniform
generator might work, but that phrase will trigger a lot of questions of the
form "please define white" and "please definer uniform". The terms independent
and equidistributed will not trigger that kind of question.
------------------------------
From: "Lassi Hippel�inen" <[EMAIL PROTECTED]>
Subject: Re: Factoring Complex Numbers
Date: Fri, 12 Feb 1999 13:48:37 +0200
Hey, why stop at complex numbers, why not use Hamilton's quaternions?
And aren't there octaves, too?
Complexity increases as dimension grows, but that is just security by
obscurity. The pitfalls (bad keys etc.) probably increase even faster.
There must be a group theorist somewhere out there who has an answer...
-- Lassi
> Trevor Jackson, III wrote:
>
> > How do you feel about factoring complex numbers whose terms are
> > integral?
------------------------------
** 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
******************************
