Do I need to worry about timing attacks in Base64 encoding/decoding of private keys? Do I need to worry about timing attacks in Base64 encoding/decoding of private keys?  This is a common operation (ex.  PEM keys) and is variable time in typical implementations.

Yes, kind of. The encoding does depend on the individual bits so there could very well be timing differences. Note that the differences would be pretty small; encoding a byte is likely much faster than e.g. modular exponentiation. But as even block ciphers are vulnerable it may very well be possible, especially since table lookup may be implemented.

The solution however is also very standard: before storing the keys you first wrap the keys with a symmetric cipher. The key can be derived from a strong passphrase. Most of the time when private keys are stored in PEM format (which is just the ASCII armor) they are encoded in PKCS#12. As the encoding after the wrapping and the decoding before, you should be secure against timing attacks against base 64. Obviously the block cipher is much more likely to be protected against timing attacks (but don't forget to verify that).

In principle PKCS#8 could also describe an encrypted private key, but that doesn't seem to be used much. PKCS#12 can be used to encrypt the private key and store the certificate (chain) for the public / private key pair.

If you directly store them in PKCS#1 or PKCS#8 format (without encryption) you should make sure the system itself is secure - especially with regards to file access.

The only inevitable data dependence in Base 64 encoding or decoding is on the length of the value being encoded or decoded.

Encoding

Extraction of 6-bit value by bit shift and masking: constant time.
Conversion from 6-bit to a character: indexing into a 64-character table, constant time.

Decoding

Conversion from a character into a 6-bit value: indexing into a 256-byte table, constant time.
Insertion into decoded data by bit shift and ORing: constant time.


With sufficient randomness, is XOR an acceptable mechanism for encrypting? I have heard criticism of various cryptosystems saying that "at their heart, they were just XOR."

Is this just ignorance, or is there something inherently wrong with XOR based ciphers?

It's important to make the distinction between ciphers which use XOR
internally as a component operation (which is nearly all of them),
and 'ciphers' which just XOR the plaintext with a secret. If the key
is the same length as the plaintext, then it's a one time pad, so in
some sense, yes, with "sufficient randomness" you can safely encrypt with XOR.
The problem with this is that it only applies if the key is
exactly as long as the plaintext, and is perfectly uniform random.
If it's not, then you've basically created a Vigenere
cipher, which
can be trivially broken. It's interesting, and unfortunate, how
the 'provable security' of the OTP fools people into thinking
they can just take a little shortcut or two and still get
something safe.

Typically, people who implement simple XOR ciphers compound their
mistake by using hard-coded keys, in which case a single known
plaintext/ciphertext pair is sufficient to decrypt anything.
That's probably mostly because if you were some kind of prebuild
crypto toolkit, it would be easier to just use AES along with your
RSA key management, etc, versus using a decent key distribution
scheme and then using XOR with your safely shared keys.

Practically though, if you were to ship (securely) a one tera-byte disk containing random bytes to a friend, then you would have a very safe channel for up to one TB of communication, enough for quite some time.


Can I measure entropy through compression only? Say I have a file containing words from the English language.  Not meaningful text, just a repetition of a few words.  The original size is 1559454 bytes and it is compressed by a certain program to 75742 bytes.  (A very good compressor, it seems.)  Can I estimate the entropy of the source producing such file using essentially the byte reduction?

Can I estimate the entropy of the source producing such file using essentially the byte reduction (when compressing the source's output)?

No, at least for Shannon entropy. Entropy is a characteristic of the source, that can't be determined from a finite sample of the output of the source. It's can't even be estimated in practice without information about what the source is, and the question gives no such information.
The best we can is estimate a plausible upper bound of the entropy of the source that generated the file: $75742/1559454$ entropy bit per output bit. That's not a mathematical certainty: it's mathematically possible that a perfectly random source generated that file (the probability is $2^{-8\times1559454}>0$). And that's not a practical certainty either, unless we add a vague hypothesis that the observed characteristic goes on: a device which output consists of the $1559454$ fixed bytes followed by indefinitely many uniformly random bytes is a source with $1$ entropy bit per output bit.
We do not get any lower bound better than $0$. Proof: any deterministic program that indefinitely outputs is a source with zero entropy. And it is trivial to make a deterministic program that indefinitely outputs a sequence starting with the $1559454$ bytes (perhaps, repeated). That's not merely theoretical:

The program which output consists of the repeated sequence of two bytes a  produces output which first $1559454$ bytes matches the problem statement, even for some actual compressor; say, one that never compresses by more than a factor of 20 (that's quite plausible for e.g. an audio compressor).
Even if we restrict to files that could reasonably occur in actual use, it's entirely possible that a program designed to obfuscate a file into english words, written as an (elementary and rather poor) steganography tool, has output that matches the problem statement (for an actual text compressor) when fed as input a file of about $50000$ bytes, including if it is all-zero.

Conclusion: practical procedures that attempt to assess the entropy of a source from its output only are doomed to, at best, give a plausible upper bound of that entropy (and can do so only under the hypothesis that the output tested is representative). Computing a compression ratio is one such method.

In this case compression would be a terrible way to measure entropy; compressing the file would lead to a non-English result, guaranteeing your entropy calculations are next to useless (although technically correct). A better way for your case would be to do some math with the selection of the words.
Calculating entropy through compression is good for binary data, not text.

How many possible words are there to choose?

More words to choose from will mean greater entropy:word ratio.

How randomly are they selected? Does the word selector have near-perfect randomness?

The entropy of this selector will make or break your word entropy levels. This is the part to direct your focus to.

How many words do you have?

if each word is selected randomly from a set of $256$ words (with perfect entropy), then each word corresponds to $1$ random byte (8 bits of entropy).

Since the English language has words of varying lengths and structure calculating entropy through compression will lead to inconsistent results. If, however, you want to measure it through compression:

Your results will be in terms of the entropy:byte ratio, not the entropy:word ratio.

To correct for this, find the average byte length of all words in your sample, then divide the entropy by that average to get the entropy:word ratio.

Certain words will be more similar, thus looking to the compressor to have less entropy.

This cannot be corrected. You can only filter this as "noise" by taking more samples of different data.
If your file is constant (you're measuring a specific file, not a random word generator) this will forever contaminate your results. A larger file will, however, lessen this.
The entropy of the English language itself will affect your results. This will be the case no matter how many samples you take.

Certain words will appear to have less or more entropy than others, while in reality each word has the same amount of entropy if chosen randomly.
Your compression function doesn't know this.

A better compression function will lead to better results

The idea of using compression to measure entropy is to compare data to an "ideally compressed" version of itself. The closer you get to ideal compression the better your results.
Once compressed with an ideal compression function, you can take the output size divided by the input size (this should be between 0.0 and 1.0). If the ideal data has 1 bit per bit entropy, the data you tested must have the number you got before.
If the compression isn't ideal compression, which it isn't, you can take the compressed data's entropy (which requires you to know the entropy of the compressed data) and multiply by the size ratio from before.

Or, just assume your compressor is perfect and accept the resulting inaccuracy. This might be more practical.
You might be able to estimate the entropy of the compressed data by repeatedly applying the compression until you get perfect entropy (no compression). Then just multiply the size ratios as stated before.

This only works if the compression function can effectively compress its own output.
In this case you end up recursively measuring entropy.

For the best possible results, you could craft a compression function for your specific data.

If you have 65536 words, you can obtain ideal compression by converting each word to a unique 16-bit sequence. This only works if the number of words is a power of 2.

Unless the number of words is a power of 256, you must be able to handle bit-length data instead of byte-length. This will take some cleverness on your part.
If you want to audit your word selection, you must then compress this using a normal compression function (this becomes the data you test the entropy of).

This could remove many biases associated with compressing the English language.
In this case you end up recursively measuring entropy.

As you can see, it might be a lot better to do a little math on your word selection. If, however, you want to know the entropy of the word selector itself, you have no choice but to use compression.

And a final takeaway:

If every sample is generated by the same way, each sample will have equal entropy.

Your compression test will disagree and say different samples have different amounts of entropy.
Compression is a good way to estimate entropy, but it doesn't determine entropy.

You can simply take the average of many samples to find the actual entropy of each sample.


AES key equal to IV (CBC mode) Application uses AES in CBC mode with 128 bit key. In this implementation key is always same and is equal to IV.
Can attacker get the key or decrypt data? If he knows:

First and second blocks of plaintexts;
All blocks of ciphertexts.

The software mentioned above is malicious program, it encrypts all office files on user's computer. And I now attempt to help user get his data back. Reverse engineering of this program shows that key is unknown, but is always same and is equal to IV.

In this answer I'm assuming that a key is used to encrypt more than one message.

The first weakness is that CBC with fixed IV leaks if messages share a common prefix.
The second weakness is that it makes a padding oracle attack much more severe. Consider a device that knows the key and decrypts a ciphertext you send to it. While it won't tell you the plaintext, it'll leak if the padding was valid (e.g. via an error message or timing). Such a device acts as padding oracle.

For normal use of CBC with PKCS#7 padding and a known (variable or fixed) IV, such a padding oracle will allow an attacker to recover the message associated with plaintext, but it will not leak the key.

When using a fixed secret IV, it doesn't recover the plaintext of the first message block directly, rather it recovers $m_1 \oplus \mathrm{IV}$. When the attacker has access to several ciphertexts, this behaves like a many-time-pad thanks to the reused IV. Due to the redundancies of natural languages this should allow recovery of the IV given only a few ciphertexts.

If the key is reused as IV this IV recovery attack becomes a key recovery attack.

I don't expect either of these weaknesses to help a ransomware victim, since the first is only a minor leak and the second requires a padding oracle, which you probably won't have.

Yes IV is not intended to be secret. It is given in clear with the ciphertext (usually the first block of it).

An attacker, given the ciphertext, can recover the first 128 bits, use them as the IV and as the key and recover the original plaintext.

The scheme you described is completely broken and to be considered not secure at all.


How to Understand Authenticated Key Exchange? I am reading some articles about key exchange. I know classic key exchange, such as Diffie-Hellman key exchange. This type of algorithm is vulnerable to man-in-the-middle attack. However, when using a digital signature algorithm, this attack is invalid.

So, does authenticated key exchange consist of classic key exchange and a digital signature algorithm? Who can tell me?

One way to understand this is through a rather abstract and constructive viewpoint, abstracting away specifics.

As you mentioned, a DH key exchange needs to be done in an authenticated manner otherwise man-in-the-middle attacks become possible. In other words, we needs the communication to happen on a authenticated channel.

How do we get an authenticated channel? One way is to use digital signatures. They would allow to verify that the message comes from the legitimate sender. However we still have a problem, the verification keys needs to be transmitted somehow and so far we only have an insecure channel.

In order to resolve this problem, we send digital signatures parameters over an authenticated channel that is obtained by using certificates. If we trust certification authorities, we have indeed an authenticated channel.

Everything put together in a constructive way:

1) Using certificates we construct an authenticated channel that allows exchange of digital signature parameters

2) Using digital signatures, we construct an authenticated channel that allows key-exchange(D.H).

3) Using key exchange results we could also construct a secure channel.

