Cryptography-Digest Digest #424, Volume #12 Sat, 12 Aug 00 04:13:01 EDT
Contents:
Re: 1-time pad is not secure... ("Trevor L. Jackson, III")
Re: Software license software with PK ???? ("Benny Nissen")
Re: Preserving confidentiality while linking data? (Paul Rubin)
Re: OTP using BBS generator? (Mok-Kong Shen)
Re: OTP using BBS generator? ("Trevor L. Jackson, III")
Re: 1-time pad is not secure... (Eric Smith)
Re: OTP using BBS generator? (lcs Mixmaster Remailer)
Re: BBS and the lack of proof ("Trevor L. Jackson, III")
Re: 1-time pad is not secure... ("Joseph Ashwood")
Magma for cryptographic applications (Scott Contini)
Re: Preserving confidentiality while linking data? ("Joseph Ashwood")
Re: OTP using BBS generator? (Mok-Kong Shen)
Re: Magma for cryptographic applications (Mok-Kong Shen)
----------------------------------------------------------------------------
Date: Sat, 12 Aug 2000 01:46:33 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
"Douglas A. Gwyn" wrote:
> "Trevor L. Jackson, III" wrote:
> > The speed of propagation of electromagnetic energy is derived from
> > the two fundamental properties that describe electromagnetic fields
> > in space. IIRC its permeability and permittitivity. Are you
> > claiming the exact match of the speed of light and the limit
> > velocity for mass is a coincidence?
>
> No, it's certainly not a coincidence. In fact, if you consider
> photons to be "pure energy", i.e. no rest mass, it follows
> immediately from simple special relativity that they have to
> move with speed 1 (in natural units, c to the uninitiated) and
> furthermore must have that speed in every frame of reference.
This contradicts at least 6 sources wherein the inspiration for SR is given as
the invariance of c. It can hardly be a consequence of SR
>
>
> You're confusing what is fundamental and what is due merely
> to the history of the way physical understanding evolved.
> Vacuum permeability and permittivity are consequences of more
> fundamental phenomena.
Har. Further pontification would be a waste.
------------------------------
From: "Benny Nissen" <[EMAIL PROTECTED]>
Subject: Re: Software license software with PK ????
Date: Sat, 12 Aug 2000 05:47:15 GMT
It is possible to use a block ciphers in CFB mode and in this way work with
small amount of data to cipher, is this also possible with a PK cipher? - I
do not think so because you have the public/private key pair?
Benny
"Joseph Ashwood" <[EMAIL PROTECTED]> skrev i en meddelelse
news:#Np2Q1vAAHA.77@cpmsnbbsa08...
> But the length of the key determines the length of the block, so a
1024-bit
> key used for ElGamal will result in a 2000-bit encrypted block. Going even
> in to block ciphers, they require that the plaintext and ciphertext match
> certain block sizes, the same requirement holds with PK, just the sizes
are
> vastly larger, and so more noticable.
> Joe
>
> "Benny Nissen" <[EMAIL PROTECTED]> wrote in message
> news:82Ck5.12319$[EMAIL PROTECTED]...
> > I can not see why it is so that a public key algorithms may need to
> inflate
> > the size of the encrypted data. The strongness/security of the algorithm
> > must be based on the keys and not based on the length of the encrypted
> data.
> > Sorry this may be a stupid statement, but it seam to me that everybody
> look
> > in the same historical direction when implementing PK systems. (because
I
> am
> > unable to understand why the security of the algorithm is based on the
> > length of the encrypted data)
> >
> > Benny
>
>
>
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Preserving confidentiality while linking data?
Date: 12 Aug 2000 06:10:23 GMT
<[EMAIL PROTECTED]> wrote:
>The proposed approach is for the custodians of each data set to
>standardise the name, address and birthdate information according to
>an agreed protocol and then apply a standard one way hash to generate
>a unique id string. This id string then replaces the identifying
>information and the resulting de-identified unit record data can be
>linked with other similarly treated datasets for analysis.
>...
>The biggest source of failed linkages (ie no linkages even though the
>records are for the same person) or spurious linkages (linkages of
>records where they are actually for different people) will be problems
>with the address information - classic issues such as surnames
>changing with marriage, or different spellings. In this context the
>level of collisions in the hash (ie the same hash being produced from
>different inputs) is less likely to be an issue. Nevertheless it is
>worth minimising all sources of error, so a hash algorithm with
>minimal collisions is preferred. This should be seen in the context of
>records covering several million people. In the interests of economies
>of data handling, it is is also preferable to have a unique hash
>output that is as short as feasible.
>
>Can someone pls offer views as to the most approporiate has[h]
>algorithms?
Any hash algorithm will start seeing collisions once the number of
hash values reaches about sqrt(number of buckets). So for 10 million
people (2**23, say) you need about (10 million)**2 or 2**46 hash buckets.
Since you asked on a cryptography newsgroup, I'd say take your favorite
cryptographic hash function (MD5, SHA, or whatever) and truncate to, say,
64 bits. The resulting hash should be collision free, or close enough
for statistical purposes.
Depending on how hot this data is, maybe you should think about
encapsulating access to it in a secure piece of hardware, like an IBM
4758 crypto coprocessor (a PCI card costing about US$ 2000), or simply
a PC in a locked box if you don't think the researchers are going to
actively attack it. The secure box would answer statistical queries
about the data but wouldn't let out individual records even with the
internal fields hashed.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Sat, 12 Aug 2000 09:05:55 +0200
Benjamin Goldberg wrote:
>
> Your q isn't a Blum Integer, I don't think.
p=11=2*4+3; q=19=4*4+3; are both Blum integers. But my
example was no good. Here a (large) cycle of length 12:
(4, 16, 47, 119, 158, 93, 80, 130, 180, 5, 25, 207)
that gives rise to LBS of 001101000111 which seems to
indicate that there is substantial correlations. Note
however that a single example shows nothing definite
but leads merely to a conjecture. What one needs is some
amount of statistical tests on moduli that are bigger
but small enough to readily reveal salient statistical
features in the LSB, if there are indeed any.
M. K. Shen
------------------------------
Date: Sat, 12 Aug 2000 02:56:48 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Since you answered my first response with a clarification I'm returning to
your previous message to continue trying to interpret it.
lcs Mixmaster Remailer wrote:
> Terry Ritter writes:
>
> > It is *not* difficult to factor N . . . if we give a factor away. To
> > even attempt to assume that factoring is difficult *implies* that the
> > system be constructed in such a way as to not give away the secret.
> > And a proper construction happens with BB&S (as far as I know), only
> > when short cycles are excluded from use.
>
> You are mixing up two things: the difficulty of factoring, and the
> proper construction of the BBS RNG.
>
> Factoring difficulty depends only on the choice of the factors.
> Nothing you do after that will affect how hard it is to factor them.
>
> Consider two RSA creators. One chooses an RSA modulus and lets the
> attacker try to factor it. The other chooses an RSA modulus and then
> sends random large integers to the attacker, which the attacker may
> use to try to help him with factoring.
>
> It should be clear that the second system is not any weaker than the
> first one. It cannot leak any information about the RSA factors merely
> by sending random data. If it could, then the first system's attacker
> could achieve the same strength simply by using a source of random values
> to aid its efforts.
>
> In particular, there is no reason for the second system to filter or
> check the random values that it sends in any way. Since these values
> cannot aid the attacker, there is no reason to worry that one of them
> may happen to reveal a factor of the RSA modulus. If circumstances
> were such that that could happen, the attacker could find the same
> information himself by running his own RNG.
>
> The second system, without any checks, still has security equal to that
> of the first. Its security is that of factoring an RSA modulus.
>
> The second system is very similar to the BBS RNG, in that we choose an RSA
> modulus and then we choose an independent random value to be the seed.
> Terry Ritter is worried that this seed could lead to a short cycle.
> It has been proven that if this happens, the RSA modulus could be
> factored.
>
> Therefore, if checking seeds to avoid those that lead to factorization
> is necessary, as Terry Ritter argues, it follows that in the second
> system above, it is also necessary to check the random values which are
> sent in order to make sure that none of them could lead to factors.
> The information which is being revealed in each case as the same effect.
>
> Since we've already established that no such checking is necessary for the
> second RSA system, it follows that no such checking is necessary for BBS.
> BBS has all the security of the factoring problem, even when its seeds
> are not checked for any special properties. They only have to be randomly
> chosen. This is what is proven in BBS and the subsequent literature.
If I understand this correctly it amounts to a claim that a rational attacker
will not test for short cycles because the effort expended, when discounted by
the odds of success, does not get him any closer to cracking the system than
an equivalent amount of effort invested in a QR search. So those who advocate
checking for BBS short cycles do so out of superstition rather than
rationality. Is this a fair conclusion?
If so, it is similar to the reasons why one need not check for long stretches
of zeros in an OTP key. The odds of a significant fraction of the pad being
zero are so long that a sane attacker will not even inspect the ciphertext.
Of course an attacker who does notice a long stretch of intelligible cipher
text could argue that the odds against the text appearing accidentally are so
long that a null key pad is the simplest explanation.
Are all opponents sane?
------------------------------
From: Eric Smith <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Date: 12 Aug 2000 00:01:31 -0700
"Douglas A. Gwyn" wrote:
> No, it's certainly not a coincidence. In fact, if you consider
> photons to be "pure energy", i.e. no rest mass, it follows
> immediately from simple special relativity that they have to
> move with speed 1 (in natural units, c to the uninitiated) and
> furthermore must have that speed in every frame of reference.
"Trevor L. Jackson, III" <[EMAIL PROTECTED]> writes:
> This contradicts at least 6 sources wherein the inspiration for SR is
> given as the invariance of c. It can hardly be a consequence of SR
It is undoubtedly the case that the invariance of c was the inspiration
for the discovery of SR.
This does not, however, prove that SR is a consequence of the invariance
of c, nor does it prove that the invariance of c is a consequence of SR.
------------------------------
Date: 12 Aug 2000 07:20:02 -0000
From: lcs Mixmaster Remailer <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Benjamin Goldberg writes:
> Here's a BBS example of a short cycle: P is 23, Q is 47, X[0] is 46.
> X[i+1]=X[i]^2%PQ The short cycle that occurs is that for X[1] onward,
> the value is 1035. This means [assuming we use the lowest bit] that the
> keystream is all 1's, and the plaintext message can be seen by XORing 1
> with every bit. HE'S FOUND THE MESSAGE!
>
> Now suppose we're using RSA, with some P and Q and message M and
> encryption exponent E with the same properties as the BBS example: that
> means X[0]=M, X[i+1]=X[i]^E%(PQ) and we've somehow got a message that
> degenerates into a short cycle: all X[i] where i>=1 are the same as
> X[1]. We've encrypted M, which mean's we've got (and sent) X[1]. Our
> opponent might learn that X[2] and X[3] and X[4], etc happen to all be
> the same as X[1], but that tells him nothing about X[0]. HE DOESN'T
> HAVE THE MESSAGE!
If you can find short cycles, you can factor the value. You have
x^2 = y^2 mod n, so (x^2 - y^2) = 0 mod n, so (x-y)(x+y) is a multiple
of n, and if you take the gcd of x-y and/or x+y with n you have a good
chance of finding a factor.
In your example, you have that 46*46 = 1035*1035 = 1035, mod 1081.
Now we can do the gcd of the modulus with 1035-46. gcd(1081,989) = 23,
which is one of the factors! We've factored the modulus.
In general, if you can find short cycles, you can factor. Hence if you
believe factoring is hard, you believe that short cycles can't be found.
That's the bottom line.
------------------------------
Date: Sat, 12 Aug 2000 03:21:49 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: BBS and the lack of proof
Mark Wooding wrote:
> Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
>
> > I detect a difference between finding _a_ cycle and finding _the_
> > cycle (from which a given sequence was taken).
>
> Ahhh. I see! You're assuming an existing sequence supplied to the
> analyst. Right.
Yes.
>
>
> [Snip stuff I don't need to disagree with.]
>
> > However, if I happen to select one of the few short cycles then it
> > will be possible to predict the sequence by traversal. Thus if I
> > select a key and do not check it for shortness I'm vulnerable to a
> > prediction by traversal. Thus the opponent with not have to use a
> > technique that requires QR decidability.
>
> I think this is where we start disagreeing.
Then we have made progress in narrowing the issues.
>
>
> The point of the proof is not that you can't predict the generator
> without solving some instances of the QRP: it's that being able to
> predict the generator's output gives you an efficient[1] way to solve the
> QRP. If we assume that QRP is difficult, then predicting the generator
> must therefore also be difficult.
>
> [1] Well, expected polynomial time.
There appears to be a gap here. I'll try to approach from the other end.
Please indicate the point at which this sequence goes astray.
(1) A BBS generator can have a short (traversable) cycle.
(2) From (1): Given a short cycle, the output is predictable by traversal.
(3a) From (2): Given predictable output enciphered messages can be deciphered.
(3b) From (2): Given predictable output a QR solution is easy (as previously
defined).
(4) From (3b): short cycle imp-> predictable generator imp-> QR solution imp->
QR is not hard.
Bzzzzzt. That does not compute.
In your conclusion you used the opposite sequence, starting with QRP
difficulty as an assumption and concluding that predicting the generator is
hard. It appears that this conclusion contradicts item (2). Yet item (2) is
a simple deduction from item (1). So either a BBS generator cannot have short
cycles or the deduction from (1) to (2) is flawed. Which is it?
Item (3a) raises an issue worth resolution. If the defect in the above
sequence is after (3a) then it is not relevant to the security of message
encrypted with a BBS generator -- they aren't provably secure. If the defect
is at or before (3a) then the provable security is intact if the sequence
(1-4) is intact.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Date: Sat, 12 Aug 2000 00:12:18 -0500
I still don't think you are quite understanding. The
complete proof of One Time Pad does not bind it exclusively
to XOR, it is simply the only known algorithm that meets the
qualifications. You could use a *weakened* version of OTP
and use the pad as a key for 3DES, of course as I pointed
out before there exists an XOR pad that will convert it to
the plaintext. You so far have not even beginned to address
the issue that I have brought up now 3 times. If I encrypt a
plaintext P with a non-OTP key K using 3DES, there exists a
OTP that will create the plaintext from the provided
ciphertext. This is a very weakened version of OTP, so how
do you propose to break it? I've given the hand-waving that
makes it obvious that the pad exists, and I have stated,
although I haven't proven it is obvious that it is true,
that the pad contains much more regularity than a true OTP,
so it MUST be weakened. Enjoy, we know how to break it in
between 2^90 and 2^112.
Joe
<[EMAIL PROTECTED]> wrote in message
news:8n2567$f9p$[EMAIL PROTECTED]...
> Over 80 messages in this thread in less than 2 days. I'm
really
> stunned. Am I breaking a record?
For longest time? or most often? *grin*
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Magma for cryptographic applications
Date: 12 Aug 2000 07:27:06 GMT
Please have a look at the document "Magma for Cryptographic Applications"
which explains how the Magma computer algebra package can be useful to the
cryptography researcher, teacher, or student. It is available at:
http://www.maths.usyd.edu.au:8000/u/contini/documents/magmacrypto.ps.gz
(zipped, postscript, 90K)
A few of the highlights include:
- Verification of the Murphy/Robshaw observations on Rijndael's
linear diffusion matrix.
- Elliptic curve scalar multiply using the Frobenius map on
Koblitz curves.
- Fast point counting on elliptic curves.
- Efficient LLL, and using it to attack Merkle-Hellman knapsacks.
- Berlekamp-Massey algorithm.
- NTRU implementation.
- McEliece cryptosystem, and attacking it using message resend.
- Primality proving, and the option of printing out the
actual proof.
- Lots more.
I would appreciate any feedback.
For more information on Magma, please visit:
http://www.maths.usyd.edu.au:8000/u/magma/MagmaInfo.html
Thank you for your attention, and have a nice day.
Scott
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Preserving confidentiality while linking data?
Date: Sat, 12 Aug 2000 00:28:09 -0500
Well I know it's not exactly a normal method, but:
Have each subject generate a public key pair (LT), but keep
it secret
store a NULL key also (ST)
When new data is to be entered have the indidual:
Generate a new public key pair (ST2)
Sign ST with ST2
Sign ST2 with LT
Sign ST2 with ST
Write the data with ST2[public] and the signatures
Sign the data with ST2
discard ST
rename ST2 to ST
This will generate a a chain of signatures, where each key
signs both the next and the previous link, as well as being
directly linked to the Long term key LT. You can easily link
messages to each other (via the chain)knowledge of the long
term key cannot be found. However if an individual wants to
link themselves to a chain, they simply reveal their public
LT, and they are instantly linked to the entire chain, with
extremely small risk of having overlap of chains. In the
event that two entities choose the same key, they should
also store the private key of one of the STs, since they
already have the most recent it's a simple issue, that
allows the absolute linking of one of the STs to the LT.
Joe
<[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> Looking for methods to reliably link unit record personal
information
> in large administrative data sets without the identity of
the people
> being accessible to those using the linked data.
>
> The proposed approach is for the custodians of each data
set to
> standardise the name, address and birthdate information
according to
> an agreed protocol and then apply a standard one way hash
to generate
> a unique id string. This id string then replaces the
identifying
> information and the resulting de-identified unit record
data can be
> linked with other similarly treated datasets for analysis.
>
> The basis of the approach is that by standardising the
format of the
> input data and using a standard hash, then each custodian
will
> generate the same hash value given the same input data. To
avoid
> simple reverse lookups of has values to input identity an
additional
> step is proposed.
>
> A third party would take each dataset with hashed id and
link the
> records using the hash values, then strip the hash values
and assign a
> random number id before making the linked data available
for analysis
> back to both the data custodians and other researchers.
>
> There remains the problem that if the patterns of values
in the fields
> of a record in one data set are sufficiently unique, that
a data
> custodian will be able to use that pattern to match a
lined record
> back to the identifying information in their own data set
and so link
> an identity with the data from another custodian's
recordset. Apart
> from deliberately scrambling the data values (and so
making the linked
> data valueless for analysis) it is not clear how this can
be avoided
> other than by controls on the practices of data custodians
such as
> separating within data custodians systems the storage of
identifying
> data and the balance of data.
>
> The biggest source of failed linkages (ie no linkages even
though the
> records are for the same person) or spurious linkages
(linkages of
> records where they are actually for different people) will
be problems
> with the address information - classic issues such as
surnames
> changing with marriage, or different spellings. In this
context the
> level of collisions in the hash (ie the same hash being
produced from
> different inputs) is less likely to be an issue.
Nevertheless it is
> worth minimising all sources of error, so a hash algorithm
with
> minimal collisions is preferred. This should be seen in
the context of
> records covering several million people. In the interests
of economies
> of data handling, it is is also preferable to have a
unique hash
> output that is as short as feasible.
>
> Can someone pls offer views as to the most approporiate
has
> algorithms?
>
> Any other comments on the scheme also welcome.
>
>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Sat, 12 Aug 2000 09:47:34 +0200
"Trevor L. Jackson, III" wrote:
>
> If so, it is similar to the reasons why one need not check for long stretches
> of zeros in an OTP key. The odds of a significant fraction of the pad being
> zero are so long that a sane attacker will not even inspect the ciphertext.
> Of course an attacker who does notice a long stretch of intelligible cipher
> text could argue that the odds against the text appearing accidentally are so
> long that a null key pad is the simplest explanation.
>
> Are all opponents sane?
I am interested to see the result of discussions on the above
issue, though I have nothing to contribute myself. A question
that occurs to me though is: Is the science of crypto entirely
separated from psychology?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Magma for cryptographic applications
Date: Sat, 12 Aug 2000 09:51:41 +0200
Does Magma run under Windows? What is the license fee for
private use? Thanks.
M. K. Shen
------------------------------
** 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
******************************
