Cryptography-Digest Digest #407, Volume #13 Mon, 1 Jan 01 17:13:01 EST
Contents:
Re: Distributing private keys on the internet (Francois Grieu)
RSA Attacks ("The Death")
Re: Distributing private keys on the internet (Tom St Denis)
GOST 28147-89 ("[Basic]")
Re: A Censorship Resistant Digital Magazine Scheme (Mok-Kong Shen)
Re: RSA Attacks (Quisquater)
Idea for Independent Study Project ([EMAIL PROTECTED])
Re: Possible AONT? (David Hopwood)
Re: GOST 28147-89 (Tom St Denis)
Re: GOST 28147-89 (Tom St Denis)
Re: AES in optimized x86 assembler? (Marc)
Re: Distributing private keys on the internet (Bill Unruh)
Re: AES in optimized x86 assembler? (Paul Rubin)
Re: AES in optimized x86 assembler? (graywane)
computing RSA keys ([EMAIL PROTECTED])
Re: Genomes (wtshaw)
Re: A Censorship Resistant Digital Magazine Scheme (wtshaw)
----------------------------------------------------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: Distributing private keys on the internet
Date: Mon, 01 Jan 2001 19:43:37 +0100
Bob Silverman <[EMAIL PROTECTED]> wrote
> (..) impersonation attacks are thwarted by proper use
> of identity checking procedures (such as certificates) and
> by key authentication techniques following the key exchange
> (i.e. use of MacTags and keyed hashes).
A websearch for "MacTags" gave nothing, and I failed to
decipher a typo.
Francois Grieu
------------------------------
From: "The Death" <[EMAIL PROTECTED]>
Subject: RSA Attacks
Date: Sun, 31 Dec 2000 22:23:43 +0200
I have started learning the field of encryptions. What attacks are used
against RSA? I currently know of:
* Regular Factoring
* Initial Segment
* Fermat Factoring
* Pollard's p-1
* Guessed Text (Not really attacking RSA, but a specific message)
* Several more that are related to shared keys
Any other attacks i should know?
The Death
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Distributing private keys on the internet
Date: Mon, 01 Jan 2001 19:21:27 GMT
In article <92d5ie$fin$[EMAIL PROTECTED]>,
Bob <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Steve K) wrote:
> > -----BEGIN PGP SIGNED MESSAGE-----
> >
> > On Wed, 27 Dec 2000 14:59:38 GMT, Bob <[EMAIL PROTECTED]>
> > wrote:
> >
> > >Is anyone in this newsgroup paranoid about distributing private
keys
> > >over the Internet?
> >
> > Probably not. The whole point of asymmetric ciphers is that it's
> > safe to distribute public keys publicly. Unless someone has made a
> > completely unexpected breakthrough that allows them to factor the
> > product of two large (*very* large) prime numbers, public key crypto
> > is highly secure. The largest risk in public key encryption is that
> > the machines it is used on generally have network connections and
may
> > be vulnerable to electronic break-ins.
> >
> > Knowing this gives the attacker no advantage, but allows anyone to
> > send plaintext down a one-way hole that only I can extract if from:
> >
>
> Well, I don't have a problem with public keys. Its the private keys.
>
> How do you send a private key securely over the Internet if a 3rd
party
> is listening to everything you send and has your client software along
> with a good debugger that allows him to easily write a private key
> cracking program?
>
> I don't think private keys are safe to transmit over the Internet.
> Please, somebody tell me I'm wrong. I would love to be wrong...
When do you ever transmit private keys? Maybe you are talking about
hybrid systems? That's a bit different!
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "[Basic]" <[EMAIL PROTECTED]>
Subject: GOST 28147-89
Date: Mon, 1 Jan 2001 20:46:41 +0100
Hi,
I need some test values for the GOST 28147-89 algo. If anyone could please
encrypt a block of 8 {0} bytes with a key array of 32 {0} bytes and the
S-Boxes as followed in ECB mode.
SBox_one 4,10,9,2,13,8,0,14,6,11,1,12,7,15,5,3
SBox_two 14,11,4,12,6,13,15,10,2,3,8,1,0,7,5,9
SBox_three 5,8,1,13,10,3,4,2,14,15,12,7,6,0,9,11
SBox_four 7,13,10,1,0,8,9,15,14,4,6,12,11,2,5,3
SBox_five 6,12,7,1,5,15,13,8,4,10,9,14,0,3,11,2
SBox_six 4,11,10,0,7,2,1,13,3,6,8,5,9,12,15,14
SBox_seven 13,11,4,1,3,15,5,9,0,10,14,7,6,8,2,12
SBox_eight 1,15,13,0,5,7,10,4,9,2,3,14,6,11,8,12
Thx for your help
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: alt.cypherpunks
Subject: Re: A Censorship Resistant Digital Magazine Scheme
Date: Mon, 01 Jan 2001 20:57:18 +0100
George Weinberg wrote:
>
> Systems like I'm discussing tend to assume that at
> least the vestiges of the rule of law will still be around
> i.e. innocent until proven guilty implies you can have
> a bunch of what looks like random bits sitting on your hard
> drive and prosecuters would have to prove that there's
> something illegal encrypted there.
I am not sure that the authorities would have to prove
that before demanding from you the key to decrypt. I may
be wrong, but it is my impression that UK is going to
have a situation where one has to surrender the key
on demand.
M. K. Shen
------------------------------
From: Quisquater <[EMAIL PROTECTED]>
Subject: Re: RSA Attacks
Date: Mon, 01 Jan 2001 21:23:48 +0100
The Death wrote:
>
> I have started learning the field of encryptions. What attacks are used
> against RSA? I currently know of:
> * Regular Factoring
> * Initial Segment
> * Fermat Factoring
> * Pollard's p-1
> * Guessed Text (Not really attacking RSA, but a specific message)
> * Several more that are related to shared keys
> Any other attacks i should know?
See mainly "Twenty years of attacks on the RSA cryptosystem"
by Dan Boneh (http://crypto.stanford.edu/~dabo/abstracts/RSAattack-survey.html)
and the PhD thesis of Marc Joye
see http://www.geocities.com/CapeCanaveral/Launchpad/9160/publications.html
(and other papers there)
and
http://grouper.ieee.org/groups/1363/Research/Cryptanalysis.html#attack9796
(ISO and Rabin)
and
M. Girault and J.-F. Misarsky. Selective forgery of RSA using redundancy In
Advances in Cryptology --- EUROCRYPT '97, vol. 1233 of LNCS, pp.
495-507.
J.-F. Misarsky. A multiplicative attack using LLL Algorithm on RSA signatures
with redundancy. In Advances in Cryptology --- CRYPTO '97, vol. 1294 of
LNCS, pp. 221-234.
and finally the thesis of JF Misarsky
(see http://security.ece.orst.edu/emails/liste-crypto99/0083)
More later.
------------------------------
From: [EMAIL PROTECTED]
Subject: Idea for Independent Study Project
Date: Mon, 01 Jan 2001 19:51:22 GMT
I need a little help with a cryptography-related
project. My AP Cal BC teacher wants me to do a
math-related project for Independent Study
(basically a science/engineering fair project)
and I chose cryptography because it's something
I'm interested in. (as both a math student and
beginning programmer) At any rate, I'm having
some trouble coming up with an idea that is both
a) within the scope of my abilities and b)
workable in the time alloted (approximately 2
months). My original idea was to try to improve
on existing factoring algorithms (Fermat's
theorem and the b-algorithm, explained in the
Sept. 1998 issue of the College Mathematics
Journal) but I think that may be beyond my scope.
A local university professor (I'm a senior in
high school) is helping me out some, but he can't
tell me what to do. So! Any ideas? Please e-mail
them to [EMAIL PROTECTED] or post them here.
Thanks in advance,
Bryan Bates
Sent via Deja.com
http://www.deja.com/
------------------------------
Date: Mon, 01 Jan 2001 20:30:11 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Possible AONT?
=====BEGIN PGP SIGNED MESSAGE=====
Benjamin Goldberg wrote:
> David Hopwood wrote:
> > Benjamin Goldberg wrote:
> > > 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,
> >
> > What assumption are you making about E? (Actually it doesn't really
> > matter because the scheme has weaknesses even if E is a perfect PRP.)
>
> For the purposes of proof security (or lack thereof), I'm assuming E is
> a random oracle that takes sizeof(k) bits as input, and has as an output
> a permutation E_k, which is randomly selected from the just less than
> 2^27! permutations which have the irreducible polys in different orders.
OK, so you're assuming it is a PRP.
> > > 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?
> >
> > It is obviously not secure according to the definition of a
> > computationally-secure AONT in [1] or [2]. Even the first word of
> > output gives a non-negligable amount of information about the file
> > (since there are less than 2^32 irreducible 32-bit polys, some
> > input files are impossible for a given output).
>
> There are approximately 2^27 irreducible order-32 polys. If the message
> is more than a few (2 or 3) 32-bit words, and significantly less than
> 2^27, and padded with a 1 as the MSB, then it should take O(2^27) work
> to rule out a possible file based on any particular word of the output.
It takes at most that, yes (I haven't looked at whether there are any
short cuts). Isn't that sufficiently easy to declare the scheme broken?
> Although 2^27 is a very small amount of work, it *is* brute force that
> needs to be done. Suppose for an instant that someone could brute force
> 128 bits. Then, one could find out the contents of a file with OAEP
> that has any number of bytes missing -- just brute force the key to the
> stream cipher, and all the information becomes visible.
>
> With this system, it could easily be expanded to require near 2^128
> effort for brute force -- use bigger polynomials, and of course a bigger
> permutation generator.
Well of course it can be fixed if you use a secure stream cipher, but
the point is that you didn't use a secure stream cipher.
If the CRC is replaced by a stream cipher applied to the message, you
have exactly OAEP:
- let G be the stream cipher, and k its key
- let H be a secure hash as before.
Then the output is (M XOR G(k)) || (k XOR H(M XOR G(k))), which
is the same as OAEP. However, the CRC-based method is not even close
to approximating a random oracle (and would still not be close if
the polynomial were larger, I think). It's also incredibly inefficient:
O(n^2) in the message length, rather than O(n).
> By the way, if OAEP is used with a smaller (say, 32 bit) hash and key,
> does it cease to be an AONT?
It ceases to be a secure AONT. The hash and seed sizes should each be
at least as large as a symmetric cipher key (128 bits or more).
Incidentally, there have been some recent papers on the security of
RSA-OAEP which are well worth reading:
Victor Shoup,
"OAEP Reconsidered,"
http://eprint.iacr.org/2000/060
Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, Jacques Stern,
"RSA-OAEP is Still Alive!"
http://eprint.iacr.org/2000/061
[Brief summary: the proof of IND-CCA2 security for RSA-OAEP was wrong,
but can be fixed, albeit with a less tight reduction. Note that these
papers are talking about the version of OAEP that was originally
proposed rather than the one standardised in PKCS #1 v2, but I think
everything extends to the standardised version (someone should really
check that, though).]
These results don't have any bearing on the security of OAEP as an
AONT in the random oracle model, AFAICS. In fact Yevgeniy Dodis'
thesis shows that a slightly simpler construction than OAEP will
suffice for constructing an AONT. I.e. the properties of an AONT are
weaker than the properties required of an encoding method that turns
a trapdoor function into an IND-CCA2 encryption scheme.
- --
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
iQEVAwUBOlAexjkCAxeYt5gVAQH3lwf+IUXDr2UFChrsQE7fkgHTCrTQIAKClK08
OWPjHFfhQ8ZV4FrvW6WNupInzNqw0xdddEndY4v1OZdSVDNX0Wf0KhNh7iH3UEYx
aj6dymHOOfkt60PY0mut4OOXJfXhqsPrF4N+zl1MsSabv64NpeTe4xU1kLcoJesX
236Jap6GH6tz7VJwERMTblqC3iGOM1cqeO3SYz3FE/zVcm5awGoSTIgr3fOf4NVT
KanKNu/gC4G6x3jhMafi8YoYoMbPZ5N4agdPdDIt6y1ZWo2OpgVQ6XGvxQakB5jr
ZmxkNJi7a75qGJ7K+eETZq2x5aoZGQRkXQn6zBGRNhz1KFoeg3AWMw==
=q/I/
=====END PGP SIGNATURE=====
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: GOST 28147-89
Date: Mon, 01 Jan 2001 20:26:47 GMT
In article <92qmr2$q4n$06$[EMAIL PROTECTED]>,
"[Basic]" <[EMAIL PROTECTED]> wrote:
> Hi,
>
> I need some test values for the GOST 28147-89 algo. If anyone could
please
> encrypt a block of 8 {0} bytes with a key array of 32 {0} bytes and
the
> S-Boxes as followed in ECB mode.
>
> SBox_one 4,10,9,2,13,8,0,14,6,11,1,12,7,15,5,3
> SBox_two 14,11,4,12,6,13,15,10,2,3,8,1,0,7,5,9
> SBox_three 5,8,1,13,10,3,4,2,14,15,12,7,6,0,9,11
> SBox_four 7,13,10,1,0,8,9,15,14,4,6,12,11,2,5,3
> SBox_five 6,12,7,1,5,15,13,8,4,10,9,14,0,3,11,2
> SBox_six 4,11,10,0,7,2,1,13,3,6,8,5,9,12,15,14
> SBox_seven 13,11,4,1,3,15,5,9,0,10,14,7,6,8,2,12
> SBox_eight 1,15,13,0,5,7,10,4,9,2,3,14,6,11,8,12
Where did these sboxes come from?
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: GOST 28147-89
Date: Mon, 01 Jan 2001 20:32:03 GMT
In article <92qmr2$q4n$06$[EMAIL PROTECTED]>,
"[Basic]" <[EMAIL PROTECTED]> wrote:
> Hi,
>
> I need some test values for the GOST 28147-89 algo. If anyone could
please
> encrypt a block of 8 {0} bytes with a key array of 32 {0} bytes and
the
> S-Boxes as followed in ECB mode.
>
> SBox_one 4,10,9,2,13,8,0,14,6,11,1,12,7,15,5,3
This sbox has DPmaxs > 4.
I bet the rest do too.
Did you pick these at random?
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Marc)
Subject: Re: AES in optimized x86 assembler?
Date: 1 Jan 2001 20:41:10 GMT
>1. run the C code through "gcc -O2 -S" on your platform
>
>2. hand optimize the assembly code for your platform
>
>Good luck. GCC will produce code good enough for almost every
>application. I would question whether or not you really need hand
>optimized assembly. Every other part of your program will likely be C
>code anyway. Are you sure most of your time will actually be spend
>running AES code?
The crypto algorithm will run 99% of execution time, because the
intended application is a BIOS INT13h patch to retrofit on-the-fly
encryption for harddrives under DOS/Win9x. No user interface no
nothing, just a bare low level patch :-) Speed is desirable because
next to resistance against selected security threats, the application
will have no perceivable effect other than the more or less reduced
harddrive speed.
I asked for .asm because I am not an experienced x86 programmer at all
(my focus are 8bit embedded systems) and will face enough problems
already with a documentated .asm source where register/memory/stack usage
is straight forward. I think this is much easier to work with (for
me) than to try glue .c into the low level INT13h context. I already
have a working .asm patch to wiggle the PC speaker during disk
accesses.
You are right that in normal applications .c is perferable over .asm,
and if I were more experienced with PC architecture and compilers
maybe even also in this particular application.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Distributing private keys on the internet
Date: 1 Jan 2001 20:59:51 GMT
In <92qlbi$c17$[EMAIL PROTECTED]> Tom St Denis <[EMAIL PROTECTED]> writes:
]> >
]>
]> Well, I don't have a problem with public keys. Its the private keys.
]>
]> How do you send a private key securely over the Internet if a 3rd
]party
]> is listening to everything you send and has your client software along
]> with a good debugger that allows him to easily write a private key
]> cracking program?
Why do you want to? If this is the key to a symmetric crypto system,
then the best way is via a public key system. If it is a public key
system then you do not send your private key anywhere.
]>
]> I don't think private keys are safe to transmit over the Internet.
]> Please, somebody tell me I'm wrong. I would love to be wrong...
Again tell us what you want?
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: AES in optimized x86 assembler?
Date: 01 Jan 2001 13:36:33 -0800
[EMAIL PROTECTED] (graywane) writes:
> True. However, most people will "optimize the hell" out of AES and
> not the rest of their application. The result will be a fast AES
> section that probably is a very small percentage of the overall
> execution time for the application as a whole.
This is irrelevant. Anything that makes the program run faster makes
the user experience better. Alternatively, if the program has a certain
amount of runtime available, any cycles saved by optimizing AES become
available for the rest of the application to use. If AES is used in
1000 applications, 1 cycle worth of AES optimization is worth 1000 cycles
of optimizing individual applications.
> In the end, how much time will you really save and how much will it
> have cost you in man hours? For most people it will be very little.
That isn't the right way to look at it.
If somebody writes an optimized AES routine and publishes it, it
doesn't cost me *any* man-hours for my application to call the
optimized one instead of an unoptimized one. A security application
will use AES the same way an engineering application might use cosines
or logarithms. Cosines are a basic building block of a math library,
so any respectable implementation will be very highly tuned. Your
application will get to use that carefully optimized cosine
implementation with no extra effort to you, even if it only computes
one cosine. You don't even have to be aware that the cosine routine
you're calling is optimized. And if you *are* computing a lot of
cosines, the optimization in the math library may *save* you the
man-hours of having to optimize the rest of your application to make
it run fast enough.
AES is (or will be) a basic building block of cryptography libraries
and an AES routine in a crypto library deserves the same type of
tuning that a cosine routine gets in a math library.
> Optimized assembly is also very hard for non-technical people to verify for
> code correctness. You have the possibility that bugs exist longer before
> they are noticed because fewer people are actually looking at the code.
> There is a reason people don't write programs in assembly much anymore.
First of all, non-technical people by definition can't verify code
correctness at all, since that's a technical process.
Second, the main thing that makes programs hard to check for
correctness is code size. Have you checked the correctness of your C
compiler lately? How about your operating system?. A 1000 line
crypto algorithm written in asm might be hard to check, but it has to
be easier than checking a 300,000 line compiler written in C.
Almost all decent public key implementations on PC's are written in
asm, by the way. They have to be, because there's no portable way to
do multi-precision arithmetic in C that uses the full capability of
the PC architecture (specifically, multiplication instructions that
give double-width products). Asm implementations are generally at
least 3x faster than C implementations.
------------------------------
From: [EMAIL PROTECTED] (graywane)
Subject: Re: AES in optimized x86 assembler?
Date: Mon, 01 Jan 2001 21:43:10 GMT
> Second, the main thing that makes programs hard to check for
> correctness is code size. Have you checked the correctness of your C
> compiler lately? How about your operating system?. A 1000 line
> crypto algorithm written in asm might be hard to check, but it has to
> be easier than checking a 300,000 line compiler written in C.
You are comparing apples and oranges. It is far easier to verify the C
version of AES than the assembly version.
> Almost all decent public key implementations on PC's are written in
> asm, by the way. They have to be, because there's no portable way to
> do multi-precision arithmetic in C that uses the full capability of
> the PC architecture (specifically, multiplication instructions that
> give double-width products). Asm implementations are generally at
> least 3x faster than C implementations.
I challenge you to write an AES implementation that is 3x faster than a good
C implementation. Pick any modern CPU you want.
I await your results.
------------------------------
From: [EMAIL PROTECTED]
Subject: computing RSA keys
Date: Mon, 01 Jan 2001 21:44:17 GMT
I'm making progress on the Javascript RSA implementation. See
http://sourceforge.net/projects/shop-js for more information.
I'm concerned about my key generation algorythm. I compute n-bit primes
(using Miller-Rabin -- if anyone can suggest a faster simple algorythm
I'd be very interested!), then calculate (p-1)(q-1).
Here's the trick I found.. I calculate a random n and find
(p-1)(q-1) * n + 1
this almost always factors easily.
The trouble is that the result often has a public exponent which is
relatively small (between 5 and 10^5). The private exponent is close to
p*q (ie the public modulo).
Does this weaken the key? It seems to me that if the public key was
(for example) 7 someone might easily calculate a modulated 7th-root of
the encrypted value even without knowing the private exponent. (Sorry I
don't know the correct mathmatical language for this.)
Am I understand the situation?
Is there a better way to calculate the multiplicative inverse? (I found
one algorythm but it didn't look very simple & quick.)
Thanks,
John
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Genomes
Date: Mon, 01 Jan 2001 15:27:43 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> Does anyone happen to know the statistical properties of the
> genome sequences in general? Are they sufficiently 'random'?
>
Since all life is similiar, so is the coded information.
--
History repeats itself when given the opportunity.
Question repeating old mistakes.
Be certain of the outcome.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Crossposted-To: alt.cypherpunks
Subject: Re: A Censorship Resistant Digital Magazine Scheme
Date: Mon, 01 Jan 2001 15:35:14 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> I am not sure that the authorities would have to prove
> that before demanding from you the key to decrypt. I may
> be wrong, but it is my impression that UK is going to
> have a situation where one has to surrender the key
> on demand.
>
> M. K. Shen
Which means that demands will be made to decrypt information where the
keys have been lost for one reason or the other. Then, you are back to
familiar problems of proving negatives, which is not the way to acquire
justice. But, justice is not the goal of despots anyway.
--
History repeats itself when given the opportunity.
Question repeating old mistakes.
Be certain of the outcome.
------------------------------
** 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
******************************