Yes, for example in SSL peers identify each other by exchanging certificate.
- each peer verifies cerfiticate that received other peer.
- If verificatioin is end successfully, client start diffie-hellman by send client's DH-parameter

that is example of authenticated key exchange


If $H(x)$ is a one-way function, is $f(x)=H(x)\cdot x^{-1}$ a one-way function? Assume $S$ is a domain. $S' \subseteq S$ and all elements in $S'$ are invertible.  $H:S'\rightarrow S$. If $H(x)$ is a one-way function, is $f(x)=H(x)\cdot x^{-1}$ a one-way function?

Let ${y=x^{-1}}$. if ${f(x)}$ is a bijective function. then we can avoid ${H(x) \cdot y= H(x) \cdot y'}$, where every ${x}$ has unique ${f(x)}$


How can an amateur introduce a cryptographic algorithm? I have a new cipher, and I want to get it properly vetted, but I don't have a strong way to prove its security properties.  I'm an amateur without ties to a strong cryptographer/university.  I have attempted a few indistinguishability proofs, but these are "back of the napkin" proofs and are likely not rigorous.  (I have colleagues that have done cryptanalysis on it, but they are not theorem types.)

As a result, I feel that I don't stand a chance of getting it published without a proof of security, but I feel that I can't find someone to help without it being published.

How can I find someone willing to join on and help write a compelling proof, and generally help write a compelling paper, (or identify a weakness that prevents me from doing something stupid with the cipher)?

Given that I have done these things:

Review previous ciphers, find they're not what you want, invent new cipher
Internally analyze it (plots, prototype code, etc.)
Socialize it to cryptanalyst peers, get tentative green light (rather, absence of red light - no new findings in a while)

Is this a reasonable path going forward:

Brief it at an IACR rump session
Have follow-on discussions at conference, express my need, find someone that way
Submit as a work-in-progress in lower tier, but bonafide crypto conference
Submit as a journal article

Is a rump session a good way to go to find interested math types, and/or as a first step to announcing the idea?  Are there other alternatives, such as quarterly meetings of some group that might be willing to hear the idea?

Similarly, is there a good "starter conference" for crypto open to new ideas that might lack the mathematical rigor?

In contrast to this thread, How to publish a cipher (concept), the main answer suggests that formalisms are a prerequisite to publishing: "If you submit a cipher, one would expect at least a formal analysis of why you think this is a good idea."  My question is what if you don't have that ability - how do you find someone that can help with that?  The rest of the answers on the thread went into how to make it into a bachelor's thesis.

In additional defense of this thread, there are many great suggestions that don't appear on that other post.  While I'm biased - but have nothing to gain - these threads are unique.  I'm okay with marking as duplicate as long as somehow you can merge the useful answers below into the other question.

First, if it's a secret-key cipher, then you'll never find any proof of security—at best you'll, exhaust the standard cryptanalysis techniques and exhaust the brilliant ideas of the brilliant cryptanalysts.  If it's a public-key cryptosystem, then at best you can prove reduction to a widely understood uniformly hard problem.  If you're not already familiar with these facts, you won't get the attention of serious cryptanalysts.

Second, you need to convincingly demonstrate (a) that you understand the standard cryptanalysis techniques, and (b) that it does not fall to them.  Cryptanalysts don't want to waste time doing your homework.  If you haven't already done your homework, you won't get the attention of serious cryptanalysts.

There's no good textbook of which I'm aware on this subject, but you might start with

  Bruce Schneier, ‘Self-Study Course in Block Cipher Cryptanalysis’, Cryptologia, 24(1), January 2000, pp. 18–34.
  https://www.schneier.com/academic/archives/2000/01/self-study_course_in.html

Third, if you want this to be anything more than an amusing intellectual exercise for bored cryptanalysts whose attention you've gotten, your cryptosystem has to fill a niche that nothing else does.  Is it faster or lower-energy on some significant platform than every other cipher providing comparable security?  Does it fill a specific need that no other cipher does, like a weird block size that is important for some particular reason?

For example, Gimli is a sponge with a much smaller state than Keccak-f1600, conveniently fitting in registers on more platforms, out of which one can build all manner of secret-key crypto gizmos.  (Gimli is a very new design, with some preliminary theoretical cryptanalysis.)

If you propose a general-purpose stream cipher that's not faster than software ChaCha or hardware AES-CTR, or a general-purpose collision-resistant hash function that's not faster than software BLAKE2b or hardware SHA-3, you won't get the attention of serious cryptanalysts who aren't either just bored or hoping their novel pet cryptanalysis techniques that failed to break the aforementioned ones might break something.

This applies even to designs that already have been published: Maybe RIPEMD160 resists collisions better than SHA-1 does, but it's not worth the time of most cryptanalysts to study it.  Maybe CAST6 is a better 128-bit block cipher than AES, but it's not worth the time of most cryptanalysts to study it.

Finally, if you want to get the attention of cryptanalysts, don't start with your cipher—start by showing that you are a competent cryptanlyst by using novel techniques to break crypto!  Best if you can break existing cryptosystems that were previously unbroken, or break them worse than the best published attacks.  This may be easier if you study cryptosystems that have received relatively little attention, including your own.

If you have a write-up demonstrating all of this—either a description of a novel cipher with evidence of resistance to standard cryptanalytic techniques and a reason to be interesting, or a novel cryptanalytic attack on an existing cipher—then a first step would be to submit it to the IACR cryptology eprint archive.  That won't impart the kind of serious review that, e.g., the AES and SHA-3 competitions did, of course, but it may catch the notice of some cryptologists and will be easier to show to someone whose review you are seeking, and if you do get the attention of a serious academic cryptologist they will likely have followup suggestions for publication venues.

The endeavor you try to enroll in may not look easy at all. Nevertheless I think a good approach to use would be to delimit your goal. For instance, the math required for cryptanalysis may be very complex but this is specially the case for public key encryption. My guess is that you are purposing a block cipher which required math is much less complex.

I good start would be to learn linear differential cryptanalysis perhaps reading this tutorial which make is easier to understand. This cryptanalysis is the most popular and AES was based on protecting against this kind of attack. For long time this cryptanalysis was kept as secret by government and industry. The tutorial uses a test cipher with the most common procedural used by ciphers which is weak and this is meant so for the purpose of learning the technique.

If you perform the linear and differential cryptanalysis on your cipher, surely it will be accepted in a Journal. Also it will determine if your cipher is strong or weak or perhaps if it need to tweaks to make it so. I guess your goal is not academic, so you may want better to summit your paper in one of these online Journals with a very high acceptance rate. Publishing your work will be true test of your cipher when inviting others to perform research on it.

Also, once your cipher is published you could challenge users in this forum as well the puzzling forum to break it.

Finally if you are not able to learn cryptanalysis you could just perform a benchmark on performance. Your cipher against the most common ciphers and if it were the case that your proposal is the fastest of all on them, then it could be good enough results for being published in a Journal or conference and let the community to research on its security since it would be interesting since it would be energy efficient. This wouldn't take that long since you could use libraries such as openSSL which has most common ciphers already implemented; you would just need to write your cipher in C/C++ to perform the benchmark (perhaps this is something you already have done).


zero knowledge proof for complete new user authentication Consider an environment, an user A who is completely new to the environment is entering. An user B who is member of the environment need to verify A as genuine not liar.

No information about user A is known to B.

Is it possible using the zero knowledge proof.

No, you can not.

You assume:

$B$ does not know anything about $A$.
You need to know if $A$ is actually called Alice.

Well, that does not work. There is no possible proof that $A$ is actually called Alice. That is unless you verify some other credentials, e.g. an ID card. But trust can not be generated out of nothing. That is simply impossible.

For example, if there is no way to verify a persons name, then no one in the world can decide if he is actually talking to the real Alice or to Eve who is just calling herself Alice.

The question has nothing to do with zero knowledge - that is just impossible in general.

You can generate a random keys pair for each user, and store the public key of each user somewhere on the net (blockchain, Usenet, ZeroDB, a website...)

Then, each of your users could share a link to their public key for their friends. Friends could then verify signature of challenge to be sure it's the real friend and not a liar.


How does asymmetric encryption work? I've always been interested in encryption but I have never found a good explanation (beginners explanation) of how encryption with public key and decryption with private key works.

How does it encrypt something with one key and decipher it with another key?

Generally speaking, the public key and its corresponding private key are linked together through their internal mathematical structure; such keys are not "just" arbitrary sequences of random bits. The encryption and decryption algorithms exploit that structure.

One possible design for a public key encryption system is that of a trapdoor permutation. A trapdoor permutation is a mathematical function which is a permutation of some space, such that computing the function in one way is easy, but the reverse is hard, unless you know some information on how the trapdoor permutation was built. Encryption is applying the function on a message, decryption is about using the trapdoor to reverse the function.

For RSA, a well-known asymmetric encryption algorithm, consider a rather big (say 300 digits or more) integer $n$. $n$ is composite: it is the product of two big prime integers $p$ and $q$. There are more such composite integers than there are particles in the observable universe, so there is no problem in generating such an integer. $n$ is called the modulus because we will compute things "modulo $n$". It turns out that:

it is easy to compute cubes modulo $n$ (given $m$, compute $m^3 \mod n$);
if $p$ and $q$ were chosen appropriately (I skip the details), raising to the cube is a permutation modulo $n$ (no two integers modulo $n$ will have the same cube, so any integer between $0$ and $n-1$ has a unique cube root modulo $n$);
computing the cube root of an integer modulo $n$ is extremely hard
... unless you know $p$ and $q$, in which case it becomes computationally easy;
recovering $p$ and $q$ from $n$ (that's factorization) is extremely hard.

So the public key is $n$, the trapdoor permutation is raising to the power 3, and the reverse is computing a cube root; knowledge of $p$ and $q$ is the private key. The private key can remain "private" even if the public key is public, because recomputing the private key from the public key is a hard problem.

There is a bit more to RSA than the description above (in particular, RSA does not necessarily uses the power 3), but the gist of the idea is there: a function which is one-way for everybody, except for the one who selected the function in the first place, with a hidden internal structure which he can use to reverse the function.

SSL (now known as TLS) is a more complex beast which usually uses some asymmetric encryption during the initial stages of the connection, so that client and server end up having a "shared secret" (a commonly known sequence of bits); the shared secret is then used to apply conventional encryption and decryption to the rest of the data ("conventional" meaning: same key to encrypt and decrypt).

There are 2 keys mathematicly related to each other . These work with a so called trapdoor function = very easy on the one side very hard on the other .
eg : multiply 2 big numbers together is easy . Finding out the prime numbers they consist of is vcery hard ( nearly impossibe ) . In RSA this works like that . In ECC things are a bit different . The encryption algo uses This public key to encrypt something . Only the related private key can decrypt it . ( the maths behind it are very complex )


How can a hash function that implements random oracle model have collision resistance? ROM is considered to be collision resistant. Does ROM assume there is an infinite set of outputs, or assume the output set is always larger than the input set? Because by the pigeonhole principle, ROM is guaranteed a collision given a large enough set of input, even when the output is generated randomly.

As Ella Rose points out in a comment, it is not that there are no collisions; rather, one can prove that the probability of encountering a collision is small in the random oracle model.

The random oracle model posits a finite domain and a finite codomain; otherwise the space of functions would be infinite and there could not be a uniform distribution on them.  If $f\colon A \to S$ is a uniform random function into a set $S$ of $n$ elements (e.g., $S$ is the set of $t$-bit strings, so that $n = 2^t$), then $f(x)$ is independent for each distinct $x$, and $\Pr[f(x) = h] = 1/n$ for each $x$ and $h$.

When we combine these two properties—$x \ne x'$ implies $f(x)$ and $f(x')$ are independent, and $\Pr[f(x) = h] = 1/n$—we can conclude from a standard birthday argument that any algorithm making $q$ queries to a random oracle has probability at most $q^2/n$ encountering a collision.  Following Ramanujan, Knuth, etc., the expected number of queries before a collision is $$1 + \sum_{k=0}^{n - 1} \prod_{i=1}^k \biggl(1 - \frac i n \biggr) = 1 + \sum_{k=1}^n \frac{n!}{(n - k)! \, n^k} \approx \sqrt{n \pi/2}.$$   Consequently, the expected query cost of any algorithm to break a cryptosystem like RSASSA-PSS signature by finding a collision in a $t$-bit random oracle is about $2^{t/2}$—which for typical values of $t$ like 256 is far beyond the capacity of humanity to carry out.

Of course, it is possible that we will learn something about SHA-256 that enables finding collisions more cheaply than generic collision searches, like we did with MD5 and SHA-1.  But this is how the random oracle model works.

That is the point of ROM. You assume 'somehow' the existence of a truly random function with no collisions. You do not care how this is constructed and designed because there is no real truly random hash function. But you assume it exists in an ideal world. Of course this has implications in real world because such a function does not exist. But ROM supporters will tell you that they provide a nice modular approach for security proofs in a way that we do not care about this function in real world: if you instantiated with a problematic hash function then you just change it. But the model, the random oracle model is sound and complete and it is focused on other attacks as well that do not change with the choice of the hash function


How to calculate a private key from public key on elliptic curve? Provided, that you have to multiply a well known G by the private key to obtain the public key, why not keep adding G to itself until you reach the public key. The private key should be the number of times you've added the G to itself. Is it correct? And if so - why isn't it feasible?

Yes your method is mathematically correct but it isn't feasible because of the size of the secret key $k$ that is used in practice.

Typically you are using curves over $\mathbb{F}_q$ where $\log_2 q \approx 256$. This means that there are $2^{256}$ possibilities for $k$ and, on average, it will take a very, very, very long time to find the correct one.

As a comparison, the Universe itself is estimated to be "only" $2^{58.5}$ seconds old. This means that even if you could try $1,000,000 \approx 2^{20}$ values of $k$ every second, it would take you $2^{255-20} = 2^{235}$ seconds to try half of the possible values. This amount of time is $2^{235-58.5} = 2^{176.5}$ times greater than the age of the Universe.

Turns out, that the public key is not calculated by adding G to itself k (private key) times. It is calculated by first changing the k to binary form and multiplying the public key variable by 2 (adding to itself) for each bit while adding G if the current bit has value of one.


Is it possible to match encrypted documents using user-defined search terms? Suppose I am storing a number of encrypted documents in a database. I would like to make it possible to identify the subset of documents whose contents match user-specified search terms without a) maintaining a plaintext index or b) decrypting documents on the fly. Is there any way to accomplish this securely?

