Re: Passport Passwords Stored in Plaintext
- Original Message - From: "bernie" <[EMAIL PROTECTED]> > Some of the people here wants to use the .NET for critical applications. I'm sorry. > How secure is the .NET? The short answer is that it isn't secure. There are two main problems with it being secure. The first is the password vulnerability that you replied to. The second is that it uses a custom blended Kerberos-esque implementation. I say Kerberos-esque because it has some significant problems. First it uses RC4, a cipher which is increasingly being considered insecure, and in using it windows doesn't take the precautions necessary to make it secure. They are the only company foolish enough to have embedded access control information in the kerberos ticket, this adds even more leaking information, and just enough of it to determine the users password. Basicly they have made nearly every effort to eliminate the security of the system while making it appear secure to a layman. For further evidence that Microsoft can't do anything secure I point to (in no particular order) IIS, pptp, pptp2, Internet Explorer, Outlook Express, Windows 95, Windows98, WindowsME, WindowsNT, Windows2000, and while I haven't verified it yet I believe also WindowsXP. Some of these probably need some explaination, IIS is the script kiddie choice it has more holes than a pound of Swiss cheese. pptp was severely broken, pptp2 was slightly less severely broken. Internet Explorer has had so many security vulnerabilities I can't even count that high. Outlook Express is a virus writers dream. Windows95 offered no security, same with 98 and ME. WindowsNT is subject to extremely basic attacks on the password system that Microsoft refused to recognise, same with 2000, and probably the same with XP. In 2000 MS introduced a "secure" encrypted filesystem which lacked any reasonable ability to encrypt documents securely (it put the keys in a file in plaintext, the file is easily readable). Even the cryptoAPI that Microsoft designed and offered has holes in it, allowing arbitrary code to be run in the place of what the programmer intended. I am unaware of anything microsoft has ever written that could be considered secure and there is evidence that they plan to continue this less than stellar performance with .NET. Joe - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: authentication protocols
- Original Message - From: "John Saylor" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Monday, March 25, 2002 3:14 PM Subject: authentication protocols > I'd like to find an authentication protocol that fits my needs: > 1. 2 [automated] parties > 2. no trusted 3rd party intemediary ['Trent' in _Applied_Crypto_] Depending on your exact requirements, there are many potential options. Let's start with the most basic: The parties securely exchange a verifier. There are many variations at this point, but the basic version is (with details omitted for brevity): A->B: I am A B->A: If you are A then you can decrypt this E(K) and use K as our shared key A decrypts and now both A and B share a one time secret This is generally done using symmetric keys More sophisticated, and scaling much better requires a trust model of some kind. This does however get very tricky. There has to be some verification of the key by a 3rd party (which can typically be the same as one of the first 2 parties). However it is possible to build something usable, as long as on one occasion you can verify the identity of the other party. This type of protocol works approximately as so: B has a verified public key for A A has a verified public key for B A->B: S(I am A, our temporary key is E(K), the current time is T) B verifies signature, and decrypts K, K is now the shared secret There are of course variations where it is E(S(K...)) instead of S(...E(K)...) There are many different variations on this, some patented, some unencumbered, some that are secure down to the use a an ATM-like PIN, some that require larger quantities of secret data, some that take 1 pass from A to B, some that take 10 passes between them, some that have nice provable reductions, some that don't. It all depends on what your needs are. But all of these require some trust model, and initial verification of the key is the problem. Moving over to situations where you are not forced to perform an initial key verification requires a trusted 3rd party, which is what you requested to avoid so I won't introduce them. Joe - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: building a true RNG (was: Quantum Computing ...)
- Original Message -
From: "Eugen Leitl" <[EMAIL PROTECTED]>
Subject: Re: building a true RNG (was: Quantum Computing ...)
> I've got a framegrabber with a 640x480 24 bit/pixel camera. It doesn't
> compress, is rather noisy, and since self-adjusting I get the maximum
> entropy at maximum darkness.
> Is there any point in compressing the video before running it through a
> cryptohash?
It will not serve a cryptographic use, however if you can find a fast enough
truly lossless compressor it can be very useful. Since I assume you'll be
taking a picture purely in the dark a usable compressor would be (please
pardon the severely abused pseduo-code)
SHA1 pool
on_pixel
{
if pixel is not black
SHA1_update(pool, pixel, pixel coordinates);
}
get_random()
{
SHA1 temp
SHA1_update(pool, "1")
temp = SHA1_duplicate(pool)
return SHA1_finalize(temp)
}
> How does e.g. SHA-1 fare with very sparse bitvectors?
It is believed to fare quite well, and considering that the line for proper
entropy distillation is actually well below the line for cryptographic
security SHA-1 is likely to remain very good for this purpose. If you are
more concerned about speed than maximum entropy containment (or require less
than 128-bits of entropy) you might also consider MD5. If you are extremely
concerned about this (and are willing to lose a few other desirable
behaviors) it is possible to use a block cipher, basically in CBC mode, to
accumulate entropy, this has the advantage that under some reduced
assumptions it is possible to compute the maximal entropy of the state at a
given time.
Joe
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: building a true RNG
- Original Message - From: "John S. Denker" <[EMAIL PROTECTED]> To: "David Honig" <[EMAIL PROTECTED]> Cc: <[EMAIL PROTECTED]>; "'Hannes R. Boehm'" <[EMAIL PROTECTED]>; "'Ian Hill'" <[EMAIL PROTECTED]>; <[EMAIL PROTECTED]> Sent: Saturday, July 27, 2002 10:52 AM Subject: Re: building a true RNG > I wrote: > > > a) if the hash function happens to have a property I call "no > > >wasted entropy" then the whitening stage is superfluous (and > > >you may decide to classify the hash as "non-simple"); I disagree. The whitening stage can perform a very important step of allowing for stretching of the entropy. Ideally a true RNG would be fast enough to supply all our needs, but that typically doesn't happen. Instead we have to depend on stretching tricks, basically using a primitive in counter mode, to stretch the bits we have as far as is needed. This can be combined with the distillation stage itself by inserting a fixed string, copying the state, and finishing the calculation, but can conceptually be thought of as a seperate stage. > David Honig responded: > > Not wasting entropy does not mean that a function's output > > is "white" ie uniformly distributed. E.g., a function > > which doubles every bit: 0->00, 1->11 preserves total > > entropy but does not produce uniformly distributed output. > > (It also reduces entropy/symbol.) > > That's a red-herring tangent. I'm not talking about any old > function that doesn't waste entropy; I'm talking about a > !!hash!! function that doesn't waste entropy. A construct that simply does not exist, more on this later. > And remember: in addition to having a non-entropy-wasting hash > function, we are also required to saturate its input. Then we can > conclude that the output is white to a very high degree, as > quantitatively discussed in the paper. > > > The simple-hash's --lets call it a digest-- function is to increase the > > entropy/symbol > > by *reducing* the number of symbols while preserving *total* entropy. I seperated this because I agree with teh statement completely, that is the one and only function of the distilling function, whether it is a hash, a cipher, or a miracle construct. > > Total entropy is preserved in the non-saturated regime. This is > documented in upper rows of the table: > http://www.monmouth.com/~jsd/turbid/paper/turbid.htm#tab-saturation I disagree. There are several ways of viewing the problem. Modelling the distillation function as a perfect entropy smoother over k bits (other than that I will be assuming a worst case). We see the following happen: When the first bit is inserted, each of the k bits receives 1/k entropy When the second bit of entropy is inserted one of those bits received 1 bit of entropy, the entire system now has 1 + (k-1)/k bits of entropy, already there is a small but measurable discrepancy Each bit now has (2k-1)/k bits of entropy The third bit results in 1 of the k bits having entropy 1 giving 1+ ((2k-1)/k)(k-1)/k bits of entropy in total While the system slowly loses entropy, it does lose entropy. It's also worth noting that this agrees with the presented analysis at 3 points, 0 has 0 entropy, 1 has 1-bit of entropy, and inf has k bits, but that for all useful lengths having k bits of entropy can never occur. > In the saturated regime, some entropy is necessarily lost. This is > documented in the lower rows of the table. This is only a small > percentage, but it is mandatory. I don't consider this to be "wasted" > entropy; I consider it entropy well spent. That is, these are > necessary hash collisions, as opposed to unnecessary ones. These don't even have to be hash collisions, it is possible for the hash function to discard entropy simply through its behavior, as in my example where entropy starts being discarded beginning with the second bit. From a theoretic standpoint, it is entirely possible that a function exists that discards entropy beginning with the first bit. > > A function like xor(bit N, bit N+1) which halves the number of bits > > can do this. While its output is whiter than its input, its output > > will not be perfectly white unless its input was. This statement is true of all deterministic algorithms. In fact it it one of the points where all presented models agree, you cannot reach a completely entropic state until you reach infinite lengths for the input. If the input if purely entropic there is some grey area surrounding this, but for a hash function to be secure the grey area disappears. > > Two scenarios where SHA is contraindicated came up: > > 1. hardware > > 2. interrupt handlers > > > > Sometimes a hardware RNG will feed raw data into a crypto-WEAK analogue of > > SHA, > > ie a LFSR which does the bit-reduction and mixing functions, > > but doesn't mix as well as SHA. (LFSR are hardware-friendly) Separating > > the bit-reduction from the mixing can be useful for analyzing what's > > really going on. > > Well, I tend to agree that systems that separa
Re: deterministic primality test
[I've got some doubts about the content here but I think the
discussion is certainly on charter --Perry]
Since I have received a number of private replies all saying approximately
the same thing; lookup for small n, use algo for large. Allow me to extend
my observation.
To quote myself from earlier:
> 1: if (n is of the form a^b, b>1) output COMPOSITE;
> 2: r=2
> 3: while(r < n) {
> 4:if(gcd(n,r)=/=1) output COMPOSITE;
> 5:if(r is prime)
> 6:let q be the largest prime factor of r-1;
n = prime number > 2
1: n is not of the form (we already know it is prime)
2: r=2
3: 2 < 3
4: gcd = 1 (since N is prime)
5: 2 is prime
6: q = ?
r=2
q = largest prime factor of (2-1) = largest prime factor of 1. 1 has no
prime factors, since 1 is by definition not prime, but has no integer
divisors except 1.
So the algorithm cannot be executed on any prime value with the exception of
2 (which it correctly states is prime). It is possible that the algorithm is
simply incomplete. The apparent intension is:
6: if(r == 2) q = 1;
else q is the largest prime factor of r-1
A few additional observations under the assumption that this is the desired
statement:
The algorithm is equivalent to (I've left the numbering for the original
instruction order:
1: if (n is of the form a^b, b>1) output COMPOSITE;
2: r=2
3: while(r < n) {
5:if(r is prime)
4:if(gcd(n,r)=/=1) output COMPOSITE;
6: if(r == 2) q = 1;
else q is the largest prime factor of r-1
7.if(q >= 4sqrt(r)log(n)) and (n^((r-1)/q) =/= 1 (mod r))
8break
9:r <-r+1
proving this is trivial. Since r is being stepped sequentially the only new
results will occur when r is prime (otherwise gcd is not dependable), this
will reduce the number of calls to gcd, and so reduce the asymptotic time.
This is obviously bounded by the time it takes to check if r is prime.
However note that we can now replace it conceptually with, without changing
anything:
1: if (n is of the form a^b, b>1) output COMPOSITE;
2: r=2
3: while(r < n) {
4:if(gcd(n,r)=/=1) output COMPOSITE;
6: if(r == 2) q = 1;
else q is the largest prime factor of r-1
7.if(q >= 4sqrt(r)log(n)) and (n^((r-1)/q) =/= 1 (mod r))
8break
9-2:r <-nextprime(r)
The asymptotic time is now bounded primarily by the runningtime of
nextprime(), the current best running time for this is not polynomial (but
there are better ways than their step by 1, prime check method). In fact
assuming that the outer while loop is the primary exit point (which is
certainly true for the worst case), the algorithm presented takes O(n) time
(assuming binary notation, where n is the function input n), this is
equvalent to the convential notation O(2^m), where m is the length of the
input. The best case is entirely different. Best case running time is
O(gcd()), which is polynomial. Their claim of polynomial running time is
certainly suspect. And over the course of the entire algorithm, the actual
running time is limited by a function I've dubbed listAllPrimesLessThan(n),
which is well studied and the output has exponential length, making such a
function strictly exponential.
Additionally it has been noted that certain composite values may pass the
test, regardless of the claim of perfection. It is unlikely that this
function is of much use.
Joe
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Seth on TCPA at Defcon/Usenix
- Original Message - From: "AARG! Anonymous" <[EMAIL PROTECTED]> [brief description of Document Revocation List] >Seth's scheme doesn't rely on TCPA/Palladium. Actually it does, in order to make it valuable. Without a hardware assist, the attack works like this: Hack your software (which is in many ways almost trivial) to reveal it's private key. Watch the protocol. Decrypt protocol Grab decryption key use decryption key problem solved With hardware assist, trusted software, and a trusted execution environment it (doesn't) work like this: Hack you software. DOH! the software won't run revert back to the stored software. Hack the hardware (extremely difficult). Virtualize the hardware at a second layer, using the grabbed private key Hack the software Watch the protocol. Decrypt protocol Grab decryption key use decryption key Once the file is released the server revokes all trust in your client, effectively removing all files from your computer that you have not decrypted yet problem solved? only for valuable files Of course if you could find some way to disguise which source was hacked, things change. Now about the claim that MS Word would not have this "feature." It almost certainly would. The reason being that business customers are of particular interest to MS, since they supply a large portion of the money for Word (and everything else). Businesses would want to be able to configure their network in such a way that critical business information couldn't be leaked to the outside world. Of course this removes the advertising path of conveniently leaking carefully constructed documents to the world, but for many companies that is a trivial loss. Joe - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Overcoming the potential downside of TCPA
Lately on both of these lists there has been quite some discussion about TCPA and Palladium, the good, the bad, the ugly, and the anonymous. :) However there is something that is very much worth noting, at least about TCPA. There is nothing stopping a virtualized version being created. There is nothing that stops say VMWare from synthesizing a system view that includes a virtual TCPA component. This makes it possible to (if desired) remove all cryptographic protection. Of course such a software would need to be sold as a "development tool" but we all know what would happen. Tools like VMWare have been developed by others, and as I recall didn't take all that long to do. As such they can be anonymously distributed, and can almost certainly be stored entirely on a boot CD, using the floppy drive to store the keys (although floppy drives are no longer a "cool" thing to have in a system), boot from the CD, it runs a small kernel that virtualizes and allows debugging of the TPM/TSS which allows the viewing, copying and replacement of private keys on demand. Of course this is likely to quickly become illegal, or may already, but that doesn't stop the possibility of creating such a system. For details on how to create this virtualized TCPA please refer to the TCPA spec. Joe - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Overcoming the potential downside of TCPA
- Original Message - From: "Ben Laurie" <[EMAIL PROTECTED]> > Joseph Ashwood wrote: > > There is nothing stopping a virtualized version being created. > What prevents this from being useful is the lack of an appropriate > certificate for the private key in the TPM. Actually that does nothing to stop it. Because of the construction of TCPA, the private keys are registered _after_ the owner receives the computer, this is the window of opportunity against that as well. The worst case for cost of this is to purchase an additional motherboard (IIRC Fry's has them as low as $50), giving the ability to present a purchase. The virtual-private key is then created, and registered using the credentials borrowed from the second motherboard. Since TCPA doesn't allow for direct remote queries against the hardware, the virtual system will actually have first shot at the incoming data. That's the worst case. The expected case; you pay a small registration fee claiming that you "accidentally" wiped your TCPA. The best case, you claim you "accidentally" wiped your TCPA, they charge you nothing to remove the record of your old TCPA, and replace it with your new (virtualized) TCPA. So at worst this will cost $50. Once you've got a virtual setup, that virtual setup (with all its associated purchased rights) can be replicated across an unlimited number of computers. The important part for this, is that TCPA has no key until it has an owner, and the owner can wipe the TCPA at any time. From what I can tell this was designed for resale of components, but is perfectly suitable as a point of attack. Joe - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Re: Overcoming the potential downside of TCPA
- Original Message - From: "Ben Laurie" <[EMAIL PROTECTED]> > > The important part for this, is that TCPA has no key until it has an owner, > > and the owner can wipe the TCPA at any time. From what I can tell this was > > designed for resale of components, but is perfectly suitable as a point of > > attack. > > If this is true, I'm really happy about it, and I agree it would allow > virtualisation. I'm pretty sure it won't be for Palladium, but I don't > know about TCPA - certainly it fits the bill for what TCPA is supposed > to do. I certainly don't believe many people to believe me simply because I say it is so. Instead I'll supply a link to the authority of TCPA, the 1.1b specification, it is available at http://www.trustedcomputing.org/docs/main%20v1_1b.pdf . There are other documents, unfortunately the main spec gives substantial leeway, and I haven't had time to read the others (I haven't fully digested the main spec yet either). From that spec, all 332 pages of it, I encourage everyone that wants to decide for themselves to read the spec. If you reach different conclusions than I have, feel free to comment, I'm sure there are many people on these lists that would be interested in justification for either position. Personally, I believe I've processed enough of the spec to state that TCPA is a tool, and like any tool it has both positive and negative aspects. Provided the requirement to be able to turn it off (and for my preference they should add a requirement that the motherboard continue functioning even under the condition that the TCPA module(s) is/are physically removed from the board). The current spec though does seem to have a bend towards being as advertised, being primarily a tool for the user. Whether this will remain in the version 2.0 that is in the works, I cannot say as I have no access to it, although if someone is listening with an NDA nearby, I'd be more than happy to review it. Joe - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: TCPA not virtualizable during ownership change (Re: Overcoming the potential downside of TCPA)
This is going to be a very long, and very boring message. But it should highlight why we have differing opinions about so very many capabilities of the TCPA system. For the sake of attempting to avoid supplying too little information, I have simply searched for the term and will make comments on each location that it appears. - Original Message - From: "Adam Back" <[EMAIL PROTECTED]> > Phew... the document is certainly tortuous, and has a large number of > similarly and confusingly named credentials, certificates and keys, > however from what I can tell this is what is going on: I wholeheartedly agree. 332 pages to say 5 pages worth of real information is not helpful. > > Summary: I think the endorsement key and it's hardware manufacturers > certificate is generated at manufacture and is not allowed to be > changed. [Search criteria "endorsement"] While I haven't found any solid evidence either way, they seem to almost deliberately avoid that discussion on Page 22 I found a fatal errorcode TCPA_NO_ENDORSEMENT at TCPA_BASE+35 "The TPM does not a EK installed" attempting to interpret the bad grammar, I believe this should state "The TPM does not [have] an [Endorsement Key] installed" which seems to indicate that the platform may ship without one. On page 35 the endorsement key is listed as persistent data. Which at first would indicate that the endorsement key happens before shipping, but since there is also an RNG state variable stored persistently, my confidence in this is undermined. Adding to the complications, down near the end of the page, in the table it says "This is the TPM's endorsement key pair. See 9.2. The default value is manufacturer-specific" which indicates that it does ship with an endorsement key, but that the key can be changed by the owner. Page 38, the existance of the CBKPUsed flag hints that the endorsement key pair need not always be present. Unfortunately the spec goes on to say "NOTE: This flag has no default value as the key pair MUST be created by one or the other mechanism." Which certainly confuses things. Page 41 "TPM_CreateEndorsementKey may be called before TPM_Startup. This is necessary because TPM_Startup will fail unless an endorsement key exists" is of no help either way. As with all the others, it states that there may exist conditions where the EK may not exist, but does not give any hints whether this is before or after the TPM leaves the plant. On page 79, the EK is metioned twice. The first time if useless for our purpose. The second time states "This SHALL be the TPM endorsement credential" which indicates that an endorsement credential must exist. Other locations though seem to hint that a void endorsement credential may be possible. Starting on Page 84 is section 4.32.1, which seems to be as close to an authority on the EK as possible, but lacks a statement of whether the EK is shipped with or added later. It does however clearly indicate that the creation of the EK occurs before the Privacy CA is contacted, which was already agreed on. [somewhere around here I stopped addressing everyt occurance of the word "endorsement" because most of them are frivolous] Page 135, Section 5.11.1, clearly states "The new owner MUST encrypt the Owner authorization data and the SRK authorization data using the PUBEK." Which clearly indicates that the EK must exist before ownership can be taken. Other places have hinted that ownership may be taken and then the EK updated, which completely contradicts the one-timeness, or this statement. Page 135 "If no EK is present the TPM MUST return TCPA_NO_ENDORSEMENT" which indicates that one can at least attempt to take ownership before an EK is present, which would contradict the requirement that the EK come from the factory. Page 178, Section 7.3 I am only mentioning because it presents a rather interesting possibility. It hints that under some circumstances it may be acceptable for a manufacturer to copy the data from one TCPA to another. This portion begins with "The manufacturer takes the maintainance blob . . ." This may however only be to update an existing one to address flaws or meet new capabilities. Page 183, hints that even the manufacturer is not allowed to known EK public key, which complicates things no end, because the Privacy CA certainly cannot at that point be permitted to view it. This would indicate that even if the EK is shipped with the system, it can never leave the system. This would limit the ability of the EK to simply certifying the owner, if that is true then it confuses me even further. Page 213 section 8.10 clearly states that if the owner clears the TCPA, everthing is cleared "except the endorsement key pair." Which would indicate that this is truly a one-shot deal. Page 240, states "This is a dead TPM. It has failed it's startup smoke test. It should not leave the factory floor." This indicates that the EK must be created before the TPM leaves the factory. Section 9.2, page 261, state
Re: Microsoft marries RSA Security to Windows
- Original Message - From: "Roy M.Silvernail" <[EMAIL PROTECTED]> > And here, I thought that a portion of the security embodied in a SecurID > token was the fact that it was a tamper-resistant, independent piece of > hardware. Now M$ wants to put the PRNG out in plain view, along with its > seed value. This cherry is just begging to be picked by some blackhat, > probably exploiting a hole in Pocket Outlook. Unfortunately, SecurID hasn't been that way for a while. RSA has offered executables for various operating systems for some time now. I agree it destroys what there was of the security, and reduces it to basically the level of username/password, albeit at a more expensive price. But I'm sure it was a move to improve their bottom line. Joe - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Key Pair Agreement?
- Original Message - From: "Jeroen C. van Gelderen" <[EMAIL PROTECTED]> > Here is a scenario: Scott wants Alice to generate a key pair after > which he will receive Alice's public key. At the same time, Scott wants > to make sure that this key pair is newly generated (has not been used > before). [snip] > It would seem that the DSA key structure facilitates this: > > 1. Scott sends SEED1 to Alice. > 2. Alice picks a random number SEED2. > 3. Alice sets SEED=SHA1(SEED1 || SEED2). > 4. Alice generates a set of DSA parameters P, Q, G using the > algorithm in Appendix 2, FIP-186-2. > 5. Alice generates a key pair (x,y) using the parameters from (4). > 6. Alice sends SEED2, counter, P, Q, G, y to Scott. > 7. Scott generates P', Q', G' based on SEED=SHA1(SEED1 || SEED2), > counter, and compares them to P, Q, G. > > This is a very expensive key generation operation but it would > seem to work. > > My questions are: > 0) who has invented this before? > 1) does it achieve what I think it achieves? > 2) does anybody know of more efficient algorithms? I can think of a more efficient algorithm off the top of my head. 1. Scott creates P,Q,G 2. Scott sends P,Q,G 3. Alice verifies P,Q,G and creates (x,y) 4. Alice sends (x,y) Scott can be certain that, within bounds, P,Q,G have never been found before, and it vastly reduces the computations (since there was no stated requirement that Alice believe the pair had never been used before). Now on to Jack's question: > Actually, that makes me wonder. Given: > y_i = (g_i^x) mod p_i for i 0...n > An you find x easier than you would with just y=g^x mod p? Obviously it > couldn't be any harder, but I wonder if there is any practical advantage > for an attacker there. I believe it is unfortunately so, depending on how strong P is. If (P-1)/2Q is always prime, then I believe there is little erosion (but some remains). The foundation of this thus. X can be determined from Y if the attacker can find inverses in all the sub groups, by the CRT. I believe there is a way to extend this such that provided you have enough sub-groups to uniquely identify a number > Y, X can be determined. If this is the case then having a large number of (Y,P,G,Q) around can erode the security of the DLP. I also believe that it is the case that each of the factors must be unique, otherwise it is simply a collision in the CRT context (although a change of G may correct this) If this is the case then it would be important that Alice generate a new X for each pair in existence, which is simply good policy to begin with. Joe - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Shamir factoring machine uninteresting?
[snips omitted, reordering also occurred for response coherency] - Original Message - From: "Anton Stiglic" <[EMAIL PROTECTED]> Subject: Re: Shamir factoring machine uninteresting? > >From: "Perry E. Metzger" <[EMAIL PROTECTED]> > > I find it odd that there has been so little comment on TWIRL. One > > would think that the crushing of 512 bit RSA keys and a strong > > demonstration of the weakness of 1024 bit RSA keys would have provoked > > some comment on the list. > > > > Any comments on why no one commented? I refrained from much in the way of comment because, while it is an interesting result, and quite damning for 1024-bit keys, it is not a very significant boost of the state of the art, and the costs given are somewhat misleading. > Some theoretical attacks attract attention because if implemented > successfully, > they would really change the way we think of crypto. TWINKLE is such an > example (when the concept of TWINKLE first came out, allot of people > were talking about it), so is the work of D.J. Berstein on factoring. > But to decide whether or not a theoretical attack can be practical or not > is difficult and time consuming. Considering the actual erosion of the problem that occured, TWIRL simply adds to the foundation of 1024-bit RSA keys are not strong, although we still don't have enough evidence to blanketly declare them weak. Bernstein's observations were a much stronger catalyst, since the apparent result was a 3x increase in the size of numbers that could be factored in a given time. Mathematically, Shamir's recent factoring advancements have been somewhat middle of the road, his results don't change the underlying asymptotic relationship. While TWINKLE did push the envelope quite a bit by changing the underlying behavior of the algorithm (even though the algorithm was unchanged), TWIRL doesn't seem to have the same major advancement capability. After my cursory examination of the paper it appears to me that TWIRL is at least near the bounds of reason, but I have not done an in depth analysis of any kind. > The best demonstration is to actually implement it. > The abstract also says that the NFS sieving step of 512-bit RSA keys > can be done in less then 10 minutes by a 10K device. 10K is not that > much to spend on research, so if this can really be implemented I'm thinking > that someone can do it soon. There in lies a problem, and where we get into the possibility of calling the numbers "misleading." It appears that these numbers are for a run of sufficient quantity, so the cost of the process of choosing where to put the circuits on the board is not accounted for. Considering the size of the end device, this would be an extremely expensive step, and the dominant factor in creating a one-off. TWINKLE had much the same problem. Given the current state of the art in taking algorithms and making them in transistors, I wouldn't expect this number to drop too dramatically for several years. So I don't expect an example of a large size unit (more than a few hundred bits) within the realistic future. > > In the abstract of the TWIRL paper, it says that TWIRL can enable > the NFS sieving step more cost effectively, with 3-4 orders of magnitude > more than TWINKLE, but TWINKLE was never implemented (and if > I'm not mistaken, there is doubt about whether or not it can be > implemented?), and 3-4 orders is not that big of a magnitude. That is certainly one thing that has been said several times, TWINKLE might not be realistically implementable. TWIRL appears to address a substantial part of that, using technology that is fairly standard (0.13 micron lithography, very much like Intel, IBM, etc currently use in their fabs or are planning soon), it also rearranges a number of portions in an apparent attempt to address the questions raised against TWINKLE. [later comment: this opinion was changed in a later message that I just received] I disagree though that 3-4 orders of magnitude is not a big deal, 3 orders of magnitude can generally be anywhere from 8 to 1000 fold increase (magnitude is exponential). I haven't examined the paper in any real depth, so I do not yet have a supportable opinion about whether it is a 3 fold increase of a 1000 fold increase, but I suspect that given the current rate of advancement, it is currently closer to the bottom than the top, and that the evolution to 0.09 micron technology in the near future will yield substantial improvements to TWIRL as well. > > Personally, I'll wait and see if someone comes up with a proof of concept, > and if so then I'll take the time to read the paper. For now, I already > consider > 512-bit RSA keys as insecure (because 512 bit integers have already been > factored, and I always allow for a cushion factor so I'm sure it can be > factored > even more efficiently). For now, there are many other results which I would > like to read about which are of interest to me at the present time as a > cryptographer with
Re: Comments/summary on unicity discussion
- Original Message - From: "Joshua Hill" <[EMAIL PROTECTED]> Subject: Re: Comments/summary on unicity discussion > It doesn't deal with plaintext, just ciphertext. In fact, unicity > distance is only valid for a ciphertext only attack. Once you get a > known plaintext/ciphertext pair, a high unicity distance works against > you (more on this later). In addition, it is isn't certain that after > observing the requisite unicity distance number of ciphertext units that > you can uniquely determine the key, it is merely very likely. There appears to be an error in there. The Unicity Distance has a very strong correlation with the uncertainty of the plaintext (entropy per message). By having access to the plaintext/ciphertext pair (often it takes multiple pairs), this removes all uncertainty as to the plaintext, this changes the unicity distance calculation by making the unicity distance as short as possible, which would make "Once you get a known plaintext/ciphertext pair, a high unicity distance works against you" Seem more than a little odd as a statement. On K complexity, while K complexity offers a convenient, if somewhat inaccurate, upperbound of the entropy, that is basically where the relationship ends. Permit me to give the basic example. Which of these strings has higher entropy: kevsnblawtrlnbatkb kevsnblawtrlnbatkb One was created by slapping my hands on the keyboard, and so contains some entropy, the other was created through copy and paste, and so contains none. However the K complexity of the two is identical. The portion of the equation you are forgetting is that the key to the pRNG may itself be compressible. This leads to somewhat of a logic loop, but at the end of it is the absolute smallest representation, as a compression of a given language (the only sense in which this makes sense). Joseph Ashwood Trust Laboratories http://www.trustlaboratories.com - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
