Cryptography-Digest Digest #384, Volume #13 Sat, 23 Dec 00 08:13:01 EST
Contents:
Re: 64bit CRC (David HofstXX)
Re: Why primes? ("Scott Fluhrer")
Re: Q: Result of an old thread? (David Hopwood)
Re: Why primes? (Benjamin Goldberg)
Re: AIM Password Encryption (John Stanford)
Re: All irreducible polys of degree 32 over GF(2) (Bryan Olson)
Jobs at CCNY CS (MikeAt1140)
Re: All irreducible polys of degree 32 over GF(2) (Benjamin Goldberg)
Possible AONT? (Benjamin Goldberg)
Re: All irreducible polys of degree 32 over GF(2) (D. J. Bernstein)
Cryptoanalysis Illegal ??? (Mark Harrop)
----------------------------------------------------------------------------
From: David HofstXX <[EMAIL PROTECTED]>
Subject: Re: 64bit CRC
Date: Sat, 23 Dec 2000 00:00:01 +0100
Mihai Preda wrote:
> I need two independent 32bit fingerprints for a message.
IMNSHO that could never be the specification for a program. At most that
would be a restriction.
David
--
XX should be EE, that should make things work.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Why primes?
Date: Fri, 22 Dec 2000 16:24:30 -0800
Simon Johnson <[EMAIL PROTECTED]> wrote in message
news:920b9c$ogj$[EMAIL PROTECTED]...
> Hrm, well this really depends on the semantics of how the primes are
> used. Lets look an example, RSA. RSA can be summarized as follows:
>
> C=M^e mod n
> M = C^d mod n
>
> M -> Plain-text block
> C -> Cipher-text block
> e -> Public exponent
> d -> Private exponent
> n -> Modulo.
>
> Now the ability to find e from d (and d from e) is conjectured to lie
> in the problem of factoring 'n'. There is good evidence of this, but no-
> one has proved it.
Warning from the nit police: that's not precisely true. It can be shown
that the ability to find d from e is computationally equivilant to
factoring n -- that is, if you can do one, you can do the other with a
polynomial amount of effort.
What I think you meant to say is that the RSA problem (which is, given n, e,
and M^e mod n, recover M) is not known to be computationally equivilant to
factoring n -- there might be a way to solve it that does not give you d.
> Now if we pick n at random, we would have two problems. In order to
> find a public d, from a selected e we would have to factor 'n'.
> Clearly, if you can do it someone else can, so this negates the purpose
> of designing the entire system. Secondly, the factors of 'n' may be
> small, which makes for quick factoring.
>
> This is why it is a bad idea to use more than two primes for 'n',
> because you can factor a composite comprised of three factors faster
> than you can two, in general.
More from the nit police: Actually, that's not known to be true. If n is
large enough that NFS (Number Field Sieve) is the most efficient method, and
the factors are large enough that ECM (Lenstra's Elliptic Curve Method) is
of no use, then having more than two factors does not appear to make the
problem of factorization easier -- NFS does not care about the number of
factors.
--
poncho
------------------------------
Date: Sat, 23 Dec 2000 03:11:00 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Q: Result of an old thread?
=====BEGIN PGP SIGNED MESSAGE=====
Benjamin Goldberg wrote:
> Offhand, does anyone know if this key-exchange method can be turned into
> a public key encryption system?
This particular scheme is insecure. However, any secure key agreement
scheme can be efficiently turned into an IND-CCA2-secure public key
encryption scheme, using the same construction that is used by DHAES:
Michel Abdalla, Mihir Bellare, Phillip Rogaway,
DHAES: An Encryption Scheme Based on the Diffie-Hellman Problem,
Contribution to IEEE P1363a,
Updated version, March 1999.
http://grouper.ieee.org/groups/1363/P1363a/Encryption.html#ABR
This also assumes the availability of a symmetric cipher, a MAC, and a
hash function that does not interact badly with the key agreement
primitive (in practice commonly used hash functions will not interact
badly).
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOkQWwzkCAxeYt5gVAQFh7AgAyOjR8BauQyZAuNWmU70jkPSsug3RC4vy
IimI3NIGwhW4AirsA32Uk8ZYfzuw1k8TZmwOdYFuK+wDXVfRl97CsUNfzHlx4PKL
yvKgDf7vPRvBmivYvXJ4KSNIauDWtaCLQLybXRMe4a6/TH/vdDxPRKHNbD/9cYu9
1gniShzHL7QUxdirE+ydtVpUUefN1PW2nZVQwgHmLy/BN5OG+PqeUTWQFLgkdroY
5o8OKupFG3O+Vvh+/Xvy2J77xeNYm7dbSeWxE0+vrK52ynqVE1lHo+6Yyq8nr7K6
BSISR2loQtEU8+Yv82rqRWbPvb3UTpTOfN0p0+l/8FYFkVW3zxML4w==
=VTw4
=====END PGP SIGNATURE=====
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Why primes?
Date: Sat, 23 Dec 2000 05:03:44 GMT
Simon Johnson wrote:
>
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> >
> > [The irritating little gnome is
> > back with new silly questions. :)]
>
> These questions are not silly, but i agree with your gnome like
> appearance :)
>
> > I've understood it that in public/private
> > key ciphering one uses quite big prime numbers.
>
> Yes, most public key systems use large primes... Some do not, e.g. the
> knapsack algorithms.
The knapsack algorithms are broken. For better examples of PK systems
which don't use large primes, consider ECC, which can work in GF(2^N)
(that is, modulo an order n irreducible polynomial), or NTRU, which uses
a small prime modulo.
--
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: John Stanford <[EMAIL PROTECTED]>
Subject: Re: AIM Password Encryption
Date: Sat, 23 Dec 2000 05:31:31 GMT
You would think that it would be difficult, but I looked at it, and they
didn't really do a very good job of encrypting it. It uses a letter
substitution algorithm. The '˙˙' characters is just a prefix that doesn't
mean anything. Each letter or number is substituted for two letters. Each
letter has its own set of substitutes dependind on where it is. The first
letter of the password has a set of substitutes. So does the second,
third, fourth, etc. It was easy to decipher because it is a fixed key/no
key cipher. If you translate ˙˙CNPEGNHO, you get the word 'open'. The
letters used are CN PE GN HO. CN represents 'o' in the first character
space. ˙˙DBOKGHGH translates to 'snow'. DB OK GH GH are the letter
groups. 'O' is represented by GH here instead of CN because it is in the
third letter space. I found this out by just changing my password over and
over and checking the registry every time and writing down the
plaintext-ciphertext pairs until I saw a pattern. AOL really doesn't have
a very good cipher since I figured it out and I'm a begginer.
[EMAIL PROTECTED] wrote:
> In article <[EMAIL PROTECTED]>,
> John Stanford <[EMAIL PROTECTED]> wrote:
> > Is this use of a cipher that could be cracked through cryptanalysis,
> or
> > is it something else? Sorry if this is a stupid question, but I'm a
> > begginer in cryptanalysis. Thanks in advance.
>
> Theoretically it could be cryptanalyzed. However that would certainly
> be the more difficult way to go about it. I assume that password has to
> be decrypted, or it is the password equivalent (used in the stead of
> the password). Therefore either you already have the correct answer, or
> you simply have to reverse engineer the portion of the AIM code that
> decrypts the password. I use the term simply because reverse
> engineering given full access to an executable, is a much easier
> problem than cryptanalysis given no algorithm. Once the algorithm has
> been reverse engineered, then cryptanalysis becomes much easier. You
> might also consider that it may be simply base-64 encoding or something
> similar.
> Joe
>
> Sent via Deja.com
> http://www.deja.com/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: All irreducible polys of degree 32 over GF(2)
Date: Sat, 23 Dec 2000 07:40:33 GMT
Benjamin Goldberg wrote:
> Curiously, this method seems to be a way to have a secure unicast file
> transmission without having a secure cipher or secure random number
> generator -- provided that you do have a statistically good PRNG, like
> Mersenne Twister.
I think you are jumping to an unwarranted conclusion.
> The sender does the following:
> MersenneTwister_state mt( seed );
> polynomial x = 1, y, z;
> do {
> y = mt.next();
> z = crc( file, y );
> send( z ); // don't send y!!!!
> x = lcm( x, y );
> } while( x.bitlength() < file.length );
Then if the attacker knows the file, he can get the
generator output.
[...]
> Also, the same secret key can safely be used for more than one file,
> although having an IV, used similar to how ciphersaber IVs are used,
> would be a good idea (append it to the secret key, then continue
> normally).
Even with the IV, that looks bad.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (MikeAt1140)
Date: 23 Dec 2000 09:32:19 GMT
Subject: Jobs at CCNY CS
http://www-cs.engr.ccny.cuny.edu/
Jobs at CCNY CS
Student Openings
Faculty Openings
* Assistant Professor
* Assistant Professor
Student Openings
Faculty openings
Assistant Professor
Location: City College, Computer Sciences
CUNY Personnel Vacancy Notice No.: FY-797
Closing Date: 2/15/01
The City College is the oldest college of the City University of New York
system. The department of Computer Sciences resides within the School of
Engineering. The department offers the BS and MS degrees in Computer Science;
the Ph.D. is offered in collaboration with the CUNY Graduate School and a BS in
Computer Engineering is offered jointly with Electrical Engineering. The
department's active research includes work in the areas of computational
geometry, computer vision, security and cryptography, databases and information
retrieval, distributed computing, graphics, graph theory and combinatorial
mathematics, human-computer interaction,information systems, multimedia,
networking, programming languages, signal and image processing, speech
recognition, and computer science education. For further information see the
department's web site at http://www-cs.engr.ccny.cuny.edu.
Duties and Responsibilities:
Research, Teaching at the undergraduate and graduate level, as appropriate, and
Service as a participant in curriculum development and other department, school
and college committees.
Qualifications/Requirements:
Ph.D. in computer engineering or a closely related field, preferably with a
specialization in hardware-software codesign, biological, nano or quantum
computing, neural computing, networks and distributed systems, parallel
architectures, real-time embedded systems, software engineering, or VLSI
algorithms; teaching experience and clear evidence of research potential.
Salary:
Commensurate with experience and qualifications
Send CV, letter of interest, and names of three references, by February 15,
2001, to:
Professor Douglas Troeger, Chair
Computer Sciences Department (CSE2)
The City College, CUNY
Convent Avenue at 138th Street
New York, New York 10031
========================================================================
Assistant Professor
Location: City College, Computer Sciences
CUNY Personnel Vacancy Notice No.: FY-796
Closing Date: 2/15/01
The City College is the oldest college of the City University of New York
system. The department of Computer Sciences resides within the School of
Engineering. The department offers the BS and MS degrees in Computer Science;
the Ph.D. is offered in collaboration with the CUNY Graduate School and a BS in
Computer Engineering is offered jointly with Electrical Engineering. The
department's active research includes work in the areas of computational
geometry, computer vision, security and cryptography, databases and information
retrieval, distributed computing, graphics, graph theory and combinatorial
mathematics, human-computer interaction,information systems, multimedia,
networking, programming languages, signal and image processing, speech
recognition, and computer science education. For further information see the
department's web site at http://www-cs.engr.ccny.cuny.edu/.
Duties and Responsibilities:
Research, Teaching at the undergraduate and graduate level, as appropriate, and
Service as a participant in curriculum development and other department, school
and college committees.
Qualifications:
Ph.D. in computerscience or a closely related field, preferably with a
specialization in Computer Vision, Databases, Image Processing, Knowledge-based
Systems, Programming Languages, or Software Engineering. The position requires
teaching experience and clear evidence ofresearch potential.
Salary:
Commensurate with experience and qualifications
Send CV, letter of interest, and names of three references, by February 15,
2001 to:
Professor Douglas Troeger, Chair
Computer Sciences Department, (Search CS1)
The City College of New York
Convent Avenue at 138th Street
New York, New York 10031
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: All irreducible polys of degree 32 over GF(2)
Date: Sat, 23 Dec 2000 09:49:37 GMT
Bryan Olson wrote:
>
> Benjamin Goldberg wrote:
> > Curiously, this method seems to be a way to have a secure unicast
> > file transmission without having a secure cipher or secure random
> > number generator -- provided that you do have a statistically good
> > PRNG, like Mersenne Twister.
>
> I think you are jumping to an unwarranted conclusion.
Note that I only said *seems* to be. I wouldn't use this method unless
I was *sure* that it was good -- that is, until I'd seen some
cryptanalysis on it.
> > The sender does the following:
> > MersenneTwister_state mt( seed );
> > polynomial x = 1, y, z;
> > do {
> > y = mt.next();
> > z = crc( file, y );
> > send( z ); // don't send y!!!!
> > x = lcm( x, y );
> > } while( x.bitlength() < file.length );
>
> Then if the attacker knows the file, he can get the
> generator output.
Eh? How? He's got a bunch of crc's of the file. Given a file, and a
CRC, how do you reproduce the crc polynomial?
I suspect that only if the attacker knows the ENTIRE message might he be
able to get the generator output. If a different seed is used with each
message, then this is irrelevant. Logically, one should use an IV, and
hash it with the secret key to create the MT seed -- this will result in
totally unrelated MT seeds for each message.
> [...]
> > Also, the same secret key can safely be used for more than one file,
> > although having an IV, used similar to how ciphersaber IVs are used,
> > would be a good idea (append it to the secret key, then continue
> > normally).
>
> Even with the IV, that looks bad.
Well, joining the IV and seed as they are done in ciphersaber would be a
Bad Idea, but I don't think that the scheme is too terrible.
--
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: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Possible AONT?
Date: Sat, 23 Dec 2000 10:00:18 GMT
This AONT idea is based very much on the recent thread about order 32
irreducible GF(2)[x] polynomials.
The security of this is depends on both a 32 bit keyed permutation
generator, E, and a secure hash function, H.
The transform is as follows:
k = (hash output size) random bytes
counter = 0
repeat (filelength/4) times
do {
poly = E_k( counter )
counter = counter + 1;
} until( irreducible( poly ) );
crcval = crc( file, poly );
output( crcval );
H.add( crcval );
end repeat
output( H.result() XOR k );
Reversing the transform is done using CRT.
Any comments? (Other than that it's probably computationally
expensive).
--
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] (D. J. Bernstein)
Subject: Re: All irreducible polys of degree 32 over GF(2)
Date: 23 Dec 2000 10:11:11 GMT
Bryan Olson <[EMAIL PROTECTED]> wrote:
> Polynomial reconstruction can be quadratic time using Lagrange's
> interpolation formula.
Much faster methods are known. One can reconstruct a monic degree-d
polynomial from d values using O(d log^2 d log log d) coefficient
operations. If d is around N/log N then this is O(N log N log log N)
operations on (log N)-bit coefficients. The log log factors disappear
for some fields.
---Dan
------------------------------
Date: Sat, 23 Dec 2000 23:27:13 +1100
From: Mark Harrop <[EMAIL PROTECTED]>
Subject: Cryptoanalysis Illegal ???
Hi all...
As you probably know from my earlier postings (asking where archives are)
that I am a newbie, so pls pardon this question if it has been answered
before, or is just plain stupid !
From reading various books and postings on the Net, it is quite obvious
how far the USA government will go to stop export etc. of Crypto devices
and programs, but what is not quite obvious, or at least not to me ;-), is
why they haven't tried to ban Cryptoanalysis ??
Just in case I have missed something, let me know if this is an old
subject, or if the Govt. HAVE tried to stop it.
As I explore further I understand the need for thorough analysis of an
algorithm to see if it is "secure" etc, but I wonder why the Govt. readily
allows people to pull apart their crypto work without so much as a complaint??
This is, of course, assuming my question is not the complete stupid
ramblings of a newbie, but if it isn't, I would like to be enlightened.
PS. Merry Christmas to all, and a SAFE and Happy New Year !!!
Cheers!
Mark Harrop
[EMAIL PROTECTED]<mailto:>
Moderator of the following Programming Lists:
Send a empty message to:
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
Cheers!
Mark Harrop
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
Moderator of the following Programming Lists:
Send a empty message to:
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
+<(:o)|<:
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
