Cryptography-Digest Digest #669, Volume #13 Sat, 10 Feb 01 10:13:01 EST
Contents:
a exp b mod n ([EMAIL PROTECTED])
Re: OverWrite freeware completely removes unwanted files from hard drive (Hit1Hard)
Re: NPC (Bryan Olson)
Re: CipherText patent still pending (Bryan Olson)
Re: CipherText patent still pending (Bryan Olson)
Re: CipherText patent still pending (Bryan Olson)
Re: Shortened signatures (Matt J)
Password authentication with symmetric key exchange ([EMAIL PROTECTED])
Re: Shortened signatures (Quisquater)
Re: a exp b mod n (Tom St Denis)
Re: OverWrite freeware completely removes unwanted files from hard (Andreas
Gunnarsson)
Re: NPC (Benjamin Goldberg)
Re: Scramdisk, CDR and Win-NT (jungle)
What is kerebos? (B. Wooster)
Re: Rijndael S-box derivation (Benjamin Goldberg)
Re: What is kerebos? ("Sam Simpson")
Re: Rijndael S-box derivation ("Brian Gladman")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: a exp b mod n
Date: Sat, 10 Feb 2001 10:12:22 GMT
Hi all!
I wanted to test a method that should return a exp b mod n. I copied it
from Bruce Schneier's Applied Cryptography. There are two such methods,
that I used with "unsigned long"s in C++, but both return 0 if a and b
get higher. n is a 32-bit prime number. Does anyone have some working
code?
THanks,
Heinz
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Hit1Hard <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.hacker,alt.conspiracy
Subject: Re: OverWrite freeware completely removes unwanted files from hard drive
Date: Sat, 10 Feb 2001 05:37:28 -0500
Anthony Stephen Szopa wrote:
>
> So where are these technological sophisticates: these brain drained
> mental armchair hackers, now?
>
They make sure the "crucial" information on the HD is encrypted with
their own encryption software.
wich is not placed on the system HD's.
Oh. And the swapfile is empty.
>
> Thanks for the grilling.
anytime.
--
Hit1Hard
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: NPC
Date: Sat, 10 Feb 2001 11:33:51 GMT
Peter Shugalev:
> I think someone tried to prove that either discrete log or
> factoring problem is NPC (not just NP). I'd like to see
> some results of these attempts.
The attempts have, to put it bluntly, failed.
Discrete log and factoring are poly-time reducible to
languages that are in the intersection of NP and CoNP. If
either is NP-Complete, then NP=CoNP.
For those not familiar with the definitions, CoNP is the
set of languages who's complements are NP. Languages in
NP are exactly those that have short-certifiers; informally,
if a string is in the language, then there exists a
poly-time verifiable proof that it's in the language. For
example to show a boolean expression is in SAT, one could
exhibit the satisfying assignment. But there's no
requirement that non-membership in an NP language be so
efficiently demonstrable.
Languages in CoNP have short-certifiers for non-membership.
If NP=CoNP, then any language with a short-certifier of
membership also has a short-certifier of non-membership.
The NP ?= CoNP conjecture is one of the great unsolved
problems. In this field, conjectures tend to either be
resolved very quickly (often by the time one has the
understanding to form them) or to remain open unto the
present. The NP != CoNP conjecture is like P != NP
in that it looks to be probably true and very hard to
prove.
Of course if P=NP then P=NP=CoNP.
> And if they are *not* NPC. Do you know any attempt to
> create a public key algorithm based on the problem
> that is known to be NPC?
"Based on" is too sketchy, as Peter Shugalev's remarks
suggested. We say that RSA is based on factoring, but
breaking it is at _most_ as hard as factoring. What we'd
like is a system such that we can reduce deciding an
NPC language to breaking the system.
The NP ?= CoNP problem seems fundamental here. The
true decryption constitues a certificate for the
correctness or incorrectness of any cryptanalysis.
Thus any system that allows unique decryption (and is
tractable) is reducible to something in the
intersection of NP and CoNP. And so a proof that
breaking it is NP-hard would also prove NP!=CoNP.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: CipherText patent still pending
Date: Sat, 10 Feb 2001 11:40:16 GMT
IPeter Shugalev:
> I think someone tried to prove that either discrete log or
> factoring problem is NPC (not just NP). I'd like to see
> some results of these attempts.
The attempts have, to put it bluntly, failed.
Discrete log and factoring are poly-time reducible to
languages that are in the intersection of NP and CoNP. If
either is NP-Complete, then NP=CoNP.
For those not familiar with the definitions, CoNP is the
set of languages who's complements are NP. Languages in
NP are exactly those that have short-certifiers; informally,
if a string is in the language, then there exists a
poly-time verifiable proof that it's in the language. For
example to show a boolean expression is in SAT, one could
exhibit the satisfying assignment. But there's no
requirement that non-membership in an NP language be so
efficiently demonstrable.
Languages in CoNP have short-certifiers for non-membership.
If NP=CoNP, then any language with a short-certifier of
membership also has a short-certifier of non-membership.
The NP ?= CoNP conjecture is one of the great unsolved
problems. In this field, conjectures tend to either be
resolved very quickly (often by the time one has the
understanding to form them) or to remain open unto the
present. The NP != CoNP conjecture is like P != NP
in that it looks to be probably true and very hard to
prove.
Of course if P=NP then P=NP=CoNP.
> And if they are *not* NPC. Do you know any attempt to
> create a public key algorithm based on the problem
> that is known to be NPC?
"Based on" is too sketchy, as Peter Shugalev's remarks
suggested. We say that RSA is based on factoring, but
breaking it is at _most_ as hard as factoring. What we'd
like is a system such that we can reduce deciding an
NPC language to breaking the system.
The NP ?= CoNP problem seems fundamental here. The
true decryption constitues a certificate for the
correctness or incorrectness of any cryptanalysis.
Thus any sysem that allows unique decryption (and is
tractable) is reducible to something in the
intersection of NP and CoNP. And so a proof that
breaking it is NP-hard would also prove NP!=CoNP.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: CipherText patent still pending
Date: Sat, 10 Feb 2001 12:25:26 GMT
Mok-Kong Shen wrote:
> Bryan Olson wrote:
> >
> > Mok-Kong Shen wrote:
> >
> > > The quote in question was the following:
> > >
> > > Experts teaching writing say to write every day. I've never
> > > heard an expert cryptologist recommend cipher design as an
> > > exercise.
> > > That's why I considered the above quoted to be misleading
> > > and argued against correspondingly.
> >
> > The quote is easy to refute if wrong; just look through the
> > crypto textbooks, or course syllabi. [...]
> As is often the case in the real world, there is the
> interpretation problem.
No. The set of "Experts" is arguable, but there are
certainly clear cases, both expert and non.
> I suppose you mean modern textbooks
> like AC contain much designs but much less about analysis.
AC is not really a textbook and I don't think it has any
exercises. If you want to read Schneier's advice on
getting into cipher design, see:
http://www.counterpane.com/crypto-gram-9810.html
[...]
> > > I am not sure it is clear that cipher design is easy.
> >
> > I'm convinced it's very hard to do well. I recall spending
> > many hours trying to convince you of the same.
>
> That's why I am not an expert but only a very humble
> learner
Then take Schneier's advice. All the experts I know
say much the same.
> Let me in this connection come back to your previous point
> of there being too many bad designs around. This fact is
> like there are too many paintings around.
The problem is nothing like that.
> However, I haven't sofar seen any
> posts in the group on suggestions of new methods of
> analysis or improvements of old ones, at least in the
> proper sense.
Read Wagner, Gillogly, Wooding, Hopwood, Flurer (and
others of course, I'm not great with names.)
> In the meantime the best that can be achieved
[...]
No one is trying to take away your right to write. Don't
forget that for some time you've been suggesting that I
shouldn't post here, while I've been suggesting that you
should make a serious effort to understand cryptology.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: CipherText patent still pending
Date: Sat, 10 Feb 2001 12:29:29 GMT
Bryan Olson wrote:
[Something that had nothing to do with this thread.]
Oops, editing-tool error.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Matt J <[EMAIL PROTECTED]>
Subject: Re: Shortened signatures
Reply-To: [EMAIL PROTECTED]
Date: Sat, 10 Feb 2001 20:44:36 +0800
Cryptonessie?
------------------------------
From: [EMAIL PROTECTED]
Subject: Password authentication with symmetric key exchange
Date: Sat, 10 Feb 2001 13:00:15 GMT
This is not a too original password authentication scheme. I would
however appreciate comments of any kind.
Purpose:
Prevent copy-and-paste attacks on the authentication protocol, where
the attacker eavesdrops the authentication part of a session, and
manages to log in later by resending the information.
Design notes:
The client might choose to abort after step 1 or 3, and if the server
allows it, thereby login at a lower security level.
Prerequisites:
Alice (server) has Bob’s (the client’s) username and password. A public
system key for Steak.
Variables:
Salt<i>: 64-bit integer
H<j>: 256-bit integer
PK<k>: 256-bit integer
CPK<k>: 256-bit integer
Functions:
Steak Steak encryption
SteakDecrypt Steak decryption
Zero(n): n bits of zeroes.
Concat(s,t): concatenation of bit strings s and t.
Legend
:= assignment
, statement separator
The result of a function is trashed if it is not assigned to a
variable.
Output:
Key: 256-bit integer
Success: True/False
Protocol:
1. Bob to Alice: Bob’s username
2.0a Alice: Salt1 := random
2. Alice to Bob: Salt1
3.0b Bob: Salt2 := random
3.1b Bob: PK1 := random
3.2b Bob: Initialize Steak, Steak(Salt1), Steak(Salt2),
Steak(Bob’s password)
3.3b Bob: H1 := Steak(Zero(256)), CPK1 := Steak(PK1)
3. Bob to Alice: Salt2, H1, CPK1
3.0a Alice: Initialize Steak, Steak(Salt1), Steak(Salt2),
Steak(Bob’s password)
3.1a Alice: if not (Steak(Zero(256)) = H1) then
exit with Success := False.
3.2a Alice: PK1 := SteakDecrypt(CPK1)
4.0a Alice: Salt3 := random
4. Alice to Bob: Salt3
5.0b Bob: Salt4 := random
5.1b Bob: PK2 := random
5.2b Bob: Initialize Steak, Steak(Salt3), Steak(Salt4),
Steak(Concat(Bob’s username,PK2))
5.3b Bob: H2 := Steak(Zero(256)), CPK2 := Steak(PK2)
5. Bob to Alice: Salt4, H2, CPK2
5.0a Alice: Initialize Steak, Steak(Salt3), Steak(Salt4),
Steak(Concat(Bob’s username,PK2))
5.1a Alice: if not (Steak(Zero(256)) = H2) then
exit with Success := False.
5.2a Alice: PK2 := SteakDecrypt(CPK2)
6.0 Both: Key := PK2, Success := True
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Quisquater <[EMAIL PROTECTED]>
Subject: Re: Shortened signatures
Date: Sat, 10 Feb 2001 14:38:17 +0100
Matt J wrote:
>
> Cryptonessie?
See http://cryptonessie.org
It is an European project the goal is to put forward a portfolio of
strong cryptographic primitives that has been obtained after an open
call and been evaluated using a transparent and open process.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: a exp b mod n
Date: Sat, 10 Feb 2001 13:24:27 GMT
In article <963465$p0o$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hi all!
> I wanted to test a method that should return a exp b mod n. I copied it
> from Bruce Schneier's Applied Cryptography. There are two such methods,
> that I used with "unsigned long"s in C++, but both return 0 if a and b
> get higher. n is a 32-bit prime number. Does anyone have some working
> code?
> THanks,
> Heinz
Um obviously you're new to computer science and math in general.
When you multiply two 32-bit numbers you get a 64-bit product. Obviously you
are losing information.
You have to write a multiple precision library (bigint type stuff).
I would read up on "Multiply-and-square" methods and "Montgomery reductions".
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Andreas Gunnarsson <[EMAIL PROTECTED]>
Crossposted-To: alt.hacker
Subject: Re: OverWrite freeware completely removes unwanted files from hard
Date: Sat, 10 Feb 2001 14:31:48 +0100
[talk.politics.crypto and alt.conspiracy removed from crossposting]
Tom St Denis wrote:
> I am a student in security and computer science. Could I see your source
> code? I want to learn how this stuff all works!
On Sat, 10 Feb 2001, Anthony Stephen Szopa wrote:
> Read the description in the Help Files at http://www.ciphile.com or
> the instructions with the OverWrite software and read the link that
> JA Malley posted.
I checked the web pages, but I can't find any description for how the
program ensures that the multiple overwrites actually take place. There
are several ways it could fail for a naive implementation:
- The OS may allocate new disk blocks when writing the patterns, leaving
the old data unaltered
- The OS may cache the writes, only actually writing the last pattern to
disk (or not even that if the file is removed afterwards)
- The SCSI controller may cache the writes
I'm interested in how you've solved this.
Andreas
--
Andreas Gunnarsson <[EMAIL PROTECTED]>
+46 31 7014268
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: NPC
Date: Sat, 10 Feb 2001 14:11:19 GMT
rosi wrote:
>
> Benjamin Goldberg wrote:
> >Peter Shugalev wrote:
> >>
> >
> >The knapsack problem is NP complete, but the most of the PKE systems
> >which use it are broken due to lattice attacks (their method of
> ^^^^^
>
> I do not think we are conclusive that 'it' is an NPc problem used.
The knapsack problem is NPC. Most PKE systems which try to use the
knapsack problem are flawed, due to the existance of practical attacks.
As Douglas A. Gwyn said:
"The design error seems to have been making an unwarranted assumption;
the idea as expressed was that the legitimate recipient would have to
solve an easy (superincreasing) knapsack problem, while the eavesdropper
would have to solve a hard knapsak problem. However, appearances were
deceiving, as it turned out that the eavesdropper's work was *not*
equivalent to solving a general knapsack."
> >transforming a hard problem into a PKE system is flawed). The only
> >knapsack-like system which isn't broken by lattice attack is NTRU.
>
> I seem to understand that NTRU tried to stay away from the word
> 'knapsack'. Just a quite incomplete observation.
This is for publicity reasons -- anything with the word knapsack in it
will have predjudice against it from the outset, because of how many
earlier knapsack systems were broken. I believe that NTRU does use the
knapsack problem, but unlike earlier knapsack systems, the size of
lattice required to break it would be infeasibly large.
> >I don't know of any other NPC problems which are used as ciphers.
> >Maybe someone else does?
>
> Again, I am a bit choosy here. I doubt if we are that keen on
> another as of now. One NPc is, based on the current state of the art,
> quite good enough.
> (Can be wrong, but c stands for complete)
True enough, but practically noone uses NTRU, afaik. Thus, we still
might want a PKE based on an *different* NPC problem -- something other
than knapsack.
Keep in mind that which crypto system is used depends on people getting
[or not getting] a warm-and-fuzzy-feelling. Noone feels WAFFy about
knapsack problems.
--
A solution in hand is worth two in the book.
------------------------------
Date: 10 Feb 2001 14:22:20 -0000
From: jungle <Use-Author-Address-Header@[127.1]>
Subject: Re: Scramdisk, CDR and Win-NT
Crossposted-To: alt.security.scramdisk
=====BEGIN PGP SIGNED MESSAGE=====
6 Feb 2001 in <Kd0g6.4797$[EMAIL PROTECTED]> Sam Simpson
[EMAIL PROTECTED]
wrote:
>
> As long as you accept that you can't 'write on the fly' to the disk,
no, I can't accept this ...
I'm using CD-R/W media for write to SD container on it without any problems,
and all files are NOT R/O as you are suggesting,
SD containers have been created on CD-R/W media directly,
and H/D did not been involved in this process ...
~~~
This PGP signature only certifies the sender and date of the message.
It implies no approval from the administrators of nym.alias.net.
Date: Sat Feb 10 14:22:14 2001 GMT
From: [EMAIL PROTECTED]
=====BEGIN PGP SIGNATURE=====
Version: 2.6.2
iQEVAwUBOoVOm05NDhYLYPHNAQFHVwf/Q7qTNedxUOmCv/LYGwJbBb/QImK3ejSC
59lvKGxjT8uL2v3iY6tEIX3Hqzprxexo57fTztk014sHZvvH8knAs5EOTip79Q1E
VhXPDKP5epDth6qn3gVbytwK7SykISR1OKfGK9AdQAo8fYxRSkDY267nM2SwCb1g
tkAWLUVqiy1/CQES9yN6wbU8U9c+bXLo8TVG18fjEZlqZ90t9VN+x0qxe1taOU1j
pf2/HPyouB2olizXv1mwC1TZvBbYJ0tgWRh+mxwSaya91QXvGWsWvraKvIoBebh5
UAddD4ZNTIoJ/P7WIyyjKBvXg2cNGO0XQuufYqFq1zGSw1VD7af0XQ==
=Vqrl
=====END PGP SIGNATURE=====
------------------------------
From: B. Wooster <[EMAIL PROTECTED]>
Subject: What is kerebos?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 10 Feb 2001 14:49:20 GMT
Can someone fill me in as to what Kerebos (Cerebos?)
security/encryption is? I'm sure others would be interested in
knowing, too.
Thanks.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Rijndael S-box derivation
Date: Sat, 10 Feb 2001 14:55:41 GMT
The multiplicative inverse of 0x02 (mod the polynomial 0x11b) is 0x8d.
(0x8d == 141).
The best way of calculating all the multiplicative inverses mod 0x11b is
to find a generator (3 is good and simple) and make two tables, "pow"
and "log", such that pow[a] = 3 ** a mod 0x11b, and log[3 ** a mod
0x11b] = a.
Then, using the fact that pow(log(a**-1)) == pow(-log(a)), you can get
the inverse (mod 0x11b) by takeing pow[255-log[a]]; The 255 is added
since you want to work with all positive numbers, and is harmless
because pow[255] = 1, so pow[255-log[a]] = pow(255)*pow(-log(a)).
To create the "pow" and "log" tables, a loop like the following will do:
for( i = 0, j = 1; i < 256; ++i ) {
pow[i] = j;
log[j] = i;
j ^= (j << 1) ^ ((j & 0x80) ? 0x11b : 0);
// The above line does j += 2j % 0x11b
// Or, equivilantly, j = j * 3 % 0x11b
}
To calculate the inverses, the following loop will do:
for( i = 0; i < 256; ++i ) {
inv[i] = i ? pow[255 - log[i]] : 0;
// the ?: is because 0 doesn't have an inverse.
}
And you said already know how to do the affine transformation.
If you choose to keep the log and pow tables for other things, keep in
mind that pow[0] = 1, pow[255] = 1, log[0] was never assigned to, and
log[1] had 0, then 255 assigned to it. There is no harm in log[1] being
255, but you might choose to assign 0 to it for some reason.
Why would you want to keep the log and pow tables? For ease of
multiplication mod 0x11b. Remember that if neither a nor b is 0, then
a*b == pow( log(a)+log(b) ). If you keep the tables, you can do:
#define gf_mul(a,b) ((a&&b) ? pow[ (log[a] + log[b]) % 255 ] : 0)
A widening conversion might be needed before the add if truncation might
occur.
--
A solution in hand is worth two in the book.
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: What is kerebos?
Date: Sat, 10 Feb 2001 15:03:57 -0000
The internet has a great feature called a 'search engine'. Typing Kerberos
into Google (http://www.google.com/search?q=kerberos ) gives a whole page of
directly links to extremely useful and pertinent information in respect of
your search term(s).
Welcome to the internet experience.
--
Regards,
Sam
http://www.scramdisk.clara.net/
B. Wooster <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Can someone fill me in as to what Kerebos (Cerebos?)
> security/encryption is? I'm sure others would be interested in
> knowing, too.
>
> Thanks.
>
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: Rijndael S-box derivation
Date: Sat, 10 Feb 2001 15:14:27 -0000
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> The multiplicative inverse of 0x02 (mod the polynomial 0x11b) is 0x8d.
> (0x8d == 141).
[snip]
> Why would you want to keep the log and pow tables? For ease of
> multiplication mod 0x11b. Remember that if neither a nor b is 0, then
> a*b == pow( log(a)+log(b) ). If you keep the tables, you can do:
> #define gf_mul(a,b) ((a&&b) ? pow[ (log[a] + log[b]) % 255 ] : 0)
It is also worth noting that mod (%) can be a high cost operation on some
processors.
There are several ways to avoid this operation, one being the use of a
double length table.
Brian Gladman
------------------------------
** 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
******************************