By the same token, I'm wondering if a collection of encrypted documents can be sorted according to an encrypted attribute (e.g., document title) without first decrypting all attribute values.

Yes.  If you encrypt the documents with this purpose in mind (you have to use a special kind of encryption algorithm), then yes, it is possible to do this, for certain kinds of search queries.

There is a rich research literature on this topic.  The buzzword is "search on encrypted data".  I'll point you to a few sample papers in this space.  Do a literature search, and you should be able to find many more for yourself.

CryptDB: Protecting Confidentiality with Encrypted Query Processing, Raluca Ada Popa, Catherine M. S. Redfield, Nickolai Zeldovich, and Hari Balakrishnan.  SOSP 2011.  See also the CryptDB web page.
Secure Indexes, Eu-Jin Goh.
Practical Techniques for Searches on Encrypted Data, Dawn Xiaodong Song, David Wagner, and Adrian Perrig.  IEEE Security & Privacy 2000.
Public key encryption with keyword search, Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano. EUROCRYPT 2004.
Designing Secure Indexes for Encrypted Databases, Erez Shmueli, Ronen Waisenberg, Yuval Elovici, and Ehud Gudes. Database Security 2005.
How to Search on Encrypted Data, Eu-Jin Goh.  Slides.
Private Searching On Streaming Data, Rafail Ostrovsky and William E. Skeith III.  CRYPTO 2005.
New Constructions and Applications for Private Stream Search (Extended Abstract), John Bethencourt, Dawn Song, and Brent Waters.  IEEE Security & Privacy 2006.
Secure Ranked Keyword Search over Encrypted Cloud Data, Cong Wang, Ning Cao, Jin Li, Kui Ren, and Wenjing Lou.  ICDCS 2010.
Enabling Efficient Fuzzy Keyword Search over Encrypted Data in Cloud Computing, Jin Li, Qian Wang, Cong Wang, Ning Cao, Kui Ren, and Wenjing Lou.
New Security Models and Provably-Secure Schemes for Basic Query Support in Outsourced Databases Amanatidis, Boldyreva, O'Neill. 2007
Privacy Preserving Keyword Searches on Remote Encrypted Data Chang and Mitzenmacher. 2005
Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries Cash et al. in CRYPTO 2013
Multi-key Searchable Encryption Popa and Zeldovich. 2013.
Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions Curtmola et al. 2006

The best scheme for your situation will depend upon your application requirements.  If you have a read-mostly database (updates are rarer than searches), then I would suggest a scheme based upon encrypted indexes.  If you need to make modifications frequently, or if searching is relatively rare, the other schemes might be preferable.

Well, if you have documents encrypted with SHA512 or MD5 or any one-way crypto, the only possibility you have is to encrypt search terms with the same crypto and make the query to the DB.


Zero Knowledge Example using discrete log I've been exploring Zero Knowledge Proofs and while the classic cave example by Jean-Jacques Quisquater makes sense, I find the discrete log example problematic.

Since the Verifier is given p, g and y, where p is a large prime, g the generator and y = g x mod p. The value x is secret. My problem is that that there is leakage of information since y depends directly on the secret x.

Alternatively, the security is that of the discrete algorithm problem. Is this a poor example or do all realizable ZKP leak information?

A zero-knowledge proof is a protocol by which the Prover demonstrate to the Verifier that he knows the solution to a given problem, without giving to the Verifier any additional information about the solution -- that is, no information that the Verifier could not already obtain alone. In the case of the discrete logarithm, the y value is not part of what the Prover sends; it is a given. The base problem consists in (p,g,y) and what the Prover tries to demonstrate is that he knows the corresponding x -- but without helping the Verifier find out x.

