Re: [cryptography] RSA signatures without padding

[Jonathan Katz]

On Fri, Jul 10, 2015 at 7:42 PM, Filip Paun  wrote:
> Hello,
>
> Thank you for your feedback. Please see my comments below.
>
> On Fri, Jul 10, 2015 at 3:59 PM, Jonathan Katz  wrote:
>>
>> On Fri, Jul 10, 2015 at 4:15 PM, Filip Paun  wrote:
>> > Suppose I have a message M for which I generate an RSA-2048 digital
>> > signature as follows:
>> >
>> >   H = SHA-256(M)
>> >   S = H^d mod N
>> >
>> > Assume N = p*q is properly generated and d is the RSA private key.
>> >
>> >
>> > And I verify the signature as follows:
>> >
>> >   S^e mod N == H'
>> >
>> > where H' is the SHA-256 of the message to be authenticated. Assume e is
>> > the
>> > RSA public key.
>> >
>> > Since I've not used any padding then are there any flaws with the above
>> > approach? What if e = 3? What if e = 2^16+1?
>> >
>> > Your guidance is much appreciated.
>> >
>> > Thank you,
>> > Filip
>>
>> This is a bad idea.
>
>
> Specifically, I am interested in the reasons why this is a bad idea for the
> case where e = 2^16+1 and the hash is SHA256. Also, it's important to point
> out that given my particular use case, an attacker can only see a few
> pre-computed signatures and cannot generate any new signatures by using the
> signer as a oracle.

The value of e is irrelevant, as the attack is based on the
homomorphic properties of RSA.

>>
>> Note that the Full-Domain Hash (FDH) signature scheme would use a hash
>> mapping the message to all of Z*_N, where here you have a hash mapping
>> to the (much smaller) space of 256-bit strings.
>
>
> My first impression was similar to yours where it just didn't feel right to
> exponentiate a 256-bit number instead of a 2048-bit number. So now I'm
> trying to search for an actual proof for why this would be bad.
>
>>
>> The problem is that this makes attacks based on factoring H(m) (in
>> your case a 256-bit number rather than a 2048-bit number) and then
>> using multiplicative properties of RSA much easier. The size of e is
>> irrelevant.
>
>
> Not sure what you mean by factoring H(m). Why would an attacker try to
> factor H(m)? Do you instead mean finding the e-th root of H(m)? (My
> assumption is that finding e-th roots in mod N is hard as claimed in
> RFC3447.)

No. The issue is that one can factor H(m), and with high probability
H(m) will even have small prime factors. You can then use an
index-calculus style attack to forge signatures.

The following papers have more details:
http://www.jscoron.fr/publications/padding.pdf
http://www.jscoron.fr/publications/isodcc.pdf

> Thanks,
> Filip
>
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] RSA signatures without padding

[Jonathan Katz]

On Fri, Jul 10, 2015 at 4:15 PM, Filip Paun  wrote:
> Suppose I have a message M for which I generate an RSA-2048 digital
> signature as follows:
>
>   H = SHA-256(M)
>   S = H^d mod N
>
> Assume N = p*q is properly generated and d is the RSA private key.
>
>
> And I verify the signature as follows:
>
>   S^e mod N == H'
>
> where H' is the SHA-256 of the message to be authenticated. Assume e is the
> RSA public key.
>
> Since I've not used any padding then are there any flaws with the above
> approach? What if e = 3? What if e = 2^16+1?
>
> Your guidance is much appreciated.
>
> Thank you,
> Filip

This is a bad idea.

Note that the Full-Domain Hash (FDH) signature scheme would use a hash
mapping the message to all of Z*_N, where here you have a hash mapping
to the (much smaller) space of 256-bit strings.

The problem is that this makes attacks based on factoring H(m) (in
your case a 256-bit number rather than a 2048-bit number) and then
using multiplicative properties of RSA much easier. The size of e is
irrelevant.
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] The Unbreakable Cipher

