Cryptography-Digest Digest #76, Volume #12 Wed, 21 Jun 00 06:13:00 EDT
Contents:
Re: Cipher design a fading field? ("John A. Malley")
Re: Double Encryption Illegal? (jungle)
Re: Is this a HOAX or RSA is REALLY broken?!? (jungle)
Re: mother PRNG - input requested (Mack)
Re: mother PRNG - input requested (Mack)
Re: Weight of Digital Signatures ("matt")
Re: S/MIME + Netscape v47 serious problem in symmetric encryption ... (Will Price)
Re: Encryption on missing hard-drives (Mack)
Re: small subgroups in Blum Blum Shub (Klaus Pommerening)
Re: small subgroups in Blum Blum Shub (Klaus Pommerening)
Re: Comments/analysis requested (Runu Knips)
Re: small subgroups in Blum Blum Shub (Klaus Pommerening)
Re: Variability of chaining modes of block ciphers (Runu Knips)
Re: small subgroups in Blum Blum Shub (Mark Wooding)
Re: mother PRNG - input requested (Tim Tyler)
Re: small subgroups in Blum Blum Shub (Mark Wooding)
how to compare the securtity between ECC and RSA (kingtim)
----------------------------------------------------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Tue, 20 Jun 2000 22:28:03 -0700
John Savard wrote:
> >"John A. Malley" wrote:
> >> That immediately raises this question : Can we even encipher and (de)cipher
> >> plaintext strings of a Turing-unrecognized language?
>
>
> Thus, the question he (may have) *meant* to ask is: can one convey
> useful information of a general sort (not counting, say, some types of
> telemetry), which is complete in itself, not merely a cipher key for
> transmitting a later message - in a language that can't be recognized
> by a Turing machine.
>
> If that could be done, one's communications would be resistant to a
> certain category of cryptanalysis.
Mr. Savard, what an excellent question!
I never reached that question because I'm still puzzled by the act of
encipher/decipher a string from a Turing-unrecognized language.
Here's where I get stuck:
A language is Turing-recognizable if and only if it is generated by some
grammar.
Therefore a language that cannot be generated by a grammar is not
Turing-recognizable - it's Turing-unrecognizable.
Every Turing-computable function from strings to strings, or from
numbers to numbers, is grammatically computable, or generated by some
grammar. A cipher system (enciphering, deciphering) is a
Turing-computable function from strings to strings, or from numbers to
numbers. Therefore enciphering and deciphering are also grammatically
computable.
Assume a string from a Turing-unrecognizable language is enciphered.
Decipher the ciphertext back into plaintext. This is the same as using
a grammar (the deciphering) to generate the plaintext string. But, the
plaintext string is from a language that is Turing-unrecognizable. There
is no grammar that can generate plaintext strings of a
Turing-unrecognizable language. We get a contradiction.
So the assumption is wrong - we cannot encipher a string from a
Turing-unrecognizable language and decipher it afterwards.
Is this conclusion solid?
Can we even encipher and decipher plaintext strings of a
Turing-unrecognized language?
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: jungle <[EMAIL PROTECTED]>
Crossposted-To: comp.databases.oracle
Subject: Re: Double Encryption Illegal?
Date: Wed, 21 Jun 2000 02:36:54 -0400
do as you wish, don't believe all what is written ...
Crypto-Boy wrote:
>
> On page 10-10 and 10-14 of the Oracle Advanced Security Administrator's
> Guide (from release 8.1.6 December 1999), it says the following (in bold
> no less):
>
> "Warning: You can use SSL encryption in combination with another Oracle
> Advanced Security authentication method. When you do this, you must
> disable any non-SSL encryption to comply with government regulations
> prohibiting double encryption."
>
> Since when is it illegal to double encrypt in the US? I don't believe
> this is true.
it is not true ...
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: Re: Is this a HOAX or RSA is REALLY broken?!?
Date: Wed, 21 Jun 2000 02:40:29 -0400
almost all from www.sunday-times.co.uk is HOAX ...
Frank wrote:
> I appended to read to this article:
> http://www.sunday-times.co.uk/news/pages/tim/99/09/29/timintint02001.html?1341861
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: mother PRNG - input requested
Date: 21 Jun 2000 06:54:31 GMT
David S. Hansen wrote:
> What prng's do you fine people find to be excellent?
>=)
>
>*** David S. Hansen
>*** [EMAIL PROTECTED]
>*** http://www.haploid.com
Most numeric PRNGs are GFSRs or combinations
with MWC, AWC or SWB (all related). These generators
expose the state after one complete cycle through the
state (not the period) in combinations they are a little better.
The shrinking format is usually the example cited for
crypto purposes.
With only 32 bits as the initial seed this makes
it even worse.
I think Alleged RC4 is currently suitable for
most medium security usage.
For high security I would stay away from
stream ciphers all together.
Stream ciphers are easy to misuse.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: mother PRNG - input requested
Date: 21 Jun 2000 07:14:34 GMT
>Has anyone used/tinkered with George Marsaglia's MOTHER
>generator?
>
Which version of mother? the MTHR4-32? or the
RANMAR? or the Lagged Fibonacci (1279,418)?
MTHR4-32 and (1279,418) are about useless for
Crypto they provide the state in 4 words and 1279 words
respectively (Known plaintext attack).
I ranmar provides the state in 97 words (this is the one
I think you mean). It consist of (97,33) lagged Fibonacci
generator (seeded) and a subtraction recursion sequence(fixed).
Since the fixed part is invariant it provides no security.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: "matt" <[EMAIL PROTECTED]>
Subject: Re: Weight of Digital Signatures
Date: Wed, 21 Jun 2000 15:31:04 +0800
Was tom just quoting some imaginary bureaucrats, saying "ecc is
secure, no wait a minute, RSA is secure more" ??? Dunno, a thought,
Matt.
"Tom McCune" <[EMAIL PROTECTED]> wrote in message
news:pmR25.10526$[EMAIL PROTECTED]...
>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: RIPEMD160
>
> In article <[EMAIL PROTECTED]>, tomstd
> <[EMAIL PROTECTED]> wrote:
>
> >Using what protocol? I think ECC is secure, but no RSA is
> >secure... how about DSA? What hash? I like TIGER but I think
> >SHA-1 is secure or perhaps RIPEMD or HAVAL...What PRNG shall we
> >use...and so on...
> >
> >This is hardly a settled issue.
> >
> >Tom
>
> Tom, please explain what you mean about RSA not being secure. I
can't
> think of a more secure signature than a 2048 bit RSA key using
either
> RIPEMD-160 or SHA1 for the hash.
>
> -----BEGIN PGP SIGNATURE-----
> Version: PGP 6.5.2 -- QDPGP 2.61a
> Comment: My PGP Page & FAQ: http://www.McCune.cc/PGP.htm
>
> iQEUAwUBOUviFDYk/PXew/BzAQONUAfyA4H4a9D9PwHWPL0WsXNdFj/7u3mWv4UF
> autoLQKIbtLKJD1McfpoPAGy0NJJ+1T6ps357hzboUZNH4BelraCWf5zx/ekdYKK
> 1J9OQY/M6CMh5KqpFsjRPYXnmfP3GyKENjP8hJoEyM2DfURzqiVvWCZ9QPes3HEh
> aCi7UsYInwFzb6+pioKGZRI3/i8FnrBWOQwacIp095BeJkFH5LZ3yKlVHix5Hqdq
> ZZBKumgrVm984vT6SsBPa6t8ovxxJm0sZEjths5ChWznCqr1tdES0ZGdq9LY021s
> DF6tzpnBgCMrs3YGs15QLQ87klM3CMchPbCXUwwKrwCUotbDWkgp
> =S/aO
> -----END PGP SIGNATURE-----
------------------------------
From: Will Price <[EMAIL PROTECTED]>
Crossposted-To: comp.security.pgp.discuss
Subject: Re: S/MIME + Netscape v47 serious problem in symmetric encryption ...
Date: Wed, 21 Jun 2000 00:45:50 -0700
Reply-To: [EMAIL PROTECTED]
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
No, he's totally right.
S/MIME v1 (the only truly deployed version of S/MIME) is a 40 bit
MUST. Your confusion is based on the fact that while 40 bit is a
MUST, S/MIME v1 also supported higher bit lengths if you're lucky
enough to figure out how to make it happen. I guess you're one of the
lucky few.
jungle wrote:
>
> you are totally wrong ...
> with v1 I'm encrypting to 128 & 168 bits ...
>
> version has nothing to do with it ...
>
> Padgett 0sirius wrote:
> >
> > > Anyway, it would be interesting to find out why it keeps
> > > reporting how to find that it is reporting ONLY and not
> > > practically using only 40
> > >bits encryption ?
> >
> > Because it is S/MIME v2 which had as a MUST 40 bit symmetric.
> > OTOH S/MIME v3 (RFC 2630-2634) requires strong encryption
> > matching FIPS 140-1.
- --
Will Price, Director of Engineering
PGP Security, Inc.
a division of Network Associates, Inc.
=====BEGIN PGP SIGNATURE=====
Version: PGP 7.0 (Build 190 Beta)
iQA/AwUBOVByqay7FkvPc+xMEQKAMACeMGOD49Zz+dVcPHd1yWXO08+elbMAoJaE
x6KwbOQ5r4LqX8XTc+fIYizR
=n+uW
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Encryption on missing hard-drives
Date: 21 Jun 2000 07:46:37 GMT
Ok lets say the drives were encrypted
since the thief had access to the
drives it is also quite possible
he had access to the key.
This seems pretty obvious.
Of course what all of this means
either
a) some idiot misplaced the drives
and then hid them when the S***
hit the fan
or
b) some spy now has the
codes to the PAL for nuclear
weapons. or whatever was on
the disks. since the information
was only secret I doubt it was
that important
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Klaus Pommerening)
Subject: Re: small subgroups in Blum Blum Shub
Date: 21 Jun 2000 08:16:56 GMT
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?
--
Klaus Pommerening [http://www.Uni-Mainz.DE/~pommeren/]
Institut fuer Medizinische Statistik und Dokumentation
der Johannes-Gutenberg-Universitaet, D-55101 Mainz, Germany
------------------------------
From: [EMAIL PROTECTED] (Klaus Pommerening)
Subject: Re: small subgroups in Blum Blum Shub
Date: 21 Jun 2000 08:38:10 GMT
In <[EMAIL PROTECTED]> Terry Ritter wrote:
> I do have a different model, but it is not a model of computation. My
> model is what I perceive as the basis for the entire field of
> cryptography: The need to find a system which is secure against any
> possible attack.
>
Not even the OTP is secure against any possible attack
(replay attack, modification of known plaintext).
Real world systems are vulnerable by brute force attacks.
> 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?
> ... Special care must be
> taken to avoid the problem simply because the workers in that
> sub-field have not been sufficiently creative to find a new phrase for
> a new concept. I suggest "statistically secure."
>
Good point. And BBS without "bells and whistles" and big enough
module is statistically much more secure than any 128 bit
symmetric cipher, and is statistically as secure as BBS with
"bells and whistles" and a slighly shorter module. (Guess:
2 or 3 bits shorter.)
[Sure, we have no clue how difficult factoring really is.
But we also have no clue, for any symmetric cipher, how
difficult breaking really is.]
--
Klaus Pommerening [http://www.Uni-Mainz.DE/~pommeren/]
Institut fuer Medizinische Statistik und Dokumentation
der Johannes-Gutenberg-Universitaet, D-55101 Mainz, Germany
------------------------------
Date: Wed, 21 Jun 2000 10:41:14 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Comments/analysis requested
[EMAIL PROTECTED] wrote:
> I am very new to this stuff but I have run across the following
> encryption technique. I am curious as to how strong it is.
> Particularly if it is possible to take the encrypted text and the
> original text and derive the encrypted password.
If you want to discuss an algorithm, first translate it into
a readable form, such as C, Pascal, or mathematical pseudocode,
not in pseudoassembly where one has to first start tracking
which register contains which value.
------------------------------
From: [EMAIL PROTECTED] (Klaus Pommerening)
Subject: Re: small subgroups in Blum Blum Shub
Date: 21 Jun 2000 08:46:52 GMT
In <[EMAIL PROTECTED]> Terry Ritter wrote:
>
> ... Using the BB&S prescriptions gives us
> the ability to say that -- other than keyspace / brute force -- we
> know of no weakness that we have not stopped.
>
>
Factoring the modulus is a much stronger attack than brute
force.
--
Klaus Pommerening [http://www.Uni-Mainz.DE/~pommeren/]
Institut fuer Medizinische Statistik und Dokumentation
der Johannes-Gutenberg-Universitaet, D-55101 Mainz, Germany
------------------------------
Date: Wed, 21 Jun 2000 11:07:02 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Variability of chaining modes of block ciphers
Mok-Kong Shen wrote:
> Runu Knips wrote:
> > Mok-Kong Shen wrote:
> > > The most popular block chaining mode seems to be CBC.
> > > There is also PBC which chains with plaintext blocks.
> > > One can also accumulate the previous blocks for doing the
> > > chaining and use plaintext as well as ciphertext for
> > > chaining. (I used this in one of my own designs.) By
> > > combinatorics this gives 8 variants. Obviously one can
> > > also use modular addition instead of xor and do some
> > > random rotations if one likes. I think that the variability
> > > of chaining modes could be advantageousy exploited such
> > > that the actual chanining mode used in a message has to be
> > > guessed by the opponent, thus redering his task much more
> > > difficult.
> >
> > I don't like that. While ciphertexts have the known property
> > of having no statistical properties and depend upon all
> > texts before the actual one, XOR'ing with the previous
> > plaintext has no such property. Just think about the case
> > that the plaintext consists of nothing but zero. PBC is much
> > more like EBC than like CBC.
>
> Ciphertext is always available to opponent, so he knows what is
> to be xor-ed out. Plaintext is not always available. That I suppose
> can be an essential difference.
Again disagreed. If the attacker knows nothing but the ciphertext,
then any good cipher algorithm should withstand all attacks anyway,
except brute force attacks of course.
So the attacker always has to guess about the plaintext to attack
modern ciphers. And almost any plaintext has some kind of structure
which can be guessed. Too, if you know a in the the expression (a
xor b) = c, what properties can you get about b or c ? So what your
PBC actually does is doubling the block size to be attacked, which
is far worse than the effect of CBC.
Okay, you CAN add the previous plaintext, but the properties of
the previous ciphertext are IMHO far more important and valueable.
If at all, I would use some kind of register which always stores
the last plaintext sum, i.e. use a form such as:
R(x) is register value in step x (x in [0..n])
C(x) is ciphertext x (x in [0..n])
P(x) is plaintext x (x in [1..n])
IV is the initialization vector
Encrpytion:
R(0) := IV
R(n) := R(n-1) xor P(n)
C(0) := ENC(R(0))
C(n) := ENC(R(n))
Decryption:
R(0) := DEC(C(0))
R(n) := DEC(C(n))
P(n) := R(n) xor R(n-1)
This has some more of the good properties like CBC. However, in
a message of all zero, or all constant values, it still works
far worse than CBC.
> > And using a different chaining method than CBC might confuse
> > the opponent, but not much more than using a nonstandard
> > cipher algorithm, isn't it so ?
>
> But, in case you (like plenty of people) have only one single favourite
> algorithm, you can at least do something in that direction.
Yep, okay.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: small subgroups in Blum Blum Shub
Date: 21 Jun 2000 09:16:11 GMT
Bryan Olson <[EMAIL PROTECTED]> wrote:
> The 'bug' in Mark's proof was that in that line he should have said "x
> in Z_n*", not just "0 < x < n";
Yes, indeed. Whoops! ;-)
-- [mdw]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: mother PRNG - input requested
Reply-To: [EMAIL PROTECTED]
Date: Wed, 21 Jun 2000 09:11:37 GMT
Joseph Ashwood <[EMAIL PROTECTED]> wrote:
[Re: If seed is only 32-bit and your messages aren't long, does having
a PRNG period longer than 2^32 really gain anything?]
: Yes it does. It gains uncertainty. For example, if I have a pRNG with a
: cycle of 12, 8-bit values, say it outputs:
: 0123456789AB
: and another generator of cycle 6 with outputs
: 012345
: and a message of length 5, from the first generator I have the possibility
: of have the random values of
[snip]
: but with the second generator I have only
: 01234
: 12345
: 23450
: 34501
: 45012
: 50123
: Giving me much better odds if I assume that a 5 exists in the list (5/6
: versus 5/12). [...]
I think you're assuming something like the internal state is the size of
the seed - and that the entire internal state is output at each step.
This need not be the case - and obviously the former can't possibly be the
case if the generator has a seed of only 2^32 - yet offers some stupendous
period.
If seed is only 32-bit, you re-key for each message and your messages
aren't ever very long, having a minimum period much longer than 2^32
seems rather pointless.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ VIPAR GAMMA GUPPY.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: small subgroups in Blum Blum Shub
Date: 21 Jun 2000 09:40:07 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
> in sci.crypt [EMAIL PROTECTED] (Mark Wooding) wrote:
>
> >secure under exactly the same assumptions, in particular that
> >factoring is hard. The cycling behaviour in question contradicts the
> >assumption, but that doesn't invalidate the proof.
>
> I have no idea what that could possibly mean. If the assumption is
> contradicted, surely we cannot say the proof stands. Unless, of
> course, we see "proof" as a mere manipulation of symbols, as opposed
> to the correct conclusion.
It seems perfectly reasonable to me, as an ex-mathematician, to make
statements of the form `X implies Y', and to show, rigorously, why
they're true. The statement makes no assertions about whether the
hypothesis X is true in any particular circumstance, just that when it
*is* true, Y is necessarily a consequence.
In the particular case under discussion, the assumption X is that our
adversary cannot factor a given BBS modulus, and the consequence is that
the BBS generator with that modulus is unpredictable by that adversary.
There is a technique common in mathematics named `reductio ad
absurdum', or `proof by contradiction', where one assumes the converse
of what is intended to be proven, and deduces a result which contradicts
its hypothesis.
We can apply this technique to the current situation. Consider a Blum
integer n, and an adversary A who is unable to factor n. Then A cannot
find a cycle in the output of the BBS generator. We prove this by
contradiction by demonstrating that, if A finds a cycle, he can factor
n. Since the base we're working on states that A can't factor n,
something must have gone wrong. The only thing which might be wrong is
the assumption that A could find a short cycle. The result follows.
What the foregoing doesn't go into is that finding short cycles might be
a sensible way to go about factoring. This question is beyond my
abilities as a number theorist to answer, although I'm well aware that
the factoring experts are using a different technique -- the Generalized
Number Field Sieve -- rather than cycle-finding, and I can only conclude
that cycle-finding isn't a realistic factoring method.
-- [mdw]
------------------------------
From: kingtim <[EMAIL PROTECTED]>
Subject: how to compare the securtity between ECC and RSA
Date: Wed, 21 Jun 2000 17:44:27 +0800
I know that ECC is more secure than RSA. But I do not know how to do the
comparsion.
Thanks
king tim
thanks
------------------------------
** 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
******************************