The Verifier can always try to solve the problem by himself. This is in fact unavoidable: since a ZK proof is about proving knowledge of a solution to a given problem, anybody can, conceptually, try to solve the problem upfront, if only by exhaustive search of all possible bit patterns for a solution.

This does not count as a leak because it is not information obtained from the Prover. It is part of the context. It is information that everybody already has. The whole of ZK is about demonstrating knowledge of some value without yielding extra information that was not already public knowledge.

(Honestly I never understood why the cave example was all the rage. It is an analogy and it breaks down when looked at too closely. For instance, Victor could say to Peggy: enter the left corridor, and exit from the right one. This would demonstrate that Peggy knows how to open the door, and would be vastly simpler than the pseudo-ZK concocted for that example.)

From y you don't get any information about x, because of the 'mod p' part, which makes the result y random.


Should I use ECB or CBC encryption mode for my block cipher? Can someone tell me which mode out of ECB and CBC is better, and how to decide which mode to use? Are there any other modes which are better?

The really simple explanation for the difference between the two is this:

ECB (electronic code book) is basically raw cipher. For each block of input, you encrypt the block and get some output. The problem with this transform is that any resident properties of the plaintext might well show up in the ciphertext – possibly not as clearly – that's what blocks and key schedules are supposed to protect againt, but analyzing the patterns you may be able to deduce properties that you otherwise thought were hidden.
CBC mode is short for cipher block chaining. You have an initialization vector which you XOR the first block of plaintext against. You then encrypt that block of plaintext. The next block of plaintext is xor'd against the last encrypted block before you encrypt this block.

(Public domain image from Wikimedia Commons.)

The advantages of CBC over ECB are many – with ECB, assuming many things, you could manage a partial decryption and easily fill in the blanks, for example if extracting data from an encrypted hard disk. With CBC, if you are missing a few blocks in the sequence encryption becomes impossible. However, there is one downside to CBC – ECB naturally supports operation in parallel since each block can be encrypted independently of the next. However, with CBC this is harder, since you have to wait on each block. (You can still parallelize decryption, though.)

CBC itself can also be considered vulnerable in certain situations, specifically the use of predictable IVs and unauthenticated decryption can allow you to guess plaintexts as explained in this answer and in more detail here.

The IV problem is resolved by using unpredictable (cryptographically random) IVs. The authentication problem is traditionally resolved using message authentication codes - however, implementation of these is not perfect. Dedicated modes have been invented which tackle the issue of authentication too, for example EAX and Galois Counter Mode.

Other modes exist to deal with specific scenarios, e.g.:

Counter Mode uses the fact that a block cipher's output in ECB mode should be indistinguishable from random, and XOR's the result of encrypting a counter+iv combination as a stream cipher.
XTS is a mode of operation used in disk encryption.

The key point to take away is that each mode has a number of merits and implementation concerns and these must be weighed up carefully (and correctly implemented). And, where possible, avoid ECB.

Expanded explanation for how resident properties propagate into ciphertext with ECB

When writing this answer, I tried to not post a picture of the typical ECB-encrypted linux penguin, but I've been asked to expand on "resident properties in the plaintext" so what follows will be the same idea, just in text form. If you don't need it, feel free to skip.

Firstly, let's use a format I know something about - the mp3 frame. Like most plaintext this is far from "indistinguishable from random" - indeed for example, the MP3 frame header begins with 11 bits set to 1.

There are two important properties of block ciphers:

On a block level, operations are deterministic. If I encrypt "Cryptography Stack Exchange" and this fits in a single block, I expect to get the same output for given parameters every time. This sounds like a crazy critera (of course we need this) but it's worth highlighting.
On a block level, the output is indistinguishable from random - more formally there's no advantage for an attacker over using a random permutation, at least in a way that is realistically computable. My terminology might be a bit off because I am self taught, but I believe if the advantage is non-zero you've got a bias and this makes the cipher a candidate for linear cryptanalysis.

These statements apply considering only a single block; however obviously in the real world we want more than that - we want to encrypt multiple blocks.

Suppose we live in an imaginary world where people think block ciphers with a block size of one byte are a good idea. Now let's imagine this is otherwise a totally fine block cipher. Now imagine you have some MP3s of Justin Bieber music and you'd very much like the NSA not to find out about this. So you take your block cipher and you encrypt your MP3.

Now, one of those blocks, making some assumptions about file alignment, is going to be 0xFF - that's 8 of your 11 ones from the frame header in the MP3. These are always there at the beginning of each frame. Now our cipher is indistinguishable from random so we get perfectly random ciphertext, say 0x1c. But it is also deterministic and we're using ECB, so every frame header that was 0xFF becomes 0x1c.

All of a sudden we're giving away information to our attacker - specifically they can deduce where the frame headers are if they suspect this to be an MP3. Cryptanalysis is sometimes about guessing correctly and a correct guess in this case will give them an idea of exactly how long the audio samples are and allow them to identify the format.

Moreover, every other ciphertext block 0x1c is now decodable too. That's not information we intended to give away, but we did.

This problem is common particularly when you consider much of what we encrypt has a rigid data format. You have to make some assumptions about alignment on the blocks, but the larger the data the more this problem becomes apparent.

This is what I mean by residual plaintext properties becoming evident in the ciphertext. These are the structure inherent to and wanted in the plaintext that inadvertedly become exposed to the attacker.

The original purpose of CBC mode was as a form of identifying corrupt messages and the security of CBC for this purpose is treated in this paper. I can't find the original realization of this idea in terms of papers, but you might be able to find it. Certainly most books on block ciphers that I have read mention it and other issues.

The problem with this question is that the question is incomplete.  It's like asking the question "should I use a hammer or a screw driver".  Without knowing the underlying application and requirements it is impossible to properly answer this question (in fact, the answer may be "tape measure").

Still, ECB and CBC each have their strengths and weaknesses.  If you have lite encryption requirements (for example, something fast and simple) then ECB is useful.  If you are looking for stronger strength, then you need to consider CBC.  However, if you must deal with data loss, than CBC becomes very difficult (you will not be able to recover the chunk of data after the loss point).  If you need to handle data loss, strong encryption, and relatively fast processing, a different technique may be required (and there are lots).

