Cryptography-Digest Digest #249, Volume #13 Fri, 1 Dec 00 00:13:01 EST
Contents:
Rudimentary Encryption ("Potyanimal")
Cryptosecurity by another name (John Savard)
'Secrets of War' available on DVD (John Savard)
Re: keysize for equivalent security for symmetric and asymmetric keys (David
Schwartz)
Re: Rudimentary Encryption (John Savard)
Re: How to find celebrity (James Felling)
PGP vs S/MIME
Re: Pentium 4 and modular exponential (Jason Stratos Papadopoulos)
Re: Trivial Encryption Algorithm (TEA) (Tom St Denis)
Re: Trivial Encryption Algorithm (TEA) (Paul Rubin)
Re: Vulnerability to Attack (Thomas Wu)
"Minesweeper" algorithm? (Max Polk)
Re: RC4 Questions ("CMan")
Re: New cipher idea (Benjamin Goldberg)
----------------------------------------------------------------------------
From: "Potyanimal" <[EMAIL PROTECTED]>
Subject: Rudimentary Encryption
Date: Thu, 30 Nov 2000 23:24:30 GMT
I need help with an encryption scheme that i'm sure will be easy for some of
you to figure out, but I'm just a novice. So here it is. I have a program,
not a very important program, and so doesn't have strong encryption, but it
does encrypt the password into a file on my network. Often I am in need of
changing the value of the encrypted password, and if I could write a program
to give me the encrypted password, it would make my job very easy. I'm
ignorant when it comes to crypto but this is what i've been able to dig up.
1) The encrypted password is the same length as the unencrypted password.
2) The seed is stored along with the encrypted password.
Examples (exact copy):
1) SEED$1:"aaaa" = "pC=
2) SEED$1:"aaaaaa" = "pC=@s
3) SEED$1:"aabaaa" = "p;=@s
...So it's the encrypted value of "abc" is stored in the form of
SEED$n:"xyz" where n is obviously the seed and xyz is the encrypted value.
Also, the crypted value can be placed in the password box to uncover the
password in the crypted value, as long as it retains the same seed.
I could talk all day about this stuff but I'm sure some one out there can
figure this out in less time than it take me to type this. I'm looking for
a formula of somekind to so that I can generate the seed and encrypted
password to manualy insert into the program.
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Cryptosecurity by another name
Date: Thu, 30 Nov 2000 23:26:21 GMT
The entropy of a sequence of bits is the actual number of real random
bits it contains.
The Kolmogorov (Chaitin, Solomonoff) complexity of a sequence is the
minimum length of a computer program (or other type of description)
that would generate that sequence. (Note that the running time of the
program is irrelevant.)
There is, of course, the famous 'nineteen syllables' argument that
Kolmogorov complexity isn't really a well-defined construct, but I'm
not prepared to go into this here.
A cryptosecure PRNG produces a sequence with a _low_ Kolmogorov
complexity. However, it is 'high' in something else:
given a class of N sequences of bits, basically generated the same way
(so their Kolmogorov complexity is constant) by a program whose
minimum running time is T (which may be longer than the program of
minimum length which gave them their Kolmogorov complexity), then,
given one of those sequences, clearly the specific sequence can be
identified in time N*T. Perhaps it can be identified in less time.
Now, has this property of a family of sequences of bits been given a
short name? We tend to refer to it as the 'time complexity of
recovering the key of a stream cipher'.
Note, too, that this is not yet the quantity G which was posited in
another thread. Let us again think of a class of N sequences of bits,
but now let the sequences be infinite. G would be the number of bits
of a sequence one requires so that identifying which of the N
sequences it is becomes 'feasible' in some sense.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: 'Secrets of War' available on DVD
Date: Thu, 30 Nov 2000 23:28:32 GMT
so there is a way to see it, even if a somewhat expensive one, for
those in places where it was not telecast. Well, at least here in
Canada, in Region 1.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Thu, 30 Nov 2000 15:21:28 -0800
Richard Heathfield wrote:
> a colossal number. But, if Moore's Law holds (and I recognise that it's
> a big IF), the day may eventually come when 128 bits isn't enough. Of
Moore's Law does not need to continue to hold for your argument to be
correct. The rate of growth of computing power just has to stay the
same.
DS
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Rudimentary Encryption
Date: Fri, 01 Dec 2000 00:15:44 GMT
On Thu, 30 Nov 2000 23:24:30 GMT, "Potyanimal"
<[EMAIL PROTECTED]> wrote, in part:
>Examples (exact copy):
>1) SEED$1:"aaaa" = "pC=
>2) SEED$1:"aaaaaa" = "pC=@s
>3) SEED$1:"aabaaa" = "p;=@s
Well, from this, it's obvious that you can make a table that looks
like:
123456
=========
a "pC=@S
b ;
Since ; isn't the next ASCII character following C, it isn't XORing a
fixed sequence of bits with your password, but it is using a fixed
sequence of alphabets.
Maybe it's simulating a rotor machine.
So just use passwords aaaaaaaa, bbbbbbbb, .... zzzzzzzz and the same
for caps, digits, and so on, and you've got it cracked.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: How to find celebrity
Date: Thu, 30 Nov 2000 18:37:38 -0600
Excellent and correct, but I was attempting to provide a plausible, but
incorrect answer.
Benjamin Goldberg wrote:
> James Felling wrote:
> >
> > [EMAIL PROTECTED] wrote:
> >
> > > Among n people, a celebrity is someone who everyone knows but who
> > > knows no one. To identify the celebrity, if one exists, you are
> > > allowed to ask questions of any of the n people, but only of the
> > > form: "Excuse me, do you that person over there?" Assume that all
> > > answers are correct. Minimize the number of questions you need to
> > > ask to determine the celebrity, if one exists, or to determine no
> > > celebrity exists in a given set of n people.
> > >
> > > suggestions please
> >
> > Learn basic induction.( this problem is easily solved through the use
> > of mathematical induction)
> >
> > the answer as to the minimum is n^2-n. The question then is why is
> > this true?
>
> Actually, the answer is in O(N), not O(N**2) -- actually between 2N-2 in
> the best case, and 3N-2 in the worst case.
>
> Done properly, each of the first N-1 questions asked eliminated exactly
> one person from the set of people who might possibly be a celebrity.
> There is then exactly one person left, who might or might not be a
> celebrity, and this needs close to 2(N-1) questions to determine if this
> is so (slightly fewer, because some of the questions have already been
> asked).
>
> I have some psuedocode showing how to do this down below.
>
> Other good questions are:
> 1) In what order would you ask the questions to get the minimum?
> 2) what is the minimum number of questions in the worst case? (3N-2)
> 3) what is the minimum number of questions in the best case? (2N-2)
> 4) what is the minimum number of questions in the average case?
> (I dunno, I think this might be a difficult problem)
>
> The method I believe would be optimal for identifying the celebrity is
> this:
>
> Set S = an ordered set of all the people (initially size N)
> Set T = a copy of set S
> While( |S| > 1 )
> X = knows( S[0], S[1] ) ? 0 : 1;
> // If S[0] knows anyone, S[0] is not a celebrity
> // If S[1] is not known, S[1] is not a celebrity
> S -= { S[X] };
> }
>
> // It is quite clear that the above takes exactly N-1 questions.
> // If we know that there exists exactly one celebrity in the group
> // we can stop here.
>
> // Having eliminated all of the people who cannot be a celebrity, we
> // are left with one person who might be a celebrity. However, since
> // it is possible that the crowd contains no celebrities at all, this
> // might be a false positive, so we need to confirm that the one person
> // in set S actually is one.
>
> foreach person P in ( T - { S[0] } )
> if( knows( S[0], P ) )
> There is no celebrity
> if(!knows( P, S[0] ) )
> There is no celebrity
> // The above takes between N-1 and 2N-1 questions, depending on how
> // many are repeat questions from the first loop.
>
> S[0] is the celebrity
>
> Note that S would be best implemented as a linked list, not an array.
> The "knows" function keeps a cache of all answers, and doesn't count as
> a question unless it hasn't been asked before. The cache is only needed
> for the second loop, and if the cache is left out, the second loop takes
> 2N-2 questions to prove that S[0] is a celebrity.
>
> --
> There are three methods for writing code in which no bug can be found:
> 1) Make the code so straightforward that there are obviously no bugs.
> 2) Make the code so complicated that there are no obvious bugs.
> 3) Insist that any apparent bugs were really intentional features.
------------------------------
From: <[EMAIL PROTECTED]>
Subject: PGP vs S/MIME
Date: Fri, 1 Dec 2000 09:27:16 +0800
A newbie here. What's the different between two? Any recommended sites or
book for reading?
Thanks.
Rgds,
SYWai
------------------------------
From: Jason Stratos Papadopoulos <[EMAIL PROTECTED]>
Subject: Re: Pentium 4 and modular exponential
Date: 1 Dec 2000 01:38:41 GMT
[EMAIL PROTECTED] wrote:
: Paul Rubin <[EMAIL PROTECTED]> wrote:
:> Interesting, thanks. I'd want to use integer instructions for modexp,
:> of course.
: The integer ops look like they'll probably be better for most
: everything, honestly.
The latencies on the critical integer ops for modexp() are terrible,
though; add with carry takes 8 clocks and can only be started every
3rd clock. The double-size integer multiply takes 14-18 clocks, worse
even than the old Pentium on a clock-for-clock basis (of course, the
clock rate is much higher).
With SSE2 things become a bit better. The holy 32x32->64 packed multiply
takes (I think) 8 clocks, so you'd need a really deep pipeline to manage
high throughput for multiprecision arithmetic. And with only 8 registers,
you have to rely on register renaming to do it. Even an SSE2 register move
takes 6 clocks of latency!
People have already begun experimenting with multiple precision and SSE2,
and the consensus seems to be that, like MMX, not having carry bits is a
horrible pain. I still think the best way to implement modular
exponentiation on the P4 uses the right-to-left method and interleaves
the two working variables; the low 64 bits of a register get 32 bits of
(base)^(power of two) and the high 64 bits get 32 bits of the running
product. This way, the computations take constant time independent of the
character of the exponent, and all the problems with propagating carries
within an SSE2 register go away.
jasonp
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Trivial Encryption Algorithm (TEA)
Date: Fri, 01 Dec 2000 01:54:02 GMT
In article <905t2p$t7t$[EMAIL PROTECTED]>,
"James Dabbs" <[EMAIL PROTECTED]> wrote:
> I've seen a brief history of this algorithm. First, it was invented,
then
> someone broke it, then the author "fixed" it by changing the key
digest.
> However, the present status of this algorighm is unclear to me. Does
anyone
> know how the "revised" TEA stacks up against 3DES and other block
cyphers?
> TEA is interesting to us because of the low CPU overhead - but we
don't want
> to use it if it's "weak" in some way we don't understand.
Low CPU overhead? My best ASM coding takes 900 cycles on a k6-II
compared to 125 cycles/block of RC5...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Trivial Encryption Algorithm (TEA)
Date: 30 Nov 2000 18:13:44 -0800
Tom St Denis <[EMAIL PROTECTED]> writes:
> > TEA is interesting to us because of the low CPU overhead - but we don't want
> > to use it if it's "weak" in some way we don't understand.
>
> Low CPU overhead? My best ASM coding takes 900 cycles on a k6-II
> compared to 125 cycles/block of RC5...
Low memory overhead (ram+program space) might be more accurate.
It's very good at that.
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: Vulnerability to Attack
Date: 30 Nov 2000 19:36:33 -0800
"James Dabbs" <[EMAIL PROTECTED]> writes:
>
> The password note is interesting. It would seem to be that this is a clear
> weakness of the protocol with a documented history of similar problems. In
No discussion of this sort would be complete without a recommendation for
strong password authentication protocols, like SRP, SPEKE, or PAK.
Instead of relying on making passwords as hard to remember as they are
hard to guess, just use better cryptography to improve resistance to
cracking without resorting to indecipherable (and forgettable) passwords.
http://srp.stanford.edu/
http://www.integritysciences.com/
> this system, passwords are pre-generated by a machine as part of the
> manufacturing process of the client box. After the systems are in the
Doesn't matter - this can be broken if *any* of the passwords are *ever*
weak. You don't get the secure chaining effect you're looking for if
you use a weak authentication protocol like C/R or CHAP.
> field, the client box can change the password by generating a random string
> and passing it to the server under protection of the *current* key from the
> *current* password. These boxes are physicsally secure - if they are not,
> then there is no need for a culprit to bother to crack the link because he
> can probably get what he wants right there. However, it has always bothered
> me that if someone cracked the code, he could "follow" all password changes
> after that.
>
> Thanks..
>
> James Dabbs
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
From: Max Polk <[EMAIL PROTECTED]>
Subject: "Minesweeper" algorithm?
Date: Fri, 01 Dec 2000 03:48:25 GMT
We all know of the Windows "minesweeper" game, where you are only told
how many bombs are adjacent to each square, and where you have to use
logic to determine where the bombs are.
If we turned a message into bits and formed a grid from these bits, where
each bit is a "bomb" as if we were playing the "minesweeper" game,
couldn't we calculate the relative bit density of each square, just as in
the minesweeper game, to arrive at an encrypted message made up of
relative bit density counts?
And then we could decrypt by programmatically "playing minesweeper" to
arrive at the original message.
To add real meat to the encryption, could we take the output of one phase
of this encryption, and after evening out and scattering the bits with
some standard intermediate phase, feed it right back in to the same grid,
but using a different grid width, and calculate relative bit densities
from that?
If so, the "key" would be which grid width you used on the first phase,
followed by which grid width you used on the second phase, and so forth.
By making the grid width highly variable, I feel that this may be
mathematically complicated to break.
After all, the basis is not the conventional technique of taking blocks
of data and performing well-known bit manipulation like xor, add,
subtract, invert, reverse, look-up tables, and so forth, on it.
Instead, it is based on "playing minesweeper" which adds the need for
game-playing logic to crack it. Can anyone please point out weaknesses I
am missing?
------------------------------
From: "CMan" <[EMAIL PROTECTED]>
Subject: Re: RC4 Questions
Date: Thu, 30 Nov 2000 21:53:20 -0700
No, I don't think so.
In RC4, which is the subject here, there are exactly 16 rows of 16 bytes, I
have watched the algorithm play out on a debugger enough times to know that.
The number of combinations is irrelevant. The storage requirement is 2048
bits for the RC4 S-box.
If we are talking about RAM, the storage requirement is 2048 bits (plus a
few bytes for the counters and modulo addition).
JK
--
CRAK Software
http://www.crak.com
Password Recovery Software
QuickBooks, Quicken, Access...More
Spam bait (credit E. Needham):
root@localhost
postmaster@localhost
admin@localhost
abuse@localhost
webmaster@localhost
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
"Richard Heathfield" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> CMan wrote:
> >
> > >
> > > First off I suggest you study what an sbox is first. A 16x16 sbox
> > > requires 128kb of ram and would actually slow down RC4 (on a commodity
> > > desktop). A 32x32 is infeasible at best.
> >
> > Um...
> > Yer math seems a bit off here. On my slide rule, I get the following:
> >
> > I calculate 2048 bits required to implement a 16 bytes/row by 16 row
RC4
> > S-box. 16 X 16 = 256 bytes. 256 bytes X 8 bits/byte = 2048 bits!
> >
> > That is if I have studied what an s-box is. :--))
>
> No, 16x16 in this context means you put 16 bits in, and you get 16 bits
> out.
>
> Since there are 65536 different combinations of 16 bits, you will need
> 65536 different values in your S-box, so you need an array of 65536
> 16-bit quantities. Thus, 128KB is correct.
>
>
> --
> Richard Heathfield
> "Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
> C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
> K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: New cipher idea
Date: Fri, 01 Dec 2000 05:04:46 GMT
Mok-Kong Shen wrote:
>
> Benjamin Goldberg wrote:
> >
> > The global variable mask contains coefficients for 8 parallel (using
> > SIMD) order 16 primitive polynomials in GF(2)^N.
>
> Questions of ignorance: What is N? In the books I have,
> I see only primitive polynomials over GF(p^m) but never
> over GF(q)^n. Could you recommend a book (or papers)
> that contains good treatment of the latter kind of objects?
> Thanks.
>
> M. K. Shen
(somefield)^N means that you have a vector of N independent items.
Multiplication is like addition; there are no dot products.
Multiplication of two values a and b in GF(2)^8 means that to get the
nth (where n is 0..7) bit of the result, multiply (in GF(2)) the nth bit
of a and the nth bit of b. This is the same as doing logical and
(operator "&" in C or C++) of two 8 bit values.
Addition of two values in GF(2)^8 is similar. The C or C++ equivilant
is doing XOR (operator "^") of two 8 bit values.
The primitive polynomials are not over GF(2)^8. They are over GF(2^16).
The mask and the pieces of data are combined using multiplication over
GF(2)^8.
Here's an example of multiplication in GF(256)^4 :
int32 a = <something>, b = <something>, c;
int8 *aa = &a, *bb = &b, *cc = &c;
cc[0] = aa[0] * bb[0]; cc[1] = aa[1] * bb[1];
cc[2] = aa[2] * bb[2]; cc[3] = aa[3] * bb[3];
return c;
The automatic truncation of 8 bit integers automatically puts the
operations into GF(256).
How you would represent values in arbitrary GF(N)^M is up to you.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
** 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
******************************
