Re: [Cryptography] Books on modern cryptanalysis
On Wed, 11 Sep 2013, Bernie Cosell wrote: Anyhow, are there any (not *too* technical) books on the modern techniques for attacking cryptosystems? Really depends what you mean by attacking; there are attacks at the protocol level (e.g., padding-oracle attacks), at the crypto level (e.g., differential cryptanalysis), and at the physical level (e.g., side-channel attacks). As a general introduction to modern crypto that covers the first two categories a bit, I recommend Introduction to Modern Cryptography by myself and Y. Lindell (soon to come out with a 2nd edition containing even more attacks!). For block-cipher cryptanalysis, I have been very impressed by the material in The Block Cipher Companion by Knudsen and Robshaw. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Homomorphic encryption prototype by microsoft
On Mon, Aug 8, 2011 at 3:37 PM, Ali, Saqib docbook@gmail.com wrote: Two years after Dr. Craig Gentry of IBM published the proof for fully homomorphic encryption, Microsoft has come up with a prototype that utilizes the technique: http://www.technologyreview.com/computing/38239/page1/ Here's the accompanying technical article: http://eprint.iacr.org/2011/405 They only implemented a somewhat-homomorphic encryption scheme, though. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: What's the state of the art in factorization?
On Thu, 22 Apr 2010, Zooko O'Whielacronx wrote: There is some interesting work in public key cryptosystems that reduce to a *random* instance of a specific problem. Here is a very cool one: http://eprint.iacr.org/2009/576 ... Unless I misunderstand, if you read someone's plaintext without having the private key then you have proven that P=NP! It is not known, and considered extremely unlikely, that P \neq NP implies symmetric-key cryptography, much less public-key cryptography. The paper you cite reduces security to a hard-on-average problem, whereas all that P \neq NP guarantees is hardness in the worst case. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
On Thu, 22 Apr 2010, Zooko O'Whielacronx wrote: On Wed, Apr 21, 2010 at 5:29 PM, Samuel Neves sne...@dei.uc.pt wrote (on the cryptography@metzdowd.com list): [2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf As one of the authors of the above paper, I have an obvious interest in this thread. =) Later I discovered this paper [2] which appears to be an improvement on that one in terms of performance (see Table 1 in [2]) while still having a tight reduction to the Computational Diffie-Hellman (CDH) problem. Strangely, this paper [2] doesn't appear to have been published anywhere except as an eprint on eprint.iacr.org. I wonder why not. Is there something wrong with it? While I don't know of any attack, the proof of security does not appear to be correct. On the other hand, there is one published scheme that gives a slight improvement to our paper (it has fewer on-line computations): it is a paper by Chevallier-Mames in Crypto 2005 titled An Efficient CDH-Based Signature Scheme with a Tight Security Reduction. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in digital signatures? Re: What's the state of the art in factorization?
On Wed, 28 Apr 2010, Zooko O'Whielacronx wrote: Anyway, although this is not one, there do exist proposals for public key crypto schemes where breaking the scheme implies solving a worst case instance of a supposedly hard problem, right? Not to worst-case hardness of an NP-complete problem, no. Quite the contrary, there has been some body of work showing that a result of this sort is unlikely. (Though, as with all things related to complexity theory where our state of knowledge is so limited, such a statement must be taken wit ha grain of salt. In any case, such a result is well beyond anything we can currently prove.) 2. some kind of strong argument that it really is secure (the gold standard would be reduction to a worst-case instance of an NP-complete problem) See above. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Question w.r.t. AES-CBC IV
CTR mode seems a better choice here. Without getting too technical, security of CTR mode holds as long as the IVs used are fresh whereas security of CBC mode requires IVs to be random. In either case, a problem with a short IV (no matter what you do) is the possibility of IVs repeating. If you are picking 32-bit IVs at random, you expect a repeat after only (roughly) 2^16 encryptions (which is not very many). On Wed, 2 Jun 2010, Ralph Holz wrote: Dear all, A colleague dropped in yesterday and confronted me with the following. He wanted to scrape off some additional bits when using AES-CBC because the messages in his concept are very short (a few hundred bit). So he was thinking about a variant of AES-CBC, where he uses just 32 (random) bits as a source for the IV. These are encrypted with AES and then used as the actual IV to feed into the CBC. As a result, he does not need to send a 128 bit IV to the receiver but just the 32 bit. His argument was that AES basically is used as an expansion function for the IV here, with the added benefit of encryption. On the whole, this should not weaken AES-CBC. Although he was not sure if it actually would strengthen it. While I am prepared to buy this argument (I am not a cryptographer...), I still felt that the argument might not be complete. After all, 32 bits don't provide much randomness, and I wasn't sure if this, overall, would not lead to more structure in the ciphercode - which might in turn give an attacker more clues with respect to the key. Are there any opinions on this? Regards, Ralph - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: A Fault Attack Construction Based On Rijmen's Chosen-Text Relations Attack
On Mon, 14 Jun 2010, Alfonso De Gregorio wrote: The last Thursday, Vincent Rijmen announced a new clever attack on AES (and KASUMI) in a report posted to the Cryptology ePrint Archive: Practical-Titled Attack on AES-128 Using Chosen-Text Relations, http://eprint.iacr.org/2010/337 Err...I read that paper by Rijmen as a bit of a joke. I think he was poking fun at some of these unrealistic attack models. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Question regarding common modulus on elliptic curve cryptosystems
[Moderator's Note: please don't top post... --Perry] Sounds like a bad idea -- at a minimum, your encryption will be deterministic. What are you actually trying to achieve? Usually once you understand that, you can find a protocol solving your problem already in the crypto literature. On Sun, 21 Mar 2010, Sergio Lerner wrote: I looking for a public-key cryptosystem that allows commutation of the operations of encription/decryption for different users keys ( Ek(Es(m)) = Es(Ek(m)) ). I haven't found a simple cryptosystem in Zp or Z/nZ. I think the solution may be something like the RSA analogs in elliptic curves. Maybe a scheme that allows the use of a common modulus for all users (RSA does not). I've read on some factoring-based cryptosystem (like Meyer-Muller or Koyama-Maurer-Okamoto-Vantone) but the cryptosystem authors say nothing about the possibility of using a common modulus, neither for good nor for bad. Anyone has a deeper knowledge on this crypto to help me? Best regards, Sergio Lerner. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Question regarding common modulus on elliptic curve cryptosystems
[Moderator's Note: Please please don't top post. --Perry] That paper was from 1980. A few things have changed since then. =) In any case, my point still stands: what you actually want is some e-cash system with some special properties. Commutative encryption is neither necessary nor (probably) sufficient for what you want. Have you at least looked at the literature (which must be well over 100 papers) on e-cash? On Mon, 22 Mar 2010, Sergio Lerner wrote: Commutativity is a beautiful and powerful property. See On the power of Commutativity in Cryptography by Adi Shamir. Semantic security is great and has given a new provable sense of security, but commutative building blocks can be combined to build the strangest protocols without going into deep mathematics, are better suited for teaching crypto and for high-level protocol design. They are like the Lego blocks of cryptography! Now I'm working on an new untraceable e-cash protocol which has some additional properties. And I'm searching for a secure commutable signing primitive. Best regards, Sergio Lerner. On 22/03/2010 09:56 a.m., Jonathan Katz wrote: Sounds like a bad idea -- at a minimum, your encryption will be deterministic. What are you actually trying to achieve? Usually once you understand that, you can find a protocol solving your problem already in the crypto literature. On Sun, 21 Mar 2010, Sergio Lerner wrote: I looking for a public-key cryptosystem that allows commutation of the operations of encription/decryption for different users keys ( Ek(Es(m)) = Es(Ek(m)) ). I haven't found a simple cryptosystem in Zp or Z/nZ. I think the solution may be something like the RSA analogs in elliptic curves. Maybe a scheme that allows the use of a common modulus for all users (RSA does not). I've read on some factoring-based cryptosystem (like Meyer-Muller or Koyama-Maurer-Okamoto-Vantone) but the cryptosystem authors say nothing about the possibility of using a common modulus, neither for good nor for bad. Anyone has a deeper knowledge on this crypto to help me? Best regards, Sergio Lerner. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: TLS break
Anyone care to give a layman's explanation of the attack? The explanations I have seen assume a detailed knowledge of the way TLS/SSL handle re-negotiation, which is not something that is easy to come by without reading the RFC. (As opposed to the main protocol, where one can find textbook descriptions.) - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Question about Shamir secret sharing scheme
On Sat, 3 Oct 2009, Kevin W. Wall wrote: Hi list...I have a question about Shamir's secret sharing. According to the _Handbook of Applied Cryptography_ Shamir’s secret sharing (t,n) threshold scheme works as follows: SUMMARY: a trusted party distributes shares of a secret S to n users. RESULT: any group of t users which pool their shares can recover S. The trusted party T begins with a secret integer S ≥ 0 it wishes to distribute among n users. (a) T chooses a prime p max(S, n), and defines a0 = S. (b) T selects t−1 random, independent coefficients defining the random polynomial over Zp. (c) T computes Si = f(i) mod p, 1 ≤ i ≤ n (or for any n distinct points i, 1 ≤ i ≤ p − 1), and securely transfers the share Si to user Pi , along with public index i. The secret S can then be computed by finding f(0) more or less by using Lagrangian interpolation on the t shares, the points (i, Si). The question that a colleague and I have is there any cryptographic purpose of computing the independent coefficients over the finite field, Zp ? Just to add two comments to what others have already said: - You can use any finite field. In particular, if your secret is a bit string of length k you can use the field GF(2^k) to get share size equal to secret size. (Whereas if you work mod p you lose a bit.) - As you describe the scheme above, note that you actually leak an upper-bound on the size of the secret (namely, it is at most p). The setup for Shamir secret sharing (and any other scheme, for that matter) assumes the range of the secret is public knowledge already.
Re: End-of-chapter questions for Practical Cryptography?
On Fri, 22 May 2009, Perry E. Metzger wrote: The field really needs a new, thorough textbook suitable for a one year course, or maybe an up to date one semester intro text and an up to date one semester textbook on modern cryptanalysis. Let me humbly suggest my own book: Introduction to Modern Cryptography, co-authored with Y. Lindell. You may find it a bit theoretical for your taste, but it was written exactly to address the need for an introductory text covering modern cryptography. (And it covers some basic cryptanalysis as well.) See http://www.cs.umd.edu/~jkatz/imc.html for further details. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: How to Share without Spilling the Beans
On Mon, 2 Mar 2009, Arshad Noor wrote: Ali, Saqib wrote: A new protocol aims to protect privacy while allowing organizations to share valuable information: http://www.technologyreview.com/communications/22238/?a=f Any links to the actual protocol itself? The article is a little vague on details. Thanks. I believe this is the paper describing the protocol in question: http://eprint.iacr.org/2009/036 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Shamir secret sharing and information theoretic security
On Tue, 17 Feb 2009, R.A. Hettinga wrote: hi, I was going through the wikipedia example of shamir secret sharing which says it is information theoretically secure. http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing ... The scheme is defined over a finite field *not* over the integers. When Shamir's scheme is run over a finite field, it is information theoretically secure. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: combining entropy
On Sat, 25 Oct 2008, John Denker wrote: On 10/25/2008 04:40 AM, IanG gave us some additional information. Even so, it appears there is still some uncertainty as to interpretation, i.e. some uncertainty as to the requirements and objectives. I hereby propose a new scenario. It is detailed enough to be amenable to formal analysis. The hope is that it will satisfy the requirements and objectives ... or at least promote a more precise discussion thereof. We start with a group comprising N members (machines or persons). Each of them, on demand, puts out a 160 bit word, called a member word. We wish to combine these to form a single word, the group word, also 160 bits in length. snip If you are interested in something with a formal analysis, you should check out work on (single-source or multiple-source) extractors. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: combining entropy
[Moderator's note: top posting is not tasteful. --Perry] I think it depends on what you mean by N pools of entropy. Are you assuming that one of these is sources is (pseudo)random, but you don't know which one? Are you assuming independence of these difference sources? If both these assumptions hold, then XOR will do the trick. If your only assumption is that one of the sources has high min-entropy (but may not necessarily be uniform), or if the independence assumption does not hold, then you may need to use some form of randomness extraction. On Mon, 29 Sep 2008, IanG wrote: If I have N pools of entropy (all same size X) and I pool them together with XOR, is that as good as it gets? My assumptions are: * I trust no single source of Random Numbers. * I trust at least one source of all the sources. * no particular difficulty with lossy combination. iang - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
On Wed, 27 Aug 2008, Eric Rescorla wrote: At Wed, 27 Aug 2008 16:10:51 -0400 (EDT), Jonathan Katz wrote: On Wed, 27 Aug 2008, Eric Rescorla wrote: At Wed, 27 Aug 2008 17:05:44 +0200, There are a set of techniques that allow you to encrypt elements of arbitrary sets back onto that set. The original paper on this is: John Black and Phillip Rogaway. Ciphers with arbitrary ?nite domains. In CT-RSA, pages 114?130, 2002. But he probably wants an encryption scheme, not a cipher. Hmm... I'm not sure I recognize the difference between encryption scheme and cipher. Can you elaborate? A block cipher is a primitive that can be used, in particular, to construct encryption schemes. But you can construct encryption schemes without block ciphers, and you can use block ciphers to construct other things besides encryption. Moreover, good encryption should generally be randomized, while a block cipher is deterministic. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
On Wed, 27 Aug 2008, Hovav Shacham wrote: - Jonathan Katz [EMAIL PROTECTED] wrote: But he probably wants an encryption scheme, not a cipher. Jon, I'm not sure I understand what you mean. If I am reading his message correctly, the original poster seems to be asking for a format-preserving encryption over a domain with 10^40 elements. Format-preserving, it seems to me, implies [a family of keyed] functions that are one-to-one and deterministic. In other words, the best security we can hope for is a PRP on that domain, and this is what B-R gives, starting from a PRP over a somewhat larger domain. In this setting, what is the difference between an encryption scheme and a cipher? Yes, I can see this might cause confusion. Just to clarify: I had emailed the original poster off-line and he told me that he was willing to use other information already being sent in the clear as a non-repeating IV. Given this, secure (and, in particular, non-deterministic) encryption is possible. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
On Wed, 27 Aug 2008, Eric Rescorla wrote: At Wed, 27 Aug 2008 17:05:44 +0200, Philipp Gühring wrote: Hi, I am searching for symmetric encryption algorithms for decimal strings. Let's say we have various 40-digit decimal numbers: 2349823966232362361233845734628834823823 3250920019325023523623692235235728239462 0198230198519248209721383748374928601923 As far as I calculated, a decimal has the equivalent of about 3,3219 bits, so with 40 digits, we have about 132,877 bits. Now I would like to encrypt those numbers in a way that the result is a decimal number again (that's one of the basic rules of symmetric encryption algorithms as far as I remember). Since the 132,877 bits is similar to 128 bit encryption (like eg. AES), I would like to use an algorithm with a somewhat comparable strength to AES. But the problem is that I have 132,877 bits, not 128 bits. And I can't cut it off or enhance it, since the result has to be a 40 digit decimal number again. Does anyone know a an algorithm that has reasonable strength and is able to operate on non-binary data? Preferrably on any chosen number-base? There are a set of techniques that allow you to encrypt elements of arbitrary sets back onto that set. The original paper on this is: John Black and Phillip Rogaway. Ciphers with arbitrary ?nite domains. In CT-RSA, pages 114?130, 2002. But he probably wants an encryption scheme, not a cipher. Also, correct me if I am wrong, but Black and Rogaway's approach is not efficient for large domains. But if you use their approach for small domains then you open yourself up to dictionary attacks. For a modern proposal to make this a NIST mode, see: http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffsem/ffsem-spec.pdf -Ekr Full Disclosure: Terence Spies, the author of the FFSEM proposal, works for Voltage, Voltage has a product based on this technology. and I'm on Voltage's TAB and have done some work for them. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Using a MAC in addition to symmetric encryption
On Fri, 27 Jun 2008, Erik Ostermueller wrote: Hello all, If I exchange messages with a system and the messages are encrypted with a symmetric key, what further benefit would we get by using a MAC (Message Authentication Code) along with the message encryption? Being new to all this, using the encrytpion and MAC together seem redundant. Thanks, --Erik Ostermueller As the other posters have already commented, encryption alone does not (in general) provide integrity. Furthermore, care must be taken in how the encryption scheme and the MAC are combined, with encryption-followed-by-MACing-the-ciphertext being the best choice unless you know what you are doing. For further discussion, see the textbook by Katz-Lindell (Section 4.9), and/or the following paper: http://www-cse.ucsd.edu/users/mihir/papers/oem.html - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: New result in predicate encryption: disjunction support
On Mon, 5 May 2008, Ariel Waissbein wrote:
[Moderator's note: Again, top posting is discouraged, and not editing
quoted material is also discouraged. --Perry]
Hi list,
Interesting. Great work! I had been looking *generic* predicate
encryption for some time. Encryption over specific predicates is much
older. Malware (e.g., virus) and software protection schemes have been
using some sort of predicate encryption or trigger for over two
decades in order to obfuscate code. For example, an old virus used to
scan hard drives looking for a BBS configuration files in a similar
manner and some software protection schemes have encrypted pieces of
code that are decrypted only if some integrity checks (predicates) over
other pieces of the program are passed.
Triggers/predicates are very promising. Yet, they are only useful in
certain applications, since eavesdropping one decryption is enough to
recover the keys and plaintext.
I co-authored a paper were we used this same concept in a software
protection application ([1]) and later we formalized this concept, that
we called secure triggers, in a paper eventually publised at TISSEC
([2]). We were only able to construct triggers for very specific
predicate families, e.g.,
- p(x)=1 iff x=I for some I in {0,1}^k
- q(x,y,z,...)=1 iff x=I_1, y=I_2, z=I_3,...; and finally
- r(x)=1 iff x_{j_1}=b_1,...,x_{j_k}=b_k for some b_1,...,b_k in {0,1}
and indexes i_1,...,i_k (|x|=k).
While these predicates do not cover arbitrary large possibilities, they
are implemented by efficient algorithms and require assuming only the
existence of IND-CPA secure symmetric ciphers. In [2] we came up with
more applications other than sofprot;)
[1] Diego Bendersky, Ariel Futoransky, Luciano Notarfrancesco, Carlos
Sarraute and Ariel Waissbein. Advanced Software Protection Now. Core
Security Technologies Tech report.
http://www.coresecurity.com/index.php5?module=ContentModaction=itemid=491
[2] Ariel Futoransky, Emiliano Kargieman, Carlos Sarraute, Ariel
Waissbein. Foundations and applications for secure triggers. ACM TISSEC,
Vol 9(1) (February 2006).
Cheers,
Ariel
Predicate encryption sounds very different from the work you are
referencing above. (In particular, as we discuss in the paper, predicate
encryption for equality tests is essentially identity-based encryption.)
I refer you to the Introduction and Definition 2.1 of our paper, which
should give a pretty good high-level overview.
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: New result in predicate encryption: disjunction support
On Sun, 4 May 2008, Scott Guthery wrote: One useful application of the Katz/Sahai/Waters work is a counter to traffic analysis. One can send the same message to everyone but ensure that only a defined subset can read the message by proper key management. What is less clear is how to ensure that decrytion with the wrong key doesn't yield an understandable (and actionable) message. This is actually pretty easy to do by, e.g., padding all valid messages with sufficiently-many 0s. Decryption with an incorrect key will result in something random that is unlikely to end with the requisite number of 0s (and so will be discarded). - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
