Re: A security bug in PGP products?
Max A. wrote: Hello! Could anybody familiar with PGP products look at the following page and explain in brief what it is about and what are consequences of the described bug? 1. The disk is encrypted using a long, secure, random, symmetric en/de-cryption key. (EDK for short). 2. The EDK is encrypted with a passphrase and stored in a header at the start of the encrypted disk 3. If you change the passphrase on the disk, it simply reencrypts the EDK using the new passphrase. It does not generate a new EDK and it does not re-encrypt the entire disk. 4. Therefore the EDK itself is still the same, and if you overwrite the new header (with the EDK encrypted by the new passphrase) using a stored copy of the old header (with the same EDK encrypted under the old passphrase), you have effectively changed the passphrase back - without having to have knowledge of the new passphrase - and can now regain access using the old passphrase. The guy who wrote that page posted a thread about it a while ago, I think it was on FD or perhaps Bugtraq. His interpretation is somewhat coloured by his transparent belief that these are big corporate monstrosities and hence /must/ be evil. His website is full of significant exaggerations/inaccuracies; for instance, when he claims that you can break the decryption using a debugger, he forgets to mention that this only applies to a disk where you originally knew the passphrase and have since changed it. It's more of a usage/documentation issue, really; an end-user might believe that changing the passphrase re-encrypted the entire disk beyond their ability to retrieve it. cheers, DaveK -- Can't think of a witty .sigline today - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Fw: A security bug in PGP products?
[ Originally tried to post this through gmane, but it doesn't seem to work; apologies if this has been seen before. ] Max A. wrote: Hello! Could anybody familiar with PGP products look at the following page and explain in brief what it is about and what are consequences of the described bug? 1. The disk is encrypted using a long, secure, random, symmetric en/de-cryption key. (EDK for short). 2. The EDK is encrypted with a passphrase and stored in a header at the start of the encrypted disk 3. If you change the passphrase on the disk, it simply reencrypts the EDK using the new passphrase. It does not generate a new EDK and it does not re-encrypt the entire disk. 4. Therefore the EDK itself is still the same, and if you overwrite the new header (with the EDK encrypted by the new passphrase) using a stored copy of the old header (with the same EDK encrypted under the old passphrase), you have effectively changed the passphrase back - without having to have knowledge of the new passphrase - and can now regain access using the old passphrase. The guy who wrote that page posted a thread about it a while ago, I think it was on FD or perhaps Bugtraq. His interpretation is somewhat coloured by his transparent belief that these are big corporate monstrosities and hence must be evil. His website is full of significant exaggerations/inaccuracies; for instance, when he claims that you can break the decryption using a debugger, he forgets to mention that this only applies to a disk where you originally knew the passphrase and have since changed it. It's more of a usage/documentation issue, really; an end-user might believe that changing the passphrase re-encrypted the entire disk beyond their ability to retrieve it. cheers, DaveK -- Can't think of a witty .sigline today - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: A security bug in PGP products?
On 21 Aug 2006, at 3:36 PM, Max A. wrote: Hello! Could anybody familiar with PGP products look at the following page and explain in brief what it is about and what are consequences of the described bug? http://www.safehack.com/Advisory/pgp/PGPcrack.html The text there looks to me rather obscure with a lot of unrelated stuff. The guy's basically confused. I wrote a long thing at the time to bugtraq with lots of detail. He's got two basic claims. The first is that if he makes a copy of a disk file, changes the passphrase on the copy, and then uses a hex editor to paste the passphrase reduction back onto the copy. Poof, the old passphrase works again. This is like saying that you can use emacs to edit a file and change 123 to ABC and then use a hex editor to change 0x41 0x42 0x43 to 0x31 0x32 0x33 and ZOMG! The change magically vanishes! As Ondrej Mikle points out, the disk hasn't been re- encrypted. If you want the disk to be re-encrypted, you press the big Re-encrypt button in panel. The other thing he did was that he found some code that basically does: if (user-types-right-passphrase) then mount-the-disk else display-error endif And then he patches out the if statement and notices that the disk will mount, but curiously is lots of random garbage. He leaves as an open problem how to make the disk readable after patching out the if statement. Jon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: A security bug in PGP products?
What they're saying is if you change the password, create some new data in the encrypted folder, then someone who knew the old password, can decrypt your new data. Why? Well because when you change the password they dont change the symmetric key used to encrypt the data. The password is used to create a KEK (key encryption key) and this in-turn is used to encrypt the folder key (which is used to do the actual data encryption.) Now in common with a lot of other systems, changing the password does not entail re-encrypting the actual data. (To do so would require waiting for it to re-encrypt. There are systems that do this, but it is a tradeoff, espeically in a single-user scenario) Personally my preferred security property (in a multi-user storage system where users can be added and removed) is that people who had access can still decrypt the stuff they had access to, but can't decrypt new data encrypted since then. I think its a good balance because that person had the data anyway, and could remember it, have backups of it etc. Another thing that can be done is to utilize an online server, which has an additional key such that it cant decrypt, but can hand it over on successful auth and can delete that key on request. Obviously the key would be combined in a one-way fashion so the server does not have to be trusted other than to delete keys on request. However the article also talks about forensics, and I think they maybe confusing something there because most encrypted content is not authenticated anyway (you can merrily switch around ciphertext blocks without triggering any integrity warnings at the crypto level). And anyway if the forensic investigator has the password, he can change anything! -- symmetric encryption keys known to others are not signatures. Adam On Mon, Aug 21, 2006 at 03:36:16PM -0700, Max A. wrote: Hello! Could anybody familiar with PGP products look at the following page and explain in brief what it is about and what are consequences of the described bug? http://www.safehack.com/Advisory/pgp/PGPcrack.html The text there looks to me rather obscure with a lot of unrelated stuff. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Solving systems of multivariate polynomials modulo 2^32
On Mon, 14 Aug 2006, David Wagner wrote:
Here's an example. Suppose we have the equations:
x*y + z = 1
x^3 + y^2 * z = 1
x + y + z = 0
Step 1: Find all solutions modulo 2. This is easy: you just have to try
2^3 = 8 possible assignments and see which one satisfy the equations. In
this case, the only solution is x=0, y=1, z=1 (mod 2).
There is a small optimization: modulo 2, x^n = x and thus if ``the
degrees of the polynomials are high (say 32) and the number of terms
they have is also big (for example 833, 2825 and 4708)'' it is not
more difficult to solve than degree 3 (xyz) with up to 8 terms. In
particular, the example is equivalent modulo 2 to
x*y + z = 1
x + y*z = 1
x + y + z = 0
[[[ Btw, something is wrong in the example: the following program
N = 2
for x in range(N):
for y in range(N):
for z in range(N):
if (x*y+z)%N==1 and (x**3+y**2*z)%N==1 and (x+y+z)%N==0:
print x,y,z
outputs
0 1 1
1 0 1
1 1 0
and apparently 1,0,1 is indeed a solution mod 2:
1*0+1=1, 1+0*1=1, and 1+1+0=0
]]]
Trying all combinations is a reasonable strategy, but it is also
possible to use an iterative simplification (especially if there are,
say, 80 variables):
if y = 0 we get a linear system
z = 1
x = 1
x + z = 0
that is 1,0,1 is a solution
if y = 1 we get also a linear system
x + z = 1
x + z = 1
x + 1 + z = 0
that is 0,1,1 and 1,1,0 are also solutions.
Linearization (and relinearization) may also be an option.
Step 2: Find all solutions modulo 4. This is again easy: since we know
x=0 (mod 2), then the only two possibilities for x mod 4 are 0 or 2.
Likewise, there are only two possibilities for y mod 4 and z mod 4.
Trying all 2^3 = 8 possible assignments, we find that the only two
solutions are x=0, y=3, z=1 (mod 4) and x=2, y=1, z=1 (mod 4).
Once we solved the system modulo 2^k, doing so modulo 2^{k+1} is much
simpler than trying all possibilities for the next bit. A nice
property of multiplication is that it gives linear relation in the
non-zero bit-slice, that is if we know that
X = x 2^k + A
Y = y 2^k + B,
where A and B are known and k0, then modulo 2^{k+1} we have
X*Y = xy 2^{2k} + (Bx+Ay) 2^k + AB = (bx+ay) 2^k + AB,
where a and b are the least significant bits of A and B (A = 2A'+a).
Since A and B are known constants, the next bit of XY is a linear
function (bx + ay + AB/2^k) of the next unknown bits of X and Y.
For example, in our case once we have (0,1,1) we represent X=2x,
Y=2y+1, and Z=2z+1 and write
2x(2y + 1) + 1 = 1
(2x)^3 + (2y+1)^2(2z+1) = 1
2x+(2y+1)+(2z+1) = 0
remove everything divisible by 4
2x + 1 = 1
2z + 1 = 1
2x + 2y + 2z + 2 = 0
and divide each equation by 2 (this is possible becuase (0,1,1) was a
solution modulo 2)
x = 0
z = 0
x+y+z=1,
that is (x,y,z)=(0,1,0) and thus (X,Y,Z) = (0,3,1) modulo 4.
We see that this requires performing 32 of these steps. On average, we
expect about one feasible solution to remain possible after each step
(though this number may vary). Each step requires testing 8 possible
assignments, times the number of assignments from the prior step. Thus,
on the average case we can expect this to run very fast.
Btw, the matrix (and thus its rank) depends only on the LSB of the
current solution, thus for each solution modulo 2, there is either a
split on each new step (if the rank is not maximal and the system is
consistent on this step), or no splits at all (if it is maximal).
--
Regards,
ASK
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: A security bug in PGP products?
On Mon, 21 Aug 2006, Max A. wrote: Could anybody familiar with PGP products look at the following page and explain in brief what it is about and what are consequences of the described bug? http://www.safehack.com/Advisory/pgp/PGPcrack.html The text there looks to me rather obscure with a lot of unrelated stuff. The system works as follows: a random key K is used to encrypt all the data on the volume; the passphrase is used to encrypt the key K. This design allows to change the passphrase without reencrypting the whole drive (only K needs to be reencrypted). One well-known side-effect is that if one knows K he can decrypt the data. So, if an attaker knows the password and can read your volume image at some point at time, he can decrypt the volume even if you change the password (recall that you have not changed the key). -- Regards, ASK - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Chasing the Rabbit - a cryptanalytic contest
Hi all! At the rump session of Crypto 2006, we started the chasing the Rabbit contest. Dan Bernstein was so kind as to present the slides on our behalf. The details of the contest are given below; they can also be downloaded from http://www.cryptico.com/Files/Filer/rabbit_contest.pdf. Best regards Erik Zenner -- Dr. Erik Zenner Phone: +45 39 17 96 06Cryptico A/S Chief Cryptographer Mobile: +45 60 77 95 41Fruebjergvej 3 [EMAIL PROTECTED] www.cryptico.com DK 2100 Copenhagen -- Chasing the Rabbit - a cryptanalytic contest At the workshop on Fast Software Encryption (FSE) 2003, the stream cipher Rabbit was presented for the first time. It used a novel approach for pseudo-random output generation and provided very high performance. Now, 3 1/2 years later, Rabbit is still unbroken. Starting from August 1, 2006, Cryptico A/S starts the Rabbit contest. The purpose is to encourage further research and analysis, but also the publication of already existing results. For the most interesting paper on Rabbit cryptanalysis, Cryptico A/S offers a price of US $ 1000. In order to qualify for the competition, a paper has to meet the following conditions: - At least part of the paper deals with cryptanalysis of the Rabbit stream cipher. - Cryptanalysis may be of the full cipher, of a reduced version, or of cipher components. - The paper has been accepted for presentation at a cryptographic conference with fully reviewed proceedings (either online or printed), or for publication in an academic journal of good standing. - Cryptico A/S has been notified about the paper's existence and the conference or journal it has been accepted for. The closing date of the competition is September 30, 2007. After that date, the Cryptico jury will decide on which paper it considers to be the most interesting. We preserve the right to split the price money between several contestants, if this seems most appropriate. Closing remarks: - Employees, former employees, and advisory board members of Cryptico A/S may not participate. - The specification of the Rabbit stream cipher and the white papers on cryptanalysis are available from the Cryptico homepage, http://www.cryptico.com/. - For any questions or comments, please contact [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: A security bug in PGP products?
Ondrej Mikle [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]... Max A. wrote: Hello! Could anybody familiar with PGP products look at the following page and explain in brief what it is about and what are consequences of the described bug? http://www.safehack.com/Advisory/pgp/PGPcrack.html It seemed a bit obscure to me at first, but it says basically: PGPdisk does not use key derived from passphrase, just does simply this: if (somehash(entered_password) == stored_password_hashed) then access_granted(); That's the REPE CMPS chain instruction (string comparison). The check can be simply skipped using debugger by interrupting the program, changing CS:EIP (i.e. the place of execution) to resume after successful check. The text probably implies that the key is stored somewhere in the PGPdisk file and key's successful extraction does not depend on knowledge of the passphrase. Nope. Well, yes, the text does imply that, but the text is seriously wrong. See my previous post for the full mechanism. (Assuming the moderator lets it through.) Given that, whatever passphrase you use, you will decrypt the EDK block and get /something/ that looks like a key, this comparison of hashes is a sanity test. If you bypass it but enter the wrong passphrase, you'll get an incorrectly-decrypted EDK, which will lead your disk to look like every sector is full of random garbage. Rather than decrypt the entire disk and run chkdsk to see if it looks sane, comparing the hashes of the passphrase is a quick and dirty way of testing if the resulting EDK is going to be the correct one. The author of the website did have this explained to him by someone from PGP corp. on FD when he first reported this, but he failed to understand it, or perhaps just refused to believe it. Bypassing this check doesn't decrypt the disk. So if you change passphrase, the disk won't get re-encrypted, just by copypasting the old bytes you will revert to the old passphrase or you can create another disk with passphrase chosen by you and use copypasting method to decrypt other PGPdisk protected with passphrase. Yes to the first one, but no to the secopnd, because when you create a disk it will have an entirely new EDK, so replacing the header block with one from a different disk will mean that, yes, you can enter the old passphrase, and yes, that will pass the hash-comparison check, but the old EDK (that you correctly decrypt with the correct passphrase) doesn't actually apply to the encrypted data on the new disk, and the disk will look like gibberish. cheers, DaveK -- Can't think of a witty .sigline today - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Hypothesis: PGP backdoor (was: A security bug in PGP products?)
Hello. We discussed with V. Klima about the recent bug in PGPdisk that allowed extraction of key and data without the knowledge of passphrase. The result is a *very*wild*hypothesis*. Cf. http://www.safehack.com/Advisory/pgp/PGPcrack.html Question 1: why haven't anybody noticed in three months? Why has not there been a serious notice about it? According to the paper, both standard .pgd and self-extracting SDA (self-decrypting archives) are affected. Systematic backdoor maybe? Possibilities: 1) it is a hoax. Though with very low probability. The text seems to include a lot of work and makes perfect sense (REPE CMPS, all the assembly), i.e. we suppose it is highly improbable that somebody would make such hoax. This can be either proven or disproven simply by checking the Win program using hex editor/debugger (using an already downloaded copy). I haven't had the time to check it yet (no Win). 2) AFAIK, Zimmerman is no longer in control of the company making PGP. AFAIK the company (NAI) has been bought by another group couple of years ago. www.pgp.org says: 2002/03/08 - NAI drops PGP Desktop 2001/10/15 - NAI to sell PGP division It may be therefore quite possible that NSA/CIA/FBI/etc. couldn't force Zimmerman to compromise his own product directly, so they have bought the company. The backdoor might have been introduced in the latest releases (e.g. 8.x, 9.x). 3) there was a lazy programmer, or a programmer-infiltrator from the ranks of intelligence services. What does one do when a cryptosystem seems unbreakable? He circumvents it. AFAIK the code has been checked many times in NAI, until some point in time. As you all probably know, there has been a lot of mischief around Zimmerman and PGP in the '90-ties. We don't think NSA/CIA/FBI/etc would just give up without fight. You know, the three-line PERL RSA implementations on T-shirts and so on. Code of PGPdisk 9.x looks like this according to the paper: when the passphrase is changed, the key itself remains untouched. If at least the encryption key has been encrypted by a symmetric key generated e.g. by PBDFK2 from the passphrase. Conclusion: it seems that NSA/CIA/FBI/etc. haven't called truce. Thought, very clever solution. Nevertheless, nothing we haven't had already seen in 1st/2nd world war tactics. What do you think? Your input is welcome. OM P.S. sorry for any misspellings of names - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Hamiltonian path as protection against DOS.
What is the complexity class for Eulerian paths/trails? Wikipedia doesn't say. -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
collisions in 64 round variant of SHA-1 with 25% chosen plaintext
http://www.heise-security.co.uk/news/77244 ``Although the demonstration was restricted to the reduced SHA-1 variant in 64 steps, it can, according to the experts, also be generalised to the standard 80 step variant. This means that SHA-1 must also be considered as cracked in principle. Christian Rechberger, who developed the new attack together with his colleague Christophe De Cannière, explained to heise Security that, in their experiments, up to one quarter of the message could be freely selected. The remaining 75 percent is, as before, determined by the attack. Rechberger suspects, however, that the amount that can be freely selected can be further increased by optimising the attack.'' -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
skype not so anonymous...
Fugitive executive is tracked down by tracing his Skype calls... http://arstechnica.com/news.ars/post/20060824-7582.html Perry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
[EMAIL PROTECTED]: [fc-announce] CFP: Usable Security (USEC'07)]
From: Rachna Dhamija [EMAIL PROTECTED] Subject: [fc-announce] CFP: Usable Security (USEC'07) To: [EMAIL PROTECTED] Date: Fri, 25 Aug 2006 10:55:05 -0400 This workshop will be held in conjunction with Financial Cryptography and Data Security '07. We encourage you to participate and to circulate this CFP to those who may be interested. FIRST CALL FOR PAPERS Usable Security (USEC'07) http://www.usablesecurity.org/ February 15-16, 2007 Lowlands, Scarborough, Trinidad/Tobago A workshop co-located with The Eleventh Conference on Financial Cryptography and Data Security (FC'07) Submissions Due Date: November 5, 2006, 11:59pm, PST Some of the most challenging problems in designing and maintaining secure systems involve human factors. A great deal remains to be understood about users' capabilities and motivations to perform security tasks. Usability problems have been at the root of many widely reported security failures in high-stakes financial, commercial and voting applications. USEC'07 seeks submissions of novel research from academia and industry on all theoretical and practical aspects of usable security in the context of finance and commerce. The workshop will bring together an interdisciplinary group of researchers and practitioners, allowing experts in human-computer interaction, cryptography, data security and public policy to explore emerging problems and solutions. ==Organizers== Program Chair: Rachna Dhamija, Harvard University Program Committee (not complete): Steven Bellovin, Columbia University Dan Boneh, Stanford University Simson Garfinkel, Harvard University Raquel Hill, Indiana University Jason Hong, Carnegie Mellon University Burt Kaliski, RSA Security and RSA Laboratories Robert Miller, Massachusetts Institute of Technology Andrew Patrick, National Research Council Canada Angela Sasse, University College London Dan Schutzer, Financial Services Technology Consortium Sean Smith, Dartmouth College J. D. Tygar, U.C. Berkeley Paul van Oorschot, Carleton University Ka-Ping Yee, U.C. Berkeley General Chair: Stuart Schechter, MIT Lincoln Laboratory ==Submission Categories== USEC'07 invites submissions in three categories: (1) research papers, (2) abstracts and demos, and (3) working sessions. For all accepted submissions, at least one author must attend the conference and present the work. Research Papers Submitted papers must not substantially overlap with papers that have been published or that are simultaneously submitted to a journal or a conference with proceedings. Research paper submissions should be at most 12 pages, excluding bibliography and appendices (appendices may include usability study materials and data). Accepted submissions will appear both in a pre-proceedings, available at the workshop, and in a formal proceedings. After receiving feedback from the workshop, authors will have the opportunity to revise their papers before submitting a camera-ready draft for the final proceedings. Abstracts and Demos Submissions in this category should consist of a short summary of work (1-3 pages in length) to be reviewed by the Program Committee, along with a short biography of the presenters. Accepted submissions will be presented at the conference, and a one-page abstract will be published in the conference proceedings. Where appropriate, software or hardware demonstrations are encouraged as part of the presentations in these sessions. Working Sessions We are soliciting topics for working sessions at the intersection of usability, security, finance and commerce. Working sessions will explore topics in depth with significant paricipation from audience members. Proposals for working sessions should include the proposed topic, format (e.g., panel of invited experts, moderated discussion session, design exercises), prospective participants, time required and a plan for engaging participation from audience members. ==Important Dates== Paper Submission: November 5, 2006 Author Notification: December 15, 2006 Camera-ready for Pre-Proceedings: January 31, 2007 FC'07 Dates: February 12-15, 2007 USEC'07 Dates: February 15-16, 2007 Camera-ready for Final Proceedings: March 15, 2007 ___ fc-announce mailing list [EMAIL PROTECTED] http://mail.ifca.ai/mailman/listinfo/fc-announce -- - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
CRCs and passphrase hashing
Howdy! I was talking to Terry Ritter, and he was explaining to me that when he needed to make some keys from a user-supplied passphrase, he computed various CRCs over the passphrase, and used those as derived keys. I'd like to know more about it, and I was wondering if anyone knew of any work that addressed the strength of this kind of passphrase preprocessing. Forgive me for not being able to hit the ground running after reading the explanation from mathworld, as I don't have a degree in discrete math. -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Provably secure cryptosystem
Hello. I humbly say that I *might* have devised a provably secure cryptosystem that actually *might* work in reality. It provides secure authentication and possibly might be extended to something else. Sounds too good to be true? Well, you're right. In reality it's a bit more complicated. I'm risking again making fool of myself, but what the heck ;-) At least I think it's something you all know, at least to some extent. I have searched for some other provably secure schemas for MACs/signatures/etc., they use many similar assumptions (e.g. random oracle assumption, strong one-way hash function with uniform distribution assumption) and some similar techniques. In the system I can prove there *is* a random oracle (this is also not so entirely true, but...you'll see). OK, the point: In complexity theory with random oracle, NP != P (cf. Shoup 1997: Lower Bounds for Discrete Logarithms and related problems, Baker-Gill-Solovay 1975). The trick is based on this fact. Keys in the cryptosystem are not *data*, but *programs*, i.e. (partially) recursive functions. The trick is to simulate random oracle by a program, each program is the key describing a random permutation on some subset of natural numbers. The cryptosystem is based on the following observation (extension of halting problem): Given a program L as an input that takes 1..n as input, L stops exactly for one 1=j =n. If we give this program to a DTM (deterministic Turing machine), no finite algorithm can decide for all possible input programs L and numbers n, for which j the input program L will stop in polynomial time. In another words, no finite program can detect every virus (virus is defined to be a self-replicating program) or check if other program will draw prescribed picture for a given input, etc. in polynomial time. So, the paper can be found here (alpha-draft, by no means complete, some parts such as related work and references, acks are not complete): -- http://urtax.ms.mff.cuni.cz/~abyssal/PS.pdf -- Be warned, it may be at least *partially* false, because I *deliberately* left out one proof (protecting the keyspace, though it's security by obscurity). Well, hopefully there are no more serious glitches ;-] The system as whole is secure, but every single instance can be of course broken by man (stealing the key, guessing the key, cryptanalysis). Integer factorization problem, (generalized) discrete logarithm problem are also elements of the system (it is a set). At least I hope you'll have some fun. OM - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Chasing the Rabbit - a cryptanalytic contest
At 15:26 +0200 2006/08/23, Erik Zenner wrote: Hi all! At the rump session of Crypto 2006, we started the chasing the Rabbit contest. Dan Bernstein was so kind as to present the slides on our behalf. The details of the contest are given below; they can also be downloaded from http://www.cryptico.com/Files/Filer/rabbit_contest.pdf. Dan did *not* make the presentation. He was on the program but didn't speak. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Hypothesis: PGP backdoor (was: A security bug in PGP products?)
On Thu, 24 Aug 2006, Ondrej Mikle wrote: 2) AFAIK, Zimmerman is no longer in control of the company making PGP. AFAIK the company (NAI) has been bought by another group couple of years ago. The rescue of PGP from NAI's gross neglect and mismanagement of the product line was orchestrated by individuals involved in the original PGP, Inc. startup, and lead by respected cryptographic engineer Jon Callas (also known for being the editor of RFC 2440) and Phil Dunkelberger (the original PGP, Inc., CEO.) As part of their acquisition of the PGP product line, they hired (nearly?) the entire PGP programming team, including such familiar faces as Will Price and Hal Finney. http://www.pgp.com/company/management.html As a former NAI employee who worked on the PGP products, I firmly believe the software is in far more capable hands now from a management standpoint. As a PGP Universal user, I'm delighted by the significant improvements in usability that the new management has allowed the engineering team to make. The myopia of NAI's executives toward the usability problems in PGP was one of the reasons I quit the company in frustration. Also, for what it's worth, Phil was ousted from NAI in 2000, prior to the discontinuation of NAI's commitment to the PGP product line, but he *is* involved with the current PGP Corporation, as a member of the technical advisory board. http://www.pgp.com/company/boards/tab.html I also have no question, personally, that if there's a backdoor in PGP, neither Mr. Callas nor any of the PGP engineers I had the pleasure to work with know of it. Your theory is indeed wild, and though I don't mean to discourage vigilance in questioning these sorts of potential subversions of integrity in software as important as PGP, you might consider doing more research into the background of people against whom you choose to levy hypothetical accusations in public forums in the future. --Len. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
