Cryptography-Digest Digest #343, Volume #13 Sat, 16 Dec 00 10:13:01 EST
Contents:
Re: How does public key crytography work, mathematically? (Simon Johnson)
Re: Nonlinear Diffusion with S-Boxes? (Simon Johnson)
Re: How does public key crytography work, mathematically? (John Savard)
Re: Securing credit card numbers (Simon Johnson)
Re: Q: Result of an old thread? (Mok-Kong Shen)
Re: Q: Result of an old thread? (Mok-Kong Shen)
Encryption detail added to cipher page (Gianna Stefani)
Nonlinearity question (Benjamin Goldberg)
Re: NT4 Password ("Mike The Man")
does CA need the proof of acceptance of key binding ? ([EMAIL PROTECTED])
Re: Unguessable sequence of unique integers? (Mok-Kong Shen)
Re: Nonlinearity question (Mok-Kong Shen)
----------------------------------------------------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: How does public key crytography work, mathematically?
Date: Sat, 16 Dec 2000 11:42:13 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> I purchased applied cryptography, and I've been reading it thoroughly,
> and while doing so, I've pondered the creation and programming/math
> involved in encryption. Symmetrical keys make perfect sense to me.
If
> f(x) = character * key simply solve for key. But I don't understand
how
> there can be a public key for encrypting and private key for
decrypting
> that both generate non-gibberish.
>
> To acheive this, I am assuming that the encryption/decryption
algorithms
> are different where the key is applied. Applied Cryptography
suggests to
> assume that the source of your program is available, so wouldn't
someone
> simply be able to look at your two equations and derive one key from
the
> other? That can't be right though... How does it work?
>
What we do is we take a problem that fundementally hard, say factoring.
We then compute the public function, F(X). We therefore compute G(x)
such F(x) * G(x) = x is true. The trick is, to base the derivation of g
(x) from f(x) on knowing the solution to the difficult problem. Thus,
an attacker would therefore have to find the solution to the problem to
work out the relationship between both keys.
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Nonlinear Diffusion with S-Boxes?
Date: Sat, 16 Dec 2000 12:06:09 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>
> Hello!
>
> Bet this is old hat to many here, but I only had this realisation a
few
> days ago (in another discussion).
>
> I was wondering on doing bits of diffusion using nonlinear S-boxes in
> the following way:
>
> a0, a1: Initial words (all words the same size)
> b0, b1: Final words
> t0, t1: Temporary words
> S-box: A wordsize by wordsize S-box
>
> t0 = a0 xor a1
> b0 = a0 xor S-box[t0]
> b1 = a1 xor S-box[t0]
>
> Deriving the inverse:
>
> t1 = b0 xor b1
> = a0 xor S-box[t0] xor a1 xor S-box[t0]
> = a0 xor a1
> = t0
> That's t0 recovered...
>
> c0 = b0 xor S-box[t0]
> = a0 xor S-box[t0] xor S-box[t0]
> = a0
> That's a0 recovered, and a1 can be recovered in the same way.
>
> An inverse of the S-box isn't needed, so the S-box doesn't need to be
> bijective (though I can imagine a nonbijective (unijective?) S-box
would
> reduce diffusion).
>
> What struck me as neat about this is that it can combine nonlinearity
> with diffusion, and it's an involution (it is it's own inverse).
>
> Thinking about it further, I ended up with an idea of a block cipher
> round using this. It exclusively uses one function:
>
> f( a0, a1 ) = S-box[ a0 xor a1 ]
>
> With a round key the same size as the block, and the block arranged
as a
> two dimensional array of words with two rows (and the key likewise, if
> you like):
>
> w0 w1 w2 w3 w4 w5 w6 w7
> w8 w9 wA wB wC wD wE wF
>
> (16 words for this example.)
>
> 1. Apply function f to corresponding block and key words, putting the
> results in the block:
>
> w0' = f( w0, k0 ) = S-box[ w0 xor k0 ]
>
> (Nothing new there!)
>
> 2. Apply function f to the words of each column of the block, putting
> the results in a temporary row (the same size as a block row):
>
> t4 = f( w4, wC )
>
> 3. Apply function f to the temporary row and the block's top row,
> putting the results in the top row:
>
> w3 = f( w3, t3 )
>
> 4. And again, but with the bottom row of the block:
>
> wB = f( wB, t3 )
>
> That's key addition, nonlinear word substitution, and nonlinear word
> pair diffusion done using just one function! (Of course, transposing
> the words between such rounds would obviously be necessary to get the
> whole block to diffuse (hypercubic? I like hypercubes, they're
easy).)
>
> Anyway, any thoughts? Comments? Confirmation that this is indeed old
> hat? Worth using as part of a block cipher? Fatally flawed from the
> outset?
>
> Simon
Clearly, this construction is based on the s-box used. If this s-box is
weak your whole set of functions is. I can't really asses the rest of
it (insuffient skill ;) what i would suggest now, is that you create a
cipher based on these techinques and see how it holds up...
Its certainly curious :)
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: How does public key crytography work, mathematically?
Date: Sat, 16 Dec 2000 11:30:56 GMT
On Sat, 16 Dec 2000 04:06:04 -0600, "lowtus" <[EMAIL PROTECTED]>
wrote, in part:
>To acheive this, I am assuming that the encryption/decryption algorithms
>are different where the key is applied.
Sometimes that is true, sometimes not.
RSA, for example, uses the same algorithm to encrypt and decrypt, but
it uses a different key for each operation.
The reason it can work is because knowing the encryption key isn't
enough to determine what the decryption key is.
Only if you know some secret information (the two individual primes
whose _product_ is given out publicly as the modulus) can you produce
_both_ a public key and a private key to work under that modulus.
Essentially, a public-key algorithm is a method of encryption that
looks like a hash function. Given inputs, it produces outputs that
seem random, with no way to go back from the output to the input.
But the method of encryption has a "trick" to it, and the intended
recipient of the messages, who set up the arrangement for encryption,
knows the trick. So the recipient, but only the recipient, knows how
to go back from the output to the input.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Securing credit card numbers
Date: Sat, 16 Dec 2000 12:25:30 GMT
In article <91dufc$ghd$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hi, I am working on an e-commerce site and I�m facing the problem of
> storing credit card numbers securely on our database.
> I have been researching for a solution for the last few weeks however
I
> still don't have a clear approach.
> I would appreciate if you can give me a hand on the securing process.
>
> The goal
> ======
> - Credit card numbers must be stored encrypted on the database.
> - For statistical analysis and fraud detection we need the encrypted
> card number to be unique, I mean that the encrypted string for one
card
> is the same in all cases �this means that we cannot use random salt
> values to help the encryption-.
>
> Card number problems
> ================
> The primary problem is that credit card numbers are not very long, and
> are quite predictable. They use a 16-digit number for the card. The
> first 4 digit is the bank identifier and the next 12 are a pseudo
> random number. Considering about 300 major banks, we have about 300 x
> 10^12 possibilities. We can reduce, even more, the space of
> possibilities because these 12 digits are not really random, they
> follow a standard, and can be generated with a variety of algorithms.
> So because the space of possibilities is too small, will it be easier
> to break any encryption algorithm?
>
> Also, if an attacker breaks into the system, he can generate all
> possible credit cards for a big bank, encrypt them using our
encryption
> program, and then compare the result with the ones on the database.
> Then if he has a match he will have a valid number with all the
> cardholder information.
> We could encrypt the rest of the cardholder information, but since
this
> is frequently used, we would like to avoid it.
>
> Alternatives
> =========
> - Use 3DES to encrypt the credit card number.
> - Use a one way hash to generate the unique number.
>
> Questions
> =======
> - Given that the possible Credit Card numbers are only around 300 x
> 10^12, is it easier to break 3DES and find the key? If so, is it true
> that adding some random data to the card number will avoid this
> weakness?
No, 3-des requires roughly 10^50 key tests to be broken by brute-force
> - If an attacker knows the pair plain text, ciphered data, lets say a
> 100 pairs, would be easier for him to find the key? What about if he
> has a million pairs?
No, millions of trillions of pairs are required to solve 3-DES.
> - Using a one way hash could lead the attacker to find a valid credit
> card number. Any idea how to avoid this, and generate a unique
> identifier for the credit card number?
Use a keyed hashing algorithm, then only the identified personel can
determine the validity of a credit card. A complexity theoretic
construction can be utilised for this purpose:
p = large prime.
k = any number below p, but p=! 0 or 1, this is the key.
Hash = (Credit-card number)^k mod p.
The security of this scheme is dependant on computing the discrete
logrithm to find k, this is a difficult problem if p is large enough.
Hope this solves the problem,
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Result of an old thread?
Date: Sat, 16 Dec 2000 13:57:25 +0100
Bryan Olson wrote:
>
> Mok-Kong Shen wrote:
> > Bryan Olson wrote:
> > > There's the problem that S is singular, so AS will
> > > also be singular. While you can't get an inverse
> > > and find a unique solution for B, you can set up the
> > > linear equations to solve for B, and use _any_ of the
> > > non-singular solutions.
> >
> > Could you elaborate a bit, perhaps with a mini-example?
>
> You have two square matrices, call them AS and ASB.
>
> Solve for B in AS * B = ASB
>
> If you don't know how, take the columns of ASB one at a time,
> and solve for the columns of B one at a time. If you don't
> know how, read chapter one of an introduction to linear
> algebra. You'll find small examples there too.
>
> When the solution allows arbitrary parameters, set them
> arbitrarily, and if the resulting array is singular, set them
> differently. Now you have a B that will work in Best's
> solution for S.
Since AS is singular, B is not uniquely determined from
the equation AS * B = ASB. Could any solution, say B',
which is not identical to Bob's original matrix B, work?
Why? And would such a B' be invertible? I suppose the
matter is not as simple as you depicted, though shouldn't
be very involved on the other hand.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Result of an old thread?
Date: Sat, 16 Dec 2000 13:58:20 +0100
Walter Hofmann wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> >Quite a time ago someone posted a scheme of transmission of
> >message without using a shared secret key as follows (all
> >matrices are of the same size):
> >
> >The message is in a singular matrix S (e.g. one with a zero
> >column). Alice chooses an arbitrary non-singluar matrix A
> >and sends AS to Bob. Bob chooses an arbitrary non-singular
> >matrix B and sends ASB to Alice. Alice multiplies it with
> >A^(-1) and sends SB to Bob, who can multiply it with B^(-1)
> >to obtain S.
>
> The non-singular matricies are dense in the space of all matricies.
>
> So you can change the coefficiants of AS by a sufficiently small
> epsilon>0 to get an invertible matrix, then you can calculate (AS')^-1.
> Go on to calculate B'=(AS')^-1.ASB then S(epsilon)=SB.B'^-1
>
> In the limit epsilon->0 the matrix S(epsilon) will converge to S as all
> operations involved are continuous.
>
> Given that S is most likely from a discrete subset of the matrix space
> using a sufficiently small but finite epsilon will break the code
> without actually doing the limit.
I doubt that your procedure works. The numerical mathematicians
try hard to deal with the nearly-singular matrices through
improving conditions etc. In the vicinity of a singular
matrix, you need increasingly high precision to invert.
In the limit, namely the true singular one, there is
no inverse. Look from another standpoint: If your technique
works, then one can 'define' an inverse for any singular
matrix (to work in any given situations, i.e. given set of
equations involving singular matrices).
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Gianna Stefani)
Subject: Encryption detail added to cipher page
Date: Sat, 16 Dec 2000 13:31:27 GMT
Xi has now added encryption details, and some clues, to its cipher
challenge page
http://www.xarabungha.btinternet.co.uk/xicrypt/xichallenge.htm
All attacks welcomed I think . . .
--
Regards,
Gianna
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Nonlinearity question
Date: Sat, 16 Dec 2000 13:48:21 GMT
It's known that the Rijndael/AES sboxes have good nonlinearity
properties. The operations used to create them are fast enough that if
RAM is in short suply, we don't need to actually use lookup tables, but
can instead compute the substitution using just the poly, more or less.
I am wondering, is it possible to make a transform, similar to how AES
makes its sboxes, using 128 bit, instead of 8 bit values?
You'd have to find an appropriate order 128 primitive polynomial, and
you'd need to change the affine function, but it wouldn't be too
difficult to do.
If this one step has good enough nonlinearity properties, then the only
other thing we need for our round function is a key add step.
Does this step have any merit, or is it utterly stupid?
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: "Mike The Man" <[EMAIL PROTECTED]>
Subject: Re: NT4 Password
Date: Sat, 16 Dec 2000 15:03:52 +0100
Now it's working!
It was right all the time, only thing that needed correction was my eyes.
/Mike
David Hopwood skrev i meddelandet <[EMAIL PROTECTED]>...
>-----BEGIN PGP SIGNED MESSAGE-----
>
>Mike The Man wrote:
>> Could anyone explain to me how the clear-text password is encrypted in
NT.
>> I understand it's Unicoded and then hashed with MD4, but it doesn't work
>> with my MD4-app.
>> If the password is 'a', shouldn't the Unicode be '6000' in hex?
>
>It should be <61 00>. Have you tried the following example from section B.2
>of RFC 2433?
>
> "MyPw" => MD4(<4D 00 79 00 50 00 77 00>)
> => <FC 15 6A F7 ED CD 6C 0E DD E3 33 7D 42 7F 4E AC>
>
>> If I feed 6000 into the MD4 it doesn't come out the same way as in
>> L0phtcrack?
>
>L0phtcrack is open-source, isn't it? In that case if you still have a
>problem, look at its implementation.
>
>- --
>David Hopwood <[EMAIL PROTECTED]>
>
>Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
>RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
>Nothing in this message is intended to be legally binding. If I revoke a
>public key but refuse to specify why, it is because the private key has
been
>seized under the Regulation of Investigatory Powers Act; see
www.fipr.org/rip
>
>
>-----BEGIN PGP SIGNATURE-----
>Version: 2.6.3i
>Charset: noconv
>
>iQEVAwUBOjsaxzkCAxeYt5gVAQGrAAgAmJyNQq4SW5mjgx8dOdVu2a8fGYZYHsRh
>JwvJ7hkVX8rlBOhXqwVEUch/zzTAfN4ZxrNnKlmfUqrHjzPBFXzDC+CHrjqgnuGF
>udc5heBm4UAQcNHxwDitsCdD8SEs1vMmLFMIG+XhPG8jCgW9TTQK3JF2bVNpt0SD
>4exRWLlU8EqAbLCru848IvNX+zvZlScPj9a57BZZW69iLezr+qTK2rYo4O+EE7jj
>U77VZpYyXuPXczRKB41zEkiYUEwKhF2L5vC9EgvknWSroaPihkRhGW7kyc8fkUKO
>JPp1loFDFXC7ywtqrP4d3Yyvc1tTw25hEfZguiNpfVlWpTgDn08stw==
>=dFpD
>-----END PGP SIGNATURE-----
------------------------------
From: [EMAIL PROTECTED]
Subject: does CA need the proof of acceptance of key binding ?
Date: Sat, 16 Dec 2000 14:27:45 GMT
when someone applies a digital certificate from a certificate authority
(CA), does the CA need the proof of acceptance for the key binding from
the applicant?
Thanks!
vincent
[EMAIL PROTECTED]
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Unguessable sequence of unique integers?
Date: Sat, 16 Dec 2000 15:49:48 +0100
Brian Gladman wrote:
>
> "Bryan Olson" <[EMAIL PROTECTED]> wrote:
> >
> > John Savard wrote:
> >
> > > Johan Hanson wrote:
> > > >I suppose I could do this
> > [generate unguessable 32-bit integers without repetition]
> > > > by using a simple counter
> > > >and encrypting the result with a symmetric algorithm.
> > >
> > > That generally would be believed to be the only safe way of doing
> > > this; however, the problem exists that if you use a block cipher with
> > > a 32-bit block, to guarantee uniqueness of the 32-bit units output, it
> > > is not believed that a block cipher with so short a block can be made
> > > secure.
> >
> > A 32-bit block cipher should be fine. The small-codebook
> > problem is the _only_ security issue that pushes us to
> > larger block sizes. That problem is irrelevant in this
> > case; what he wants is the permutation, not the cipher.
>
> Maybe I have not fully understood what is proposed but would there not be a
> danger that an adversary could obtain the full sequence from a small number
> of samples in such a situation?
>
> What I am thinking of is the proposed approach in which a 32-bit cipher is
> fed by a simple counter. In this case, if the cipher key was short, it
> would be possible to do an exhaustive key search by 'decrypting' two
> adjacent numbers to look for keys that resulted in original 32-bit values
> that differed by one. And if two blocks were not a good enough
> discriminant, additional blocks could be decrypted in those situations where
> trial decryptions gave adjacent values.
>
> Of course I don't have a threat model (criteria to clarify what the
> originator meant by 'unguessable') but I am assuming that being able to
> recreate the whole sequence given a small contiguous sub-sequence would be a
> problem.
>
> Hence while the cipher might have a short block length, the key length would
> need to be significantly longer. And here I admit that I have not given any
> thought to the consequences of using short block, long key ciphers in this
> application. Would this be adequately secure given threats of the above
> type (or others)?
If the block size is sufficient small, longer key would
barely help. This is clear from considering the limiting
case of one bit block. Whether 32 bit block with large
number of rounds and long keys suffices in respect of
security for the purpose of the original poster is certainly
a question that is difficult to answer objectively. However,
if one is not satisfied with the output of block cipher,
then the natural consequence, I suppose, is to post-process
it, which should lead to certain additional difficulty for
the opponent. Shuffling the output stream with a sufficiently
long buffer, e.g. Marsaglia's scheme, suggests itself for
this purpose.
M. K. Shen
================================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Nonlinearity question
Date: Sat, 16 Dec 2000 15:49:55 +0100
Benjamin Goldberg wrote:
>
> It's known that the Rijndael/AES sboxes have good nonlinearity
> properties. The operations used to create them are fast enough that if
> RAM is in short suply, we don't need to actually use lookup tables, but
> can instead compute the substitution using just the poly, more or less.
>
> I am wondering, is it possible to make a transform, similar to how AES
> makes its sboxes, using 128 bit, instead of 8 bit values?
>
> You'd have to find an appropriate order 128 primitive polynomial, and
> you'd need to change the affine function, but it wouldn't be too
> difficult to do.
>
> If this one step has good enough nonlinearity properties, then the only
> other thing we need for our round function is a key add step.
>
> Does this step have any merit, or is it utterly stupid?
My knowledge is certainly very poor in this issue. However,
I guess the difficulty is a practical one, namely in
verifying that the S-box obtained is indeed good, which in
case of 128 bit could presumably take up big resources.
(Note that there are also other criteria than nonlinearity
that one would like to check.)
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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