[Jonathan Katz]

On Wed, Sep 25, 2013 at 1:30 PM, Greg Rose  wrote:

>
> On Sep 25, 2013, at 9:40 , Jonathan Katz  wrote:
> > "Every cipher is breakable, given enough traffic": in principle, yes, as
> long as the traffic (formally, the entropy of the traffic) is larger than
> the key length.
>
> You misstated this. It's breakable if the *redundancy* of the traffic is
> larger than the key length.
>

Not so; this is most easily seen by taking the uniform distribution over
n-bit messages, in which case the entropy is n and the redundancy is 0.


> regards,
> Greg.
>
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] The Unbreakable Cipher

[Jonathan Katz]

On Wed, Sep 25, 2013 at 10:11 AM, John Young  wrote:

>  NSA Technical Journal published "The Unbreakable Cipher" in Spring 1961.
>
> http://www.nsa.gov/public_info/_files/tech_journals/The_Unbreakable_Cipher.pdf
>
> Excerpts:
>
> [Quote]
>
> David Kahn, "Lyen Otuu Wllwgh WI Etjown" pp. 71, 83, 84, 86,
> 88 and 90 of the *New York Times Magazine *November 13, 1960
> says that an unbreakable cipher system can be made from one
> time key "that is absolutely random and never repeats."  ...
>

I'm not sure why this was news in 1961; Shannon had this observation a
decade earlier and the one-time pad predates that.


>
> [Answer to the question:] "Does there exist an unbreakable cipher"
> would be this, "Every cipher is breakable, given enough traffic, and
> every cipher is unbreakable, if the traffic volume is restricted
> enough."
>
> [End quote]
>
> Is this conclusion still valid?
>

"Every cipher is breakable, given enough traffic": in principle, yes, as
long as the traffic (formally, the entropy of the traffic) is larger than
the keylength.

"Every cipher is unbreakable, if the traffic volume is restricted enough":
not true; the cipher that ignores the key and outputs the message in the
clear is not secure for any non-zero traffic. On the other hand, the
one-time pad is secure as long as the traffic is less than the keylength.


> If so, what could be done to restrict traffic
> volume to assure unbreakablility? And how to sufficiently test that.
> Presuming that NSA and cohorts have investigated this effect.
>
> ___
> cryptography mailing list
> cryptography@randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography
>
>
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Examples of Boneh/Silverberg Multilinear Forms

[Jonathan Katz]

The Weil and Tate pairings give (cryptographically useful) *bilinear* maps.

Cryptographically useful *multilinear* maps were unknown until recently:
  https://eprint.iacr.org/2012/610
  https://eprint.iacr.org/2013/183


On Wed, Aug 14, 2013 at 11:27 AM, Scott Guthery  wrote:

> In "Applications of Multilinear Forms to Cryptography," Boneh and
> Silverberg cite Weil and Tate pairings as examples.
>
> Are there others?
>
> Cheers, Scott
>
> __**_
> cryptography mailing list
> cryptography@randombit.net
> http://lists.randombit.net/**mailman/listinfo/cryptography
>
>
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Looking for earlier proof: no secure channel without previous secure channel

[Jonathan Katz]

Isn't it obvious? (I mean, there is some value in formalizing the model,
but still...)

Consider authentication of A to B. If there is nothing distinguishing
(impersonator) Mallory from (honest) A, then anything A can do can also be
done by Mallory.


On Thu, Jun 6, 2013 at 1:31 PM, Ralph Holz  wrote:

