Cryptography-Digest Digest #598, Volume #12 Sat, 2 Sep 00 16:13:01 EDT
Contents:
A good MAC algorithm? ("Rafael R. Sevilla")
Re: New cryption method... (wtshaw)
Re: Extending RC4 to 16 bits ("Scott Fluhrer")
A good MAC algorithm? ("Rafael R. Sevilla")
Re: PGP ADK Bug: What we expect from N.A.I. ("musashi_x")
Re: one-time pad question (Jim)
Re: one-time pad question (Jim)
Re: Serious PGP v5 & v6 bug! (Timothy M. Metzinger)
Re: A good MAC algorithm? ("Scott Fluhrer")
Re: RSA history (Bodo Moeller)
----------------------------------------------------------------------------
From: "Rafael R. Sevilla" <[EMAIL PROTECTED]>
Subject: A good MAC algorithm?
Date: Sun, 3 Sep 2000 02:38:30 +0800
I've just implemented a few of the AES candidates for a 16-bit x86-type
embedded processor which I am using in my project, and after some testing
and optimization, have decided on Rijndael as the algorithm, as it seems
to be the most efficient candidate for my particular platform, providing a
sufficient level of security with reasonable speed. Unfortunately,
another chore of my embedded system is to compute a MAC, and have been
hard-pressed to find a good MAC algorithm which is efficient to implement
on my platform.
I could use Rijndael in CBC-MAC mode to generate a MAC, but this
effectively doubles the time it takes for my system to perform an
encryption. Doubling encryption time is not a particularly palatable
solution, although it could be done if no better way is available.
Another way which I briefly considered was to use HMAC-SHA1.
Unfortunately, HMAC-SHA1 is extremely difficult to optimize in 16-bit 8086
assembly language, as it uses a 32 bit rotate, which is quite expensive on
my platform; and certainly would produce even poorer performance than
Rijndael CBC-MAC. HMAC-MD5 is scarcely better, and people on the
newsgroup have warned me against it due to security risks. If there's a
hash algorithm out there other than RIPEMD-160, SHA-1, and MD5, one that
would be fast to implement on 16-bit x86, I'd be happy to hear about it.
Yet another solution would be to find and implement an block cipher that
may be weaker, but more efficient, than Rijndael, with a block size of at
least 128 bits. This is not something I've been able to find, and if
there are any algorithms of this kind that anyone can suggest I'm all
ears. I found RC2, which fits the criterion of efficiency, unfortunately,
its blocksize is way too small to be useful as a MAC (64 bits only).
Another idea I got was to use a CRC as the basis for a MAC, this from the
Handbook of Applied Cryptography. We would use a family of 128-bit CRC
polynomials, choose a polynomial and a 128-bit MAC key, compute the CRC of
the data using the polynomial, then use a 128-bit blocksize Rijndael with
the MAC key to encrypt the CRC to come up with the final MAC. This would
definitely be much cheaper than either of the first two approaches, as we
would only need a CRC table, one lookup and one 128-bit XOR per byte, plus
one encryption. However, I have no idea how secure this MAC would be
against forgery and collision resistance, and don't have the faintest clue
as to how to choose a family of polynomials to use. If anyone can give
more web pages and online documents that describe the theory of CRC codes
besides Ross N. Williams' excellent introduction: "A Painless Guide to CRC
Error Detection Algorithms", which sadly doesn't really answer the
question of how to choose polynomials, or an explanation of why or why not
this method would make a good MAC, regardless of the polynomials used,
that would be much appreciated.
Thanks in advance for any responses.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
PGP Key available at http://home.pacific.net.ph/~dido/dido.pgp
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: New cryption method...
Date: Sat, 02 Sep 2000 12:14:11 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> PROdotes wrote:
> >
> > I think I've found an cryption method that could be very hard to break.
> [snip]
> > The only problem is that the output is 2-3 times as large as the input...
>
>
> Common ciphers preserve the length of messages. There are
> some ciphers that expand the lengths. In general, it's
> easier to attain the same level of security with expansion
> than without, for reasons quite comprehensible.
There are lots of systems that expand a message 2-3 times, including many
rather insecure methods. Still, something might be learned on a new
approach if it is not something else rehashed/duplicated. For a serious
cipher, even a doubling of output is likely still too much.
--
A Pangram:
Vexed xenophobes fear crypto's jazzy, quaint works.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Extending RC4 to 16 bits
Date: Sat, 2 Sep 2000 11:30:35 -0700
Barry Adams <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> RC4 is a nice simply symmetric stream cipher, that has been well
> discussed after the algorithm (a trade screat of RSA inc) leaks the
> public domain. For some application a stream of 16-bit short word data
> may occur. So how about extending RC4 to 16bits as follows here coded
> in Java.
>
[snip]
>
> Although the initalization of the state space for a given
> key is relavitely slow (65536 steps), but the encryption and
> decryption of data is very fast. The state array although big at 128k
> bytes is still able to fit in the Level 2 cache of modern
> microprocessors and should offer no problems to speed (especial if
> cache prefetch instructions are used).
Actually, having run no tests, I'd naively expect this to run somewhat
slower than RC4. Yes, it'll fit in an L2 cache, but L2 caches are not that
profoundly fast when compared to the core CPU. Essentially, you'll be
reading 3 L2 cache entries and writing 2 L2 cache entries for every 16 bits
produced (except for that occasional case where a cache entry you need is
already in the L1 cache). Cache prefetch instructions don't appear to help,
because they don't affect how much is transferred, only when. Still, that's
only a guess...
In addition, the data will be in the L2 cache only if it was accessed
recently -- if you just did the key setup, or it was accessed to encrypt
another byte. If you use it to encrypt a stream, go away for a few
milliseconds, and then try to generate some more keystream, you're likely to
get a large number of cache misses, as your table will have dropped out of
the cache in the mean time...
>
> The questions are how mathematically sound is the algorithm? Of the
> top of my head i would think that huge state space would make
> for a hard to decryption cipher, but will it be well randomized
> especially with small keys. Are their any pitfalls in the algorithm?
> and generally would it also useful to extended other 8-bit stream
> ciphers to 16 bit in this sense?
>From all the analysis of RC4 I've seen, this should be significantly
stronger than 8 bit RC4. Only pitfall I can think of is to discard the
first couple outputs, to avoid the weakness due to weak keys that Roos noted
(just like in 8 bit RC4)
>
> Legally is the algorithm covered by any patents or other
> ownship problems? If not and if it is original let me immediately
> declare it to be copyleft under the Gnu Public License.
Errr, two things:
- Algorithms cannot be copyrighted, only expressions of algorithms
- Ignoring that, the idea of generalizing RC4 to include other bit sizes has
already appeared in the literature. It may be a bit too late to try to try
to place it under the quite restrictive Gnu copyright...
--
poncho
------------------------------
From: "Rafael R. Sevilla" <[EMAIL PROTECTED]>
Subject: A good MAC algorithm?
Date: Sun, 3 Sep 2000 02:57:12 +0800
I've just implemented a few of the AES candidates for a 16-bit x86-type
embedded processor which I am using in my project, and after some testing
and optimization, have decided on Rijndael as the algorithm, as it seems
to be the most efficient candidate for my particular platform, providing a
sufficient level of security with reasonable speed. Unfortunately,
another chore of my embedded system is to compute a MAC, and have been
hard-pressed to find a good MAC algorithm which is efficient to implement
on my platform.
I could use Rijndael in CBC-MAC mode to generate a MAC, but this
effectively doubles the time it takes for my system to perform an
encryption. Doubling encryption time is not a palatable solution,
although it could be done if no better way is available.
Another way which I briefly considered was to use HMAC-SHA1.
Unfortunately, HMAC-SHA1 is extremely difficult to optimize in 16-bit 8086
assembly language, as it uses a 32 bit rotate, which is expensive on my
platform; and certainly would produce even poorer performance than
Rijndael CBC-MAC. HMAC-MD5 is scarcely better, and people on the
newsgroup have warned me against it due to security risks. If there's a
hash algorithm out there other than RIPEMD-160, SHA-1, and MD5, one that
would be cheap to implement on 16-bit x86, I'd be happy to hear about it.
Yet another solution would be to find and implement an block cipher that
may be weaker, but more efficient, than Rijndael, with a block size of at
least 128 bits. This is not something I've been able to find, and if
there are any algorithms of this kind that anyone can suggest I'm all
ears. I found RC2, which fits the criterion of efficiency, unfortunately,
its blocksize is way too small to be useful as a MAC (64 bits only).
Another idea I got was to use a CRC as the basis for a MAC, this from the
Handbook of Applied Cryptography. We would use a family of 128-bit CRC
polynomials, choose a polynomial and a 128-bit MAC key, compute the CRC of
the data using the polynomial, then use a 128-bit blocksize Rijndael with
the MAC key to encrypt the CRC to come up with the final MAC. This would
definitely be much cheaper than either of the first two approaches, as we
would only need a CRC table, one lookup and one 128-bit XOR per byte, plus
one encryption. However, I have no idea how secure this MAC would be
against forgery and collision resistance, and don't have the faintest clue
as to how to choose a family of polynomials to use. If anyone can give
more web pages and online documents that describe the theory of CRC codes
besides Ross N. Williams' excellent introduction: "A Painless Guide to CRC
Error Detection Algorithms", which sadly doesn't really answer the
question of how to choose polynomials, or an explanation of why or why not
this method would make a good MAC, regardless of the polynomials used,
would be much appreciated.
Thanks in advance for any responses.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
PGP Key available at http://home.pacific.net.ph/~dido/dido.pgp
------------------------------
From: "musashi_x" <m u s a s h i _ [EMAIL PROTECTED]>
Subject: Re: PGP ADK Bug: What we expect from N.A.I.
Date: Sat, 2 Sep 2000 14:59:18 -0400
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
"Rick Braddam" <[EMAIL PROTECTED]> wrote in message
news:8okv0a$opf$[EMAIL PROTECTED]...
> Just a couple of opinions:
> "David A. Wagner" <[EMAIL PROTECTED]> wrote in
> message news:8okbcg$574$[EMAIL PROTECTED]...
> > Mark Wooding <[EMAIL PROTECTED]> wrote:
> > > I disagree that it's a totally daft feature.
> > >
> > > There is a definite requirement for an employer to want to
> > > recover messages sent to an employee in the course of his or
> > > her job if the employee is unable to decrypt messages for some
> > > reason (e.g., run over by a bus, disgruntled and left, or
> > > whatever).
> >
> > But for email!?
> >
> > There is an important distinction between escrowing
> > communications and escrowing stored data. Escrowing
> > communications is rarely sensible.
>
> You don't think that just the presence of an ADK would dissuade
> employees from including their employer's proprietary information
> in outgoing email? Information such as cost vs price, inventory
> levels, production rates, budgets, preparation for patent
> applications, etc? If an employee did send such information to
> unauthorized destinations, the ADK would make
> detection and prosecution possible, too.
>
> > Escrowing stored data -- also called "making backups" -- may well
> > make a lot of sense for some businesses.
>
> I think of escrowing data as storing it in secure containers like
> ScramDisk or PGPDisk. Making a backup would be saving a copy of the
> secure container in a second location.
>
> > Compare to what the law-enforcement agencies want: they want
> > escrow of communications keys and don't care so much about
> > storage keys.
>
> I think it would be unwise to assume what (some) law enforcement
> agencies want based on what they've asked for. They might not ask
> for that which they are very sure they have no chance of getting
> *at the present time*. It could be very useful to a detective or
> investigator to be able to open secure (scramdisk, PGPDisk)
> containers in hope that they would contain evidence of criminal
> transactions.
>
> > That's backwards from what businesses are typically likely to
> > want.
> >
> > I think I first saw this point raised by Matt Blaze.
>
> I don't like the idea of government escrowed keys, but I think that
> in a business environment escrowed keys or an ADK could be
> essential. For personal use, I might use an ADK to help secure
> information I wanted my heirs to be able to access to enable
> settling my estate (such as it is). I would, of course, have other
> "normal" keys to protect information they would have no use for if
> I wanted to keep that information private.
>
> Rick
Besides, anyone who is planning to transmit business secrets or
anything incriminating could always just bring in their own
stand-alone encryption program on a floppy, CD-R or zip disk.
Something that makes a standalone Blowfish or Twofish EXE, for
example. If PGP is running in memory, wouldn't it be possible for
employees to bring in their personal (from home) keyrings on a disk
and encrypt to those instead of company issued keys? I suppose it
would depend on whether or not the company does the encryption at
workstation or server level...
- --
To respond, remove the spaces from the following
address. m u s a s h i _ [EMAIL PROTECTED]
Thanks!
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 6.5.3 for non-commercial use <http://www.pgp.com>
Comment: Vicious Circles: Exercises in Paranoia!
iQA/AwUBObFOA8HkmuudisobEQJNWACfUARD/J2vCOjIskptjinbo+QRDgIAnjYQ
0DiAxcaFpacLG2puqKUNO3o2
=UlEu
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Jim)
Subject: Re: one-time pad question
Date: Sat, 02 Sep 2000 19:12:16 GMT
Reply-To: Him!
On Fri, 01 Sep 2000 19:46:10 +0000, Jim Gillogly <[EMAIL PROTECTED]> wrote:
>Jim wrote:
>>
>> On Thu, 31 Aug 2000 22:36:38 GMT, [EMAIL PROTECTED] (Mr. Ian E. Yolk)
>> wrote:
>
>> >be done. The main reason that pure randomness is stressed in the
>> >description of a one time pad is that the mathematical proof that the
>> >method is secure depends on that provision, among other things. A
>> >technically non-random pad might still be secure, but you won't be able to
>> >prove it.
>>
>> So it must follow that, because the perfectly random key does not
>> exist, that any and all OTP can be broken?
>
>No, Mike said the opposite: it might still be secure, but there's no proof
>available if the key isn't random.
>
>If a key is non-random in some known way, then information is leaked.
>Perhaps not enough to break an intercepted "OTP" with ciphertext only,
>but quite likely enough to determine with an adequate level of
>confidence whether a particular long ciphertext message matches a
>particular known plaintext. This may not often be a useful test, but
>it does demonstrate that some information is leaked, and thus the
>"OTP" is no longer perfect.
Yes, I know. Sufficiently random then, Jim!
--
Jim Dunnett
amadeus at netcomuk.co.uk
nordland at lineone.net
g4rga at thersgb.net
------------------------------
From: [EMAIL PROTECTED] (Jim)
Subject: Re: one-time pad question
Date: Sat, 02 Sep 2000 19:12:17 GMT
Reply-To: Him!
On Sat, 02 Sep 2000 07:16:45 GMT, [EMAIL PROTECTED] (Mr. Neil Okya)
wrote:
>"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>
>>Jim wrote:
>>> So it must follow that, because the perfectly random key does not
>>> exist, that any and all OTP can be broken?
>>
>>No, the conclusion is not true and neither is the hypothesis.
>
>[EMAIL PROTECTED] (Jim) has a confusing combination
>of email address and name, doesn't he? At first I thought you had
>incorrectly attributed that bit of flawed logic to Jim Gillogly, but then I
>realized that your attribution was actually correct.
>
>You know, the more I look at that email address, the more I suspect that he
>was just pulling our legs.
Yes I was. Sorry about the confusion with the addresses, but there
is method to my madness. Please bear with me.
--
Jim Dunnett
amadeus at netcomuk.co.uk
nordland at lineone.net
g4rga at thersgb.net
------------------------------
From: [EMAIL PROTECTED] (Timothy M. Metzinger)
Date: 02 Sep 2000 19:16:56 GMT
Subject: Re: Serious PGP v5 & v6 bug!
In article <8pRp5.4083$[EMAIL PROTECTED]>, "Nathan
Williams" <[EMAIL PROTECTED]> writes:
>Simple solution that allows for the use
>of PGP without adding the complexity( and therefore the added risk)
>of a an ADK.
and destroys non-repudiation.
Timothy Metzinger
Commercial Pilot - ASMEL - IA AOPA Project Pilot Mentor
'98 M20J - N1067W
Pipers, Cessnas, Tampicos, Tobagos, and Trinidads at FDK
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: A good MAC algorithm?
Date: Sat, 2 Sep 2000 12:07:46 -0700
Rafael R. Sevilla <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> I've just implemented a few of the AES candidates for a 16-bit x86-type
> embedded processor which I am using in my project, and after some testing
> and optimization, have decided on Rijndael as the algorithm, as it seems
> to be the most efficient candidate for my particular platform, providing a
> sufficient level of security with reasonable speed. Unfortunately,
> another chore of my embedded system is to compute a MAC, and have been
> hard-pressed to find a good MAC algorithm which is efficient to implement
> on my platform.
>
Another approach would be to use something like UMAC, which does
authentication by doing a (quick) universal hash of your data with a shared
random data into something short, and then applying a secure hash function
to that. This has the advantage is that most of the work is done by the
universal hash, which is quite quick. This does require you to have stored
some random data, which may or may not be practical on your system.
There are several other MACs with these properties -- there's Square Hash
that was presented at Crypto '99, and I believe D J Bernstein has one as
well. The following is the URL for the UMAC web page, but you may want to
investigate the others...
http://www.cs.ucdavis.edu/~rogaway/umac/
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Bodo Moeller)
Subject: Re: RSA history
Date: 2 Sep 2000 19:24:38 GMT
D. J. Bernstein <[EMAIL PROTECTED]>:
> Knuth proposed exponent 3 in ACP volume 2, second edition, 1981. Does
> anyone know a prior proposal to use a fixed exponent coprime to phi(n)?
e = n in C.C. Cocks, A Note on Non-Secret Encryption, CESG Report, 1973
(according to http://jya.com/ellisdoc.htm). Since this didn't become
public until 1997, it may not count as "RSA history", though ...
--
Bodo Möller <[EMAIL PROTECTED]>
PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html
* TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt
* Tel. +49-6151-16-6628, Fax +49-6151-16-6036
------------------------------
** 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
******************************