Another strength/weakness comparison is random access/parallel processing.  ECB blocks can be encrypted and decrypted in parallel.  Each ECB block can be accessed completely randomly, and any amount of loss or corruption in previous blocks has no effect on the current block.  In CBC, encryption is completely serial (you can't encrypt block N until you encrypt block N-1, and so on back to block 1).  Decryption requires 2 blocks (you need block N-1 to decrypt block N).  So, random access in CBC requires twice the data as ECB.

Still, ECB is a very poor choice for message encryption unless the message is either very short (not longer than the block size), or undergoes a whitening process first (using another system to make the underlying bits look random - white noise).

In summary, ECB by itself, does not provide much in the way of security.  CBC by itself does not provide great error recovery (some, but not great).  ECB is a good building block as part of a larger system (heck, it's used in CBC).  CBC is great for systems that have low error rates and no random access encryption needs (for example, when writing a file).  Understanding these limitations helps in deciding which to use and when (or if you need something completely different).


Is RDSEED a true RNG? Is Intel's RDSEED a true random number generator?

Yes, RDSEED is a true random number generator.

From Wikipedia:

  The entropy source for the RDSEED instruction runs asynchronously on a self-timed circuit and uses thermal noise within the silicon to output a random stream of bits at the rate of 3 GHz [...].

RDSEED is however used as a seed for (software implemented) PRNGs of arbitrary width.

No one knows, so we can't say because of the two obstacles of non auditability and computational indistinguishably. But it's not looking good at all.

Since the device is completely unverifiable, it could do anything.  All we know for certain is that it is impossible to mathematically verify true randomness.  Computational indistinguishably means that the output could simply be any decent $ \operatorname{E}_{k \; \oplus \; cpuid} (ctr) $  like CSPRNG. Intel state that it's AES-CBC-MAC throughout anyway.

Wikipedia is not the oracle of all truth, and has to be ignored in this context.  The primary verification of the device is ANALYSIS OF INTEL’S IVY BRIDGE DIGITAL RANDOM NUMBER GENERATOR. That was followed up with an academic report, A Provable-Security Analysis of Intel’s Secure Key RNG.  Unfortunately for users, both reports are based on a raw entropy rate of ~0.5 bits/bit. And to be a gold standard TRNG, (entropy out) < (entropy in). But it says in those reports:-

  "We did not have access to Ivy Bridge parts, so Intel provided us with testing data from
  pre-production chips. These chips allow access to the raw ES output, a capability which
  is disabled in production chips. "

The whole analysis is built on sand. Many factors create reasons for suspicion:-

It is not in the interest of the US government/NSA/security community to produce fast secure random number generators for public use. Cui bono?
The NSA has form on this, with many examples publicly available.
All public analysis of the chip is based on unverified data samples supplied by Intel themselves. Is ~0.5 bits/bit real?
The primary analysis of RDSEED was paid for by Intel which is a huge conflict of interest, tantamount to marking your own homework. From that report's front page  - "This report was prepared by Cryptography Research, Inc. (CRI) under contract to Intel Corporation".
The entropy source operates at a suspiciously high 3GHz.  Academic laboratory TRNG's have only recently attained this rate using optical means (green line below). If true, I would expect huge correlation at this sample rate. Injecting 1% entropy into a CSPRNG stream does not make a TRNG.
The pink marked devices show how easy/common it is to over-hype your TRNG.  These marked devices have exceeded a very conservative engineering limit (Shannon-Hartley) beyond which it is mathematically impossible to extract any more entropy.  Some others appear to be suspiciously right on the limit.  From Recommendations and illustrations for the evaluation of photonic random number generators.
The entropy source is an atypical circuit not replicated in the hacker community, and the only detailed analysis is by Intel themselves and unpublished. (C. E. Dike, "3 Gbps Binary RNG Entropy Source," Intel Corporation (unpublished),
2011.)
The typical completely in-silicon TRNG is synthesised via multiple ring oscillators.  Inverters are easy to burn in their hundreds.  There are numerous examples at all levels of academia and commerce. Intel chose not to for some reason, preferring to go analogue on an otherwise entirely digital die.
There is no raw entropy source available for inspection, and even if there was, the level of integration means that we can't verify that the source is actually used.
*nix developers do not trust it.

But the best for last. Even Intel could not convince it's own agent that it's a good TRNG:-

  Under heavy load, it should
  provide security equivalent to 128-bit AES, even against an attacker who can see some of
  its outputs and, after a good reseed, force the ES to output nonrandom, known values.

-Cryptography Research, Inc. (CRI).

If you accept that an effective TRNG has information theoretic security via the entropy input/output ratio, Intel's isn't.  Given all the evidence against, and who benefits if it isn't, I have to conclude it's a CSPRNG (at best), and not a TRNG. Most of the *nix community agrees with me.


Shannon entropy of string, not same in Binary form? But just as good as a password? This string, "Au+u1hvsvJeEXxky" has a Shannon entropy of 3.75 and a length of 16.

The binary form of the string ( derived from Ascii-table ) is:

01000001 01110101 00101011 01110101 00110001 01101000 01110110 01110011 01110110 01001010 01100101 01000101 01011000 01111000 01101011 01111001

This string has a Shannon entropy of 1.39 and a length of 128.

So while both strings are interchangeable, their entropy differs. Why is
that? And are both strings evenly strong in resisting a brute force guessing attack?

thnx.

I'm going to telepathically make a wild guess.

My wild guess is that you generated the string Au+u1hvsvJeEXxky by asking a computer to choose sixteen characters independently and uniformly at random from the alphabet consisting of a-z, A-Z, 0-9, +, and -, which is, coincidentally, the base64 alphabet.

The distribution on individual characters has 6 bits of entropy per character.  The distribution on strings of sixteen characters chosen independently from this distribution is sixteen times that, namely 96 bits of entropy per string.

If I, as the adversary knowing this information about your process but not knowing the particular outcome, tried to guess your string, I would have a $1/2^{96}$ chance of getting it right.  If I kept trying guesses, the expected number of guesses before I get it right—that is, the average of number of guesses over all possible values of your string—is $2^{95}$.  That's a lot of guesses.

However, as the adversary, I often have more powers than that.  Often, what I have is some hash of your string $H(s)$, and not just yours but $H(s_0), H(s_1), \ldots, H(s_{9999})$ of ten thousand different users who all used the same process.  My goal as the adversary is to find at least one of the strings $s_i$—chances are if I can get a foothold by compromising one user, I can use that to compromise more users in a network.

If I do this intelligently, the cost of my attack—measured in joules, or USD, or EUR—is significantly less than $2^{95}$ times the cost of testing a single guess by evaluating $H$.  With the help of Oechslin's rainbow tables, if parallelized $p$ ways, at least hundred million, I can share work between attacking many targets at once, and it will cost only about $2^{82}$ evaluations of $H$, in the time for about $2^{82}/p \leq 2^{56}$ sequential evaluations.  The Bitcoin network spends this cost in about a year; $2^{56}$ nanoseconds is about two years.

That's a high cost, and a long time to wait, but it's absolutely within the budget of a major corporation or government.  I would recommend making sure that the cost is around $2^{128}$ evaluations of $H$ so that it is completely out of reach of foreseeable human engineering.  There are three ways to do this:

Have every user choose from ${\geq}2^{256}$ possibilities uniformly at random.  For example, instead of sixteen-character base64 strings, use forty-three-character base64 strings.  Or use sequences of twenty words chosen independently uniformly at random from a word list of 7776 words.
Store a salt unique to each user, and use $(\sigma_i, H(\sigma_i, s_i))$ where $\sigma_i$ is the $i^{\mathit{th}}$ user's salt and $s_i$ is the $i^{\mathit{th}}$ user's secret.  This thwarts rainbow tables and prevents the adversary from sharing work between multiple users.
Use a password hash that is costly to evaluate like scrypt or argon2id.

Method (1) is something the users can do.  Alternatively, the computer can choose the user's secret for them, and ask the users to remember it.  Methods (2) and (3) are things that whatever uses the secrets can do—something that the engineers of an application can put into their system to defend it against brute force attacks even if some users choose secrets poorly like human-chosen passwords.

All of the numbers above are premised on the model I telepathically guessed.  Not everyone guesses the same model.  The ent utility suggested by Paul Uszak and an entropy calculator on the web suggested by conchild instead guess the following probability distribution on symbols: probability 1/8 for u and v, probability 1/16 for {+, 1, A, E, J, X, e, h, k, s, x, y}, 0 probability for any other character.  They suggested this by (a) counting the number of appearances of each character in your string, and (b) dividing by the length of your string.  I, instead, used knowledge of common protocols on the internet to guess that you are using the base64 alphabet.  We all assumed independence between characters.  But nobody here knows anything about the process you used.

You may have seen an equation similar to:-

$$ H = -K\sum_{i=1}^n {p_i \log p_i} $$

It comes from Shannon's A Mathematical Theory of Communication, 1948 and is the classic definition of information entropy.   The cryptographic security notion of entropy is different to this, but your calculations are based on Shannon's classic definition (Note 1.).   Ignore the scalar K for this question, but feel free to follow up in Shannon's work.

What you will not have seen much of on this site is the definition of $i$.  This is the crux of your question, and why Shannon entropy is tricky to measure accurately. $i$ relates to the alphabet used, and even that is confusing as the alphabet may be over multiple characters, such as "qu" in English. Bits, bytes and words may the tallied differently and produce different entropy measures.

To demonstrate my answer with a more substantial dataset, consider a 4 MB file of sequential 32 bit integers from 0 $\rightarrow$  999,999. Measure it's entropy using different bit widths for $i$:-

i (bits)         Hrate (bits /byte)    Htotal (bits)
  1                    7.1                 28M
  8                    6.3                 25M
 32                    3.5                 14M
 ???                 0.0031              12,464

where ??? is unknown as Htotal was obtained via a proprietary  compression algorithm (paq8px_v112). This example effectively changes the alphabet (read $i$) used in digesting the file, just as the question does with a swap to ASCII.  Compressors exploit correlation over many bits, and thus the resultant measure is so small. But the result is as expected, in that the entropy of the first million integers is clearly  low.

Anyway, that's why your entropy numbers come out differently.

Note 1. This subtle distinction in entropy definitions will cause us all problems. Some commentators will suggest that your strings do not have any entropy whatsoever, in contrast with accepted information theory and Shannon himslef.  A good example of entropy measures of fixed text is this entropy rate graph from Thomas Schürmann and Peter Grassberger, Entropy estimation of symbol sequences.


One-time-pad encryption As we know, intercepted ciphertext created by a one-time pad only reveals the length of the message. That is the only information the attacker can get since this ciphertext is unbreakable without the key.

I understand that for a file 1GB in size we need a key that is 1GB long. My question is: why is the one-time pad not more widely used in encryption for communications that use a small bandwidth?

One time pads are used in many low bandwidth situations.  However, they suffer from a fundamental problem of key distribution.  It's hard to transmit 1GB of key information.

One time pads are most effective in situations where the trust communication channels are highly asymmetric.  If you can hand deliver your OTP to an individual, positively confirm their identity, and then hand the pad over, then OTP can be quite effective.  In times of war, where you can be physically provided your key material before you travel into the hostile area, this pattern can be very powerful.  In more symmetric situations, transferring the key material securely can be just as difficult as transmitting the material itself!  These symmetric situations are more common on the internet.

Because there's hardly any good One-Time Pad software available except for FinalCrypt (which is not well known) and because national security agencies would go out of (cracking core) business, so they don't want OTP as a standard.


How to handle authenticated encryption for big files? First I need to mention that I can't use BouncyCastle to implement this solution.
I have to encrypt files into the file system. Those files are not going to be tranfered over the wire to any other location. They are only going to be stored in the server for later use by an application installed there. The file system may or may not be encrypted at an OS level, but that's something that I can't count on.
My files are going to be big files (say from several hundreds of megs to some times a couple of GBs). And they will be created on a regular basis, so I can expect to have a growing number of them. Also, sometimes some of this files are going to be deleted cause they may no longer be needed, and some other times files will be kept for years.
I already have the encryption in place, with AES/CBC/PKCS5Padding, using a 256 bit key and  I/O Cipher Streams. I have no authentication thought.
I don't think I can assume that it is safe to just encrypt and not use authentication as the server could be hacked I guess and the files stolen.
Also, by reading several questions it's clear that no authentication is just someting I shouldn't even think of.
So what are my options here then? I see 2 with some pro/cons analysis:
Option 1: AES/CBC + MAC (say with SHA-256)
Pros

Already have the encryption part working
Supported by Java with no extra libs

Cons

I have to deal with the computation of the MAC
I have to deal with appending the mac to the file and extracting it later
I will have to handle validation myself.
Lots of room for me not getting that right I'm affraid.

Option 2: Use GCM operation mode
Pros

Forget about handling tag computation / message authentication
Supported by Java (I'm using 1.8, so the default provider supports it)

Cons

I found that there are people who wouldn't recommend it.
Also this post seems to suggest that performance is somewhat an issue with Java8, but that's something I haven't verified (Update: @archie pointed to here and here that comfirm the performance issues).
It is badly broken in Java 1.7. I have yet to verify it works ok in Java 1.8 (update: this thread verifies that problems are still present in Java 8)
I'm using a single symmetric key for encryption. I'm worried about how to manage the nonce so I don't break the security properties of the algorithm (My current implementation gets the IV from cipher.getIV() after the Cipher is initialized. I'm not sure if that's good enough for GCM or if I need to take other special considerations.)

Are those options that I mention valid? What about the pro/con analysis? Is there any other suggestion you would have? Which approach would you choose?

If you definitely can't use other libraries such as Bouncy Castle, your best option is probably to just add an HMAC authentication tag (it should be easy to write a MacInputStream/MacOutputStream to chain it into your existing pipeline).

The primary reason is that the JDK 8 (at least up to 1.8.0_25) GCM implementation suffers from two problems that make it impractical for large files:

The implementation buffers the entire plaintext on decrypt (this is intended to prevent release of unauthenticated plaintext, but cripples the cipher implementation for uses that handle that at a higher level in the security protocol)
The performance is crippled (3MB/s on my server) due to a naive multiplier implementation and no hardware acceleration for the GCM calculations (AES in JDK 8 is AES-NI accelerated and very quick, but AES/GCM is completely dominated by the broken GCM performance). There are intentions to implement hardware acceleration, and there have been third party submissions to improve the performance with, but these haven't made it to a release yet.

If you go with the AES/CBC + HMAC option, you'll also want to make sure you have independent keys for the encryption and Mac (e.g. using something like HKDF to generate the two keys from a single master key).

If you can use Bouncy Castle (even using the lightweight API if your restriction is that you can't use another JCE provider) then the OCB, GCM and EAX implementations in that will give you better performance (and take away a bunch of the manual fiddling you'll have to do with the HMAC approach).

Actually, you might be better of without any authentication.

But why? Everyone recommends it. Truth isn't so simple.

When we define our problem we define attackers we want to stop.

You cannot stop your attacker from learning data you store when he is on your machine (when you can decrypt it, he can too).
You cannot stop attacker from manipulating data on fly, or just learning HMAC key and using it to authenticate data for you.

So you, if you want to encrypt files on the server then authentication might be pointless. Encryption at all might be pointless if you store key on that server anyway.

So please define who you are trying to protect that data from. It might be pointless to do HMAC or any encryption in your case. Also, as a side note, when your files are big, you might consider AES-CTR since it has parallelization on both encryption and decryption.


Combining a keystream generator with a block cipher I understand that:

A stream cipher's security is diluted if the same key is used more than once. This is fixed by using an additional initialization vector in the keystream's computation.
A block cipher run in the most simple way, electronic codebook mode, has negligible security due to pattern preservation. This is avoided by using cipher-block chaining or another mode of operation.

Consider that using a keystream generator like in stream ciphers to produce a string of keys for encipher individual blocks of a message with a block cipher:

Does not fall prey to the problems that reusing a key plagues stream ciphers with because of the avalanche effect present in block ciphers.
Does away with the need to use more complicated modes of operations in a block cipher due to each block being encrypted with a different key.

Is this analysis correct? Are there implementations like this that are already out there?

Under your scheme, the keystream generated by the stream cipher will be the same for each message enciphered with the same key. While your scheme does not encrypt identical blocks of plaintext in the same message to the same value, it does encrypt identical blocks of plaintext in different messages to the same value, meaning that XORing two ciphertexts together will give clues to the structure of the plaintext inside. This can quickly become relevant when used, for example, in a network protocol, because the sorts of structured data computers like to exchange with each other frequently include significant repeated or predetermined segments.

Completely beside the issue of whether your scheme provides confidentiality, it can't replace using "complicated" block cipher modes of operation, because its performance would be abysmal. It's not obvious from the definition of a block cipher, but there is a reason that all the popular block cipher modes of operation vary what they do with the plaintext or what they do with the ciphertext but never get inventive with what they do with the key. In block ciphers, a significant amount of computation is put into expanding the key into a "key schedule," or list of the subkeys that will be used in each round of the cipher. Once the key schedule has been calculated, subsequent blocks can re-use the same data if the key hasn't changed, meaning that encrypting 1,000 blocks with a single key is much, much faster than encrypting them to different keys. If you wanted to change the key for each block, you'd have to re-do the key schedule operation each time, and that would suck.

Finally, a note on IVs. An external source of entropy, in the form of an IV, is required for probabilistic encryption schemes. Probabilistic encryption guarantees that the same message encrypted twice will not produce the same ciphertext, and that property is needed to assure semantic security. However, semantic security is a very strong requirement, and while using deterministic encryption (for example, by calculating an IV deterministically as I suggest in the comments on Maarten's answer) means you won't have semantic security, for many applications it's good enough. Consider implementing strong encryption on a microcontroller, where entropy is scarce and available sources are easily tampered with: deterministic encryption will leak that you've encrypted the same thing twice, but that's usually much more acceptable than courting the spectre of a full-blown break if someone somehow manages to poison your PRNG.

Yes, your analysis is right. Don't know why Maarten Bodewes - owlstead says something else. This doesn't mean that your scheme is secure or the best idea.

Every plaintext block will be encrypted with a new, pseudo random key. If the bit generation of the stream cipher is secure then there's no known way to get the original password without brute forcing it.

All in all you just use a stream cipher, but not with the common XOR operation to combine the key and the plaintext, but with a block cipher. You will still have all the security properties of a stream cipher, at least if the block cipher is still "secure". Even if the block cipher is broken it's still very hard to break the encrypted block because there's only one block encrypted with the particular key.

But what happens if the key generation is broken? The attacker has to have known plaintext blocks and the appropiate ciphertext blocks. With a secure block cipher, it's still only possible with brute force to get the key - and then he or she only has one part of the key stream of the stream cipher. (This only holds for "normal" breaks. If the stream cipher starts to output the same known key for every block, then all hope is lost.)

What happens if you reuse the key? Every identical plaintext block at the same position (index of the block position) will be encrypted to the same ciphertext. If the plaintext block itself or the position in the whole plaintext changes, then the output block will change completely (because of the avalanche effect of the block cipher). Changing the position of the block changes the key used to encrypt the block, and there's no (assailable) correlation in the output of two instances (with different keys) of a (secure) block cipher, regardless of the used plaintext. If only the plaintext itself changes by one bit, then you will still have no (assailable) correlation. The use of a block cipher defies this attacks on the whole cipher, even if the same original key was used.

Timing or power attacks could be a problem for this scheme. You do the key setup of the block cipher not only one time (like in a normal block cipher mode), but as often as the amount of plaintext blocks. Attacks on this have much higher hopes for a success.

But be warned, you still have some problems of the typical stream cipher. For example the same plaintext encrypted with the same key will still lead to the same output. Your scheme doesn't change this, and you still need to use different keys every time you want to encrypt a message - the same way you have to do it for a normal stream cipher. Changing one bit of the output message will destroy the whole plaintext block. It's still advisable to just use a normal encryption mode with a block cipher - as the other answers already mention, it's still faster, esier and maybe more secure to do this than inventing your own scheme.


When will AES be "upgraded"? AES is secure, but compared to other encryption algorithm which are marked as secure, it's slow. For example, ChaCha20 is faster than AES, but still secure.

Also other standard-algorithms like SHA were upgraded in the last few years, so can we expect a AES upgrade in the near future?

No.

Basically your question is:

  The car maker X recently updated its flag ship car and the motor cycle maker Y makes a bike that is accelerating faster in straight lines - will the Lorry maker Z make a new lorry soon?

And I‘ll try to put this in laymen’s terms:

AES as a successor of DES is - in comparison to the lifetime of DES - relatively young.

Additionally, you are comparing ciphers that are not equivalent. ChaCha20 is a stream cipher and AES is a block cipher. The SHA family of hashing functions got new family members because the existing ones were showing signs of age and were generally thought to be feasible to break in several years because of the increasing computing power as well as increased progress in the cryptanalysis of sha1.

As to why you think AES would be slow, as Steffen said in the comments: this only might be true for software implementations. Yet, even smartphones do have hardware accelerated AES.

The process of replacing a cipher is very lengthy and I didn’t yet hear a call for papers for a successor of AES, so there should be at least years until AES gets replaced, probably a decade or two.

That being said, post-quantum cryptography is an active field of research and depending on when good enough quantum computers will be possible, a paradigm shift in standard ciphers will be necessary - yet I don’t think this applies to AES.

Why only focus on AES? In fact, AES can easily replaced with stronger algorithms like, Twofish, Serpent, or newer ones like AEGIS and MORUS. And without the strenght of AES-NI, AES has more weaknesses than strengths against the others. Really, forget about standards like AES and bet on crypto-diversity. And don't use software which only supports AES for cryptography. It's always better to have possibilities.


VIC cipher author known? Does anybody know if the design of VIC cipher is attributed to anybody? I've tried Google and found nothing. There are quite a few sites describing the method in detail, a few implementing it programmatically, and ample stories of the code in the coin, but who actually came up with it? Who decided to put the ideas together in that way? Some Russian scientist I assume, but does anybody know who?

Russian spy Reino Häyhänen, code name VICTOR;
https://en.m.wikipedia.org/wiki/VIC_cipher


Using the output of a stream cipher, how to guarantee the integrity of 4 bytes of data? I am designing a simple and secure stream communication protocol. My idea was to build each message sent to the wire as:

(message size || clear text || UHASH(message size || clear text)) $\oplus$ unique stream cipher output

where UHASH is the main function from UMAC (see question Using UMAC with stream cypher), || is concatenation and $\oplus$ is exclusive or.

The problem is that I found it was very easy to DoS attack my system; all it takes is to flip a high order bit of the 4 byte message size, and the receiver will wait for a multiple gigabyte message before having the chance to verify the MAC.

My solution is, if the message is bigger than some reasonably small size, I will add a MAC just after the size, validating it, so no very long message will be expected without validation. It seems to work, but given the overhead of calculated a 8 bytes keyed MAC from a 4 byte value, I wondered if there is any simple way of guaranteeing the integrity of such a small value using only a stream cypher and a few bytes more than the value I want to protect.

Do you know of any? For instance, let $\times$ be multiplication mod $2^{32}$, sending such a header:

(message size $\oplus$ cipher output 1) || (message size $\times$ cipher output 2)

would solve my problem? I understand that the probability of forgery can not be smaller than $1 / 2^{n} $ for the n extra verifications bits I send, but how to guarantee this chance is close to the minimum?

So you have a small integer, and you want to transmit it in such a way that (a) you don't particularly care if the attacker finds out what that integer is, but (b) no matter what the attacker changes or substitutes, you don't want the receiver to be tricked into thinking you sent some other number (in particular, some other much larger number).

securing the integer

As you've already figured out, that is exactly the purpose of a MAC such as a UMAC
and the purpose of a digital signature.

There are many protocols (including gzip and MP3) that add a CRC immediately after the header, in order to allow the receiver to immediately reject a packet with accidental noise in the "length" field (a), (b), for exactly the reason you mention.

I've seen a few ad-hoc constructions where the transmitter sends the number N
followed by some simple function of N, such as (N+1), (~N), (-N), N itself again, CRC(N), fletcher_checksum(N), etc.

Alas, as you already know, a standard CRC is vulnerable to malicious modification (even when encrypted by a stream cipher):
an attacker who knows the exact position of the length field and the CRC that covers it
can flip the high bit of the length field, and then flip the effected bits of the CRC,
resulting in a valid-looking header -- even if the entire message -- length, CRC, and all -- is protected by a "perfectly-secure" one-time pad.
(Most other "simple function of N" are just as vulnerable).

(Does switching from a stream cipher to a block cipher help?)

Your idea of using a MAC such as UMAC to protect the header (including the "length" field and perhaps also including a few bytes of random nonce) helps a lot, but it doesn't completely fix the DoS issue you mention:

message = header || MAC(header) || clear text || MAC( header || clear text )

then transmit

( message ) ⊕ unique stream cipher

The " Should we MAC-then-encrypt or encrypt-then-MAC? " question implies that it may be better to do that in the opposite order:

header = (length || other stuff) ⊕ unique stream cipher
body = (clear text of message) ⊕ unique stream cipher

then transmit

header || MAC( header ) || body || MAC( header || body )

Either way, the attacker won't be able to "blindly" DoS your system by sending a short message that looks like a valid header for a gigabytes-long message, unless he comes up with a valid-looking MAC(header) -- which is difficult.

securing the integer isn't enough

However, if you ever really do start sending a valid message with a valid header indicating "gigabytes of data will follow", and then if the attacker manages to insert or delete or change any bits or bytes in the following message, then the receiver will still get hung up doing useless work processing those gigabytes of data, only to throw them all away in the end.
(And what happens next week when the attacker sends a short message that replays that valid "gigabytes of data follows" message header again?)

alternatives that don't require securing the integer

For this reason, many protocols and file formats (ZMODEM, IPv4, IPv6, gzip, MP3, etc.) put a hard limit on the maximum length of a packet (with a "length" field of 16 or fewer bits), forcing larger amounts of data to be chopped up into a series of packets.
Rather than "a 4 byte message size",
they have, for example, "a 12 bit message size field",
and then files of data longer than 4 KBytes are sent as a series of packets,
each packet with its own independent CRC or MAC or digital signature.

In addition to avoiding the "DoS" problem you describe, breaking up long messages into packets
also has other advantages.
When a few packets are damaged by "innocent" noise,
the system can figure out which packets were damaged,
and then resend just those packets,
rather than re-sending the multi-gigabyte file all over again from the beginning.

Possibly related questions:

Can you make a hash out of a stream cipher?
Converting a stream cipher into a block cipher

SipHash is argued to be a pseudo-random function. If you were to use that it would work if I remember all the definitions correctly. Concretely use the stream as a key for SipHash, and send the length followed by the SipHash of the length.


Is there a password hash function with a human component? Sort of Related: Is there a cryptographic hash function that can be performed with pencil and paper?

One problem with hashing passwords is that the attacker has more of everything it seems. More speed, more memory, more time, newer algorithms, etc. It's a constant race to keep up. We have the advantage of having to try less passwords, but even that is only somewhat enough.

What if we threw a human into the mix? Currently, solving 1000 captchas, for example, is \$2. If we had a task as complex as a captcha incorporated into a hash function, and the attacker needed a billion guesses, that would be \$2,000,000 to crack one password.

Of course, incorporating captcha into a hash function I'm pretty sure would be impossible. But there are other tasks that humans seem better that are purely computational. For example, see foldit.

The idea is that when the user enters their password, at a certain step in the hash function, there would be a problem that a human can solve much more efficiently, and the human does it (it can, for example, be presented as a game). It would probably be for the more security conscious, depending how "fun" the hash function is to compute.

Is there such a thing? Is there a hash function such that one of the steps is much more efficient for a human to compute, while still being cryptographically secure?

Note: As for why captchas probably wouldn't work is this, there are only two approaches I can imagine, neither of which works:

The algorithm produces an image for the human to solve (based on the input and other parts of the algorithm). The human solves it, and the algorithm factors that into the hash. The problem is that, unless it used some direct method, to generate a captcha it would need to generate a random word, and then create a distorted image of that word. An attacker can simply edit out the "create a distorted image" step from the algorithm, and no human is necessary. (Perhaps cryptographic obfuscation could be used to prevent removing the distortion part of the algorithm, but that technology is practical yet.)
Same as above, but to generate the captcha, and has a huge base of images. Keep in mind that it simply needs to be a captcha, the algorithm doesn't need to know what word goes with each captcha (that's what the humans for). The problem is that A) you would need an infeasible number of images to make it secure and B) whoever is generating all these captchas may make them in such a way that they know what how to solve them.

Also, computers are somewhat good at solving captchas.

Okay, here's what I think we need:

There must be a very large number of problems (on the same order as the number of passwords/inputs).
A computer must be able to efficiently generate a random problem without knowing the solution.
A human must be able to solve the problem a couple of orders of magnitude better than a computer.

It should be hard for the computer to guess the answer as well. This means the space of possible solutions needs to be large.

There should be a unique solution.

The computer should be able to check if something is a solution

Bonus: Being fun

With these, what we do is:

Use the password/input to seed a random number generator
Generate a random problem
Have the human give the solution
Now process that into the final hash

Steps #1 and/or #4 will involve computer hashing algorithms. (It doesn't need to exactly follow the above steps; I'm just trying to reduce it to a simpler problem.)

Answer: No.

Reason: Useless.

Explanation:

Not necessarily perfectly reproducible as crowds of people may give different output. So you will end up introducing some degree of tolerance.
Once introducing that degree of tolerance, pattern recognition algorithms will be able to automate that and possibly even achieve a higher accuracy than the humans.
NSA will hire many cheap labour agents and manage to get them work for you and cause your hashes to be insecure. NSA is rich, they can hire many of such cheap labour. How can you ensure that the many humans that are solving hashes for you are actually honest people that are not NSA agents?

My opinion: you are trying to solve an existing problem (so the problem actually exists). It's just that your proposed solution is not going to solve the problem. Instead, I even think it will worsen the situation. You seem to be over estimating the uniqueness humans have. Humans are not that unpredictable. Some human-only problems are considered solved by pattern recognitions algorithms. I also think that humans are more predictable than PRNGs. So why not incorporate a seeded PRNG into your hashing function instead? Such seeded PRNGs are less predictable than humans aver all.


If you iterate a cryptographic permutation long enough will you map the input to itself? Given a cryptographic permutation $\{0,1\}^n \rightarrow \{0,1\}^n$ does it follow that after some number of iterations you must eventually map the input to itself?

Any permutation $f$ (cryptographic or not) on a finite set $X$ satisfies $f^n=id$ for some $n>0$.

To see this, note that there's only finitely many functions from $X$ to itself. Hence $f,f^2,f^3,\dots$ aren't all distinct, so $f^k=f^l$ for some $k$ and $l$ with $l<k$. Now $$id=f^{-l}f^l=f^{-l}f^k=f^{k-l}$$ so we can set $n=k-l$.

A 256-bit hashing algorithm is a permutation of 2^256 input values.

The permutation is the product of an unknown number of cycles with a total length of 2^256.

One particular 256 bit value is member of a cycle of some length l <= 256 and will reappear after l iterations.

If you let L = least common multiple of all cycle lengths then applying hashing L times is the identity, that is each value is mapped to itself.

Obviously l is likely so large that you can’t perform the operation, while L could be ridiculously huge.


it is possible to use quantum algorithm search (Grover's algorithm) for new searching strategies for differential and linear attacks I am trying to use Grover's algorithm to find  Differential characteristic of Feistel and SPN structures block ciphers. basically, which is Finding a good differential characteristic with high probability in the (related-key) differential attack

For example, using  Matsui’s Algorithm to Search for related-key differential
characteristics in DES-like ciphers by Alex Biryukov, Ivica Nikolic.:  FSE 2011

also using Integer programming-based method ( Differential and linear cryptanalysis using mixed-integer linear Programming ) by Nicky Mouha, Qingju Wang, Dawu Gu, Bart Preneel Inscrypt 2011.

my question

can construct Grover's algorithm to find  Differential characteristic of Feistel and SPN structures block ciphers?

Grover's algorithm is a probabilistic quantum algorithm that finds (with high probability) the unique input to a black box function that produces a particular output value, using
$$
O({\sqrt  {N}})
$$ evaluations of the function, where the fuction has domain of size $N$.
is the size of the function's domain.

Keeping in mind the fact that the spedup is only quadratic, unlike Shor's algorithm which provides exponential speedups on a different problem,  it can be applied to any search problem over a finite domain.

The normally suggested countermeasure to this algorithm in the symmetric crypto setting is quite mild: symmetric key lengths can be doubled to compensate for the risk.

Edit: For multiobject search for $\ell$ objects, Boyer et. al. in 1 proved the following theorem, which as pointed out by @poncho in the comments, is a bit counterintuitive.

Theorem: (paraphrased) Assume that $\ell/N$ is small. Then
any search algorithm for $\ell$ objects, in the form of [grover search]
takes on average $O(\sqrt{N/\ell})$ iterations in order to be successful with positive probability $>1/2$
independent of $N$ and $\ell.$

M. Boyer, G. Brassard, P. Høyer and A. Tapp, Tight bounds on quantum searching, Fortsch. Phys. 46 (1998), 493–506. See related paper on arXiv here


Is MD5 particularly vulnerable when given multiple MD5 hashes using a common, secret suffix? Suppose I've got a list of "passwords" that are hashed using the same suffix, so basically what we do is hash = md5_digest(prefix+suffix), with suffix being a constant.

Now, if I know a single prefix and hash pair, I can trivially do a brute-force search for suffix.

But given multiple different known matching pairs of prefix and hash, is there a better than brute-force way of finding the value of suffix? Is there an algorithmic vulnerability of MD5, relying on the internal state that would allow me to do this? Or, alternatively, to construct a fake prefix that would generate a known hash when concatenated with the unknown suffix?

Update: Please don't suggest alternative hashing schemes, as I'm not designing a system or anything, I just want to understand how MD5 works.

Update 2: Okay, I might not have made myself clear enough. I'm not interested in any other "solution" for the simple reason that my problem isn't "how do I secure this system?" but "how does this specific algorithm behave?". Yes, I do know the difference between a hash algorithm and message authentication, yes, I do know HMAC, yes I do know MD5 is broken.

is there a better than brute-force way of finding the value of suffix?  Is there an algorithmic vulnerability of MD5, relying on the internal state that would allow me to do this?

The best attack better than brute-force I could found is described in this paper, it has a complexity of 2^123.4 and a memory complexity of 2^45×11 words. AFAIK this is not practical

  Or, equivalently, to construct a fake prefix that would generate a known hash when concatenated with the unknown suffix?

This is not equivalent to your first question. Your first question is a preimage attack, meaning finding the original value (prefix + suffix) that generated the hash.

This question can be interpreted in two ways:

You're asking for an algorithm that can generate a second pre-image, meaning a second value different from the original one that produces the same hash. In this case there is no known second pre-image attack against MD5
You're asking if it's possible to find a collision for a given hash using a fixed part in the message. To this question I only know there are algorithms to efficiently find collisions for a given MD5 but I don't know if those methods can be adapted to use a fixed part in the message (The suffix)

Assuming you're dealing with a message-signing scenario, use HMAC.

It's designed as a safe keyed hash. If you do something like what you're proposing, e.g.

signature = md5(secret || message)

there are weaknesses that allow attacks (for secret prefix, you can google length extension attacks). See Stop using unsafe keyed hashes, use HMAC for a starting point.

The linked text especially states that "md5 with a secret suffix is completely broken", and that's basically what you propose to use. If you're set on using md5, that's still viable when you use hmac-md5. But note that there are some serious weaknesses in md5 and that attacks on md5 won't get any worse, just better, so I'd counsel against using md5 as your hashing primitive.


Advantages/disadvantages of using symmetric encryption function as hash function? Next to the traditional MD5 and SHA-1, other hashing algorithms exist based on symmetric encryption algorithms. An example is the Matyas–Meyer–Oseas construction.

What are the advantages/disadvantages of this approach instead of using traditional hash functions, such as MD5 and SHA-1?

The disadvantage of this approach is that block ciphers are not necessarily designed with this goal in mind. Specifically, AES has related-key problems, and DES completely breaks in Davies-Meyer. In general, block ciphers are not necessarily ideal ciphers and should be used as intended which is as pseudorandom permutations. In contrast, SHA256 and the like were constructed specifically with the collision resistance goal in mind. It doesn't mean that they achieve this goal, but they have a far better chance.

Matyas–Meyer–Oseas one-way compression method is a cryptographic algorithm based in block ciphers. The difference is that the subkeys of each round are calculated differently unlike normal block ciphers were you specify the key before data encryption. It can be seen as a special MAC algorithm.

The advantages of this algorithm compared to SHA-1 are computational complexity when trying to get a hash collision.

Theoretically SHA-1 needs $2^{61}$ operations for a full collision but Matyas–Meyer–Oseas needs $k \cdot 2^{\frac{n}{2}+1}+2^{n-k+1}$

Please take a closer look at this paper where the complexity of breaking Matyas-Meyer-Oseas is discussed in full detail.


Should we MAC-then-encrypt or encrypt-then-MAC? Most of the time, when some data must be encrypted, it must also be protected with a MAC, because encryption protects only against passive attackers. There are some nifty encryption modes which include a MAC (EAX, GCM...) but let's assume that we are doing old-style crypto, so we have a standalone encryption method (e.g. AES with CBC chaining and PKCS#5 padding) and a standalone MAC (e.g. HMAC with SHA-256). How should we assemble the encryption and the MAC?

MAC-then-Encrypt: Compute the MAC on the cleartext, append it to the data, and then encrypt the whole? (That's what TLS does)
Encrypt-and-MAC: Compute the MAC on the cleartext, encrypt the cleartext, and then append the MAC at the end of the ciphertext? (That's what SSH does)
Encrypt-then-MAC: Encrypt the cleartext, then compute the MAC on the ciphertext, and append it to the ciphertext? (In that case, we do not forget to include the initialization vector (IV) and the encryption method identifier into the MACed data.)

The first two options are often called "MAC-then-encrypt" while the third is "encrypt-then-MAC". What are the arguments for or against either?

I'm assuming you actually know all of this better than I do. Anyway, this paper neatly summarizes all these approaches, and what level of security they do or don't provide. I shall paraphrase it in English, rather than Mathematical notation, as I understand it.

Encrypt-then-MAC:

Provides integrity of Ciphertext. Assuming the MAC shared secret has not been compromised, we ought to be able to deduce whether a given ciphertext is indeed authentic or has been forged; for example, in public-key cryptography anyone can send you messages. EtM ensures you only read valid messages.
Plaintext integrity.
If the cipher scheme is malleable we need not be so concerned since the MAC will filter out this invalid ciphertext.
The MAC does not provide any information on the plaintext since, assuming the output of the cipher appears random, so does the MAC. In other words, we haven't carried any structure from the plaintext into the MAC.

MAC-then-Encrypt:

Does not provide any integrity on the ciphertext, since we have no way of knowing until we decrypt the message whether it was indeed authentic or spoofed.
Plaintext integrity.
If the cipher scheme is malleable it may be possible to alter the message to appear valid and have a valid MAC. This is a theoretical point, of course, since practically speaking the MAC secret should provide protection.
Here, the MAC cannot provide any information on the plaintext either, since it is encrypted.

Encrypt-and-MAC:

No integrity on the ciphertext again, since the MAC is taken against the plaintext. This opens the door to some chosen-ciphertext attacks on the cipher, as shown in section 4 of Breaking and provably repairing the SSH authenticated encryption scheme: A case study of the Encode-then-Encrypt-and-MAC paradigm.
The integrity of the plaintext can be verified
If the cipher scheme is malleable, the contents of the ciphertext could well be altered, but on decryption, we ought to find the plaintext is invalid. Of course, any implementation error that can be exploited in the decryption process has been by that point.
May reveal information about the plaintext in the MAC. Theoretical, of course, but a less than ideal scenario. This occurs if the plaintext messages are repeated, and the MACed data does not include a counter (it does in the SSH 2 protocol, but only as a 32-bit counter, so you should take care to re-key before it overflows).

In short, Encrypt-then-MAC is the most ideal scenario. Any modifications to the ciphertext that do not also have a valid MAC can be filtered out before decryption, protecting against any attacks on the implementation. The MAC cannot, also, be used to infer anything about the plaintext. MAC-then-Encrypt and Encrypt-and-MAC both provide different levels of security, but not the complete set provided by Encrypt-then-MAC.

In many applications, only part of the data (m) is encrypted, and some so-called Additional Authenticated Data (AAD, usually some header data including nonce) a is only authenticated but not encrypted.

Here is my argument: When AAD is used, Authentication-then-Encryption provides an additional layer of protection for AAD than Encryption-then-Authentication, thus one may argue it could be more secure in certain usages.

When AAD a is used, if we use Encryption-then-Authentication, we will get:

E(m) + A(a + E(m))

for scheme, which means we encrypt m first, and then concatenate it with a, and then encrypt the result. Notice how a is only protected by one layer of cryptographic operation, the MAC operation A.

And if we use Authentication-then-Encryption, we will get

E(m + A(a+m))

which means we first encrypt concatenated a and m, then concatenate the resulted MAC code with m, and then do the encryption. Notice a is effectively protected by two layers of cryptographic operations, both A and E.

Now suppose the authentication method is somehow broken and the encryption is not, which is not that far-fetched since some MAC algorithms (like HMAC-MD5) is indeed found weak, then a will be fully exposed to tampering when using Encryption-then-Authentication. The same cannot be said for Authentication-then-Encryption.

 Update on 2016-09-27:

I agree with some of the top comments that applying a cipher multiple times doesn't always lead to better security so I retracted that statement. But it actually is not relevant to my main point of AtE provides additional layer of security since we are not applying the same cipher to the same data twice in these A/E schemes.