> Hi,
>
> I am currently doing a write-up that dives into some of the more formal
> aspects of authentication. In particular, I am wondering when exactly it
> was formally proved that two entities A and B cannot establish a secure
> channel between them without such a secure channel having been available
> to them at a previous point in time. Or, in other words, you cannot
> authenticate without already having authenticated credentials for that
> purpose.
>
> To the best of my knowledge, the earliest such proof is the one by Colin
> Boyd:
>
> Colin Boyd. Security architecture using formal methods. IEEE Journal on
> Selected Topics in Communications. 1993.
>
> Does anyone know of an earlier such (formal) proof?
>
> Ralph
>
> --
> Ralph Holz
> I8 - Network Architectures and Services
> Technische Universität München
> http://www.net.in.tum.de/de/mitarbeiter/holz/
> Phone +49.89.289.18043
> PGP: A805 D19C E23E 6BBB E0C4  86DC 520E 0C83 69B0 03EF
> ___
> cryptography mailing list
> cryptography@randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography
>
>
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] OAEP for RSA signatures?

[Jonathan Katz]

On Sat, 26 Jan 2013, ianG wrote:


Apologies in advance ;) but a cryptography question:

I'm coding (or have coded) a digital signature class in RSA.  In my research 
on how to frame the input to the RSA private key operation, I was told words 
to effect "just use OAEP and you're done and dusted." Which was convenient as 
that was already available/coded.


However I haven't seen any other code doing this - it is mostly PKCS1, etc, 
and RFC3447 doesn't enlighten in this direction.


Could OAEP be considered reasonable for signatures?  or is this a case of 
totally inappropriate?  Or somewhere in between?




iang


The following paper seems relevant here:
"Versatile Padding Schemes for Joint Signature and Encryption," Dodis et 
al., ACM CCCS 2004.

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Client certificate crypto with a twist

[Jonathan Katz]

On Wed, 10 Oct 2012, Guido Witmond wrote:


Hello Everyone,

I'm proposing to revitalise an old idea. With a twist.

The TL;DR:

1. Ditch password based authentication over the net;

2. Use SSL client certificates instead;

Here comes the twist:

3. Don't use the few hundred global certificate authorities to sign
  the client certificates. These CA's require extensive identity
  validations before signing a certificate. These certificates are
  only useful when the real identity is needed.
  Currently, passwords provide better privacy but lousy security;

4. Instead: install a CA-signer at every website that signs
  certificates that are only valid for that site. Validation
  requirement before signing: CN must be unique.


Looking at this just from the point of view of client-server 
authentication, how is this any better than having the website generate a 
cryptographically strong "password" at sign-up time, and then having the 
client store it in the password cache of their browser?


Note that both solutions suffer from the same drawback: it becomes more 
difficult for a user to log on from different computers.

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] chaos-based cryptosystem with quantum crypto similarities

[Jonathan Katz]

On Fri, 28 Sep 2012, d...@geer.org wrote:



I was asked to read this

Fundamentals of a classical chaos-based cryptosystem with some quantum
cryptography similarities
Vidal G, Baptista MS & Mancini H
International Journal of Bifurcation and Chaos
World Scientific Publishing Company


I am not aware of a single quality paper on chaos-based cryptography. I've 
never even seen a paper on chaos-based cryptography where the authors had 
the slightest idea of what secure encryption means, or how to do anything 
beyond the most basic cryptanalysis.


The submission probably belongs in the reject pile.


Abstract: We present the fundamentals of a cryptographic method
  based on a hyperchaotic system and a protocol which
  inherits some properties of the quantum cryptography but
  that can be straightforwardly applied on the existing
  communication systems of non-optical communication channels,
  and it is an appropriate tool to provide security on
  software applications for VoIP, as in Skype, dedicated
  to voice communication through Internet. This would enable
  that an information packet be sent through Internet
  preventing attacks with similar strategies to the employed
  if this same packet is transferred in an optical channel
  under a quantum cryptographic scheme. This method relies
  on fundamental properties that chaotic signals and coupled
  chaotic systems have. Some of these properties had never
  been explored to communicate securely.


I clearly need to read something else first.
Suggestions?

--dan

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography


___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

[cryptography] cryptanalysis of 923-bit ECC?

[Jonathan Katz]

