Cryptography-Digest Digest #549, Volume #13 Thu, 25 Jan 01 15:13:00 EST
Contents:
unknown encryption algorithm ([EMAIL PROTECTED])
Re: "How do we know an Algorithm is Secure?" (was RC4 Security) ("Douglas A. Gwyn")
Re: Secure game highscore server (Matthew Skala)
Re: Transposition code ("Douglas A. Gwyn")
Re: Knots, knots, and more knots ("Douglas A. Gwyn")
Re: Differential Analysis of "A + (B xor X)" (Tom St Denis)
Re: Knots, knots, and more knots (Richard Heathfield)
Re: How much of this group's discussion violates the DMCA (Mok-Kong Shen)
Re: Windows encryption: API and file system ("Ben Newman")
Re: "How do we know an Algorithm is Secure?" (was RC4 Security) (William Hugh Murray)
Re: Windows encryption: API and file system (Darren New)
Re: Transposition code ("Douglas A. Gwyn")
Re: finding inverses and factoring (Bob Silverman)
crypt(3C) algorithm under Solaris 2.6? ([EMAIL PROTECTED])
Re: Random stream testing. (long) ("Paul Pires")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: unknown encryption algorithm
Date: Thu, 25 Jan 2001 17:22:23 GMT
Hi,
does somebody of you have an idea, what kind of algorithm was used to
encode the following plaintext?
plaintext:
dclient177-193
some examples of encrypted (all of the same plaintext)
kUqmnlaqr433-774
jemuvastu663-255
aEcofidqd366-512
Djltfhmpi664-422
2dnsymiov322-450
EEouuclio090-343
any help or hint is welcome :)
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: "How do we know an Algorithm is Secure?" (was RC4 Security)
Date: Thu, 25 Jan 2001 16:40:56 GMT
William Hugh Murray wrote:
> We never really know that an encryption algorithm is strong.
In some cases it is possible to characterize the "strength"
of a cryptosystem. Consider a system where the key changes
before unicity distance is reached, as an oversimplified example.
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Secure game highscore server
Date: 25 Jan 2001 00:35:06 -0800
In article <[EMAIL PROTECTED]>,
graywane <[EMAIL PROTECTED]> wrote:
>The only way to prevent cheating is to play with people who don't cheat.
>Sad but true.
If the game is one where a computer player can trivially outperform a
human, then the game sucks anyway. Good games necessarily require human
intelligence. In the Kosmos Online project we're facing this kind of
issue over and over again, because we're building an open source
multiplayer networked roleplaying game. There's no question that anything
the client knows, the player knows - so the client cannot be told anything
the player isn't allowed to know. There's no question that anything the
client can do, the player can do - so the client cannot be allowed to do
anything the player isn't allowed to do. There's no way to distinguish a
computer behind the controls from a human, that's a harder problem than
creating a simulated human in the first place, so the game cannot be one
where a present-day-tech AI would have an advantage over a human. That
last requirement touches on every aspect of the game. There can't be any
critical reflex actions; there can't be any "strategy" tests that come
down to automatable things like arithmetic or simple logic. Instead, we
have to concentrate on social interactions and role-playing, the things
computers are no good at.
What a coincidence that they call them "role-playing games".
--
Matthew Skala
[EMAIL PROTECTED] :CVECAT DELENDA EST
http://www.islandnet.com/~mskala/
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Transposition code
Date: Thu, 25 Jan 2001 17:06:02 GMT
Benjamin Goldberg wrote:
> From your post, I wrote the following: ...
> However, it doesn't seem to work quite right.
I wasn't going to say anything, but at this point
perhaps you could use some friendly programming advice.
The simplest appraoch is often best -- don't try to
fold all the tranformations together in a few compact
lines of code, at least not until you have gotten the
code right. Use your diagram as a guide:
1 2 3 plaintext (input) column number
-----
K E Y
2 1 3 ciphertext (output) column number
-----
1 2 3 plaintext message sequence
4 5 6
7
-----
l s s
The last line indicates whether the column is long or
short. First step is to obtain the geometric parameters:
message length, number_of_columns := key_length. Then
compute the lengths of short and long columns:
short_column_length := message_length // key_length,
long_column_length := short_column_length + 1. The
number_of_long_columns (may be 0) := message_length -
number_of_columns*short_column_length. If you lay the
plaintext out as a doubly-indexed array (perhaps using
dynamic allocation as I posted a week ago) it will be
easy to index "down the column", or if you lay it out
in a 1-dimensional array it is easy enough to step
along that array to pick out every number_of_columns-th
character, as in the following. Write out the entire
algorithm using all the variables described above;
the key trick will be to pay attention to the column length:
for out_column in output (keyed) order:
(starting) position := plaintext[column]
number_of_rows_to_output :=
if input_column_number[out_column] <
number_of_long_columns
then long_column_length
else short_column_length
for out_row from 0 up to but not including
number_of_rows_to_output:
output plaintext[position]
add number_of_columns to position
Once you have the code working correctly (try examples
with all columns the same length, just 1 long column, and
just 1 short column), *then* if you feel the necessity you
can go back over the code and transform it via a series of
*equivalencies* into code that uses fewer variables and
combines operations. However, there wouldn't seem to be
any point in doing that for this application. Clearer code
is better, so long as it is fast enough and small enough.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Knots, knots, and more knots
Date: Thu, 25 Jan 2001 17:08:53 GMT
Richard Heathfield wrote:
> Consider the descriptions in English:
> Eight ones.
> Eight zeros.
> A couple of one-zero pairs, then a zero, then three ones.
> Surely the last one is more complex?
Clearly that "complexity" measure depends on the chosen
language. The general approach is known as "algorithmic
complexity theory" and Kolmogorv and Chaitin were its
best-known pioneers. Chaitin has a Web page as I recall.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis of "A + (B xor X)"
Date: Thu, 25 Jan 2001 18:07:27 GMT
In article <[EMAIL PROTECTED]>,
"Alexis Machado" <[EMAIL PROTECTED]> wrote:
> Hi,
>
> I'm studying the function "F(X) = A + (B xor X) (mod 2**n)" differential
> properties.
That's easy, a change in X is virtually always isolated. I.e consider
flipping the MSB it must flip the MSB of the output bit.
Besides I would use a linear attack to solve this it would be much more
efficient.
For example you can collapse the LSB of A and B into a single bit and solve
it. Then once you do that repeat it for the next bit of A and B... i.e an
attack with 8 steps.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
Date: Thu, 25 Jan 2001 19:38:51 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Knots, knots, and more knots
"Douglas A. Gwyn" wrote:
>
> Richard Heathfield wrote:
> > Consider the descriptions in English:
> > Eight ones.
> > Eight zeros.
> > A couple of one-zero pairs, then a zero, then three ones.
> > Surely the last one is more complex?
>
> Clearly that "complexity" measure depends on the chosen
> language.
Absolutely. One could argue that all of the above descriptions have the
same complexity, because they can all be described in eight bits! And
round the circle we go...
> The general approach is known as "algorithmic
> complexity theory" and Kolmogorv and Chaitin were its
> best-known pioneers. Chaitin has a Web page as I recall.
Indeed. It's http://www.cs.auckland.ac.nz/CDMTCS/chaitin/
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: How much of this group's discussion violates the DMCA
Date: Thu, 25 Jan 2001 19:35:26 +0100
Jerry Coffin wrote:
>
> It's _very_ clear that what takes place here is discussion,
> not action. As such, it is protected as free speech.
It might be of interest to recall in this connection that
decades ago there was once a (unrealized) suggestion that
editors of scientific journals voluntarily submit articles
about crypto, the publication of which could be of relevance
to national security, for preview by some institutions.
Thus it might very well suit the 'ideal' thinking of some
people behind projects like DMCA, if such self-imposed
'disciplines' could have existed on the internet in issues
of concern.
M. K. Shen
------------------------------
From: "Ben Newman" <[EMAIL PROTECTED]>
Subject: Re: Windows encryption: API and file system
Date: Thu, 25 Jan 2001 13:40:49 -0500
This is an excellent start. I was hoping for a more detailed discussion of
how an OS can secure files, and how Windows has implemented their encryption
protocol.
This bug is just plain sloppy engineering!
--ben
"Bryan Mongeau" <[EMAIL PROTECTED]> wrote in message
news:VUYb6.6219$[EMAIL PROTECTED]...
> Ben Newman wrote:
>
> > I'd like to learn more about criticisms of the Windows cryptography
> > implementation. In response to an earlier post, someone characterized it
> > as "practically useless." This seems like a particularly important issue
> > given the amount of knowledge your average Windows user has about
crypto.
> >
> > --ben
> >
> >
>
> I don't know if this what you mean but I saw this on Bugtraq
> a few days ago:
>
> ----------------------------------------------
> BugTraq: EFS Win 2000 flaw
> From: Rickard Berglind <[EMAIL PROTECTED]>
> To: [EMAIL PROTECTED]
> Date: Fri, 19 Jan 2001 12:29:50 +0100
>
>
> I have found a major problem with the encrypted filesystem
> ( EFS ) in Windows 2000 which shows that encrypted files
> are still very available for a thief or attacker.
>
>
> The problem comes from how EFS works when the encryption
> is done. When a user marks a file for encryption a
> backup-file, called efs0.tmp, will be created. When
> the copy is in place the orginal file will be deleted
> and then recreated, now encrypted, from the efs0.tmp-
> file.
> And finally, when the new encrypted file is succesfully
> created, the temporary-file ( which will never be shown
> in the user interface ) will be deleted as well.
>
> So far, so good. The only file remaining is the one
> which is encrypted.
>
>
> But the flaw is this: the temporary-file is deleted
> in the same way any other file is "deleted" - i.e.
> the entry in the $mft is marked as empty and the clusters
> where the file was stored will be marked in the $Bitmap
> as available, but the psysical file and the information it
> contains will NOT be deleted. The information in the
> file which the user have encrypted will be left in the backup
> file efs0.tmp in total plaintext on the surface of the disk.
>
> When new files are added to the partition will they
> gradually overwrite the secret information, but if
> the encrypted file was large - the information could
> be left for months.
>
> So how can this be exploited ? If someone steals
> a laptop or have psysical access to the disk it will
> be easy to use any low level disk editor to search
> for the information. For example, the Microsoft
> Support Tool "dskprobe.exe" works fine for locating
> old efs0.tmp-files and read information, in plain-text,
> that the user thought was safe.
>
> In my opinion there should be a function in the EFS
> which physically overwrites the efs0.tmp at least once
> to make it a lot harder for an attacker to gain control
> over secret information.
>
>
>
> Here is a description how to test this :
>
> Use any version of Windows 2000.
> Install the Support Tools from the Win2000 CD.
>
> For demonstrating purposes - create a new partition with
> the size of 7 MB.
> Choose to format with NTFS.
> Create a new small file ( easier to find ) with Notepad
> and put some text in it. Save this file in the root of the
> new partition.
>
> Do not encrypt it yet.
>
> Let us look at the file through DiskProbe before encryption-
> start Diskprobe from Support Tools on the Start Menu.
>
> A. Choose the "Drives"-menu and "Physical Drive"
> Double click on "physical drive 0" ( or other drive you are using )
> Click "Set active" and then "OK"
>
> B. Choose "Drives" again and this time "Logical Volume"
> Double click the drive letter for your new partition
> and then "Set active" and "OK"
>
> C. Choose the "Sectors"-menu and "Read". For starting number
> type 80 and for the number - 35 perpaps.
>
>
> Maximize the window and click the arrow for "Next sector".
>
> At sector 86 you should see the name and contents of your
> file ( assuming you made a new partition )
>
> The file is obiously in plain text and easy to read for anyone
> with physical access to this disk, regardless of permissions
> in the ACL, which is ignored when using this kind of utiliy.
> Better encrypt this file .. !
>
>
> Now close the DiskProbe utility and open Explorer and locate
> your new file. Choose Properties - Advanced - Encrypted - OK.
> The file is now encrypted.
>
> Wait a few moments to be sure the new data has been written
> to the disk.
> Open Diskprobe again and repeat steps A, B and C.
>
> When reaching sector 86 you should be able to see the name
> of your file, but not be able to read the information - it
> is now encrypted.
>
> But.. continue to click the Next Sector-Arrow and look carefully
> at the information being displayed. A few sectors away from the
> orginal file there should be a file called efs0.tmp - which is
> the backup file EFS creats during encryption. You should ALSO
> be able to see the contents of this efs0.tmp file - which will
> be the data from the file you encrypted. The problem is just that
> the data is in clear and plain text.
> So again - anyone with physical access to this disk can read
> the data you thought was safe.
>
>
> / Rickard Berglind
> -------------------------------------------------
>
>
> --
> <==================================>
> Bryan Mongeau
> Lead Developer, Director
> eEvolved Real-Time Technologies Inc.
> www.eevolved.com
> <==================================>
>
> "The fear of death is the most unjustified of all fears, for there's no
> risk of accident for someone who's dead."-- Einstein
>
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: "How do we know an Algorithm is Secure?" (was RC4 Security)
Date: Thu, 25 Jan 2001 18:31:43 GMT
"Douglas A. Gwyn" wrote:
> William Hugh Murray wrote:
> > We never really know that an encryption algorithm is strong.
>
> In some cases it is possible to characterize the "strength"
> of a cryptosystem. Consider a system where the key changes
> before unicity distance is reached, as an oversimplified example.
Agreed.
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Windows encryption: API and file system
Date: Thu, 25 Jan 2001 19:01:00 GMT
Ben Newman wrote:
> This bug is just plain sloppy engineering!
Isn't it more a question of what kinds of attacks this encryption is
supposed to defend against? Surely if the user's login record / password /
whatever is used to encrypt the files, and no passphrase is needed for
accessing an encrypted file, stealing the disk will give you all the
information you need to decrypt the encrypted files anyway, yes?
What kinds of attacks does Microsoft think this defends against? Theft of
backup materials, maybe? Reading of files by administrators?
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"It says this wine has syphilis."
"I think that's pronounced `sulphates'."
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Transposition code
Date: Thu, 25 Jan 2001 18:23:41 GMT
"Douglas A. Gwyn" wrote:
> (starting) position := plaintext[column]
That was supposed to be [out_column] (when I changed the
name during editing I missed that instance).
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: finding inverses and factoring
Date: Thu, 25 Jan 2001 19:12:21 GMT
In article <94n7ao$4mj$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
>
> Hi,
>
> I recall that in RSA, knowledge of d alone, combined with e and n, is
> enough to derive phi(n) and factor. I don't recall the proof,
> unfortunately - so I apologize if this post turns out to be trivial.
If you know d, then you know a multiple of phi(n), so just apply
Pollard's P-1 factoring algorithm.
> Two related questions.
>
> Suppose I publish n, g1 a generator of some subgroup in n,
You need to be more specific. "subgroup in n" isn't very clear.
Do you mean a multiplicative sub-group of Z/nZ*? How big is the
subgroup?
and g2 a
> generator of some subgroup of "the exponents mod n", which have order
> phi(n).
This is unclear. Do you mean Z/(phi(n))*? These elements, since
they are co-prime to phi(n) all have maximal order in Z/nZ*. Is
this what you are looking for?
> Further I publish g1^(g2^x) and g2^x.
I assume these are taken mod n?
> The value n is made public,
> but phi(n) is not revealed. Can phi(n) be feasibly determined?
You have not said what x is. Assuming it is a random integer:
Since g2 has maximal order, g2^x will be a random element in the
maximal cyclic subgroup. Whether phi(n) can be recovered now depends
on the order of g1. If g1 generates a relatively small subgroup,
then yes.
Can you be more specific?
--
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/
------------------------------
From: [EMAIL PROTECTED]
Subject: crypt(3C) algorithm under Solaris 2.6?
Date: Thu, 25 Jan 2001 19:52:01 GMT
Hi,
Does anybody now what encrypt algorithm is used by crypt(3C) under
Solaris 2.6? I'm looking for DES encryption under 2.6. Solaris 7 and
8 seem to include libraries for these.
- Abraham
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Random stream testing. (long)
Date: Thu, 25 Jan 2001 12:02:49 -0800
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Paul Pires wrote:
> > First off, the notion that this is testing the randomness
> > of the data. It seems obvious to me that it is only
> > comparing the results to an expectation of how
> > random data would look according to very narrow
> > criteria. It say's nothing about the data's randomness
> > per se but only how it compares to a theoretical result,
> > according to a very limited criteria. No test can detect
> > randomness.
>
> Randomness is not a property of data but rather of the
> process that generates the data. What can be properly
> tested is the hypothesis that the generator draws a
> uniform random sample (or from some similar specified
> theoretical source). Testing can contribute evidence
> for or against that hypothesis.
>
> The best way to make use of such evidence is to accrue
> it a la Turing, Good, Kullback, et al. ("weight of
> evidence") and evaluate it as asymptotic chi-square.
Sounds like a good place to look. Thanks,
>
<snip>
> That's not how chi-square is evaluated. One can take
> the given value of observed chi-square and degrees of
> freedom and look up the likelihood that the observed
> value would be at least that large *if* the hypothesis
> is true. Absent any other evidence and without any
> a priori expectation one way or the other, it is then
> reasonable to take that likelihood as one's first cut
> at betting for or against the hypothesis.
I was actually mis-quoting from a document supporting
the random test suite known as "ent".
http://www.fourmilab.ch/random
While I garbled it a bit, but it does discribe the test like that.
>
<snip>
> > I've almost worked myself into a paradox here. Single
> > results are meaningless and group results are
> > incomprehensible. What's left?
>
> I suppose you could go off and study statistics a while
> to figure out what error led you to the contradiction.
Not bad advice.
>
> > Many say that RNG output is better quality than PRNG output
> > but I have never seen a demonstration of such an evaluation.
>
> Just read one of the papers that shows how a PRNG version
> of "one-time pad" has been successfully cryptanalyzed via
> a ciphertext-only attack. Obviously a true uniform RNG
> version would not be susceptible to such an attack.
If handy, could you provide me with a name or a link to
one or two such papers?
Thank you.
Paul
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
** 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
******************************
