Cryptography-Digest Digest #650, Volume #12 Sun, 10 Sep 00 20:13:01 EDT
Contents:
Re: CRC's as MAC's ("Scott Fluhrer")
Re: CRC's as MAC's (Bryan Olson)
Re: CRC's as MAC's (Terry Ritter)
Re: RSA Patent -- Were they entitled to it? (Roger Schlafly)
Re: RSA public exponent (Ed Pugh)
Re: PRNG ("Paul Pires")
Encrypted internet voice solutions ?? (Ed Pugh)
Re: Dangerous holiday reading? ("Miki Watts")
Re: RSA public exponent (Future Beacon)
Re: RC5-SAFE? - SAFEBOOT ("lala")
----------------------------------------------------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: CRC's as MAC's
Date: Sun, 10 Sep 2000 15:45:03 -0700
Dido Sevilla <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> I've been shopping for a MAC algorithm these days and have not been
> fortunate enough to find an algorithm that provides reasonable defense
> against forgery and modification detection while not being an
> unreasonable algorithm to implement on a low-powered embedded
> microcontroller. All the well-known ones are too expensive.
>
> The best idea I've been able to find so far is the use of a CRC
> algorithm. The MAC would essentially be a 128-bit CRC, encrypted with a
> block cipher, which provides our keying. We'd have a set of polynomials
> to be used for the CRC, say a set of sixteen 128-bit polynomials which
> are randomly selected along with a 128-bit block cipher key. We use the
> polynomials to calculate a CRC on the data, and the CRC is encrypted by
> the block cipher.
Question on what the above means. Do you mean:
- We have preselected sixteen 128-bit polynomials, and any use of the mac
will select one of the sixteen in a key dependent fashion.
- We select 16 random (key dependent) 128-bit polynomials, and the mac
output somehow depends on all of them.
If you mean the first, then it's obviously pretty weak. If the attacker
guesses which one a particular message uses (probability 1/16 of being
right), then he can make modifications that leave that particular CRC
unaffected. This allows the attacker to forge messages with a 1/16
probability of success. For that matter, it wouldn't be too hard to devise
modifications that preserve all 16 CRCs, giving you a modfication that a
probability 1 of success.
If you mean the second, then (unless you have a 256 byte mac) you'd need to
combine the CRCs somehow. I'd need to see how you combine the CRCs before I
can really say much about the security. However, if you actually do compute
16 CRCs over the message, it's likely to be dog slow.
One possibility would be to use a single key dependent 128 bit polynomial.
I suspect [1] that the set of all 128 bit CRCs might be "almost universal"
on strings less than 2**128 bits long (given that you handle messages of
different lengths properly), which would give you provable limits on
forgability. However, I wouldn't think it would give you as good
performance as other known AU based MAC schemes, like UMAC or hash127.
[1] Meaning: it sounds reasonable to me, but I have no intention of trying
to prove it.
--
poncho
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: CRC's as MAC's
Date: Sun, 10 Sep 2000 23:03:27 GMT
Dido Sevilla wrote:
>
> I've been shopping for a MAC algorithm these days and have not been
> fortunate enough to find an algorithm that provides reasonable defense
> against forgery and modification detection while not being an
> unreasonable algorithm to implement on a low-powered embedded
> microcontroller. All the well-known ones are too expensive.
What's your platform and what speed/code-size/memory-size
could you live with?
[...]
> We'd have a set of polynomials
> to be used for the CRC, say a set of sixteen 128-bit polynomials which
> are randomly selected along with a 128-bit block cipher key. We use
the
> polynomials to calculate a CRC on the data, and the CRC is encrypted
by
> the block cipher.
>
> Questions: does this make a good MAC, regardless of what polynomials I
> choose, or to put it differently, are there sets of polynomials
> available that if used produce a good MAC?
It's terrible no matter what polynomials you choose.
To produce collisions with a given message, multiply the
polynomials, and add to the message any multiple of that
product.
> I don't have any references on the theory of CRC's so I
> have no clue as to how to answer this question.
There's a lot experience with the use of CRC's in
cryptography, almost all of it bad. As a rule of thumb,
CRC's are for protection against errors, not adversaries.
Fast MAC's have come a long way in the last several years.
If you state your efficiency requirements, maybe someone
can point you in a more promising direction.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: CRC's as MAC's
Date: Sun, 10 Sep 2000 23:11:53 GMT
On Mon, 11 Sep 2000 05:54:50 +0800, in
<[EMAIL PROTECTED]>, in sci.crypt Dido Sevilla
<[EMAIL PROTECTED]> wrote:
>[...]
>are there sets of polynomials
>available that if used produce a good MAC?
Even a random polynomial can detect errors. But the usual practice in
CRC's is to choose a primitive mod-2 polynomial (perhaps multiplied by
11), because real errors are not distributed evenly. A well-designed
CRC can detect error patterns involving just a few errors better than
one might expect from a random polynomial.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: RSA Patent -- Were they entitled to it?
Date: Sun, 10 Sep 2000 16:14:36 -0700
Terry Ritter wrote:
> In this section of law, I think the word "known" applies to an
> invention "revealed without expectation of secrecy." In my view, even
> if GCHQ had told NSA and NSA proceeded to implement the invention in
> the US, the fact that it was kept secret would preclude the
> application of 35 USC 102(b).
Yes, the secrecy precludes application of 35 USC 102(b). But not
35 USC 102(a).
If it makes you feel betters, patents are hardly ever broken
under 102(a). Breaking the patent requires antedating the patentee's
date of invention, and that date is not published with the patent.
------------------------------
From: [EMAIL PROTECTED] (Ed Pugh)
Subject: Re: RSA public exponent
Date: 10 Sep 2000 23:17:05 GMT
Reply-To: [EMAIL PROTECTED] (Ed Pugh)
Thomas Pornin ([EMAIL PROTECTED]) writes:
> According to Paul Schlyter <[EMAIL PROTECTED]>:
>> If I instead wanted a full-length public exponent too, it must
>> be selected somehow. How would I do that?
>
> Select it at random. All that is required is that it must be relatively
> prime to phi(N)=(p-1)(q-1) where N=pq is the modulus.
>
> 65537 is useful because it is prime, and therefore has a high probability
> of being relatively prime to phi(N) for a randomely chosen N. But there
> is no obligation to choose a prime number.
When generating keys, we can "set" one exponent to a specific number
and let the algorithm find the other exponent. Both exponents must
be relatively prime to phi(N) (as stated elsehwere). If one is r.p.
to phi(N), then so is the other. Therefore we must choose one
exponent to be r.p. to phi(N), and let the algorithm select the other
exponent.
Now, if the chosen exponent is small (in comparison with N), then the
other exponent will most likely be large (AFAIK; someone please correct
me if I am wrong about this). Therefore, it is best to choose the
public exponent to be relatively small, so that the secret exponent
will be large.
Also, it is more efficient for the encryption algorithm if the public
exponent has the smallest possible "binary weight" (i.e. the smallest
possible number of set bits). (For the "fast" modular exponential
algorithm, the time to do it is proportional to the bit length plus
the binary weight -- i.e. the number of set bits -- of the public
exponent.)
Therefore, it is usually easiest to use a PRIME public exponent of the
form 2^k + 1, where k is an integer that makes the result prime. (A
prime public exponent has a higher probability of being r.p. to phi(N)
than a non-prime exponent would, so we choose a prime one.)
For this reason, RSA often uses public exponents 3 (2^1 = 1), 17
(2^4 + 1) and 65537 (2^16 + 1).
Since it is actually the secret exponent that we want to keep from
being found, I am not really sure that the size of the public exponent
has much bearing on the security of the secret key. (Again, though,
somebody please correct me if I am wrong about this.) Therefore, I
believe we can use smaller public exponents without compromising the
security of the secret key.
One thing to keep in mind, though, is that there are actually
INFINITELY MANY (Aleph-Null, to be exact) secret exponents for any
one public exponent. The smallest secret exponent can be found by
d = (e^-1) [mod (LCM((p-1),(q-1))], where e is the public exponent,
N = pq and LCM(a,b) is the least common multiple of a and b. Any
number congruent to d [ mod (LCM(p-1),(q-1))] will work as the secret
exponent for RSA decryption. Therfore if an attacker can find ANY
such value, then the secret key has been broken.
It is (AFAIK) currently believed that factoring N is the easiest way
to find the secret exponent of a RSA key. I often wonder, however,
if there may be an easier attack available, given the fact that
there are infinitely many possible secret exponents.
Best regards,
--
Ed Pugh, <[EMAIL PROTECTED]>
Richmond, Ontario, Canada (near Ottawa)
"Bum gall unwaith-hynny oedd, llefain pan ym ganed."
(I was wise once, when I was born I cried - Welsh proverb)
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: PRNG
Date: Sun, 10 Sep 2000 16:25:00 -0700
Cristiano <[EMAIL PROTECTED]> wrote in message
news:8ph1vq$scp$[EMAIL PROTECTED]...
>
>
> I frequent many newsgroup, but the bad manners that I have found here are
> incomparables!
> You and other guys assault the people, please quiet down!
>
> Cristiano
????
I was on my best behavior. What in my response offended
you so mightily?
I did ask for the basis of some (to me) strange claims you made.
This is rude? I notice you did not address my questions.
You demand I quiet down?
Go pound sand. There, now you've been offended.
Paul
------------------------------
From: [EMAIL PROTECTED] (Ed Pugh)
Crossposted-To:
comp.security.pgp.tech,comp.security.pgp.resources,comp.security.pgp.discuss,alt.security.pgp
Subject: Encrypted internet voice solutions ??
Date: 10 Sep 2000 23:24:45 GMT
Reply-To: [EMAIL PROTECTED] (Ed Pugh)
Hello, all.
This posting lists several questions about encrypted Internet
voice/telephony programs. These are the only newsgroups I
could think of for posting this. So, if there is a better
newsgroup for these types of questions, please let me know.
Also, if I have posted to an inappropriate newsgroup, please
accept my apologies.
As well, I would appreciate it if you could please CC: my E-
mail address in any follow-up posting. My E-mail address is:
[EMAIL PROTECTED] (alias [EMAIL PROTECTED])
Now, to my reason for posting ...
I would like to set up an encrypted internet telephony voice
program for non-commercial use. Right now, I know of only
three freeware offerings (in alphabetical order): Nautilus,
PGPfone and SpeakFreely. I am wondering if anyone has
experience with two or more of these programs for comparisons.
Also, I am wondering if there might be another alternative
using PGP Freeware 6.5.8 "VPN". Specifically, can I set up
PGP 6.5.8 VPN for use with a "normal" (non-encrypted) Internet
"voice chat" program, or some other Internet telephony type
program?
I would like to set this up on my home PC, and on a lap-top,
so I can use it to talk with my family while travelling on
business. (I.e. for PERSONAL use only; not for business use.)
It would be best if I can set this up on my home PC so that it
would use a Windows GUI interface, rather than a DOS command-
line I/F. (So, Nautilus would not really be a good solution
for this, but I would consider it if the security and voice
qualities far outweigh the other solutions.)
If you have some experience with this, what is the best way to
set up encrypted Internet voice connections?
My home PC has the following stats:
CPU: Pentium II 233 MHz
RAM: 64 Mb
OS: Windows 95
Sound Card: Creative Labs AWE 64
Modem: 56 kbps modem, but connection is usually 26.4 on
my "less expensive" ISP, or anywhere between 42
to 46.7 kbps on my "more expensive" ISP
(the latter supports 56 kbps, but my telephone
connection is not up to the task).
My laptop will be newer and will be a much faster Pentium III
with 256 Mb of RAM.
Here are some specific questions:
1. Are there any more freeware programs that will do
encrypted internet telephony, in addition to the three
I listed above? Are there other alternatives (such as
using PGP "VPN" as I asked above, or yet other choices
that I have not thought of) ?
2. What are the advantages / disadvantages of each offering
or each solution?
3. SpeakFreely has an echo server, which will send the
encrypted voice packets back to the client after a 10
second delay. (This allows one to test the voice quality
over an actual internet connection, before involving
another party.) Are there similar servers for any of the
other voice encryption programs?
4. Does any voice encryption solution use a protocol that will
work across a corporate firewall, gateway and/or proxy
server?
5. PGPfone suggests turning off error correction on the modem.
Is this true for internet connections over a PPP dial-up
service as well as direct modem-to-modem connections? If
so, should this also be done for the other programs
(Nautilus, SpeakFreely)?
6. Do you have any other tips, notes or warnings about any of
these, or other, similar applications?
7. CANADIANS: Is there any Canadian export law prohibiting
international travel with lap-tops, that have strong
encryption software installed?
TIA for any help or tips you might have.
Regards to all,
--
Ed Pugh, <[EMAIL PROTECTED]>
Richmond, Ontario, Canada (near Ottawa)
"Bum gall unwaith-hynny oedd, llefain pan ym ganed."
(I was wise once, when I was born I cried - Welsh proverb)
------------------------------
From: "Miki Watts" <[EMAIL PROTECTED]>
Subject: Re: Dangerous holiday reading?
Date: Mon, 11 Sep 2000 02:45:01 +0200
> I'm a student about to go on holiday to Israel with my girlfriend; along
> with all the novels etc. I was about to pack a copy of `Applied
> Cryptography' in order to get ahead for a final year course on RSA etc.
> However it struck me that what with Israel's legendarily tight security, I
> might be asking for trouble. Are there any well-travelled crytographers
> out there who can advise me?
Excuse me?
I live in Israel. We don't have laws about importing or exporting crypto
materials. The security checks are related to explosives and weapons.
I have ordered 'Applied Cryptography' over the internet and didn't had any
problem whatsoever getting it.
Miki Watts
------------------------------
From: Future Beacon <[EMAIL PROTECTED]>
Subject: Re: RSA public exponent
Date: Sun, 10 Sep 2000 19:46:39 -0400
Ed,
Is the nature of the message at all relevant to finding the private
key or is that process completely independent of the data being
sent? Would you expect no greater difficulty in finding the private
key if the messages were all random numbers? Is there anyway to use
regularities known to be present in the intended message to crack
the code?
Thank you for your help.
Jim Trek
Future Beacon Technology
http://eznet.net/~progress
[EMAIL PROTECTED]
On 10 Sep 2000, Ed Pugh wrote:
> Thomas Pornin ([EMAIL PROTECTED]) writes:
> > According to Paul Schlyter <[EMAIL PROTECTED]>:
> >> If I instead wanted a full-length public exponent too, it must
> >> be selected somehow. How would I do that?
> >
> > Select it at random. All that is required is that it must be relatively
> > prime to phi(N)=(p-1)(q-1) where N=pq is the modulus.
> >
> > 65537 is useful because it is prime, and therefore has a high probability
> > of being relatively prime to phi(N) for a randomely chosen N. But there
> > is no obligation to choose a prime number.
>
> When generating keys, we can "set" one exponent to a specific number
> and let the algorithm find the other exponent. Both exponents must
> be relatively prime to phi(N) (as stated elsehwere). If one is r.p.
> to phi(N), then so is the other. Therefore we must choose one
> exponent to be r.p. to phi(N), and let the algorithm select the other
> exponent.
>
> Now, if the chosen exponent is small (in comparison with N), then the
> other exponent will most likely be large (AFAIK; someone please correct
> me if I am wrong about this). Therefore, it is best to choose the
> public exponent to be relatively small, so that the secret exponent
> will be large.
>
> Also, it is more efficient for the encryption algorithm if the public
> exponent has the smallest possible "binary weight" (i.e. the smallest
> possible number of set bits). (For the "fast" modular exponential
> algorithm, the time to do it is proportional to the bit length plus
> the binary weight -- i.e. the number of set bits -- of the public
> exponent.)
>
> Therefore, it is usually easiest to use a PRIME public exponent of the
> form 2^k + 1, where k is an integer that makes the result prime. (A
> prime public exponent has a higher probability of being r.p. to phi(N)
> than a non-prime exponent would, so we choose a prime one.)
>
> For this reason, RSA often uses public exponents 3 (2^1 = 1), 17
> (2^4 + 1) and 65537 (2^16 + 1).
>
> Since it is actually the secret exponent that we want to keep from
> being found, I am not really sure that the size of the public exponent
> has much bearing on the security of the secret key. (Again, though,
> somebody please correct me if I am wrong about this.) Therefore, I
> believe we can use smaller public exponents without compromising the
> security of the secret key.
>
> One thing to keep in mind, though, is that there are actually
> INFINITELY MANY (Aleph-Null, to be exact) secret exponents for any
> one public exponent. The smallest secret exponent can be found by
> d = (e^-1) [mod (LCM((p-1),(q-1))], where e is the public exponent,
> N = pq and LCM(a,b) is the least common multiple of a and b. Any
> number congruent to d [ mod (LCM(p-1),(q-1))] will work as the secret
> exponent for RSA decryption. Therfore if an attacker can find ANY
> such value, then the secret key has been broken.
>
> It is (AFAIK) currently believed that factoring N is the easiest way
> to find the secret exponent of a RSA key. I often wonder, however,
> if there may be an easier attack available, given the fact that
> there are infinitely many possible secret exponents.
>
> Best regards,
> --
> Ed Pugh, <[EMAIL PROTECTED]>
> Richmond, Ontario, Canada (near Ottawa)
> "Bum gall unwaith-hynny oedd, llefain pan ym ganed."
> (I was wise once, when I was born I cried - Welsh proverb)
>
------------------------------
From: "lala" <[EMAIL PROTECTED]>
Subject: Re: RC5-SAFE? - SAFEBOOT
Date: Mon, 11 Sep 2000 09:56:54 +1000
I didn't want start a flame war. But thanks both for advice. P.S. Tom when
you say 'I would avoid the program at all costs.' - is this because it is
trully insecure or too slow? I'm not trying to defeat the NSA here only
ensure data is inaccessable from mid/large business for a year or two.
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:8pftps$7th$[EMAIL PROTECTED]...
> In article <1gDu5.37341$[EMAIL PROTECTED]>,
> "Paul Pires" <[EMAIL PROTECTED]> wrote:
> >
> > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > news:8pesut$5sf$[EMAIL PROTECTED]...
> > > In article <8peohu$2n8$[EMAIL PROTECTED]>,
> > > "lala" <[EMAIL PROTECTED]> wrote:
> > > > Sorry, I', a novice, so sorry if this question is stupid. I
> believe
> > > this
> > > > program is great for total disk encryption.
> > > > Some information sent to me says,....
> > > > "The encryption method is based on the RC5 algorithm published by
> RSA
> > > > Laboratories. This algorithm uses a 1024 bit key and 12 rounds
> with a
> > > 32-bit
> > > > word size in CBC mode. Using this method, SafeBoot is able to
> encrypt
> > > data
> > > > at the rate of ~6MB/sec."
> > > > Is this totally insecure, or still not bad encryption? It's the
> 32bit
> > > not
> > > > the 1024 bit I should be looking at right? i.e. this is not 128bit
> > > > encryption. Thanks for advice.
> > >
> > > Your obviously a crypto-newbie. The 32-bit word size means RC5 is
> > > implemented as a 64-bit block cipher. The 1024-bit key is a bit
> > > disconcerning since RC5 is normally only used with keys from 64 to
> 256
> > > bits. 1024 bits seems excessive.
> > >
> > > Also with 12 rounds a differential or linear attack could in theory
> be
> > > applied, I would use at least 16 rounds and hope not to have a weak
> key
> > > (low chance really).
> > >
> > > plus 6mb/sec is really slow. My RC5 code with 12 rounds gets 22.25
> > > MB/sec on my K6-2. So thats about four times slower then it should
> be.
> >
> > Sorry for the off track but...
> >
> > It's Dennis Miller time.
> >
> > Gosh, if everybody would state the platform and clock speed when
> > discussing stats it would be so nice. Clocks per byte isn't great but
> I think
> > it's the most relevent spec if it is derived from actual testing.
> Another wonder
> > spec is when someone posts C source and then claims performance for
> > what is obviously a higly optimized, pipelined nitro-burning
> assembler version.
> > "The Source is free and un-patented. Oh, you want the fast one? I'll
> have our
> > sales rep set up an appointment." By the way Tom. I'm not aiming this
> at you.
> > Your post just reminded me of it.
>
> Well ok, I get 15 cycles/byte with my implementation in Assembler. And
> it's *FREE* to use if you don't live in the states. Except my RC5 key
> schedule doesn't work right in asm (the rest is ok).
>
> Or you could try TC6a which is the fastest block cipher in the world in
> plain C code on a x86 series cpu. I get 12 cycles/byte. It's rather
> secure except for a impossible differential attack that would require
> about 2^64 work anyways.
>
> Tom
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
** 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
******************************