Anyone know any technical details about this? From the news reports I've 
seen, it's not even clear to me what, exactly, was broken.


http://www.pcworld.com/businesscenter/article/257902/researchers_set_new_cryptanalysis_world_record_for_pairingbased_cryptography.html

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] RSA Moduli (NetLock Minositett Kozjegyzoi Certificate)

[Jonathan Katz]

On Mon, 26 Mar 2012, Thierry Moreau wrote:


Florian Weimer wrote:

* Thierry Moreau:


The unusual public RSA exponent may well be an indication that the
signature key pair was generated by a software implementation not
encompassing the commonly-agreed (among number-theoreticians having
surveyed the field) desirable strategies.


I don't think this conclusion is warranted.  Most textbooks covering
RSA do not address key generation in much detail.  Even the Menezes et
al. (1996) is a bit sketchy, but it mentions e=3 and e=2**16+1 as
"used in practice".  Knuth (1981) fixes e=3.  On the other side, two
popular cryptography textbooks, Schneier (1996) and Stinson (2002),
recommend to choose e randomly.  None of these sources gives precise
guidance on how to generate the key material, although Menezes et al.
gives several examples of what you should not do.


The original RSA publication suggests generating the RSA modulus N, and then 
the encryption and decryption exponents, resp. e and d, so that the first 
selection of the public exponent e might be rejected.


The current recommendations fixes the decryption exponent, and then tries 
random N until e mod phi(N) and d mod phi(N) are both >1. The current 
"desirable strategies" encompass more provisions, of course.


That can't be correct, for several reasons:
- If you deterministically fix the decryption exponent in advance, then 
everyone knows it. (Maybe you meant "choose d at random, and then find N 
compatible with that choice of d." Still, I don't see why you would do 
that, and if you did then there is no particular reason e would not come 
out to be non-prime.)
- Maybe you meant to fix e in advance, and then find N compatible with 
that value of e. But the check for compatibility is that gcd(e, phi(N))=1, 
not that e mod \phi(N) > 1.


Going back to the original question, I see no reason why non-prime e 
should be much less secure than prime e. In particular:
- The information leaked to the attacker is that gcd(e, \phi(N)) = 1. So 
the attacker arguably learns a bit more information about the factors of N 
if e is non-prime than if e is prime. But I don't see how this information 
can be used to help speed up current factoring algorithms.
- Fix e = e1 * e2, where e1 ande2b are prime. Conditioned on the fact that 
gcd(e, phi(N))=1, it is as secure to use public exponent e1 (or e2) as to 
use public exponent e. In particular, if an attacker could invert RSA 
with public exponent e, then it could also invert using public exponent 
e1; the (easy) reduction is left to the reader. =)


For the record, in the Katz-Lindell book we say that choice of e is 
arbitrary as far as security goes, but e=3 is prefered in practice for 
efficiency.

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] "Combined" cipher modes

[Jonathan Katz]

On Mon, 20 Feb 2012, Harald Hanche-Olsen wrote:


["Kevin W. Wall"  (2012-02-20 07:11:52 UTC)]



So my first question: Are there ANY "combined" cipher modes
for block ciphers that do not cause the ciphers to act as a key
stream? (That seems to be cause most of the ones I found build
the confidentiality piece around CTR mode.) If "yes", please name
a few (especially those with no patent restrictions).


You can always construct a "combined" mode (also caled an "authenticated 
encryption scheme") by combining a secure encryption scheme with a message 
authentication code (MAC) -- applying the MAC to the ciphertext, using 
independent keys. The NIST modes and others you have seen are slightly 
more efficient, however.



So my second question is, if all the "combined" cipher modes all
cause a cipher to act as if it is in a streaming mode, is it okay
to just choose a completely RANDOM IV for each encryption?


I'll bite on this one, leaving the harder part of your question to the
real experts. Yes, that should be okay, PROVIDED you have access to a
good source of entropy (aka randomness). See the long, long thread on
duplicate primes in RSA moduli to get a notion of how horribly wrong
things can go if you don't.


What he said. Note also that the potential problems with IV reuse, etc., 
don't go away by choosing a non-streaming mode, anyway. But modes are 
designed to be secure assuming the IVs are randmly chosen.

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] looking for DES implementation in C

