Cryptography-Digest Digest #465, Volume #13 Sat, 13 Jan 01 15:13:00 EST
Contents:
AIM encryption explained... but what doe sit mean? (Nemo psj)
Re: AIM encryption explained... but what doe sit mean? (Nemo psj)
Re: AIM encryption explained... but what doe sit mean? (Nemo psj)
Re: that security proof for ECDSA ?? (DJohn37050)
Re: AIM encryption explained... but what doe sit mean? (Nemo psj)
t�rk�e yaz��mak isteyen var m�? ("hasan")
Security proof (Benjamin Goldberg)
t�rk�e ([EMAIL PROTECTED])
Re: On cryptographic proofs and their (lack) of concreteness ("John A. Malley")
Re: Need of very simple algorithms? ("r.e.s.")
Challenge/response with MD5 (Ivan Skytte =?iso-8859-1?Q?J=F8rgensen?=)
Re: A Small Challnge (Steve Portly)
Re: Security proof (Benjamin Goldberg)
Re: On cryptographic proofs and their (lack) of concreteness (Simon Johnson)
The Word Problem and Group Isomorphism ("Ben Hopson")
Re: Challenge/response with MD5 (Roger Schlafly)
Big block DES construct. (Benjamin Goldberg)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Nemo psj)
Date: 13 Jan 2001 15:10:37 GMT
Subject: AIM encryption explained... but what doe sit mean?
Ok im trying to make an AIM client and it appears that the password has to be
"roasted" these are the instructions i'm given..
[Roasted Password: To avoid sending passwords in plaintext, but also avoiding
any kind of real encryption, passwords are exclusive ORed with the modulo byte
in the "roasting" string "Tic/Toc" converted to ASCII hex and prepended with an
"0x". Hence "password" becomes "0x2408105c23001130".
]
I've been playing around a bit and all I can think of is the string "Tic/Toc"
is conveted into ascii then xored with the ascii value of the password wich is
in thise case "password".
then the result is converted to hex so
the character "T" is the first character in "Tic/Toc" and character "p" is the
first character in "password"
firststep = asc("T")
secondstep = asc("p")
thirdstep = fiststep xor secondstep
fourthstep = hexit(chr(thirdstep))
final = fourthstep
where asc = a ASCII converted (character is converted to its integer value)
XOR is a XOR operator
chr is a character function taking an integer value from 0-255 and converting
it to its character eqiv.
hexit is a function that turns chareacetrs ito there integer eqiv and then
converts to the inntergers hex value.
Is this what all of you are seeing or do i need more sleep? :)
------------------------------
From: [EMAIL PROTECTED] (Nemo psj)
Date: 13 Jan 2001 15:12:38 GMT
Subject: Re: AIM encryption explained... but what doe sit mean?
I think I got it (in VB6)
ch1 = Asc("T")
ch2 = Asc("p")
ch3 = ch1 Xor ch2
ch4 = HexIt(Chr(ch3))
ch4 is the result or 24
------------------------------
From: [EMAIL PROTECTED] (Nemo psj)
Date: 13 Jan 2001 15:49:50 GMT
Subject: Re: AIM encryption explained... but what doe sit mean?
Yup I got it, for anyone who is interested, this is the technique in Visual
basic.
Inp = roast string or "Tic/Toc"
Inp2 = your password
Function XorIt(Inp, Inp2)
On Error GoTo 10
Dim x As Long
Dim y As Long
Dim buffer As String
Dim ch1
Dim ch2
Dim ch3
Dim big As Integer
If Len(Inp) < Len(Inp2) Then
big = 2
Else:
big = 1
End If
ch5 = "0x"
x = 1
y = 1
1:
ch1 = Asc(Mid(Inp, x, 1))
ch2 = Asc(Mid(Inp2, y, 1))
ch3 = ch1 Xor ch2
ch4 = HexIt(Chr(ch3))
ch4 = Format(ch4, "00")
ch5 = ch5 & ch4
10:
If big = 2 Then
If Len(ch5) > Val(Len(Inp2) * 2) Then _
XorIt = ch5: Exit Function
Else:
If Len(ch5) > Val(Len(Inp) * 2) Then _
XorIt = ch5: Exit Function
End If
x = Val(x) + 1
y = Val(y) + 1
If big <> 1 And x > Len(Inp) Then x = 1
If big <> 2 And y > Len(Inp2) Then y = 1
GoTo 1:
End Function
'#### Hex function
Function HexIt(Inp)
Dim x As Long
Dim length As Long
Dim buffer As String
length = Len(Inp)
For x = 1 To length
buffer = buffer & Hex(Asc(Mid(Inp, x, 1)))
Next x
HexIt = buffer
End Function
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 13 Jan 2001 16:03:52 GMT
Subject: Re: that security proof for ECDSA ??
Nope that is not it. The only reason I have not mentioned it is the author has
not yet publicly.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Nemo psj)
Date: 13 Jan 2001 16:06:12 GMT
Subject: Re: AIM encryption explained... but what doe sit mean?
Small revision
If big <> 1 And x > Len(Inp) Then x = 1
If big <> 2 And y > Len(Inp2) Then y = 1
should be
If x > Len(Inp) Then x = 1
If y > Len(Inp2) Then y = 1
now it wont error when the password is larger or smaller then the other.
------------------------------
From: "hasan" <[EMAIL PROTECTED]>
Subject: t�rk�e yaz��mak isteyen var m�?
Date: Sat, 13 Jan 2001 18:17:23 +0200
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Security proof
Date: Sat, 13 Jan 2001 16:46:25 GMT
I want to try and prove my hypercrypt cipher is a Strong Psuedo Random
Permutation under the assumption that the byte pair mixing function is
also an SPRP. To do this, I want to first attempt to show that a
reduced blocksize version is secure, and then show that expanding it
does not weaken its strength.
I informally define a Strong Psuedo Random Permutation as a block cipher
which is secure against an adaptive chosen plaintext and ciphertext
attack.
Notation:
Let M be an SPRP, and M(K) is a particular 2N bit permutation.
Let a, b, c, d each be 1/4 of the 4N bit plaintext.
Let w, x, y, z each be an N bit temp variable
Let e, f, g, h each be 1/4 of the 4N bit ciphertext.
The reduced size cipher is as follows:
(w, x) = M(K0)(a, b)
(y, z) = M(K1)(c, d)
(e, f) = M(K2)(w, y)
(g, h) = M(K3)(x, z)
How do I go about proving that this construct is an SPRP?
I think it can be done... but I'm not sure how.
I think I should mention that there are some *possible* weak keys under
certain improbable situations, and I'll list below the assumptions
needed to avoid them.
Here's a couple of examples:
Suppose there exists some Ka, Kb, such that
M(Ka)(x1, x2) = swap(M(Kb)(x1, x2))
Then, if K0=Ka, K1=Kb, K2=K3, a=c and b=d, then e=g and f=h
Suppose that there exists some Ka, Kb, Kc, Kd, such that
M(Ka)(x1, x2) = swap(M(Kb)(x1, x2))
M(Kc) = M(Ka)^(-1);
Then, if K0=Ka, K1=Kb, K2=K3=Kc, a=c, and b=d, then e=g=a, and f=h=b.
There might also be some way, with some keys, for the cipher to be an
involution, even with M as a Strong Psuedo Random Permutation -- but I
can't think how offhand.
To avoid problems like this, I'm going to make the following
assumptions:
1) There is no Ka, Kb such that M(Ka) = M(Kb)^-1
2) There is no Ka, Kb such that M(Ka) = swap(M(Kb))
3) There is no Ka, Kb such that for all x1, x2 M(Ka)(x1,x2)=M(Kb)(x2,x1)
4) All compositions of the above.
For the cipher to be decryptable, I'll also assume that for all keys K,
M(K)^-1 is as easily computable as M(K), but the function for M^-1 is
sufficiently different from M that (1) above holds.
If M is implemented as a fiestel with an even number of rounds, these
assumptions are all perfectly reasonable.
A way to make all of the above assumptions fail, is to say that M is a
fiestel with an x+1 bit key, and if the first bit is 0, encrypt with the
next x bits, and if the first bit is 1, decrypt with the next x bits. M
could still be an SPRP, but the assumptions (1)..(4) would not hold.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: [EMAIL PROTECTED]
Subject: t�rk�e
Date: Sat, 13 Jan 2001 16:55:51 GMT
t�rk�e yaz��mak iteyan var m�?
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: On cryptographic proofs and their (lack) of concreteness
Date: Sat, 13 Jan 2001 09:23:54 -0800
Simon Johnson wrote:
[snip]
>
> Yes, but what if the assumptions are wrong? The whole system of logic
> collapses.
> >
Suppose one builds a proof of cryptographic security upon assumptions as
Mr. Ashwood outlined at the start of this thread.
The assumptions are axioms, aren't they?
An axiom is a statement taken as "self-evident truth," by agreement,
among a group of people. Someone derives new statements from these
agreed-upon initial truths. Anyone in the group of people who agreed to
those axioms can examine the new statements and prove/disprove the truth
of a new statement with reference to those axioms. No one in the group
who agreed to those axioms can derive new statements that prove/disprove
the truth of the axioms.
So as Mr. Ashwood says, we can generate proofs of security based on
assumed truths (axioms). He provided a list of commonly agreed-upon
truths used in some situations
"The common assumptions are things like:
The RSA problem is hard
The Discrete Log problem is hard
SHA-1 acts as a random oracle"
Statements of cryptographic security derived from one set of axioms A
can not be directly compared to statements of cryptographic security
derived from a set of axioms B unless one can derive the "axioms" in one
set from the other set or one makes a third set of axioms C
incorporating both A and B and an axiom on the relationship between an
axiom in A and B to link them together.
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms?
Date: Sat, 13 Jan 2001 09:32:53 -0800
"Simon Johnson" wrote ...
[... re Solitaire encryption algorithm ...]
| Counterpane have apparently done some analysis on it,
| and said it is unlikely that there any short cycles
However,
http://www.counterpane.com/solitaire.html
also implies (incorrectly) that Solitaire
is reversible, so I think there's room for
doubt.
| and it holds up will against analysis, though i can't
| remember a link to this analysis.
For more than a year & a half, that site has
contained the following misleading statement:
"Security Analysis
There's quite a lot of it;
watch this space for details."
There are still no such details posted in that space.
If there is a detailed security analysis, it would be
nice to see them.
Maybe some embarassing flaws have been found?
--r.e.s.
------------------------------
From: Ivan Skytte =?iso-8859-1?Q?J=F8rgensen?=
<[EMAIL PROTECTED]>
Subject: Challenge/response with MD5
Date: Sat, 13 Jan 2001 18:37:50 +0100
I am developing a challenge/response authentication which authenticates
both ends.
Each end generates a random 32-byte challenge. The first 4 bytes are not
random - they are the current unix time (seconds since 1970). Otherwise
it is as random as you can get on a determistic machine.
Each end calculates the response by doing a MD5 over a shared secret and
the challenge, and then sends the response to the other end.
The stuff with the first 4 bytes was included to protect against replay
attacks - it can only be replayed for 3600 seconds with the current
implementation. After that the challenge is considered "too old".
Furthermore each "peer" can only try authentication once every 5
minutes.
It should be reasonable secure.
But I am bit worried about information about the shared secret being
leaked by the MD5 response, and that someone could send challenges and
receive the response and thereby detect some parts of the shared secret.
So I am considering changing response into two parts: yet another random
block and the MD5 of the shared secret, the random challenge and the
random block. Would this by more secure?
To elaborate:
receive challenge B1
generate random block B2
calculate MD5(shared_secret+B1+B2)
send MD5 + B2
(this is done by both ends)
Any opinions?
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: A Small Challnge
Date: Sat, 13 Jan 2001 12:38:44 -0500
Mok-Kong Shen wrote:
> rosi wrote:
> >
> [snip]
> > A QP key is an asymmetric cryptographic key with the
> > following special feature: from the viewpoint of the holder
> > of the secret decryption key, the QP encryption key (which
> > is made public) is not really made public. In other words,
> > the understanding and viewpoint of the encryption key is
> > different between the holder(s) of the secret decryption key
> > and any other in the general public which includes potential
> > attackers on the cryptographic scheme.
> >
> > So, a re-visit to the notion of 'asymmetry': in the public-
> > key scheme, there is a knowledge difference between the holder
> > of the secret decryption key and the general public on the
> > secret decryption key (i.e. the holder knows everything about
> > the decryption key but the general public do not), while in QP,
> > there is in addition a knowledge difference about the publicly
> > known encryption key as well.
>
> Very probably I misunderstood. Do you mean that the
> encryption key is not known to the general public but only
> to a selected subset of people, including the case of only
> one person (a determined single sender)? But then you have
> given up the benefit of PK and could use a symmetric
> encryption system just as well, don't you?
>
> M. K. Shen
You make a very good point, and my observation is probably redundant however
this sounds more like a multiple key symmetric system:? It would be trivial
to create an encryption method that decrypts to different messages depending
on which of the multiple secret keys are used. If such is the case perhaps
one should focus more on the *esoteric* methods used for passing the secret
private key.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Security proof
Date: Sat, 13 Jan 2001 17:43:44 GMT
PS, does anyone know where I can find an online version of the original
Luby-Rackoff paper? I'm not entirely certain, (since I don't have it)
but I think that it will give me enough help to be able to create the
proof in an information-theoretic manner.
[snip]
> Let M be an SPRP, and M(K) is a particular 2N bit permutation.
> Let a, b, c, d each be 1/4 of the 4N bit plaintext.
> Let w, x, y, z each be an N bit temp variable
> Let e, f, g, h each be 1/4 of the 4N bit ciphertext.
>
> The reduced size cipher is as follows:
> (w, x) = M(K0)(a, b)
> (y, z) = M(K1)(c, d)
> (e, f) = M(K2)(w, y)
> (g, h) = M(K3)(x, z)
>
> How do I go about proving that this construct is an SPRP?
> I think it can be done... but I'm not sure how.
[snip]
I think that my proof may depend on the fact that if
(y1, y2) = M(K)(x1, x2), and M is an SPRP,
then y1 is a PRF of (x1,x2) and y2 is a PRF of (x1,x2)
and only together can y1 and y2 be used to get x1 and x2;
but again, it's something I'm not sure of.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: On cryptographic proofs and their (lack) of concreteness
Date: Sat, 13 Jan 2001 17:45:18 GMT
In article <[EMAIL PROTECTED]>,
"John A. Malley" <[EMAIL PROTECTED]> wrote:
>
> Simon Johnson wrote:
> [snip]
> >
> > Yes, but what if the assumptions are wrong? The whole system of
logic
> > collapses.
> > >
>
> Suppose one builds a proof of cryptographic security upon assumptions
as
> Mr. Ashwood outlined at the start of this thread.
>
> The assumptions are axioms, aren't they?
>
> An axiom is a statement taken as "self-evident truth," by agreement,
> among a group of people. Someone derives new statements from these
> agreed-upon initial truths. Anyone in the group of people who agreed
to
> those axioms can examine the new statements and prove/disprove the
truth
> of a new statement with reference to those axioms. No one in the group
> who agreed to those axioms can derive new statements that
prove/disprove
> the truth of the axioms.
>
> So as Mr. Ashwood says, we can generate proofs of security based on
> assumed truths (axioms). He provided a list of commonly agreed-upon
> truths used in some situations
>
> "The common assumptions are things like:
> The RSA problem is hard
> The Discrete Log problem is hard
> SHA-1 acts as a random oracle"
>
> Statements of cryptographic security derived from one set of axioms A
> can not be directly compared to statements of cryptographic security
> derived from a set of axioms B unless one can derive the "axioms" in
one
> set from the other set or one makes a third set of axioms C
> incorporating both A and B and an axiom on the relationship between an
> axiom in A and B to link them together.
>
> John A. Malley
> [EMAIL PROTECTED]
>
Ah, okay, that makes it clearer.
Thanks.
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: "Ben Hopson" <[EMAIL PROTECTED]>
Subject: The Word Problem and Group Isomorphism
Date: Sat, 13 Jan 2001 18:02:08 -0000
Sorry I screwed up the date before. OS problems...
Forgive me as I am an outsider. Does anyone know of cryptosystems based on
the undecidability of the word problem? (ie the difficulty in identifying
the groups generated by relations).
I realise that many group based systems have exhibited exactly the kind of
patterns which are undesirable and wonder whether the freedom offered by
semi-groups has been looked into in much depth.
I know from experience the difficulty in trying to enumerate the cosets of
large groups, most of which can be generated by very few
generators/relations. Even trying to determine whether a given group is
trivial is a hard problem (in general undecidable, but in practice there are
Todd-Coxeter stratergies which will yield a result eventually - but with
provably no bound on time (or storage)). Similarly there are quick and dirty
stratergies but these aren't even guarenteed to terminate.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Challenge/response with MD5
Date: Sat, 13 Jan 2001 11:19:41 -0800
Ivan Skytte J�rgensen wrote:
> But I am bit worried about information about the shared secret being
> leaked by the MD5 response, and that someone could send challenges and
> receive the response and thereby detect some parts of the shared secret.
> So I am considering changing response into two parts: yet another random
> block and the MD5 of the shared secret, the random challenge and the
> random block. Would this by more secure?
>
> To elaborate:
> receive challenge B1
> generate random block B2
> calculate MD5(shared_secret+B1+B2)
> send MD5 + B2
> (this is done by both ends)
I don't see why. Someone who intercepted a successful exchange
would know B1, B2, and MD5. He could then try an exhaustive
attack on MD5(shared_secret+B1+B2) until he guesses the
shared_secret. The guessing might succeed if the secret is
a short password.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Big block DES construct.
Date: Sat, 13 Jan 2001 19:25:36 GMT
I think that I should also note that DES could easily be used for M.
Thus, if the proof succeeds, we could have a strong cipher with 128 bit
blocksize, which can be calculated in the same amount of time as 2DES.
As a diagram:
|||||||| ||||||||
--DES0-- --DES1--
|||| \\\\ //// ||||
|||| \\\X/// ||||
|||| \XXX/ ||||
|||| /XXX\ ||||
|||| ///X\\\ ||||
|||| //// \\\\ ||||
--DES2-- --DES3--
|||||||| ||||||||
Consider that encipherment 2 gets the two left half outputs of 0 and 1,
and encipherment 3 gets two right half outputs of 0 and 1. This might
or might not be enough to thwart the meet-in-the-middle attack which
works on 2DES.
Also, considering larger block sizes... 4 DES boxes across does exactly
the same amount of computation as 3DES would for the same amount of
data, but with larger effective blocksize.
Thus, it's no slower than 3DES, [hopefully] no weaker than 3DES, and it
uses a larger blocksize, and a bigger key -- which should all make it
much stronger than 3DES.
If this is implemented in hardware, one 256 bit encipherment should take
exactly as long as one 64 bit 3DES encipherment, since parallelism can
be exploited.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
** 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
******************************
