Cryptography-Digest Digest #825, Volume #9 Fri, 2 Jul 99 21:13:03 EDT
Contents:
Re: Posting on sci.crypt.research ([EMAIL PROTECTED])
Re: How do you make RSA symmetrical? ([EMAIL PROTECTED])
Re: Posting on sci.crypt.research ([EMAIL PROTECTED])
Re: additive RNGs ([EMAIL PROTECTED])
Re: I don't trust my sysadmin (Scott Gifford)
Re: two questions (D. J. Bernstein)
Re: I don't trust my sysadmin (John Myre)
Re: How do you make RSA symmetrical? (David A Molnar)
Re: Quantum Computers (Anti-Spam)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Posting on sci.crypt.research
Date: Fri, 02 Jul 1999 21:22:38 GMT
In article <7lj2vf$k59$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> That or somebody created a 16-bit version of RC4.
Then they should not call it 'quantum email cryptor' or whatever they
called it. It's snake oil to me (no paper, no pseudo, no real claims,
3 strikes!!!)
BTW would RC4 with n-bit (n != 8) tables have weak keys like in the
normal 8-bit RC4?
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How do you make RSA symmetrical?
Date: Fri, 02 Jul 1999 21:18:03 GMT
In article <7litm5$bkk$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
> Not all 0s, just the leading ones.
>
> 0000000000000000011011 is the same as 11011 in the sense that
> they both have the same numerical value, but one has a lot of
> 0s in front and the other doesn't.
Oooh so that saves like what 5 bits on average? Big deal. I think
that this is moot since you don't normally try to compress ciphertext
anyways...
> Why do you think this is the halting problem ?
Cause I was confused... sorry... i just thought if you 'dump' the bits
you don't want decompressing would be hard (since there are no rules).
> The length could be quite short to store - say 2 = "10", while
> if you're referring to _all_ the zeroes and their positions,
> that might be large. My point is that it's plausible that
> one might have enough storage for the length, but not for
> the zeroes.
Unless you store the lenth how do you know the packet was not just
truncated?
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Posting on sci.crypt.research
Date: Fri, 02 Jul 1999 21:21:01 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> Under "e-mail encryption method", there is a posting of a patent
> application for a method of encryption that is supposed to give
> "perfect" security...
>
> and it uses a random table with 65,536 16-bit entries.
>
> Could someone be trying to steal Scott16u?
Well if it matters I wrote a method that uses four 16-bit tables
(requires 128*4 KB of ram...). Each table is a permutation and the 64-
bit block cipher had four rounds... I have the source if you want.
It's grossly inefficient (in terms of memory) but really fast...
Why would anyone copy scottu? The cipher posted is just a hoax though,
they have intel asm code at the bottom which a) is invalid and b)
includes false timings... The author just wanted to get the work out
as quickly as possible (hmm sounds like me :) except I never claim
perfect secrecy...)
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
Date: Thu, 01 Jul 1999 20:46:00 -0400
From: [EMAIL PROTECTED]
Subject: Re: additive RNGs
[EMAIL PROTECTED] wrote:
>
> In article <[EMAIL PROTECTED]>,
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> > If you're storing one bit per byte, which is the easiest way to
> > program such algorithms in C, this is almost the right approach.
> > However, you should use memmove(), not memcpy(), because the
> > latter can malfunction when the source and destination overlap.
>
> I am doing word sized elements (for brute force searching I am using
> byte size...)
>
> > > 2. What is the cycle length for various array sizes.
> >
> > It depends on the feedback function. Golomb's book "Shift
> > Register Sequences" (available from Aegean Park Press) is a
> > good introduction to this subject.
>
> Is there any specifics? I know that for these types there are two
> parameters for length it is a(2^n) where n is the word size in bits
> and 'a' is the multiplier. For example with (4, 1, 0) I got 7.5(2^n)
> with (7, 1, 0) I got 63.5(2^n)... etc...
>
> > > 3. Are all LFSR polynomials good for this type of RNG?
> >
> > No, for maximal period the characteristic polynomial must be
> > irreducible, and unless 2^n-1 (n = # stages) is prime, not
> > all irreducible polynomials yield maximal period. This is
> > covered in Golomb section 3.4.
>
> Well I don't have the book so can you spare me a bit. Max period in
> these though is (2^n)-1 which is fairly easy to obtain with the LFSR
> registers I have tested (note 5, 2, 0 doesn't work and I don't know
> why!)
For tiny LFSRs you can use a spread sheet to inspect each state of the
cycle. This works up to about 12 bits. 6 bits you can do by hand.
>
> > > 4. The additive generator is linear? Is it at least statistical
> > > sound?
> >
> > Whatever that means. Golomb discusses the "randomness" properties.
> > He also has a lot about nonlinear feedback shift registers.
>
> Well is the output at least balanced between 0 and (2^n)-1? Are there
> odd/even characteristics (as in the LCG)? etc...
>
> Tom
> --
> PGP key is at:
> 'http://mypage.goplay.com/tomstdenis/key.pgp'.
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
------------------------------
Crossposted-To: comp.unix.security
Subject: Re: I don't trust my sysadmin
From: Scott Gifford <[EMAIL PROTECTED]>
Date: 02 Jul 1999 18:29:18 -0400
[ I have crossposted this to comp.unix.security, where you may find a
better answer. ]
If the password is stored in a place where Cron can read it, then the
sysadmin will be able to read it also. If this sysadmin is malicious
instead of just nosy, and has the time to do it, they have access to
your keystrokes, and to the memory of any programs you are running.
This makes it very close to impossible to do what you want to.
My recommendation would be to hire a sysadmin that you trust. :-)
=====Scott.
"David N. Murray" <[EMAIL PROTECTED]> writes:
> I'm not sure I presented my problem correctly.
>
> I have a completely automated process (e.g. a cron job)
> that needs to connect to a DBMS (e.g. Oracle). The DBMS
> requires a username and password to connect to the database
> in order to do any meaningful work.
>
> If I were to use a form of trusted access (implemented by
> the DBMS), then the sysadmin could simply login as that
> user. Instead, I configure the DBMS to accept uname/password
> and have the program login that way.
>
> How do I protect the uname/password that the app needs to
> connect with?
>
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: two questions
Date: 2 Jul 1999 23:12:17 GMT
A typical high-security stream cipher expands a 256-bit key into 2^71
bits of hard-to-predict, randomly accessible output---namely, 128 bits
of output for each of 2^64 possible counters.
A typical high-security block cipher expands a 256-bit key into 2^135
bits of hard-to-predict, randomly accessible output---namely, 128 bits
of output for each of 2^128 possible inputs---with the frivolous
additional constraint of invertibility.
So it's hardly a surprise that stream ciphers are faster. Your favorite
128-bit block cipher wouldn't need as many rounds if the cryptanalyst
were forced to use inputs that ended with 64 zeros and weren't allowed
to apply the inverse function; well, that's exactly what happens if you
run the cipher in 64-bit counter mode and call it a ``stream cipher.''
Harvey Rook <[EMAIL PROTECTED]> wrote:
> Stream ciphers have two inherent security holes that require extra
> work to plug.
Block ciphers have the same problems. They do not guarantee message
integrity. They do not prevent replay attacks. They leak information
when they are used for more than one message.
The standard solutions are the same for both block ciphers and stream
ciphers: use a message authentication code, attach a message number, and
make the encryption depend in a sensible way on the message number.
---Dan
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: I don't trust my sysadmin
Date: Fri, 02 Jul 1999 16:39:32 -0600
"David N. Murray" wrote:
>
> I'm not sure I presented my problem correctly.
I think you did. Sometimes people don't read well.
> I have a completely automated process (e.g. a cron job)
> that needs to connect to a DBMS (e.g. Oracle). The DBMS
> requires a username and password to connect to the database
> in order to do any meaningful work.
Understood.
> If I were to use a form of trusted access (implemented by
> the DBMS), then the sysadmin could simply login as that
> user. Instead, I configure the DBMS to accept uname/password
> and have the program login that way.
OK.
> How do I protect the uname/password that the app needs to
> connect with?
>
> Thanks again,
> Dave
You were correct in your original post - there is *no way* to
prevent someone with unlimited access to machine "A" from finding
out everything that machine "A" knows. This is, I presume, an
accurate description of your sysadmin. And since the job is
automated, your machine "knows" whatever it takes to log on to
the database, so it cannot be made secure against the sysadmin.
(I will ignore the possibility that the machine provides
the ability to hide things from the sysadmin. Multilevel
secure operating systems do exist - within the constraints
that any large software system probably has bugs - but I'd
be shocked if you were using one. The validation process
is so slow and expensive that it is a very limited market.)
Do you need to be able to "prove", in some legal sense, that
the sysadmin cannot access the database? Or do you want a
little less - that you (or rather, those at your organization
who are responsible) accept it is sufficiently "unlikely" that
the sysadmin will access the database?
I do not think you can do the former. The latter could perhaps
be accomplished with obfuscation, or steganography. That is
to say, you can't stop the sysadmin if he is bright enough,
or determined enough (if nothing else, he can probably snoop
on the network traffic!). But maybe you can make it hard
enough that it "isn't worth the trouble".
Your example of encrypting the password, and only decrypting it
at login time, is a good example. Yes, plainly the sysadmin
can discover the algorithm and the key used to decrypt the
password, because of course those things are on your machine.
But at least it's a practical roadblock; maybe the sysadmin
isn't "smart enough" to realize what you've done.
So in that spirit, here are a few more ideas. Maybe one or more
might even be worth using.
First, you could invoke the job from within a compiled program,
rather than from a script. At least that way the information
won't be sitting there in ASCII where it's obvious what it is.
You could consider changing the password really often, maybe
in some automated way, so that at least the sysadmin would have
to access your machine directly each time he wanted to break
in. If you log accesses to your machine (even by sysadmin's),
maybe this might reveal nefarious activity, even if it doesn't
prevent it. If the password automatically changes every time
you log in, and you ask for (and store) the new password as
part of the job, then if the sysadmin accesses the database
with your username and password, he probably won't realize that
there is now a new password needed, and he won't get in again.
Of course, neither will your program - but at least you have
detected the intrusion.
You could consider trying to lay some false clues. For instance,
you could have a script, with a username and password, that calls
some do-nothing program as if it were your job. Then the script
invokes something like "log" or "cleanup" or something that is
the real job, and hides the username/password.
Hmm - here's a question. Does the automated job in question
actually have to have access to the Oracle database that could
be dangerous? What if, instead, the only thing your machine
could do (using the automated username/password) was to add some
information to a log. Then some *other* action causes that
information to perform the sensitive operations. Oracle has the
ability to do things based on time, or it could trigger off the
addition of the log itself. It could be worth the trouble to
require the log to obey certain restrictions of form, so that
even if the sysadmin managed to get access to the database the
only thing he could do is roughly the same thing your job does
anyway (but perhaps with false data).
How about this? What if the Oracle database knows when your
machine is supposed to report, and only activates the account
at that time? Of course the sysadmin could realize this, but
on the other hand, maybe he won't.
Here's another one. What if the only thing your automated
username/password had access to was an Oracle procedure that
returned a temporary username and password that was good for
the access your program needs - for minute or so? It could
even return the username and password in and obfuscated form
(say, ROT13, or something easy to do in PL/SQL). If the
sysadmin doesn't go to the trouble of disassembling your
program, then he won't realize what's going on.
Well, my imagination is getting tired, and besides, it's time
for the holiday.
Good luck -
John M.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: How do you make RSA symmetrical?
Date: 3 Jul 1999 00:02:00 GMT
[EMAIL PROTECTED] wrote:
> In article <7litm5$bkk$[EMAIL PROTECTED]>,
> David A Molnar <[EMAIL PROTECTED]> wrote:
>> Not all 0s, just the leading ones.
>>
>> 0000000000000000011011 is the same as 11011 in the sense that
>> they both have the same numerical value, but one has a lot of
>> 0s in front and the other doesn't.
> Oooh so that saves like what 5 bits on average? Big deal. I think
> that this is moot since you don't normally try to compress ciphertext
> anyways...
I think the context is more along the lines of having a fixed-width
register or area in memory. Say you have a chip with 32 bits
in each register. If you add two numbers and get a 20-bit number,
the other 12 bits have to be set to _something_.
This originally came up as a padding question, right ? The point
was that you always "pad" a number when you exponentiate it,
in the sense that you can think of the number with lots of leading
0s.
Then we can figure out better padding methods. :-)
>> Why do you think this is the halting problem ?
> Cause I was confused... sorry... i just thought if you 'dump' the bits
> you don't want decompressing would be hard (since there are no rules).
No problem. and I don't see any good way to get the bits back either.
>> The length could be quite short to store - say 2 = "10", while
>> if you're referring to _all_ the zeroes and their positions,
>> that might be large. My point is that it's plausible that
>> one might have enough storage for the length, but not for
>> the zeroes.
> Unless you store the lenth how do you know the packet was not just
> truncated?
Unless there's something else telling you (like the design of the
system), you don't.
I'm sorry - in this paragraph I was referring to all the
0s in a number, like
100101110101010
^^ ^ ^ ^ ^ ^
i
and my point was that it's possible that you _would_ have
enough space to store the length, but not enough to
store the 0s. this of course would mean you couldn't
use a number that size, since as you noted above,
there doesn't seem to be any good way to get back
to the original number.
-David
------------------------------
Date: Fri, 02 Jul 1999 17:16:08 -0700
From: Anti-Spam <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
Greg Ofiesh wrote:
>
> > If we use cryptosystems "orthogonal" or independent of those
> > QC-acceptable algorithms attacks, then our cryptosystems are immune.
> > QCs pose no threat if we are careful.
>
> So, would you say that either DLP or ECDLP problems are immune from
> QCs? How about the idea that QCs once developed sufficiently can
> perform massive parallel computations? Then does any algorithm appear
> immune to a QC? Just want to get your feel on this.
>
Well, to the best of my knowledge (from reading that book, papers at the
LLNL on-line, and various web sites devoted to QC), there are only 7 QC
algorithms:
one for a True Statement Problem
three different algorithms for Factoring Integers
one for Database Searching
one for estimating the Mean of a sample set
one for estimating the Median of a sample set
Cryptosystems based on modulo arithimetic and large integers formed by
multiplying two large primes are (pardon the pun) prime candidates for
cryptanalysis by a QC running one of the Factoring Integers algorithms.
Rapid database queries (looking for an entry that matches the conditions
defined by the search parameters) could be used to speed up searches for
correlations in ciphertext across numerous inercepted and indexed
encrypted messages, or for spotting correlations in PRNG output or
streaming ciphertext (a hunch on my part, but seems reasonable. Both
are nice research projects.) Estimates of the Mean or Median of a sample
set could also be used to speed up crytanalysis of streaming ciphertext
or cryptosystems that use PRNGs (another hunch, I haven't worked on this
yet, but these statistics will/should be different for PRNG output
verses a true RNG output, and that's why I think there's some merit to
using QCs to analyize such systems.)
The truth assigment problem is trying to find a true statement in a list
of two statements. A gedanken experiment with limited engineering
application.
What's very interesting is that Richard Jozsa showed that that many
functions, such as the SAT problem (the propositional satisfiability
problem) cannot be computed by QCs (due to the quantum parallelism) at
all. Now, here's the great part! If we can show that the cryptanalysis
of a cryptosystem is mathematically eqivalent (by some linear
transformation) to answering the SAT problem, then we can use Mr.
Jozsa's results to prove that our cryptosystem is secure against this QC
assault. I have a hunch that differential cryptanalysis mathematics
might be mappable to a boolean equation whose truth or falsehood given
assigned values to its variables leads to the plaintext most likely
encoded by the cryptosystem. (This is an attack on block ciphers.)
Since a QC cannot solve the SAT problem, a QC could not attack the
cryptosystem in this manner. However, I'm ignoring the side/orthogonal
issue of the RNG used in that cryptosystem which could be attacked by
other QC means, as previously described hunches above, and possible
reveal the keys used in the cryptosystem (I'm assuming the attacker has
state info or other data on the PRNG used in lieu of a true RNG.)
What are others thoughts on these potential applications?
[EMAIL PROTECTED]
------------------------------
** 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
******************************