[Jonathan Katz]

On Thu, 16 Feb 2012, Billy Brumley wrote:


I pointed my students to this clean one for a course I recently ran:

http://mayor.fri.uniza.sk/v731/u2/des.c


Thanks -- this worked for me, and satisfied the test vectors I ran it on. 
No further replies are needed.

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

[cryptography] looking for DES implementation in C

[Jonathan Katz]

I'm looking for a stand-alone implementation of DES in C. Can anyone point 
me to one (or send me one of their own)? Note: I know that there exist C 
crypto libraries that include DES, but I'd rather not install an entire 
library just to get access to DES.


(For those who are curious: this is for a course assignment. Though now 
that the students have alerted me to the fact that DES implementations 
seem to be hard to find -- doesn't anyone use triple DES? -- I'm also 
interested myself in getting my hands on one.)

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Duplicate primes in lots of RSA moduli

[Jonathan Katz]

On Wed, 15 Feb 2012, Steven Bellovin wrote:



On Feb 15, 2012, at 11:56 45AM, Ben Laurie wrote:



I did this years ago for PGP keys. Easy: take all the keys, do
pairwise GCD. Took 24 hours on my laptop for all the PGP keys on
keyservers at the time. I'm trying to remember when this was, but I
did it during PETS at Toronto, so that should narrow it down. With
Matthias XXX (I've forgotten his surname!).



How many keys?  They had 11M keys, meaning there are 121e12 pairs.  That's
a lot of GCD operations...


The blog post here:

https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs

Explains how it can be done in linear time.
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Chrome to drop CRL checking

[Jonathan Katz]

On Mon, Feb 6, 2012 at 9:52 PM, Steven Bellovin  wrote:
> http://arstechnica.com/business/guides/2012/02/google-strips-chrome-of-ssl-revocation-checking.ars
>
>                --Steve Bellovin, https://www.cs.columbia.edu/~smb

Interesting blog post on this topic by Adam Langley here:
  http://www.imperialviolet.org/2012/02/05/crlsets.html

One question, though. Langley writes:
   "If the attacker is close to the server then online revocation
checks can be effective, but an
attacker close to the server can get certificates issued from many
CAs and deploy different
certificates as needed."
Anyone follow this line of reasoning?
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?

[Jonathan Katz]

On Wed, 1 Feb 2012, Nico Williams wrote:


On Wed, Feb 1, 2012 at 3:49 AM, Francois Grieu  wrote:

The talk does not give much details, and I failed to locate any article
with a similar claim.
I would find that result truly remarkable, and it is against my intuition.


The video you posted does help me with the intuition problem.  The
idea seems to be to replace the normal arithmetic in SHA-1 with
operations from a zero-knowledge scheme such that in the end you get a
zero-knowledge proof of the operations that were applied to the input.
That makes complete sense to me, even without seeing the details.
But maybe I'm just gullible :^)

Nico


In some sense this is all not very surprising. The Cramer-Damgard paper he 
cites in his talk describes a zero-knowledge proof for the NP-complete 
problem of boolean circuit satisfiability. So the only question is to 
express SHA-1 (plus a check for string equality) as a boolean circuit and 
then apply their technique. And implement it, of course. =)


(Anyone have an estimate as to how many gates such a circuit would have, 
assuming you are evaluating SHA-1 on a two-block input?)


As he says in his talk, the point of the exercise is not to claim any 
novelty for the resulting protocol, but to explore how efficient these 
generic techniques can be when applied to circuits of practical interest. 
Since he appears not to have written up the work, it is unclear what 
additional optimizations could have been made.

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Password non-similarity?

