Cryptography-Digest Digest #916, Volume #12 Sat, 14 Oct 00 04:13:01 EDT
Contents:
Re: Why trust root CAs ? (Greggy)
Re: Why trust root CAs ? (Greggy)
Re: What is meant by non-Linear... ("Scott Fluhrer")
Re: Why trust root CAs ? (Greggy)
Re: Why trust root CAs ? (Greggy)
Re: Why trust root CAs ? (Greggy)
Re: Why trust root CAs ? (Greggy)
Re: Why trust root CAs ? (Greggy)
Re: working with huge numbers (Ray Dillinger)
Re: Storing an Integer on a stream (SCOTT19U.ZIP_GUY)
Re: Why trust root CAs ? (Paul Rubin)
Re: working with huge numbers (David Blackman)
----------------------------------------------------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: Sat, 14 Oct 2000 04:59:31 GMT
> However, there is a good reason to
> use a CA authority that has nothing to
> do with snake oil verifying.
No there is not.
> While you can trust the WSJ or your local
> newspaper somewhat more than CAs repository
> (how many keys could you improve by distributing
> some unmarked cash?), it is a hassle to transfer
> your bank's public key from a paper newspaper
> into your browser compared to letting your
> browser ask a CA.
You are stating that ease of use is a good benefit. Ease of use is
contrary to the concept of verification. Verification involves work.
You are putting the verification work back onto the shoulders of the
CA. That means you are trusting them to verify it for you and then
supply it in an electronic form so you don't have to verify it yourself.
But if you won't bother to verify it, then why have it at all? What is
the point of it?
If ease of verification is important then I suggest the banks use ECC
instead of RSA.
--
If I were a cop, I would refuse to go on any no knock raid.
But then, I am not a cop for basically the same reasons.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: Sat, 14 Oct 2000 05:04:09 GMT
> CAs provide a service. You can take advantage of that service or
> you can roll your own. The choice is yours. A business, such as a
> bank, has the same choice.
I never said otherwise. I said that the business model makes no sense,
but it is being pawned off like it really does.
Yes, the banks can roll their own for us. But some have stock in these
CAs. My comments were that the strategy is not sound. That makes it a
fraud for consumers.
--
If I were a cop, I would refuse to go on any no knock raid.
But then, I am not a cop for basically the same reasons.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: What is meant by non-Linear...
Date: Fri, 13 Oct 2000 21:46:50 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:8s6t4s$dcs$[EMAIL PROTECTED]...
>
> If I understood Bihams paper "On Matsuis Linear Cryptanalysis" (which I
> might not have) they form a chain of linear approximations through the
> rounds like one would for a differential attack.
>
> Is the analogy not correct?
I'm not certain. IIRC, the best version of Matsui's attack works like this:
- You have a single 14 round linear approximation (that is, the
approximation is one linear equation) between rounds 2 through 15, which
involves a small subset of the bits going into round 2 and coming out of
round 15.
- You use that approximation as a distinguisher. That is, for all the
subkey bits in rounds 1 and 16 that affect any of the bits involved in the
approximation, you cycle through all possible values. For each value of the
subkey bits, you compute (for all your known plaintext/ciphertext) what the
values at rounds 2 and 15 would be, and then you check if the linear
equation holds more often or less often than random. Once you find the
setting that gives you a significant bias, you know those bits of the
subkeys, which gives you certain of the key bits.
- Once you have those key bits, you brute force the rest.
Now, I'm not certain what's the best differential attack against DES.
Certainly, you can use a differential as a distinguisher, which would give
you something similar to the above attack (except, of course, you usually
only guess subkey bits in the last rounds). However, another feature about
differentials is that, if a differential holds, then subkey bits must be
certain settings to make it hold, and at least in the first/last rounds,
those settings can often be guessed. For example, given a particular
differential, that attacker might be able to deduce that 6 particular bits
of the subkey must be one of the following settings: (000101, 001101,
010011, 110111, 111000). Collect enough probable differentials, and the
attacker might be able to gesalt a good fraction of the key without
bothering with the rather large amount of computation involved with a
distinguisher.
--
poncho
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: Sat, 14 Oct 2000 05:12:34 GMT
> If you are a business 'rolling your own'
> what benefits do you get apart from
> distributed password management and
> centralised cert issuing (as opposed to
> cetralised password management and UserID
> issuing). That is, without going
> the German route of E3 accredited
> hardware for every user before legal
> validity can be attached to the output.
If you were a bank and you had these choices before you and your
marketing people were telling you that you can either:
A) use this totally insecure CA strategy and provide your customer base
with a very simple to use web site that would save you money in teller
payrolls
or
B) use a real strategy for security that makes your customers work
harder, which in turn would drive your customers away from your new web
sites (and you lose the payroll savings as well)
which would you choose?
People don't use on line banking because it is very secure, but because
they realize the odds are stacked in their favor and the system is very
easy to use.
--
If I were a cop, I would refuse to go on any no knock raid.
But then, I am not a cop for basically the same reasons.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: Sat, 14 Oct 2000 05:17:26 GMT
> Now, an implications of this is that if you can verify an electronic
> signature with the public key, then it was signed with the private key
> VeriSign asserted was once in the posession of Amazon.com. If you
> trust Amazon.com not to lose control of its private key, then you can
> conclude the signature was made by Amazon.com (whatever it means to
> say a business entity "signed" something). If the key is being used
> to set up a secure browser session, then you can conclude your browser
> session is with Amazon.com rather than Joe's Discount Browser Session
> Hijacking.
But you missed the real problem with CAs. Can Verisign answer the
following for you:
Can you prove none of your employees took a bribe and provided me with
a bad cert?
Can you prove none of your employees maliciously provided me with a bad
cert?
Can you prove none of your employees failed to follow every step of
your certification process?
Can you prove that your certification process is adequate for my needs?
The answers: no, no, no, and no. And if they tell you otherwise, that
should be big news for this newsgroup. They would most likely be lying.
--
If I were a cop, I would refuse to go on any no knock raid.
But then, I am not a cop for basically the same reasons.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: Sat, 14 Oct 2000 05:28:06 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Larry Kilgallen) wrote:
> In article <eMoD5.416654$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] writes:
>
> > So, I can discover snakeoil CA's procedures for verifying bogus.com,
> > and assure myself that they have checked out bogus.com.
> > But how can I trust snakeoil CA itself ?
> > I had a conversation with a CA on this subject and the answer was
> > "because it's in the browser". But my browser was downloaded off
> > the Internet in clear, and besides, do I really trust the browser
> > vendor ? Do you trust Microsoft not to lie ? Do you trust Microsoft
> > or Netscape to produce secure independantly verified code ?
>
> If you obtained your browser via download, that does mark you as a
> trusting individual.
Or a fool. Take your pick...
> But I do believe that Netscape allows you total control over what
> root certificates it honors, so you can turn off their defaults and
> load your own.
>
> It was not until I heard a talk in Cambridge a few years ago by
> Steve Kent that I understood "self-signed" certificates. The signing
> does not convey any trust -- it is just an artifact to get
certificates
> into a form with which relying software is accustomed to dealing.
It is a means to root the tree of trust. Someone must ultimately be
trusted at the root.
Now here is a point of interest. The more people you must trust in the
CA chain, the less secure it becomes. Thus, if BofA were simply to
publish a public key in the WSJ, then they could verify the printing of
their key before allowing their servers to provide the services. If the
key were bad (mistake perhaps) then they could keep their servers
offline until the public was warned and the key could be changed. In
this scenario, you only have to trust BofA. A much more secured chain
of trust, if you ask me.
>
--
If I were a cop, I would refuse to go on any no knock raid.
But then, I am not a cop for basically the same reasons.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: Sat, 14 Oct 2000 05:33:24 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Larry Kilgallen) wrote:
> In article <8s8cvj$m04$[EMAIL PROTECTED]>, JD <[EMAIL PROTECTED]>
writes:
> >
> >> It was not until I heard a talk in Cambridge a few years ago by
> >> Steve Kent that I understood "self-signed" certificates. The
signing
> >> does not convey any trust -- it is just an artifact to get
> > certificates
> >> into a form with which relying software is accustomed to dealing.
> >
> > It's more important than that; in fact, I would say that the
signature
> > is actually half of the trust equation.
> >
> > It proves that the self-signer actually controls the private key
that
> > corresponds with the public key contained within the certificate.
>
> So the trickster merely must replace the public key and use their
> own private key. Nothing is proven by self-signing.
>
I don't think it was ever ment to prove anything. You have to begin
your root trust with something that YOU trust. You don't prove it, you
trust it. It proves the rest of the certificates for you. You don't
have to trust the others, but you do have to trust the root. To that I
say, Why should I trust anyone other than my bank?
--
If I were a cop, I would refuse to go on any no knock raid.
But then, I am not a cop for basically the same reasons.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: Sat, 14 Oct 2000 05:42:32 GMT
> I don't think it was ever ment to prove anything. You have to begin
> your root trust with something that YOU trust. You don't prove it,
you
> trust it. It proves the rest of the certificates for you. You don't
> have to trust the others, but you do have to trust the root. To that
I
> say, Why should I trust anyone other than my bank?
Hey, what an idea - make my bank my root certificate and get rid of all
the rest. I go down to the branch office and get their certificate
directly and install it as the only certificate on my machine. That
would be the only way it could work for me. More work, yes, but real
security because I know I have the right certificate. I don't have to
trust anyone other than my bank.
I'm going to try this on one of my machines I will set aside for online
banking only. The others can browse away at other things as they
desire. What an idea...
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Ray Dillinger <[EMAIL PROTECTED]>
Subject: Re: working with huge numbers
Date: Sat, 14 Oct 2000 05:48:34 GMT
On Thu, 12 Oct 2000, Benjamin Goldberg wrote:
>Ray Dillinger wrote:
>>
>> Using such libraries for crypto has not really been a problem
>> at all; Okay, my modular exponentiation routine may take three
>> or four eyeblinks instead of one -- but I don't really care
>> because encryption/decryption tends to be quite fast, measured
>> in human terms, anyway. So I don't deal with the machine code
>> and hand-tweak processor scheduling and carefully arrange blocks
>> to fit into the cache on particular CPUs (all of which techniques
>> I see in the PGP code), I just write numerical algorithms on 16-
>> bit and 32-bit integers. They are efficient *algorithms*,
>> so they run in the "right" order of magnitude -- but chasing down
>> every last bit of performance available is just not worth my time
>> or the trouble of verifying the resulting assembly-language code.
>
>When you do multiplications, do you use Montgomery form? This isn't
>merely a little tweak that gets a tiny increase in performance, it is a
>major speed-up.
Hmmm. Maybe not. I don't know what you mean by "Montgomery Form".
What I do for the first cut is the basic russian algorithm;
1) Make a new buffer to hold the answer and initialize it to 0's
2) Pick the operand that has the lowest binary weight
(number of 1's in its binary representation) and
call it "B". The other number becomes "A".
3) for each 1 bit in "A", I add "B" to the answer buffer
at that bit's offset.
4) When the last 1 bit in "A" is processed, the answer
buffer holds the answer.
======
When I'm coming back through and making things better, there
is another algorithm that becomes substantially faster on
large numbers. Well, actually it's the same algorithm really,
just counting in base 16 instead of base 2. Is this what you're
calling "Montgomery"?
1) Make a new buffer to hold the answer and initialize it to 0's
2) Call the operand with the fewest different nybbles A and the
other operand B. Or if one has a lot of zero nybbles, it will
also make an excellent choice for A.
3) Make an array of 15 buffers to hold B*1 to B*15, but don't
compute them until step 4 indicates that you actually need
them.
4) For every nonzero nybble in A add B times that nybble to
the answer, at the offset of that nybble.
======
The numbers have to be awfully damn big before it becomes a
performance win to allocate 255 buffers and go by bytes instead
of nybbles, but I've done that twice -- once in my C library
(for numbers bigger than 8182 bits) and once in Pascal.
>Also, I believe that there's some kind of way to use
>Fourier transforms to get large speed increases (not sure on this,
>though).
I'm not aware of this method -- and it doesn't sound plausible
to me for any kind of non-modular arithmetic.
>In other words, do you use the most efficient algorithms, or
>the easiest to code?
Somewhat a tradeoff. I would not consider, eg, a linear
algorithm if there were a logarithmic one available, nor
a polynomial algorithm if there's a linear one available.
But I'm fairly cavalier about logarithmic to a slightly
higher base power or linear with a somewhat higher factor
if I can get simpler, clearer code by making that choice.
>Also, for exponentiation, there's a method that
>works using repeated squaring, and squaring a big integer can be faster
>than multiplying it by itself.
The Exponentiation algorithm I usually use is similar to
the first of the two above, except I work with a *copy* of
B, which I square each time I process a bit, and multiply
the answer buffer by (instead of adding it with a power
offset) when processing a one bit.
However, the "squaring" I do is actually just a call to the
multiplication function -- I've learned a faster algorithm
for cubing something, but alas, there doesn't seem much call
for cubing things.
>I agree, sort of, but I think that using a pre-written library is even
>better for verifying your code is correct, if you are able to assume
>that the library is correct.
Oh Gods yes, I quite agree. Remember, most of my goal with
these bignum libraries has been to learn the languages involved
-- If you have no such goal, or if you are working in a language
that's already familiar to you, then by all means go and get the
one that's prefab and probably more efficient -- provided it does
what you want.
Ray
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: comp.compression
Subject: Re: Storing an Integer on a stream
Date: 14 Oct 2000 07:23:58 GMT
[EMAIL PROTECTED] (Benjamin Goldberg) wrote in
<[EMAIL PROTECTED]>:
>
>> For example one may wrongly think
>> that if one had a data file of 256 bytes. You might think one needs
>> a file of 257 bytes. This is the maximun you need but sometimes you
>> can get by with less.
>
>Your messed up grammar makes this nearly impossible to understand. I
>would *guess* you are saying that to encode the integer value 256 you
>need to use 8 bits, but I'm not sure.
>
It means sometimes you add up to a maximun of 8 bits. Sometimes less
sometimes the resultant file is shorter.
>> >stored? As a fixed sized integer, in base 128, in base 255, using a
>> >fibonacci coding, or something else? *What* the integer means isn't
>> >particularly important to this discussion, but *how* it's stored on
>> >the stream/in the file *is*.
>>
>> The way it is stored is rather complicated. ANd as sure as hell
>> I will tell you wrong.
>
>Probably, but if you don't make the attempt, noone will learn how it
>works. Would you consider a fib encoding "rather complicated?" It's
>certainly more complicated than the other 3 methods of writing an
>integer. That doesn't, however, make it better for all cases (only ones
>above a certain size, and only if you aren't worried about byte
>boundaries, only bit boundaries).
>
>> But my code is there you can test it and see for itself. Its thousands
>> of C code character long.
>
>And this is supposed to encourage me? If you didn't habitually
>obfuscate your C code, perhaps I would look at what you've got.
>Instead, I want you to tell me (and the rest of us on these NGs).
>
>> Take a look if you want an example give me a set of data and I can
>> give you the set with the pointer added.
>
>Ok. Here is my data: I want to encode the pointer 3287 and send it
>over a bitstream. What is the string of 0s and 1s that gets sent.
Actually the way its encoded is a function of the file. Maybe It would
be easier explained if you don't just think of it as added in. But welded
in.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: 14 Oct 2000 00:49:09 -0700
Greggy <[EMAIL PROTECTED]> writes:
> But you missed the real problem with CAs. Can Verisign answer the
> following for you:
>
> Can you prove none of your employees took a bribe and provided me with
> a bad cert?
How is it *possible* to do that in a way that you couldn't detect instantly?
> Can you prove none of your employees maliciously provided me with a bad
> cert?
How is it *possible* to do that in a way that you couldn't detect instantly?
> Can you prove none of your employees failed to follow every step of
> your certification process?
For at least some types of Verisign signing processes, the proceedings
are videotaped in front of witnesses.
> Can you prove that your certification process is adequate for my needs?
The certification practices statement is public. The only person who
can decide if it's adequate is you.
> The answers: no, no, no, and no. And if they tell you otherwise, that
> should be big news for this newsgroup. They would most likely be lying.
Look, Verisign is pretty straight about what guarantees they give you.
If you have financial losses from problems with a Verisign cert,
they'll cover you up to some amount (the amount depends on the type of
certificate). What do you want them to do instead? What would *you*
do instead?
Suppose you run a grocery store and a customer wants to write you a
check and shows you a valid-looking drivers license as ID. Can you
know the DL isn't forged? Of course not; but you generally take it
anyway. You've decided that the probability of a forged drivers
license times the amount of loss caused by a bad check for some
groceries is less than the profit you'd forgo by declining the check.
Making that kind of probability-based decision is called risk
management. With enough transactions you'll get bitten a few times,
but less often than if you didn't ask for ID at all.
Certificates in a PKI are a risk management device, not an absolute
guarantee of anything. Verisign's marketing pitch is that
authenticating with a class 2 Verisign PKI certificate is about as
good as looking at someone's drivers' license: they can be faked, but
not easily. A class 3 certificate is supposed to be as good as
looking at a passport: harder to forge than a drivers license, but
still not impossible. I don't claim to believe those estimates, but
in any case, the certs have a certain level of security that's not
trivial and not infinite. This is good enough for most of the
business purposes that they're sold for.
------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: working with huge numbers
Date: Sat, 14 Oct 2000 18:54:54 +1100
Benjamin Goldberg wrote:
> When you do multiplications, do you use Montgomery form? This isn't
> merely a little tweak that gets a tiny increase in performance, it is a
> major speed-up. Also, I believe that there's some kind of way to use
> Fourier transforms to get large speed increases (not sure on this,
> though). In other words, do you use the most efficient algorithms, or
> the easiest to code? Also, for exponentiation, there's a method that
> works using repeated squaring, and squaring a big integer can be faster
> than multiplying it by itself.
I'm not sure that Montgomery multiplication is such a huge win, at least
for numbers of crypto size. I guess for really huge numbers where FFT is
a win, Montgomery should help.
Back around 1990 a friend and i wrote a bignum package that didn't use
Montgomery, and just used obvious algorithms, in portable C. On the
computers we had, it did modular exponentiation a bit faster than the
Lenstra/Manasse code which was about the only bignum package that we
could get hold of at the time. Lenstra/Manasse did use Montgomery. This
Lenstra/Manasse code was part of the distributed network factoring code
that was used in some of their record breaking factoring.
We did use squaring where appropriate in the modular exponentiation (for
about 2/3 of the multiplies typically i think). This wasn't a huge win,
but it did help a bit. Maybe 10% faster overall.
------------------------------
** 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
******************************
