Cryptography-Digest Digest #863, Volume #8 Fri, 8 Jan 99 02:13:02 EST
Contents:
Re: On the Generation of Pseudo-OTP ("Kevin G. Rhoads")
IEEE P1363 March Meeting Announcement (IEEE 1363)
Re: DES Hardware Implementation!! (Matthew Kwan)
Re: ScramDisk - password size - high ASCII (Brad Aisa)
Re: DES Hardware Implementation!! ("hapticz")
Call For Papers -- National Information Systems Security Conference (Program
Committee)
Re: coNP=NP Made Easier? (rosi)
Re: One-time pads not secure ? (NSA's Venona project) (Serge-Antoine Melanson)
Re: On leaving the 56-bit key length limitation (wtshaw)
Re: What is left to invent? (wtshaw)
Re: On leaving the 56-bit key length limitation ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: "Kevin G. Rhoads" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 07 Jan 1999 18:42:44 -0800
>>A transcendental constant does not have that, it is not
>>periodic.
>
>Is that always true? Someone a year ago claimed that it is not
>universally true.
Any number which exhibits finite repeating digit patterns (i.e.,
periodicity) when digit expanded in ANY number base
can be represented as the ratio of two integers (i.e, it is
a rational number). All transcendentals are irrational.
Therefore any number with a periodic (insert number base of one's
choice) digit expansion is NOT transcendental.
QED (with rigorous parts elided -- easiest is proof by construction,
showing how to construct a rational representation given the
repeating digit expansion. Should anyone truly be interested,
I can sketch those proof steps. [Only my bachelor's was in
theoretical math, I switched to EE/CS in grad. school])
--
Kevin G. Rhoads, Ph.D. (Linearity is a convenient fiction.)
[EMAIL PROTECTED]
[EMAIL PROTECTED]
------------------------------
From: IEEE 1363 <[EMAIL PROTECTED]>
Subject: IEEE P1363 March Meeting Announcement
Date: Thu, 07 Jan 1999 22:33:47 -0500
IEEE P1363 Working Group:
Standard Specifications for Public-Key Cryptography
MEETING NOTICE
Wednesday, March 17, 1999, 9:00am-5:00pm
Thursday, March 18, 1999, 9:00am-5:00pm
Friday, March 19, 1999, 9:00am-5:00pm
Omni Chicago Hotel
Chicago, Illinois, USA
This meeting of the P1363 working group, open to the public,
will review ballot comments on the IEEE P1363 document and
continue to assess contributions to the IEEE P1363a
addendum. Information Security Corp. is the meeting's host.
TENTATIVE AGENDA
Wednesday, March 17
1. Approval of agenda
2. Approval of minutes from previous meeting
3. Officers' reports
4. Ratification of November vote on electronic voting
procedures
5. Nomination procedures for new officers
6. Review of ballot comments
Thursday, March 18
6. Review of ballot comments (cont'd)
7. New P1363a contributions
8. Discussion of P1363a encryption and signature schemes
Friday, March 19
8. Discussion of P1363a encryption and signature schemes
(cont'd)
9. P1363a planning
10. Work assignments
11. Meeting schedule
There will be an IEEE meeting fee of $60 for the three days.
For more information, contact Burt Kaliski, the working
group's chair, at (781) 687-7057 or <[EMAIL PROTECTED]>.
Information on the standard is available through
http://grouper.ieee.org/groups/1363/. To join the working
group's electronic mailing list, send e-mail with the text
"subscribe stds-p1363" to <[EMAIL PROTECTED]>.
===========================================================
MEETING LOCATION
Omni Chicago
676 Michigan Ave.
Chicago, IL 60611
(312) 944-6664, fax (312) 266-3017
The Omni Chicago Hotel is on Michigan and Huron (about 5
blocks north of the Chicago river), roughly 1/4 of the way up
Chicago's "Magnificent Mile." It is surrounded by what is
arguably the finest shopping and heaviest concentration of
restaurants in the city.
We have reserved a block of 12 rooms until 2/16 at the
rate of $169/night.
http://www.omnihotels.com/scripts/hotel_set.asp?h_id=13
------------------------------
From: [EMAIL PROTECTED] (Matthew Kwan)
Subject: Re: DES Hardware Implementation!!
Date: 8 Jan 1999 14:48:56 +1100
[EMAIL PROTECTED] (Christof Paar) writes:
>Samer EL HAJJ ([EMAIL PROTECTED]) wrote:
>: Hello!
>: I'm working on the hardware inmplementation (with VHDL into an FPGA) of
>: DES decryption.
>: after many searh I did not find any publication or example about this
>: topic.
>:
>: Can anyone point me to some documentation on the subject?
>: Thanks in advance!!
>Please check our SAC '98 paper and Jens Kaps' MS Thesis, both of which
>can be found on our web page at:
>http://ece.wpi.edu/Research/crypt
Also, if you're interested in minimizing the number of gates needed to
implement the DES S-boxes, have a look at http://www.darkside.com.au/bitslice
I make no promises about the designs being faster, but they use fewer
gates.
mkwan
------------------------------
From: Brad Aisa <[EMAIL PROTECTED]>
Subject: Re: ScramDisk - password size - high ASCII
Date: Thu, 07 Jan 1999 21:32:25 -0500
Jim Rollins wrote:
> I understand that bigger is better, when it comes to passwords, and that
> the more random a password is the less successful a dictionary attack
> will be. For the moment however, let us forget the ease with which a
> short password could be calculated. My first question is, does the
> length of the password have any effect on the randomness of the encoded
> volume? Put another way, will a ScramDisk volume with a short password
> be any less subject to decryption than a volume with a long password? I
> believe the name for the type of attack I'm thinking of is
> cryptoanalysis, a direct attack upon the contents of the encoded file.
I cannot speak for ScramDisk in particular (though I have evaluated it,
and consider it and excellent product), however any serious
cryptographic system worth its salt :) either "hashes" or otherwise
scrambles its passwords, before using them as keys, or uses a cipher
whose ciphertext is relatively random with respect to any arbitrary
key.
However, one has to always presume the attacker has the algorithm, and
even if the key is hashed or salted, the attacker can perform the same
step. Therefore, the big problem with short keys, in an otherwise well
designed cryptographic system, is that a brute force attack that starts
with short keys will reach the specific short-ish key in a finite amount
of time, thus revealing your encrypted text. Oops. :)
So the key has to be of a minimum length, to thwart such a brute force
attack. I would hazard a guess that if one had to choose between a very
short, but fully random key, or a very long, but fairly unrandom key
(say, dictionary words), then the long key is probably more secure.
You might consider as a password strategy, to go for length, but in a
way that enables you to remember it (without being too obvious), while
also introducing an element of true randomness to confound simple
dictionary-phrase type attacks. If you embed the random elements
judiciously (or better: randomly :) ), then it would seem to be quite
resistant to any brute force attack.
--
Brad Aisa
[EMAIL PROTECTED]
"Laissez faire."
------------------------------
From: "hapticz" <[EMAIL PROTECTED]>
Subject: Re: DES Hardware Implementation!!
Date: Thu, 7 Jan 1999 23:00:53 -0500
Motorola made a 64 pin ceramic dip integrated circuit for just this purpose.
i only saw it in a motorola data book as recently as 1979
was to be used in 68000 systems and was directly addressable
probably was slow though! your newer approach will definitely be an
improvement
--
best regards
[EMAIL PROTECTED]
------------------------------
From: Program Committee <[EMAIL PROTECTED]>
Subject: Call For Papers -- National Information Systems Security Conference
Date: Thu, 07 Jan 1999 23:31:50 -0500
Reply-To: [EMAIL PROTECTED]
The National Information Systems Security Conference (NISSC) welcomes
papers, panels, and tutorials on all topics related to information
systems security. Our audience represents a broad range of information
security interests spanning government, industry, commercial, and
academic communities. Papers and panel discussions typically cover:
-- research and development for secure products and systems, presenting
the latest thinking and directions;
-- electronic commerce;
-- legal issues such as privacy, ethics, investigations, and
enforcement;
-- practical solutions for government, business and industry
information security concerns;
-- network security issues and solutions;
-- management activities to promote security in IT systems including
security planning, risk management, and awareness and training;
-- implementation, accreditation, and operation of secure systems in a
government, business, or industry environment;
-- international harmonization of security criteria and evaluation;
-- evaluation of products, systems and solutions against trust
criteria;
-- tutorials on security basics and advanced issues;
-- security issues dealing with rapidly changing information
technologies;
-- highlights from other security forums; and
-- implementing policy direction.
For more details see http://csrc.nist.gov/nissc/call.htm.
------------------------------
From: rosi <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: coNP=NP Made Easier?
Date: Thu, 07 Jan 1999 17:48:44 -0800
Matt Brubeck wrote:
> [snip]
>
> > Interesting typo or omission by M. et. al.
>
> When defining the class P, I often see references omit the exact
> definition of the algorithm or machine which must solve the problem in
> polynomial time. Strictly speaking, P is the class of problems solved in
> polynomial time by DETERMINISTIC TURING MACHINES. The "Handbook" failed to
> mention this. Apparently you were an unwitting victim of Menezes and
> company's editorial oversight.
>
Three things. First, you perhaps did not consider my other question.
That is if NDTM is real, NP problems can be solved in P time. But still,
according to 'P by DTM', P!=NP. That does not conflict with what I
tend to believe: NDTM solves a proper superset (again the assumption:
NDTM is _ever_ real). Adopting such a notion, P!=NP does not offer any
protection, which is not reconcilable with an NP-hard problem reducible
to a cryptographic problem can be secure. Secondly, either way one says
it, by DTM or by NDTM, coNP=NP is not affected. Once one side is P, the
bound for it is a decision point for deciding the complement problem.
Lastly, it is not simply a coNP?=NP thing. There is a bigger problem.
It is not which way we say something. Any way we try to comfort ourselves
gives us discomfort.
I want to make what I just said clear: 'tend to believe' only comes
after NDTM being real.
By the way, anybody can get in touch with Menezes and get what should
be the correct words?
I do not want to sound arrogant. At least at this point, I don't think
any book written so far can satisfy me pertaining to the issue currently
discussed. I say coNP=NP and I am going against God know what.
> Of course, you should have suspected the problem. Given your definition of
> P, it would be obvious that P=NP, and one of the most famous open problems
> of mathematics would be reduced to a triviality.
>
> rosi:
>
> >>> I here also commit my understanding of the definition.
> >>> As long as the problem is solvable in polynomial time,
> >>> it is be via DTM or NDTM, in P.
>
> Planar:
>
> >> And this is equivalent (for people who know the correct
> >> definition of P and NP) to claiming P = NP.
>
> rosi:
>
> > I guess you are also a complexity theory super guru. Show
> > us the equivalence, which would be your daily cup of tea.
> > The quote did not say the extra words you gave. I do not
> > have the habit of putting my stuff in other people's mouths.
>
> I don't claim to be a "guru," nor am I accusing you of misquoting anyone,
> but the definition given in "Handbook of Applied Cryptography" was not
> complete. This appears to be the source of the misunderstanding here.
> Through no fault of your own, you have been using an incorrect definition
> for P.
Matt, I sincerely welcome your opinion.
Taking M. et. al.'s verbatim, I do not even see a problem. We still
have to show (not as Ilias claimed 'trivial') coNP=NP. That is exactly
what I did. Maybe, to some other people when NDTM is real, it is trivial
that coNP=NP. Once one sees it, it is no longer too difficult. Once one
is given a concrete construction, it will not be too difficult for one
to see.
Assuming NDTM is real, whether P equals NP or not, as to complexity
theory, I think experts in complexity theory can say better than I do.
There is a couple of things I would like to mention. I hope you will
not find it offending.
1. You say it may take exp time. I think we agree that complexity
theory (some may give a quantifier such as 'conventional') is conerned
with the worst case scenario. The behaviour you descirbe which I believe
is the same as 26 which Ilias adopted is problematic, im my opinion.
It CAN blow any bound you put on it! This is so obvious and trivial in
my opinion that I did not think worthwhile to make it so explicit. I can
go to more details, but I think a brief look (in informal manner) suffices.
Since it is N.D., any bound you put on it, violates the preporty of N.D.
For obviously it becomes deterministic with any fixed bound. I may be wrong.
But the people who invented this and maintained this, took too much liberty,
in my opinion. It is not responsible if they realize this and do not do
anything to clean it up. Now, regardless of what bound, it should be
obvious that the worst case for using (a finite number of) such
mechanisms may not sovle NP problems in polynomial time. Then I think
we can go to the piece of homework I gave and give it a thought.
2. You were a bit loose as well. You said:
NP is obviously a superset of P ...
I think we need a proof. If you meant that it is your belief, it cam be
listened to as nother story.
>
> With that confusion cleared up, hopefully you can continue your argument
> using the same definitions as your colleagues.
>^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
I certainly can. But just wonder, why they can not use the ones I
use. For example, why can't we take M. et. al.'s verbatim? (I would not
mind taking any other). For another, why can't we take the notion of
infinite parallelism of NDTM?
One other thing I can not understand is: why it seems so easy to side
with those who denounce 'coNP=NP'? Why there always seems something wrong
with what I say? Why nobody, absolutely nobody said a single word when Ilias
claimed that NDTM simply exists and we need not see a construction of it.
Why no one so far has posted a single NDTM that solves (in a hypothetical
way) the NP problems? Well, bluffing that it somehow solves them can
deprive me from saying: when BluffBluff(S, i", n) < f(n), after f(n) we
can conclude i" is not a subset sum of S?
>
> Matt Brubeck
Thanks Matt. I hope you see something wrong, something terribly wrong.
--- (My Signature)
------------------------------
From: Serge-Antoine Melanson <[EMAIL PROTECTED]>
Subject: Re: One-time pads not secure ? (NSA's Venona project)
Date: Fri, 08 Jan 1999 00:13:52 -0500
Thanks for your kind answer. It's very surprising that the russians didn't find a
more efficient electronic mean to generate those pads.
/Serge-Antoine
Jerry Leichter wrote:
> | I once read in Bruce Schneier's "Applied Cryptography" that one-time
> | pads were un-breakable but I saw an article on CNN's web site
> | about NSA's VENONA project that seems to contradict this:
> |
>
>http://www.cnn.com/SPECIALS/cold.war/experience/spies/spy.gadgets/espionage/one-time.pad.html
> |
> | So did the russians used pseudo-random number generators to print
> | those pads or what? If those pads were breakable does it mean their
> | characters sequence was not truly random or generated using a
> | reproducible process?
>
> According to various published reports (particularly Spycatcher), the
> Russians apparently used human typists with some kind of protocol that
> generated excellent random pads. However, the volume of pads required
> eventually led to shortcuts. Two attacks resulted:
>
> 1. To cut down on the required number of pads, the Russians
> started re-using them, sending the same pad to two or
> even three different "channels" (military, intelligence,
> diplomatic). The Venona attack relied on collecting
> huge amounts of ciphertext and searching for such
> re-use. The effectiveness of this should serve as a
> warning about (a) the amount of effort an intelligence
> service is willing and able to apply when the potential
> value is high enough; (b) the power of the resulting
> brute force.
>
> 2. The human typists weren't really capable of producing
> truely random numbers, at least not when the demands
> got high enough. The result was that the pads had
> various internal correlations - e.g., some pairs of
> consecutive digits might be easier to type than
> others, hence more likely. While I've seen reports
> of such correlations, I don't recall seeing any
> reports about breaks that resulted from them (which of
> course says absolutely nothing about whether such
> breaks *did* occur.) It's a good guess that such
> correlations helped in the massive effort of the
> Venona project, though I haven't seen any indication
> of this.
> -- Jerry
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: On leaving the 56-bit key length limitation
Date: Thu, 07 Jan 1999 23:21:54 -0600
In article <[EMAIL PROTECTED]>,
> >
...
> Alpha text is especially bad as the odds of an ambiguous decryption being even
> vaguely of the form of text is vanishingly small. This allows the analyst to
> unambiguously reject all but a vanishingly small fraction of the ambiguous
> decryptions.
If you play your cards right, the analysist will throw out the part that
has the ture message.
--
If government can make someone answer a question as they want him to, they can make
him lie, then, punish him for not telling the truth. Such an outrage constitutes
entrapment.
In Base 81: y\7RBRNBN 6*1O+aDR* QBOMR1OhE \*/XtS4+~ ;g/4,Y=Jn 6)IL;OC;H o93bR?bk\
v+/G(J=lE Ni@8L*x)I L(!\+O6;E Hu~u;Ho;R 9lX=g3x*n :Y(Yce;w~ 3l(9kS;NT YfmnPX=ya
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: What is left to invent?
Date: Thu, 07 Jan 1999 23:19:00 -0600
In article <Ufcl2.104$[EMAIL PROTECTED]>, "Nick Payne"
<[EMAIL PROTECTED]> wrote:
> This reminds me of Lord Kelvin's pronouncement about a century ago that all
> of Physics had been discovered and all that was needed was a bit of tidying
> up around the edges...
>
If he had known what has gone on since, he would have cooled down somewhat
from making such a claim.
--
If government can make someone answer a question as they want him to, they can make
him lie, then, punish him for not telling the truth. Such an outrage constitutes
entrapment.
In Base 81: y\7RBRNBN 6*1O+aDR* QBOMR1OhE \*/XtS4+~ ;g/4,Y=Jn 6)IL;OC;H o93bR?bk\
v+/G(J=lE Ni@8L*x)I L(!\+O6;E Hu~u;Ho;R 9lX=g3x*n :Y(Yce;w~ 3l(9kS;NT YfmnPX=ya
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: On leaving the 56-bit key length limitation
Date: Fri, 08 Jan 1999 05:02:23 GMT
james.felling wrote:
> Another example if you are encrypting alphanumeric text
> then if one decryption is 'Dxc99OVq3 rzx$jP=W' and the other
> is 'Steal the plan now'. Both are valid decryptions, but
> I'll bet that the analyst will discard the former posiblity
> and believe that the message sent was 'Steal the plan now'
> Just because multiple decryptions exist does not mean that
> they will be multiple ambiguous decryptions.
That seems to imply a two-part test: a decryption is valid
if it's alphanumeric, but the analyst will reject it if it's
not sensible text.
In Shannon's model that doesn't happen. The probability
distribution of the message space (or the analyst's
estimate of it) is the sole criteria for grading candidate
decryptions. If 'Dxc99OVq3 rzx$jP=W' has negligable
probability, then it's not a valid decryption. If it has
significant probability, then the analyst will not reject
it.
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** 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
******************************