[Jonathan Katz]

On Tue, 3 Jan 2012, Solar Designer wrote:


On Mon, Jan 02, 2012 at 09:40:36PM -0500, Jonathan Katz wrote:

Say passwords are chosen uniformly from a space of size N. If you never
change your password, then an adversary is guaranteed to guess your
password in N attempts, and in expectation guesses your password in N/2
attempts.

If you change passwords constantly, and an adversary guesses a random
password (with replacement) each password-guessing attempt, then in
expectation the adversary guesses your password in N attempts.


Not exactly.  In N attempts, assuming that N is very large, their chance
will be more like 1-1/e, which is around 63%.  For a 50% chance, I think
they need to try merely N*ln(2) passwords, or about 69% of N.


At the risk of belaboring this point, there is no contradiction: You are 
calculating the probability of compromise after N attempts, and I was 
referring to the expected number of attempts before a compromise occurs.

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Password non-similarity?

[Jonathan Katz]

On Mon, 2 Jan 2012, lodewijk andr?? de la porte wrote:


The reason for regular change is very good. It's that the low-intensity
brute forcing of a password requires a certain stretch of time. Put the
change interval low enough and you're safer from them.

We've had someone talk on-list about a significant amount of failed remote
ssh login attempts. Should he chose not to force user to change their
passwords they wouldn't. And the likelyhood of a successfull login
would improve with the years (given coordination) to somewhere above the
admin's comfort zone.


I just don't buy this argument; am I missing something?

Say passwords are chosen uniformly from a space of size N. If you never 
change your password, then an adversary is guaranteed to guess your 
password in N attempts, and in expectation guesses your password in N/2 
attempts.


If you change passwords constantly, and an adversary guesses a random 
password (with replacement) each password-guessing attempt, then in 
expectation the adversary guesses your password in N attempts. Not much of 
an advantage.


(This seems like such a trivial point I hesitated to post it, but I 
haven't seen it come up explicitly at any point in this thread.)


The point you raise below (about limiting exposure once a password *is* 
guessed) remains valid, though for common-use passwords (where an 
adversary can simply lock the legitimate user out of the account once the 
password is guessed) I wonder how much benefit there really is.



The timeframe in which a password has to change also limits the maximum
time exposed once someone has cracked it. This is relevant when the
adversary needs multiple opportunity's to coincide. The amount of time
it'll have access without triggering resource-counting or other
"suspicious behavior" alarms becomes limited, as changing a password would
either lock him or the legitimate user out.

For most systems though, it's a complete waste of time.
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Minimally Sufficient Cryptosystem

[Jonathan Katz]

On Tue, 5 Jul 2011, Scott Guthery wrote:

Adi Shamir gave a talk at MIT last week at which I think he said that the 
following cryptosystem was minimally sufficient:


XOR Key / Permutation / XOR Key

He seemed to me to imply that (informally speaking) any additional complexity 
would be more likely to provide attack opportunities than not.


Perhaps anybody else that was there or is familiar with Shamir's work along 
this line might comment.


Hard to say what he was talking about without some context, but it sounds 
like he might (?) have been referring to DES-X:

  http://en.wikipedia.org/wiki/DES-X
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] wanted: recommendations for best papers in cryptology

[Jonathan Katz]

On Fri, 7 Jan 2011, travis+ml-rbcryptogra...@subspacefield.org wrote:


Hey all,

I'm attempting to create an extensive archive of papers on -graphy and
-analysis, locally stored and broken down by category/hierarchy,
according to my own personal taxonomy.  Maybe one day I'll try to
figure out how to annotate their metadata in some way, possibly a
bibtex-to-filename-to-hyperlink mapping, and web apps to ease data
entry.

[SNIP]

I recall Schneier had an interesting self-study course in block
cipher cryptanalysis:

http://www.schneier.com/paper-self-study.pdf

Is there anything else out there like this?


