Cryptography-Digest Digest #81, Volume #12 Thu, 22 Jun 00 01:13:00 EDT
Contents:
Re: small subgroups in Blum Blum Shub (Tim Tyler)
Re: small subgroups in Blum Blum Shub (Tim Tyler)
Re: small subgroups in Blum Blum Shub (Tim Tyler)
Re: obfuscating the RSA private key (Paul Rubin)
I need help to find reliable external MIME decoding utility, (jungle)
Re: Comments please: A protocol for Digital voting (zapzing)
Re: Weight of Digital Signatures (John Savard)
Re: AWFUL PUN (John Savard)
Re: MD5 Expansion (Andrew Bortz)
Re: Missing Info in the crypto-gram of MR BS (Andrew Bortz)
Re: Linear Feedback Shift Register *with* lock-up? (wtshaw)
Re: small subgroups in Blum Blum Shub (David A Molnar)
Re: Try it. (S. T. L.)
RE: Help - IEEE P1363 needed! (TAY YUE WENG)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Reply-To: [EMAIL PROTECTED]
Date: Wed, 21 Jun 2000 23:56:53 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
: in sci.crypt [EMAIL PROTECTED] (Klaus Pommerening) wrote:
:>In <[EMAIL PROTECTED]> Terry Ritter wrote:
:>> * We *can* build a generator which does not use short cycles.
:>
:>BTW the BBS generator outputs the LSB of its internal state
:>x_i for each step. (x_i = x_{i-1}^2 mod n)
:>Is there any known result that some choice of parameters in BBS
:>guarantees that the LSBs don't give short cycles?
: Not that I know of. I never even thought of investigating such a
: thing on my small models. I guess I assumed that sort of thing was
: exactly what the proofs guaranteed.
Since n = p * q (product of two primes), the /only/ way the lowest bit
could exhibit a cycle (of length c) smaller than min(p,q) would be if
it was always 0, or always 1.
*If* the cycle were known to be large enough this would be impossible,
though a shortage of such states. c > S/2 - assuming one bit is output.
If you output more than 1 bit this approach would not work - since you
have some other possible cycle lengths (related to the number of bits
output) to check for.
I don't know if c >= min(p,q) is in some sense "good enough" :-|
Alternatively - if this was admitted to be a possibility - it /might/
still be possible to retain a security proof that eliminated the
possibility of bad seeds by the use of a usually-rapidly-terminating test
that rejected what appear to be all-0 and all-1 streams as potential
problem cases :-/
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Reply-To: [EMAIL PROTECTED]
Date: Thu, 22 Jun 2000 00:23:50 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
: in sci.crypt [EMAIL PROTECTED] (Klaus Pommerening) wrote:
:> Terry Ritter <[EMAIL PROTECTED]> wrote:
:>> Mathematics being presumably the way to reach such a result,
:>> "proven secure" is well-understood to be the goal of cryptography
:>> itself. It is not a term to be usurped and re-defined as something less.
:>>
:>Less than what?
: "Less than" a proof that no known weakness exists which we can eliminate.
There appears to be no possibility of getting such a proof with BBS,
anyway - regardless of any concerns about the use of short cycles.
It only claims to be as hard to break as factoring the modulus - and
nobody really has any idea how hard that is.
Even if the factoring problem is hard, factoring the modulus is a
significant attack in itself. We'd be likely to get much better security
from the same key with a big table of hardware-generated, high quality
random numbers - XOR'd with the BBS output for good measure ;-)
This is a "known weakness" which certainly looks like it could be
eliminated - albeit at some expense.
I don't think "a proof that no known weakness exists which we can
eliminate" is on the cards.
Would you settle for a demonstration of no short cycles?
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ VIPAR GAMMA GUPPY.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Reply-To: [EMAIL PROTECTED]
Date: Thu, 22 Jun 2000 00:08:57 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
: <[EMAIL PROTECTED]> wrote:
:>[EMAIL PROTECTED] (Terry Ritter) writes:
:>> [...] As I said in a previous posting, the issue here is nothing
:>> less than the meaning of "proof" itself: If you are willing to call
:>> something "proven secure," when the math itself says there is a
:>> small, but preventable probability of weakness, you are willing to
:>> bend more then I am.
:>
:>Could you state what you mean by "provable security"?
[snip discussion of what "provable" means - or should mean]
: I suggest "statistically secure."
That's not going to appeal very much to managers or marketing.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: obfuscating the RSA private key
Date: 22 Jun 2000 00:58:20 GMT
In article <8irha1$[EMAIL PROTECTED]>,
Dave Ahn <[EMAIL PROTECTED]> wrote:
>Our group has client-server programs that are open sourced for peer review.
>We distribute these programs in source and precompiled binary form. Users
>download the client binary and use it to connect to servers over the
>Internet.
>
>We wish to ensure that the users of the client software are using the
>official precompiled binary as opposed to a custom-compiled version based
>on the public source code. We do not trust the client users. But we do
>trust the server administrator. We also trust the network connection
>between the client and the server (i.e. ignore eavesdropping or man-in-middle
>attacks).
>
>We address this authentication problem using RSA. A keypair is generated
>for each client on each platform. The public key is published and added
>to the server key ring. The private key is embedded into the client binary
>during the compile process. To validate the client, the server uses a typical
>challenge-response scenario by encrypting a random number with the public
>key which only the client can decrypt and send back.
This doesn't make any sense. If you think the client users are going
to try to hack you, then either
1) you think they're sophisticated and willing to spend time, in
which case your RSA scheme is no good and not worth doing, or else
2) you think they're not going to go to a lot of hassle, in which case
your RSA scheme is overkill and not worth doing.
Either way, it's not worth doing.
If you're trying to stop sophisticated attackers and you -really- need
a client application distributed in source form, all you can really do
is put it into a sealed processor such as a smart card or Dallas iButton
at the low end, or something like an IBM 4758 at the high end.
If you're trying to slow down unsophisticated attackers, it should be
enough to just put the application into a signed .cab or .jar file
(assuming it's a browser extension) and let the browser security
system take care of it. Or, use a secret-key authentication with a
key for each client.
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: I need help to find reliable external MIME decoding utility,
Date: Wed, 21 Jun 2000 21:08:06 -0400
I need help to find reliable external MIME decoding utility,
decode MIME from file ...
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Comments please: A protocol for Digital voting
Date: Thu, 22 Jun 2000 01:27:29 GMT
In article <[EMAIL PROTECTED]>,
Roadkill <[EMAIL PROTECTED]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
>
> zzapzing wrote:
> <snip>
>
> > I have also noticed that this protocol is unnecessarily
> > complex in at least one aspect. That is, the multiple
> > validations that are done by a long string of remailers, in
> > order to eventually get I validated. Let me explain a simpler
> > way to do this.
>
> I figured that there should be a few bits reserved for a checksum in I
> because otherwise check(v(I)) would just result in unverifyable random
> bits. It isn't so that each remailer should validate v(e[1..n](I)),
and
> they couldn't. Still after stripping of one layer of encryption, the
> package would change so that it couldn't be traces by Echelon e.g.
> (which is a good thing).
Oh, yeah. That is kind of important, isn't it?
otherwise anyone could just make up a false
"v(I)" and backencrypt to an I. Good thing you
pointed that out.
>
> > First of all, each voter puts his individual string, I into
> > an electronic envelope. Let e(I) denote this. This is the
> > same as your protocol. Next, the voter sends, through
> > anonymous broadcast, the pair V,e(I) to the validator. the
> > validator checks V against his list and then validates e(I)
> > inside its electronic envelope. Call the result of this
> > v(e(I)). the validator publishes a list of all the values of
> > V along with their corresponding values of v(e(I)). The
> > voters find their V values in this list and read off their
> > corresponding v(e(I)) value, from which they calculate their
> > individual value of v(I) (by removing the elctronic envelope).
> > The voters send in their votes along with their v(I). I
> > believe this would result in less traffic and computation but
> > have the same security features as the procedure you proposed.
>
> I don't see why e(I) should be broadcasted anonymously. The resulting
> v(I) should however be send through serveral remailer chains. The
beauty
> of your modification is that now v(I) (AKA your vote with signature)
can
> be send through several different chains of remailers. So if one
> remailer goes down and stays down, you can still send your vote to the
> tallier through a different chain not including the downed remailer.
> Broadcasting also takes up a lot of bandwide I think and tends to have
> the anonymous broadcaster somewhere in the middle (which is bad for
> anonymity).
I think you're right. the first anonymous broadcast
is not needed. So only the vote needs to be broadcast
anonymously,
--
So glad deja is healthy again.
Hope it will last. Hated remarq.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Weight of Digital Signatures
Date: Thu, 22 Jun 2000 01:47:44 GMT
On Wed, 21 Jun 2000 20:04:08 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>Lyalc wrote:
>> In this scenario, the technology of a PIn is coupled with the ATM
>> technology, which is coupled with DES encryption, DES key management, and
>> PIN issuing technologies, finally coupled to an ATM printed receipt as a
>> backup transaction record.
>> take the receipt to your bank, and ask them the verify the transaction
>> record is correct from start to finish (ie the processing from ATM to
>> account ).
>> lyal
>Do you actually obtain such printed records that can be proved to
>be genuine?
Although it is true that the things you get from a bank machine don't
seem to be terribly well protected against forgery, nor do they have
some cryptographic signature on them,
they don't stand alone. They have a date and time printed on them,
plus the number of the machine from which they came.
So, theoretically, the bank could confirm that the slip records a
transaction that actually took place - from its own records - and sign
or stamp the paper. I don't know of any bank that provides such a
service, but that's beside the point.
The difficulty with digital cash is if it is to be anonymous, or if it
is to be able to be processed off-line. Otherwise, there is no
problem, which is why we already have credit cards.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.math
Subject: Re: AWFUL PUN
Date: Thu, 22 Jun 2000 01:43:39 GMT
On Wed, 21 Jun 2000 18:01:04 GMT, [EMAIL PROTECTED] (Mike Andrews)
wrote, in part:
>I inherited one from my
>supervisor (I'd rather have him than the book)
You mean that literally, then. My condolences, however belated.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Andrew Bortz <[EMAIL PROTECTED]>
Subject: Re: MD5 Expansion
Date: Wed, 21 Jun 2000 22:34:07 -0400
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> >>I little bit of miscommunication here. I meant a linear
> > transform of
> >>the message, not the hash, so it looks something like this:
> >>
> >>A = H(m) B = H(L(m))
> >>
> >>Final hash = AB
> >>
> >>Are you saying this is not secure as well? I'm interested, if
> > it isn't
> >>secure, how one might break it. Just from the outside (amateur)
> > view,
> >>it seems as though L(m) could be something as simple as
> > flipping the
> >>first bit of the message and this would still be effective
> > because the
> >>avalanche effect of the hash would amplify that difference
> > tremendously.
> >
> > Well we can find collisions in A such that
> >
> > A = H(m) = H(m') for m != m'
> >
> > Then we just need to find collision in B such that
> >
> > B = H(L(A) || m) == H(L(A) || M')
> >
> > The first has a probability of 2^-64 of happening before the bday
> > threshold, the second has an equal prob... together it is
> > 2^-65... that's if I get this right, ... err.. I am tired...
>
> Umm, you still haven't read what he said right. B=H(L(m)), notH(L(A)||m).
> And in any case, two events with probability
> 2^-64 combine to give a probability of 2^-128, not 2^-65.
>
> However, in Applied Cryptography, Bruce Schneier describes a method for
> doing this (pages 430-431), which is more complicated (involving
> concatenating the message with its hash), which he says various people
> have
> 'serious reservations about'. If that system is thought untrustworty, this
> system
> is likely to be too.
>
>
> ben
>
>
Yes, I read that too... If none of these methods work, then what options
do I have for a secure 256-bit hash? Yes, I know that's overly paranoid,
but it just seems to be that 2^64 work to find collisions or even 2^80
is not enough of a security margin, especially with the small amount of
extra computation for a 256-bit hash.
Andrew
------------------------------
From: Andrew Bortz <[EMAIL PROTECTED]>
Subject: Re: Missing Info in the crypto-gram of MR BS
Date: Wed, 21 Jun 2000 22:45:34 -0400
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
>
> I don't often go to the BS site about encryption
> because maybe its his physics trainning. I have
> a Master Degree in Electronic Engineering Control Theory
> and we seldom see eye to eye.
>
> Like many of his Crypt Grams this one starts very proper
> and talks about Claude Shannon who in the 40's came up
> with the concept called "unicity distance" He states that
> English would require about 8.2 bytes of data for DES type of
> cypher. Claude Shannon is the kind of genuis that Mr BS
> is not. He goes on to state for Des only 2 cipher text blocks
> need to be decoded. If the first block looks like English
> and the second block also looks like English "you've found
> the correct key". At this point he goes to state that
> compression increases the "unity distance". It is at this
> point that he does those wishing to understand the science
> of encryption a disservice and the NSA would give him bonus
> points. The fact is most "compression does not really add
> to the unity distance".
> What either Mr BS fails to understand or is misleading people
> about. Is that most compression help the attacker and his
> statement about compression increasing the unity distaance
> and the statement about a random file haveing infinte unicity
> distance is quite false for most compression schemes.
> The main thing hidden from the user is for the compression
> to actually increase the unity distance not only does the file
> have to compress but the compression routines used must be
> of the following form. for any file that is the result of
> a "wrong key" that resulting file must be such that when it
> is uncompressed to a test file. That file must compress back
> exactly to the resulting file. This eliminates many canditate
> files. It can eliminate so many files that the NSA does not
> even need to know what kind of file you are compressing since
> contrary to the statement that a random file has infinite unicity
> they could in fact pretend they have zero knowledge about
> the file. And only search for one by whatever means at there
> disposal to find one that when uncompressed and compressed back
> comes back to the test file. Since for most compression schemes
> for files of most lengths there would only be one solution.
> This to me means that the unicity distance is far form infinity
> and that one should be very careful about what compression one
> uses when encrypting data since there is lot that Mr BS chose
> to leave out of his so called crypt gram.
>
> check out http://members.xoom.com/ecil/compress.htm
> at hss pointers to Tim's and Matt's site they seem
> to have more of an understanding about what this kind
> of compression is than anything you would find at the
> BS site.
At some level there will be identifying information that an automated
program can use to distinguish a correct decryption from an incorrect
one. And most compression algorithms are defined at a file format level,
leaving the implementation up to the programmer. With algorithms that
rely on searching, there will always be more than one way to compress a
file.
Andrew
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Crossposted-To: comp.theory,sci.math
Subject: Re: Linear Feedback Shift Register *with* lock-up?
Date: Wed, 21 Jun 2000 21:37:54 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> On 20 Jun 2000 18:19:09 GMT, [EMAIL PROTECTED] (Ponder)
> wrote, in part:
>
> >What I'm really looking for, though, is an LFSR that counts
> >through 2^N values and then *does* get stuck in the last state.
>
> An LFSR can't do that. But if you use nonlinear feedback, it is quite
> possible.
>
> John Savard (teneerf <-)
> http://www.ecn.ab.ca/~jsavard/
If you are hardwiring the thing and have complementary outputs for each
gate, use diode logic to detect an all hi condition, selecting the
appropriate normal or inverse output for each gate. I used this sort of
thing to make multi-frequency dividers out of plain ttl parts some 20
years ago, cheap and effective. When all hi is detected, the common side
of all the diodes should be monitored as it traverses to a high logic
condition, shich you can clock in out of phase with the rest of the
circuit.
Boy, I have a strong desire to break out the chips, do circuit boards, but
that is physically out of the question for now. It's summertime; never
solder in shorts.
--
Some Turkeys can fly, for short distances. If you are to depend on
birds for communication, if it's with turkeys, consider the
discussions that might occur while feasting on one.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Date: 22 Jun 2000 04:00:13 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
> [snip discussion of what "provable" means - or should mean]
> : I suggest "statistically secure."
> That's not going to appeal very much to managers or marketing.
I saw the flap which IBM PR made over the Ajtai-Dwork cryptosystem
being "provably secure." Other than that, where has this kind of "provable
security" come up in PR or marketing or management decisions?
I do not mean snake oil claims which cannot be backed up, but instead I am
interested in how the academic concept of "provable security" has been
interpreted in practice.
thanks
-dmolnar
------------------------------
From: [EMAIL PROTECTED] (S. T. L.)
Subject: Re: Try it.
Date: 22 Jun 2000 04:35:10 GMT
NDA to _purchase_ an encryption system? Ha ha ha.
-*---*-------
S.T.L. My Quotes Page * http://quote.cjb.net * leads to my NEW site.
Pages up: 395 Quotes, 31 reviews of 165 science books, and a review of
the Foundation series. Newest Page: S.T.L.'s Fighter Jet Paper Airplane!
------------------------------
From: TAY YUE WENG <[EMAIL PROTECTED]>
Subject: RE: Help - IEEE P1363 needed!
Date: Thu, 22 Jun 2000 12:40:01 +0800
Dear people,
I need a copy of IEEE P1363(standard specifications of public key
cryptography). Can somebody who have it email a copy to me? Thanks.
Tay Yue Weng
------------------------------
** 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
******************************
