Cryptography-Digest Digest #756, Volume #11 Thu, 11 May 00 17:13:01 EDT
Contents:
Re: RSA-primes, smoothness (Roger Schlafly)
Re: Request for cryptanalysis: lja1 (David A. Wagner)
Re: PlatyMAC a new Message Authentication Code. (David Formosa (aka ? the Platypus))
Re: How does one test an encryption algorithm? (Richard Heathfield)
Re: Q: Searching for authentication protocols (Thomas Wu)
Re: Newbie question about generating primes (Jeffrey William)
Re: Why no civilian GPS anti-spoofing? / proposal (zapzing)
Re: UK issue; How to determine if a file contains encrypted data? (zapzing)
Re: An argument for multiple AES winners (Mok-Kong Shen)
Further request for cryptanalysis: tweaked lja1 (Andru Luvisi)
Try it. (None)
Re: Newbie question about generating primes (John Myre)
----------------------------------------------------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: RSA-primes, smoothness
Date: Thu, 11 May 2000 12:16:20 -0700
Jerry Coffin wrote:
> > I say it is snake oil because it gives an illusion of security
> > when there actually is none. If someone wants to make an RSA key
> > that he will disavow later, there are other ways:
>
> IOW, taking steps that improve security are snake oil unless they
> provide an absolute assurance of security.
No, but the step should have some security advantage or it is useless.
> The simple fact is, this step eliminates one entire class of weak
> keys. It's quite effective in doing so.
No. Keys generated by the ANSI/Silverman process are not any stronger
than keys generated randomly, according to most experts.
> Yes, there are other ways a
> key could be weakened, and there's probably no way to eliminate all
> of them. This does NOT make it snake oil to eliminate one class of
> weak keys, and saying it is simply makes you look foolish.
An extra feature is snake oil if it is added in order to claim
some security advantage when the feature has no such advantage.
Don claims that the ANSI/Silverman key generation will help prevent
users from disavowing keys. However, as I explained, it doesn't do
that at all, because there are alternate ways of disavowing keys
and some of them are easier.
> Don't get me wrong: I'm not saying that I think this particular
> requirement is necessary, or necessarily even does a lot of good.
> Harmless (if useless) appendages to otherwise strong encryption do
> NOT turn it into snake oil.
No, but the useless appendage is snake oil.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Request for cryptanalysis: lja1
Date: 11 May 2000 11:37:58 -0700
In article <[EMAIL PROTECTED]>,
Andru Luvisi <[EMAIL PROTECTED]> wrote:
> Where can I learn more about slide attacks?
Well, Alex Biryukov and I had a paper at FSE'99 on the subject.
It's online at http://www.cs.berkeley.edu/~daw/papers/slide-fse99.ps.
> [EMAIL PROTECTED] (David A. Wagner) writes:
> > These ideas can probably be extended to get a key-recovery attack.
>
> I am having trouble figuring out how.
I'm not exactly sure how, either, but I am thinking that looking
first at (X,X,..,X) plaintexts, then (X,Y,X,Y,..,Y) plaintexts, and
so on, might start giving you enough information about the key table
to start peeling off rounds, etc.
Or, maybe not. Maybe there is no key-recovery attack here..
This is all merely unsubstantiated speculation on my part.
> Of course, I would never *use* one cycle, just on general principle.
> [...] At least two cycles would be needed in order to prevent an attacker
> from knowing the output of any given round.
Right. Sounds reasonable.
------------------------------
From: [EMAIL PROTECTED] (David Formosa (aka ? the Platypus))
Subject: Re: PlatyMAC a new Message Authentication Code.
Date: 11 May 2000 19:32:57 GMT
Reply-To: dformosa@[202.7.69.25]
On 9 May 2000 07:44:05 -0700, David A. Wagner
<[EMAIL PROTECTED]> wrote:
>First, let me see if I understood the MAC:
> The i-th compression function f_i : GF(2)^256 -> GF(2)^128
> is chosen as a random affine function using 256*128 + 128 bits
> of output from a pseudorandom generator.
Well its a secure pseudorandom number generator, rather then just a
plain PNG, this wasn't made clear in the original spec but was the
intent.
[...]
>For instance, consider G_bad defined by G_bad(x) := S(t(x))
>where S() represents a secure stream cipher (e.g., RC4 or 3DES-OFB)
>and where t() is the function that drops the high byte of its
>input. Clearly this G_bad is a secure PRG if S is;
I don't quite aggry with you here, anything that ignores a bit of its
key is not a secure. Though your point that a related key attack
exists is a valid one.
>The solution is that we should use a pseudorandom function
>(a PRF) F : Keys x IVectors -> {0,1}^*. We could then replace
>G(key xor IV) with F(key,IV), and the result will be secure.
Rather then useing F which IMHO just adds a new thing that could go
wrong could the following construct be used?
G(x) := S(x) ^ IV
Where ^ is xor and S(x) is a secure stream cypter?
>Question: How efficient is this MAC in practice?
I think its going to fall into the "secure but to slow to be usefull"
class.
--
Please excuse my spelling as I suffer from agraphia. See
http://dformosa.zeta.org.au/~dformosa/Spelling.html to find out more.
Interested in drawing platypie for money? Email me.
Crack my Hash win$200 http://dformosa.zeta.org.au/~dformosa/PlatyMAC.txt
------------------------------
Date: Thu, 11 May 2000 20:36:45 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: How does one test an encryption algorithm?
Runu Knips wrote:
>
> [EMAIL PROTECTED] wrote:
> > I have an dynamic encryption algorithm and it needs to be tested. Is
> > there a newgroup or a group of freelance hackers :-) or some place
> > where I could test by hiring services.
>
> You can publish the algorithm in this newsgroup. Many excellent
> experts are reading it. No, I'm none of those ;-)
This idea of publishing your algorithm, which Runu correctly suggests,
is counter-intuitive. It's more natural to think that your algorithm
will be more secure if you keep it secret. This is, however, a fallacy.
If the security of your encryption relies on the secrecy of your
algorithm, you are at the mercy of whoever disassembles your code to
find out how it works. Yes, you could keep the algorithm a secret from
sci.crypt by simply not posting it here, but you can't keep your
algorithm a secret from /everyone/ if you want to exchange encrypted
information with anyone else, because they will need a copy of your
program, and therefore you must cede the complete control over your code
which alone ensures security. Even if your encryption algorithm is
intended only to safeguard data on your personal computer, bear in mind
that you wouldn't even consider encrypting information on your machine
if you weren't concerned that someone else had physical access to that
machine - and if they have physical access, they can grab your algorithm
and analyse it.
The consequence is simple: whilst a good algorithm is necessary, the
security must rest in the key alone. Therefore, a good algorithm could
be said to be one which combines the key with the plaintext in a way
which cannot be reversed within a reasonable time (a few million
computer-years at least - consider Moore's Law!) except by using the
key.
>
> > All I want to know is that if my algorithm is tough to crack.
I too would like to know if my algorithm is tough to crack. I posted it
here, and a weakness was kindly pointed out to me. As a result, I have
(I think) improved my algorithm, although it's not yet ready to meet the
challenge of being posted here.
> > How does one estimate the confidence factor of an encryption algorithm?
Tricky one. It all depends against whom you are protecting your data. If
your 'threat model' is your kid sister, then a simple bit flip would
probably suffice! (Unless, of course, your sister works for GCHQ or the
NSA.) If you're trying to protect against major governments, your task
is considerably more difficult, and may be impossible (who knows?).
My own threat model is nothing so heavy - I'm only really interested in
protecting network packets against casual crackers. So I'm not too
concerned with finding the 'perfect' algorithm.
> > Are there any metrics defined?
Runu answers this point much better than I can:
>
> If there would be such a metric, this newsgroup would be obsolete.
> Your statement shows that you don't know much about crytography,
> therefore its unlikely (but of course still possible) that your
> algorithm is really good.
>
> You have to publish the algorithm and let the experts discuss it.
Quite so. This is the bridge you have to cross, and it can be difficult
for some people to do. But it really is the right way to go.
>
> Or use one of those well-tested algorithms already available, such
> as Blowfish, or Rijndael, Serpent, Twofish, or others.
Yeh yeh yeh, and how much fun is /that/ for a programmer? :-)
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
35 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (62
to go)
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc
Subject: Re: Q: Searching for authentication protocols
Date: 11 May 2000 12:34:43 -0700
Tom�s Perlines Hormann <[EMAIL PROTECTED]> writes:
> Thanks for the info!
>
> It sounds really interesting to me, specially as it doesn't require many
> ressources.
>
> The next issue is if you consider it feasible to do a sort of
> cross-authentication in a multicast environment. Let's say that 3 or
> more (>2) students want to discuss a certain issue but they are remotely
> connected to a whiteboard (wb). Would you think that SRP could handle
> the authentication of each of the principals to the others?
> Currently I am thinking of having this authentication being controlled
> by a TTP as the Kerberos system would do it. But I am searching for
> alternatives, specially since Kerberos needs a dedicated server (acting
> as KDC), which on top of it all has to be trusted and therefore secured.
If the students registered their verifiers (v) with the whiteboard "server",
then each of the students could authenticate themselves to the wb just by
knowing their passwords. At that point, everyone would have a session key
exchanged with the server, which could be used to set up an secure session
that allowed them to draw, send data, issue commands, etc. to the whiteboard.
No public key files or containers would ever be necessary, nor would this
require a TTP.
--
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: Jeffrey William <[EMAIL PROTECTED]>
Crossposted-To: alt.math
Subject: Re: Newbie question about generating primes
Date: Thu, 11 May 2000 14:47:25 -0500
Dann, good answer, but I *think* that the question really related to the
algorithm being used to generate the primes. Using your example of 256-bit
primes, unless you generate all of them (an interesting task :), you're going to
have a methodology for generating a set of 256-bit primes. If I know the
methodology, I can use it to duplicate the set of 256-bit primes. Unless you're
set of primes is really really big,
I've got a significant advantage.
Presumably, therefore, the algorithm used to generate the set of primes must
make use of a secret key (or seed value or whatever you care to call it) and the
set of primes themselves must be kept secret.
A newbie question, but a good one.
Dann Corbit wrote:
> "Thomas Scharle" <[EMAIL PROTECTED]> wrote in message
> news:8fet8c$[EMAIL PROTECTED]...
> > I have another newbie question about generating primes
> > for cryptographic purposes.
> >
> > I presume that the method that you choose to generate
> > primes will generate only a certain subset of the primes.
>
> Since we can only generate finitely many, and there are an infinite number
> of primes, your statement is trivially true.
>
> > Wouldn't that reduce the search that someone would
> > have to do to find the prime factors?
>
> Let's suppose that we decide to create primes of exactly 256 bits. That
> means that we know before-hand the first bit of the prime candidates!
> Sounds limiting doesn't it? And primes at a size of 256 bits are much more
> rare than primes at a size of 10 bits, for instance. Sounds even more
> limiting!
>
> But consider the prime counting function pi(x). It can be approximated very
> well by the logarithmic integral or by Riemann's prime count estimator.
>
> If you look at this web page:
> http://mathworld.wolfram.com/PrimeCountingFunction.html
>
> You will see that (for instance) there are 234,057,667,276,344,607 primes
> with 19 digits or less (which also counts all with 18, 17, etc.). And there
> are 2,220,819,602,560,918,840 primes with 20 digits or less. That means
> that single digit gives us nearly ten times as many primes as all the primes
> up to one digit less before it. By the time you get to hundreds of bits,
> the addition of one more bit of length will add a prodigious number of
> primes.
>
> A simple way to generate primes of a given size is to pick some random odd
> number with the number of bits that you desire. Then throw prime tests at
> it. If it is not prime, add two to our large odd number and try again.
> There are probably a lot more sophisticated ways than that also. At any
> rate, large primes are currently very useful for secure communications
> because of the RSA algorithm.
> --
> C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
> "The C-FAQ Book" ISBN 0-201-84519-9
> C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
> C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Why no civilian GPS anti-spoofing? / proposal
Date: Thu, 11 May 2000 19:40:55 GMT
In article <8fdh0n$jpl$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Paul Rubin) wrote:
> In article <8fdg6h$vhn$[EMAIL PROTECTED]>, zapzing
<[EMAIL PROTECTED]> wrote:
> >If you are using a public key system, then you would include the time
> >in the message block that is being encrypted. Everyone could decode
> >and see that at least the signal claims to have been sent at such and
> >such a time. And since only the legitimate transmitters have the
> >encoding key, it must have come from a legitimate transmitter. Not
> >susceptible to a replay attack. No Problemo.
>
> The thing is, there's not exactly a message block being encrypted or
> signed. It's more complicated than that, and it's not obvious that
there's
> a workable answer.
>
I'm a little canfused, are you the same Paul Rubin
who wrote the following:
"
I'd like to propose that civilian signals on the new carriers have
public-key digital signatures, signed by the satellites. Receivers
would be able to check the signatures by having the public key inside.
The receiver would not need any secret keys, so it would be
unclassified.
"
in message number
<8f35o6$o7i$[EMAIL PROTECTED]
??
Did you recently come upon some new
information?
--
Do as thou thinkest best.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: UK issue; How to determine if a file contains encrypted data?
Date: Thu, 11 May 2000 19:54:45 GMT
In article <[EMAIL PROTECTED]>,
Jeffrey William <[EMAIL PROTECTED]> wrote:
>
>
> zapzing wrote:
>
> >
> > Here in America, they are thinking
> > of outlawing the science of Astronomy,
> > because some astronomers have taken to
> > tracking low earth orbit objects,
> > including fedgov spy sattelites. They
> > don't like that, so they just talk
> > about outlawing astronomy. So when
> > you find a favorable country, let me
> > know.
>
> Being an astronomy buff living in the USA, I was taken aback by this
> statement. Could you please provide some references about this? And
how
> could you possibly
> outlaw astronomy? Blind the entire populace?
It was in this week's Time magazine, the one
with the Love Bug on the cover. The title
of the article was "Quick, hide the tanks!".
It was about a group of amateur astronomy
buffs who track military sattelites. It said
that they were considering outlawing the
practice. And, since one would obviously
not neccissarily know which sattelites were
top-secret ones, it would become illegal to
track any sattelite under this proposal.
Unless of course they told us which
satellites not to track, but there are
obvious problems with that, too :)
As for your idea of blinding the entire
populace, I wouldn't give them any ideas.
--
Do as thou thinkest best.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: An argument for multiple AES winners
Date: Thu, 11 May 2000 22:07:12 +0200
"David A. Wagner" wrote:
> Sam Simpson <[EMAIL PROTECTED]> wrote:
> > Details of he patent have been VERY well known about for some time.
> > I don't think anyone who has any vague interest in cryptography were
> > unaware that Hitachi has already asserted the same two patents
> > covered SHA-1 (way back in August of 1998!).
>
> Really? Probably I'm just showing my ignorance, but I'd never heard
> of the Hitachi patent until just this year. Of course, one should not
> draw any conclusions from a sample size of one :-), but are you sure
> this patent was as well-known as you say?
I suppose the basic problem is that many people don't have time or
interest to read patent documents. It would be fine, if some crypto
journal could create a review column about new patents that are
relevant to encryption. Let's hope that the academics will also pay
some more attention to patents in the future than hitertofore.
M. K. Shen
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Further request for cryptanalysis: tweaked lja1
Date: 11 May 2000 13:34:18 -0700
Based on the advice of David Wagner, I have modified the lja1
algorithm to protect against the slide attack. I invite further
comments and suggestions:
/* key[] is a 256 element array, containing 0-255 in a random order */
/* blocksize is the number of bytes in block */
void lja1_encrypt(unsigned char *key, unsigned char *block,
int blocksize, int cycles)
{
unsigned char acc;
int i, j, counter;
counter = 0;
while(cycles--)
{
for(i = 1; i <= blocksize; i++)
{
for(j = 0, acc = 0; j < blocksize - 1; j++)
{
acc += key[block[(i + j) % blocksize]];
acc = key[acc];
}
block[(i + j) % blocksize] ^= acc ^ (counter++);
}
}
}
void lja1_decrypt(unsigned char *key, unsigned char *block,
int blocksize, int cycles)
{
unsigned char acc;
int i, j, counter;
counter = blocksize * cycles;
while(cycles--)
{
for(i = blocksize; i > 0; i--)
{
for(j = 0, acc = 0; j < blocksize - 1; j++)
{
acc += key[block[(i + j) % blocksize]];
acc = key[acc];
}
block[(i + j) % blocksize] ^= acc ^ (--counter);
}
}
}
Andru
--
==========================================================================
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| [EMAIL PROTECTED] | Textile imports from Provence, France |
==========================================================================
------------------------------
Subject: Try it.
From: None <[EMAIL PROTECTED]>
Date: Thu, 11 May 2000 13:37:56 -0700
http://www.aasp.net/~speechfb
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Newbie question about generating primes
Date: Thu, 11 May 2000 14:51:33 -0600
Jeffrey William wrote:
>
<snip>
> Presumably, therefore, the algorithm used to generate the set of primes must
> make use of a secret key (or seed value or whatever you care to call it) and the
> set of primes themselves must be kept secret.
Right. If I might expand on this a bit, a common way to say this is
that
your seed value needs sufficient "entropy". That is to say, it has to
have
enough bits, generated "randomly", to prevent someone from guessing it.
This is why there is so much discussion on sources of random numbers.
Also, of course, the generation algorithm has to actually make use of
the
entropy. If the algorithm is poor, so that many seed values are
equivalent,
the attacker could be left with only a few (relatively speaking)
different
seeds to check.
In practice, if you want (say) a 1000-bit prime, you don't start with
1000 random bits. But you do start with (say) 100 random bits (as
random
as you can get, anyway). Then you expand those out to 1000 bits in a
cryptographically secure way. Then finally you step through numbers in
some regular way (starting with your 1000 semi-random bits) until you
find a prime.
So now there are two ways an attacker could discover the prime. First,
perhaps he can guess the seed. We hope that the seed is large enough
that
this is not feasible. Second, perhaps the attacker can take advantage
of
the structure of the prime search. Now we hope that, even if there is
some structure there, that it doesn't help enough, because the search
space is now so much larger (1000 bits).
A common search method is effectively to add 2 (i.e., checking each
odd number). Then you get the "nearest larger prime" from your 1000
bit value; this is not enough of a clue to help (there are too many
primes).
A poor search procedure might be, for example, to turn 1 bits to 0 bits
until you find a prime, starting at the left bit (except for the top
bit).
I just made this up; I have no idea if it is really weak. But it
doesn't
look good, does it?
As you say, a good question.
John M.
------------------------------
** 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
******************************