For cryptanalysis, see Heys's survey "A Tutorial on Linear and 
Differential Cryptanalysis", 
http://www.engr.mun.ca/~howard/Research/Papers/ldc_tutorial.html



Also, here are three books I wish I had.  Do they exist, or will I
have to compile them over the next decade or two?

0) Cryptographic Protocol Design

Something like this:
http://www.subspacefield.org/security/security_concepts/index.html#tth_sEc28.6
However, I think it could be made into an entire book, and covered in far
more detail and less like a "cookbook", but still accessible to security
engineers, as opposed to discrete math postgrads.


Of course, as far as a basic crypto reference goes I have to mention my
textbook "Introduction to Modern Cryptography", but that book is geared 
more to people interested in theory than to practice. (On the other hand, 
it does cover problems with using e=3 incorrectly for RSA, hash length 
extension, chosen-ciphertext attacks, and some other things that fall into 
your category 1 below).




1) Cryptography: A Study in Failure

Show cryptosystems and how they were broken or semi-broken, over the
years.  That _is_ how we learn, right?

I'm thinking of knapsack, Kerb, e=3 SSL keys, hash length extension,
PKCS#7 padding oracle, and so on.


Maybe not exactly what you are looking for, but see lecture 9 here:
  http://www.cs.umd.edu/~jkatz/security/f09/syllabus.html
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Generating passphrases from fingerprints

[Jonathan Katz]

On Sat, 4 Dec 2010, Jens Kubieziel wrote:


Hi,

recently I had a discussion about biometric data. The following problem
occured:
Assume someone wants to register at a website. He swipes his finger over
his fingerprint reader. The reader generates strong passphrase from the
fingerprint and other data (hostname of the targeted site, user name
etc.) and creates a strong password. This will be the users login
password. Everytime the user wants to log in again he swipes his finger
over the reader, password is generated again and sent to the site.

We were not sure if it possible to generate the same passphrase again
and again. Does anyone know if such systems exist? Will generating the
passphrase work? I'd glad to hear some opinions about this.


There has been much work on this question in the cryptography literature 
under the name "fuzzy extractors", though I don't think any of it has yet 
been implemented. A survey from 2008 is available here:

  http://www.cse.psu.edu/~asmith/pubs/2008/fuzzysurvey.pdf
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] short signature scheme?

[Jonathan Katz]

On 2010-11-08 15:51, Jonathan Katz wrote:


I am looking for a short signature scheme (certainly shorter than RSA
signatures, as short as possible would be nice...) that is *patent-free* 
and (less important) easy to implement. Any suggestions?


Thanks to everyone who answered. (And I especially liked the suggestion to 
use the [GJKW] scheme!) I was actually hoping for something even shorter, 
though maybe that is not known.


A few questions remain:
- In general, what are the patent issues involved in using dlog-based 
signature schemes (whether DSS or [GJKW] or something else...) when 
instantiated using elliptic curve groups?


- Some people mentioned that 2^k security requires signatures of length 
2k, presumably by analogy with hash functions. Although I see some 
intuition for thinking this, I don't see formally why this must be the 
case. (In particular, I don't see why it's an issue if two legitimately 
issued signatures happen to be the same, as long as they couldn't have 
been forged in advance.) Even more so if some application is signing short 
messages to begin with.

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

[cryptography] short signature scheme?

[Jonathan Katz]

I am looking for a short signature scheme (certainly shorter than RSA 
signatures, as short as possible would be nice...) that is *patent-free* 
and (less important) easy to implement. Any suggestions?

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] What's the state of the art in digital signatures? Re: What's the state of the art in factorization?

[Jonathan Katz]

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.
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] What's the state of the art in factorization?

[Jonathan Katz]

On Thu, 22 Apr 2010, Zooko O'Whielacronx wrote:


On Wed, Apr 21, 2010 at 5:29 PM, Samuel Neves  wrote
(on the cryptogra...@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".

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography