Cryptography-Digest Digest #819, Volume #10 Sat, 1 Jan 00 19:13:01 EST
Contents:
encryption algorithm with 21-character results? (Can Leonard)
Re: Q: transcendental pad crypto (No Spam)
Re: Attacks on a PKI ([EMAIL PROTECTED])
Re: HD encryption passphrase cracked! (Matthew Montchalin)
Re: encryption algorithm with 21-character results? (stanislav shalunov)
Re: Maybe I'm just blind, or maybe just stupid (Scott Fluhrer)
Re: Encryption: Do Not Be Complacent ("Joseph Ashwood")
Re: stupid question ("Joseph Ashwood")
Re: Maybe I'm just blind, or maybe just stupid ("Joseph Ashwood")
----------------------------------------------------------------------------
From: Can Leonard <[EMAIL PROTECTED]>
Subject: encryption algorithm with 21-character results?
Date: Sat, 01 Jan 2000 16:13:15 -0500
I dont know if i formulated the subject line that well, but here's the
basic outline:
I'm working on a unix version of the online chat program "Yahoo
Messenger", and I have code that worked for an older protocol version,
but need to figure out the new protocol (no documentation) before I can
actually write the "pretty" stuff..
The authentication mechanism _used_ to be that the client connected to
an HTTP server, got a cookie,, and then sent a subset of that cookie to
the actual chat server as its authentication string... The new protocol
seems to ignore the cookies and instead sends an "encrypted(?)" string
such that:
- for two different users with the same password, the string sent is the
same;
- there seems to be a fixed "header" of sorts that is shared across all
encrypted passwords (but I havent tested that many of them to know if
that really holds).
- the fixed string appears to be: $1$_2S43d5f$
- In addition, the encrypted password seems to be comprised of
upper/lower case characters + digits + '.' + (perhaps other stuff that I
didnt come across)
- the portion following the header has a fixed length of 21 characters,
followed by a terminating "/\001" (that is, '/' followed by '\001')
- sample encrypted passwords are:
bokbok => xaInRiSeIMvfhzcRYNla.
koyiim => KRFFzhZoX8w4ppMt0nx7Q
So, now to the question:
It seems like Yahoo would not patent a new encryption algorithm just for
their simple pager, so they must be using an existing (well known?)
algorithm for this... I want to know if anyone in the audience knows of
such an algorithm and where I can get more information (ie, the
particulars of encryption, perhaps sample source code);
I'm certainly not trying to crack the passwords; just want to know
enough about the protocol so I can talk to the server...
Thanks in advance
Ozgur Can Leonard
Columbia University
ps: If you could send your answers to my email address rather than post
it to the newsgroup, that would be awesome... I'm not really an
encryption person, so I dont read this newsgroup regularly. :)
------------------------------
From: No Spam <[EMAIL PROTECTED]>
Subject: Re: Q: transcendental pad crypto
Date: Sat, 01 Jan 2000 16:43:51 -0500
Reply-To: [EMAIL PROTECTED]
Bob Silverman wrote:
>
> In article <83m4t3$[EMAIL PROTECTED]>,
> "dls2" <[EMAIL PROTECTED]> wrote:
> > "John Savard" <[EMAIL PROTECTED]> wrote:
> > > "dls2" <[EMAIL PROTECTED]> wrote:
> > >
> > > >Do transcendental numbers qualify as pseudo-random, or
> > > >as truely-random, for purposes of one-time pads?
> > >
> > > Pseudo-random, since calculating the value of a transcendental
> > > number is a deterministic process. And an inefficient one, for the
> > > level of security provided.
> >
> > If there are an infinite number of transcendental numbers, then I fail
> > to see why. If the transcendental is picked randomly,
>
> Let me try to put an end to this nonsense before it goes any further.
>
> (1) There are very few numbers in mathematics that are actually KNOWN
> to be transcendental. One can indeed construct infinitely many
> transcendentals based on Liouville's theorem or from Thue's theorem.
> But such numbers are USELESS for cryptographic purposes: they have
> predicatable digit patterns and they are NOT normal numbers.
>
> (2) Since there are so few transcendentals known that would be useful
> for cryptography (useful because they are normal or believed to be
> normal), then using one as a basis for a one-time pad is fruitless.
> If someone discerns that you might be using a transcendental as the
> basis for a OTP, then it would be too easily guessed; there are not
> enough of them known.
>
> A reasonable alternative might be to use (say) 10000 digits from
> an ALGEBRAIC irrational starting at its (say) 40,000'th digit. One
> can specify such an irrational just by specifying the coefficients
> of its minimal polynomial and some indication as to which conjugate you
> are using. Assuming that the degree was large enough and that the
> coefficient space was large enough, the keyspace should be large enough
> that having an opponent guess your number should be very low
> probability.
>
> You do NOT want to start the pad at the first digit, because given
> the first few digits, one can make a good guess at the entire number
> using e.g. Ferguson/Forcade.
>
> Bob Silverman
> "You can lead a horse's ass to knowledge, but you can't make him think"
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
Bob,
I have a stupid question about PRNGs I hope you will answer for me.
It seems that most of the postings in this news group view the use of
PRNG in encryption as very poor.
If I create a key pass phrase: "ABCDEGGH" and use the first three, two
byte pairs (AB, CD, and EF) as 16 bit seeds for a PRNG.
Taking the ouput streams fron the PRNG for each of the three seeds, and
XORing the output into a 10K buffer. So the PRNG's output was XORed
into the 10k buffer three times.. each with a different seed (AB, CD,
EF).
Then I take the last key pair GH, seed the PRNG and use the PRNG to pick
the bytes from the 10K buffer to use as a streaming encryption XOR .
Is there any attack that can be used to break the code other than a
brute force key phrase attack?
If a large amount of the plain text was know.. say 100K of a 100,100
byte message, is there an attack the will decrypt the last 100 bytes?
Green in New Hampshire
Reply2 [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Attacks on a PKI
Date: Sat, 01 Jan 2000 22:18:59 GMT
In article <84inqd$k88$[EMAIL PROTECTED]>,
Greg <[EMAIL PROTECTED]> wrote:
> > > > As for the comments that the effort to maintain PKI security is
as
> > > > great as keeping shared secret keys, the difference is
> > >
> > > The difference is that it is an illusion and has no value.
> > >
> > the security of a PKI is as strong as the weakest link. At the end
of
> > the day, you must trust that the person you are doing business with
is
> > genuine. This trust can be violated through the many flaws in PKI.
>
> I disagree. The security of PKI is weak due to its lack of a
> complete protocol definition. For example, the concept of a
> certificate being validated by another certificate in a pyramid
> of certificates, with the top being undisputed, but no way to
> define within the PKI protocol how to make such a top level
> certificate 100% undisputed leaves PKI useless. PKI is a good
> idea that has not been finished yet. It has holes in that
> those with monetary interests are willing to gloss over today
> at our expense.
>
Wouldn't you say that PKI security is weak due to it's inherent flaws
rather than just protocol definition? My view is that no matter how
much the protocols are tweaked, PKI will always remain fundamentally
flawed.
If you haven't already done so, I'd recommend you read the
Ellison/Schneier PKI paper found at www.counterpane.com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Matthew Montchalin <[EMAIL PROTECTED]>
Crossposted-To: misc.misc
Subject: Re: HD encryption passphrase cracked!
Date: Sat, 1 Jan 2000 14:19:00 -0800
On Sat, 1 Jan 2000, Lincoln Yeoh wrote:
|On Mon, 27 Dec 1999 12:07:24 -0800, Matthew Montchalin
|<[EMAIL PROTECTED]> wrote:
|
|>Have you ever opened up your hard drive and pulled out the magnetic
|>medium with a pair of tweezers? Sure, they say that microscopic
|>particles of dirt get into the hard drive, substantially compromising the
|>storage capabilities, but if you really wanted to eradicate every last
|>trace of the data, and yet still be able to use the medium (that is the
|>important part), you can swipe a kitchen magnetic over and around and
|>around the medium before replacing it again. Of course, after doing
|
|What's the point? After opening up the drive you can't rely on the drive.
Why not? You a smoker? Don't use air purifiers? Got lots of barnyard
animals moseying around in your livingroom?
|If you are going to do that, you might as well blowtorch the entire drive
|and buy a new one. Drives are cheap nowadays.
Um, you work for the 'government,' right?
------------------------------
From: stanislav shalunov <[EMAIL PROTECTED]>
Subject: Re: encryption algorithm with 21-character results?
Date: 01 Jan 2000 17:29:32 -0500
Can Leonard <[EMAIL PROTECTED]> writes:
> - for two different users with the same password, the string sent is the
> same;
> - there seems to be a fixed "header" of sorts that is shared across all
> encrypted passwords (but I havent tested that many of them to know if
> that really holds).
> - the fixed string appears to be: $1$_2S43d5f$
> - In addition, the encrypted password seems to be comprised of
> upper/lower case characters + digits + '.' + (perhaps other stuff that I
> didnt come across)
> - the portion following the header has a fixed length of 21 characters,
> followed by a terminating "/\001" (that is, '/' followed by '\001')
> - sample encrypted passwords are:
>
> bokbok => xaInRiSeIMvfhzcRYNla.
> koyiim => KRFFzhZoX8w4ppMt0nx7Q
It appears that the result you're seeing is a base64 encrypted string
(final slash probably being part of it) that's 128 bits long.
Now, that could be basically anything. Doing any meaningful
cryptoanalysis on just two entries isn't feasible.
It's probably a block of cyphertext they encrypt with a secret key.
Since you probably have the client, you could reverse-engineer it (if
the license allows doing so) and see what does it use. There could be
a subroutine name that would give a hint. The key is probably in the
binary as well, *if* it really ignores the cookies (rather than using
[part[s] of] them as the key).
Just out of curiosity I checked whether it's a well-known one-way
hash, such as MD5. Doesn't look so (unless they add something to the
password before hashing it).
Try to see whether that string you get to send for a given user
changes over time.
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: Maybe I'm just blind, or maybe just stupid
Date: Sat, 01 Jan 2000 23:04:06 GMT
In article <OxFldNmU$GA.271@cpmsnbbsa05>,
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
>Now I know we're all rather against the inexperienced/unpublished posting
>new algorithms. But I've had this one kicking around my head for a few years
>now, and I haven't made much progress (see after algorithm), and I haven't
>been able to find a reference regarding it's use or analysis. With that said
>let me say that I have come up with other ideas but upon my examination I
>found them either lacking or that someone else had the idea first. Now on to
>the entertainment.
>
>I have spent quite a bit of time trying to express this in something
>readable (and ended up with pseudocode) and I'm still not sure if it's any
>good, please feel free to ask, also the algorithm is slower than it could
>be. It is very slow in software, but very fast in hardware ( <10 ns per
>block in TTL). I am deliberately being arbitrary about the numbers because
>I'm fairly sure that an attack on one length if quite likely to be
>applicable to large blocks/keys. I am only presenting the minimal function
>because it lends itself to analysism, and can be repeated easily.
{Snip pseudocode]
Well, I see several weaknesses:
- This cipher maintains hamming weight. This means that, even if the attacker
cannot find out what the plaintext is, he can often figure out what the
plaintext isn't -- given a plausible plaintext from another source, he can
often rule it out. It also helps the attacker recognize when the same plaintext
is encrypted with two different keys.
- If this cipher is used to encrypt multiple different plaintexts with the
same key, the attacker can rederive the sort order if he has several of those
plaintexts (O(log(N)) blocks, where N is the block size, should be more than
sufficient). This leads to the obvious questions -- what do you do when you
have more message text than key? If you insisted that you always have as
much key, then you'd be better running an OTP. If you just reused the key
for each block, then you run the risk of the attacker decrypting it, if he
gets (or guesses) part of the message.
- What's the size of a 'subblock'. If it's more than a single bit, that introduces
additional weaknesses. For example, if it's a character, then the attacker
knows that a 'k' will occur in the ciphertext only if it was in the plaintext,
and so if he doesn't see a 'k', the word 'attack' could not appear.
--
poncho
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Encryption: Do Not Be Complacent
Date: Sat, 1 Jan 2000 15:24:15 -0800
While I think it's a good start, it still has too much residual that comes
from a known Language (English for Teen and Cockney). I think a better idea
would be to use the occurance table (e.g. e=x% of the text) to build a
reversing table utilizing a larger area. The basic idea goes like this.
Based on a significant amount of prior text we build a frquency table, say
0= 37%
1= 63%
Based on that and using a larger area we determine ranges for the symbols
0= 0 through 36
1= 37 through 99
We then choose a random number in the ranges and use it for obfuscation,
then we encrypt and send. At the other end, we decyrpt, make use of our
symbol ranges such that
0 . . . 36 = 0
37 ... 99 = 1
Of course in the encrypt stage I would expect the use of good compression
(one that has no structure), the idea is not necessarily compression, but
instead an additional symbol change. The disadvantage is of course that the
space used is increased, the advantage is that frequency analysis on the
result reveals nothing, so the extra step of going through the recombination
is needed. In most protocols this isn't necessary but until recently I was
dealing with a protocol that was >99% predictable because of this, and it
vastly increased the apparent randomness, but I'm not sure if it increased
the actual randomness.
Joseph
"Guy Macon" <[EMAIL PROTECTED]> wrote in message
news:84j9qg$[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Anthony
Stephen Szopa) wrote:
>
[snip Navajo, Teen, and Cockney]
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: stupid question
Date: Sat, 1 Jan 2000 16:01:51 -0800
Basically yes there is an attack. There exists a pRNG function that will
generate the exact same output, and it's likely to be faster. OTOH given the
48-bit keyspace you suggested it would take less time to brute-force the
pRNG than to find the function and search for an inversion. Without knowing
which pRNG you were considering using Ican;t and probably no-one else can
tell you either, but I'm not sure, we have some absolutely brilliant people
around here.
Joseph
"No Spam" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> It seems that most of the postings in this news group view the use of
> PRNG in encryption as very poor.
It's not that we view it as poor, if you ask around you'll find that one of
the favorite ciphers is RC4 which is nothing more than a pRNG and an XOR.
There are known attacks on the underlying data when this is done, but very
little that can be done to recover the data without solving the pRNG.
> If a large amount of the plain text was know.. say 100K of a 100,100
> byte message, is there an attack the will decrypt the last 100 bytes?
That depends exclusively on your pRNG. Using even a minimal keysize in RC4
we could not find the last 100bytes without finding the key, although with
the minimal size 100k might be getting close to predictability. It is my
opinion that using a method more significant that XOR with pRNG would be
highly useful, as a matter of fact I'm trying to find my own solution to
several problems that I believe will be useful in this category (results to
be posted here when finished).
Joseph
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Maybe I'm just blind, or maybe just stupid
Date: Sat, 1 Jan 2000 15:48:15 -0800
> Well, I see several weaknesses:
Thank you, I'm very interested in learning from both my mistakes and the
mistakes of others.
> - This cipher maintains hamming weight. This means that, even if the
attacker
> cannot find out what the plaintext is, he can often figure out what the
> plaintext isn't -- given a plausible plaintext from another source, he
can
> often rule it out. It also helps the attacker recognize when the same
plaintext
> is encrypted with two different keys.
I hadn't thought of that one, but you are definitely right, it would
certainly need to only be used as a part of a method.
> - If this cipher is used to encrypt multiple different plaintexts with the
> same key, the attacker can rederive the sort order if he has several of
those
> plaintexts (O(log(N)) blocks, where N is the block size, should be more
than
> sufficient). This leads to the obvious questions -- what do you do when
you
> have more message text than key?
I rather like the block filling that's performed in SHA-1, but any method of
filling the block and marking where it ends should be sufficient.
Without the problem you pointed out (the logn blocks needed) I'd be inclined
to simply use a stand chaining method to alter the key, instead I'm more
inclined to simply list this under the trivial to break portion of my brain.
>
> - What's the size of a 'subblock'. If it's more than a single bit, that
introduces
> additional weaknesses. For example, if it's a character, then the
attacker
> knows that a 'k' will occur in the ciphertext only if it was in the
plaintext,
> and so if he doesn't see a 'k', the word 'attack' could not appear.
I hadn't planned on any reasonable implementation using larger than 1-bit
subblocks.
I did find another problem. there are a large number of keys which are
ambiguous, and whose encryption would be determined by which sort you used,
more specifically whether given a list of e.g. a a whether or not it would
swap the characters.
I'm withdrawing my suggestion, it's simply too weak, has too many already
well known holes, I don't see it being useful in and of itself, if someone
would care to use it, feel free.
Joseph
------------------------------
** 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
******************************
