Dictionary attack on pass-phrases on common algorithms? I don't yet perfectly understand the difference between brute-force and dictionary attack since this differentiates one attacking the key and another attacking password: apparently attacking passwords can take longer, right?

But it's not necessarily true depending how unaware users can be, and that's where dictionaries shine.

So as the recent XKCD demonstrated, pass phrases are much more secure not because of their bit entropy, but because of their bit length, and even if a pass phrase is done with common words which also are in a dictionary, a dictionary attack of a pass phrase is still "infeasible" if it is at least 3 or 4 words, which makes it still very easy to memorize.

So would it be a good design choice to force users to choose at least 3 words in the dictionary to have a long enough password, for example with some auto-complete feature? What do you think?

PS: I'm asking this not in the context of expensive information requiring design efforts, I'm more thinking into good privacy for public use, considering the attacker has access to the cipher-text (which is not necessarily true on the web).

"Brute force" is a loosely-defined traditional expression to designate a kind of attack of low mathematical cleverness, namely trying all possible values for some unknown. For instance, in the context of symmetric encryption with AES, using a 128-bit key, "bruteforcing" would be trying all possible sequences of 128 bits as possible keys, until one matches (and there are so many such sequences that the average attack cost will be astronomical, hence totally impractical).

A dictionary is a set of "possible passwords", and a dictionary attack is about trying all possible passwords from a dictionary. Thus, a dictionary attack can be called "brute force". However, the expression "brute force" somehow suggests unsubtlety, and there can be quite some psychological finesse in the definition of a dictionary. As I said, "brute force" does not have a well-established mathematically meaning.

In "to force users to choose at least 3 words in the dictionary", the worst word is "force". Enforcing password rules on users tend to be counterproductive. Users should cooperate, and if you antagonize them, then they will actively seek countermeasures with great creativity. You really do not want the users to resent the password as a burden. Remember that almost none of your users will have a mathematically correct notion of password entropy; most will not care, and most of those who care will think about passwords in the same way as passwords are used in movies: witty allusions to some events or objects, supposed to defeat attackers through some "cleverness".

The second worst word in your proposal is "choose". To defeat a dictionary attack, the dictionary (as "the set of potential passwords") should be huge. The set of potential passwords is what users will effectively choose, not the length of the list you gave them. If you give them a list of 1000 words and tell them to "choose" one of them at random, many will pick a word in the first 10. Human beings are simply not good at doing things with uniform randomness. The password selection process should involve a physical device (e.g. dice, or a coin) and -- that's the important point -- the user MUST stick with the randomly selected words. If users are free to choose as they see fit, most will see fit to select words with a meaning (e.g. a sequence of words which "says something") because that's what they will remember best.


What are the vulnerabilities of XOR in the following scenario? What are the security vulnerabilities of the XOR operator in the following scenario:

The Key, The Cyphertext and the Plaintext are the same size in bits.
The Key is only used once and it's secret
The Plaintext is only used once and it's secret
Hence the Cyphertext is only used once, but it's public
Only the Cyphertext, and hence the size of the key is known to the adversary

However:

The Key was generated by a pseudorandom number generator
The Plaintext (which is a private key to something else) was also generated by a pseudorandom number generator

Therefore neither the key nor the plaintext is fully random, vulnerable to frequency attacks.

So I don't care about practical issues, like the difficulty of key sharing. I only care about security issues.

We can identify that this setup can be vulnerable to frequency analysis and such described here:

https://stackoverflow.com/a/1135204

But are there other vulnerabilities besides the pseudo-random nature of the key and the plaintext?
If both the key and the plaintext were truly random, would this provide perfect secrecy?

What you basically have is a binary additive stream cipher, using your pseudorandom number generator as the keystream generator.  Used properly (i.e. in such a way that the same keystream is never used twice), the security of such a cipher depends entirely on the strength of the pseudorandom number generator.

If the output of the generator cannot be practically distinguished from a stream of truly random bits without knowing the seed of the generator, and if the seed itself is chosen randomly from a large enough space to make brute force testing of all possible seeds impractical, then such a cipher is indeed secure (in the sense of protecting the confidentiality of the plaintext; note that such XOR-based ciphers are generally malleable, and thus vulnerable to active tampering attacks).

Unfortunately, most pseudorandom number generators are not designed to remain indistinguishable from random even to a deliberate attacker; a typical PRNG's output only looks random to a casual observer, but can be easily distinguished from random if you know how the generator works.  Algorithms that are designed to resist such distinguishing attempts are generally described as CSPRNGs, or simply as stream ciphers.

If the keystream were truly random, then what you have would be a one-time pad, and would therefore indeed provide perfect secrecy (but still be malleable).  The randomness of the plaintext does not matter here — the whole point of perfect secrecy (and its computational variant, semantic security) is that a cipher with perfect secrecy will reveal no information about the plaintext whatsoever (except for its length), no matter what the plaintext may be or how it's chosen.

That said, if you intend to use the plaintext as the key to another cipher, then it certainly should be generated in such a way as to make it impractical to guess (even using massive amounts of computing power to test possible guesses).  Otherwise an attacker could just ignore your XOR stream cipher / one-time pad entirely, and simply try to guess the key to the other cipher directly.


Do known-plaintext attacks exist for public key encryption? In asymmetric ciphers we publish the public key for anyone, which means an attacker can encrypt any message they want and compare the ciphertext and plaintext without communicating with the owner of the private key. So do known-plaintext attacks make sense for asymmetric ciphers, or are they only for symmetric ciphers?

Ps. What are all the attacks there exist for public key ciphers? (I know of chosen ciphertext and timing attacks.)

Known-plaintext attacks are key-recovery attacks. By design, an asymmetric cipher cannot be susceptible to known-plaintext attacks; it would be completely worthless.

The property you describe that asymmetric ciphers such as textbook RSA lack is called semantic security. Some considerations:

In practice, RSA might be used only to encrypt a randomly generated key for a symmetric encryption algorithm, since encrypting a large message would be very slow with RSA alone. If that key is long enough (e.g., 256 bits), it isn't feasible to launch an attack encrypting every possible plaintext; there are too many of them.
If RSA itself is used to encrypt the message, proper implementations apply some random padding to the message.
Symmetric ciphers do (should) not suffer from this, since you need the secret key to encrypt a message.

Last, it's not possible to enumerate all existing attacks on public-key cryptography. They're different for every cipher and even for different implementations of the same cipher (see blinding).


Given C is a code of length n. Containing M code-words with a distance d I'm studying for my exam and came across this question below.
I don't understand how to get $d$. I get $C$ is a code of length $n$.
Containing $M$ code-words with a distance $d$.

$(n,M,d)$

But how do I get $d$ below?

  Give one (5,4,d) code in … as below …
      Z^(5) base 2.

  C={
  0,0,0,1,0
  0,1,1,0,1
  1,0,1,1,0
  1,1,0,1,1
  }

The distance of the code word is the minimum number of bit flips that transforms one codeword into another. It's just the minimum of all possible hamming distances between the codes.

Also you can define the weight of a codeword to be the distance from the zero vector.

For your code it looks like $d = 2$.


Building blocks of SHA-1 and SHA-2 I ask myself some questions about the compression function of SHA-2 (and SHA-1) hash function. Are these compression functions based on a block cipher? I've not found this information on Wiki... So, I think that these compression functions have been designed from scratch, without relying on a block cipher.

What about the compression function of MD5?

Thank you for your answer.

For each of the "MD" functions (MD4, MD5, SHA-1, SHA-256, SHA-512, and derivatives), one can view the compression function as a "tilted block cipher": the message block is used as key, and the function encrypts the current state.

More formally, if you look at MD5, then there is a block cipher $B$ that takes as inputs a 512-bit key and a 128-bit block. The Merkle-Damgård construction then uses a 128-bit running state $r$, initialised to a conventional initial value. The processing of message block $X$ consists in computed $B(X,r)+r$, which becomes the new value for $r$: the current state is encrypted, using the message block as key, and the encryption output is added (in the case of MD5, this is word-wise addition) to the previous state.

If you look at the block cipher details for MD4, MD5 and SHA-1, then you can see that it is a kind of generalised Feistel scheme. In a "normal" Feistel scheme, the input block is split into two halves, and one half is then combined (usually by XOR, but it also works with other reversible combinations like modular addition) with the other half; then the two halves are swapped. In MD5, the input block is split into four words; a function is computed from three words, result being combined with the fourth, and then the words are rotated. Successive SHA functions tend to add a few extra operations but don't change the general structure.

For all the classic MD functions, the inner block cipher was designed "from scratch", i.e. specifically for the hash function. However, in the case of SHA-1 of SHA-256, the block cipher was afterwards awarded a name of its own, SHACAL. I am not aware of any significant deployment of SHACAL as an encryption function.

Similarly, one might want to take an existing block cipher, and turn it into a hash function: this is what Whirlpool is about.

This block cipher / hash functions relationship is subtle, and, altogether, disappointing. Excellent performance of hash functions does not translate to fast encryption: while MD5 can crunch lots of data per second it does so by 512-bit blocks; the underlying block cipher, for the same amount of work, processes only 128 bits, so its bandwidth is going to be only 1/4th of that of MD5. Security is not that good either: most block ciphers are not very strong against related-key attacks because such attacks use an esoteric, impractical setup that does not apply to practical situations; however, when the block cipher is turned into a hash function with the Merkle-Damgård construction, the related-key attacks become collision attacks, and these are very practical. This is why Whirlpool uses a block cipher called W, derived from Rijndael (i.e. AES), but with a much strengthened key schedule: W is believed immune to related-key attacks, and this was done so to make Whirlpool immune to collision attacks.

You might want to investigate the design documents for Skein, a former SHA-3 candidate. Skein is built upon an internal block cipher (dubbed "Threefish"), but it uses it with another structure ("ARX") in which the block cipher is not "tilted", which avoids the trouble with related-key attacks, and allows a better performance mapping between hashing speed and encryption speed.


Can RSA be used to encrypt p? In RSA you choose $n=pq$ where $p$ and $q$ are large primes with similar length. Then you choose $e$ that is coprime with $\phi(n)$ and find $d$ that is modular multiplicative inverse of $e$ modulo $\phi(n)$, so $ed \equiv 1 \mod \phi(n)$.

Then $(m^e)^d \mod n = m$ for any natural $m$ less than $n$.

As far as I have researched it, the exponentiation to the power $ed=k\phi(n)+1$ where $k$ is an integer relies on the Euler's theorem that states $a^{\phi(n)} \equiv 1 \mod n$ which is true if $a$ is coprime to $n$.

This leads me to a question, what happens if you choose $p$ as the message? Does RSA handle it in any way? I would like to know both about Textbook RSA and the Deployed RSA.

Yes, both textbook and practical RSA can reversibly encrypt $p$.

Textbook RSA can encrypt and decrypt any plaintext in $[0,N)$ as long as $N$ is squarefree (which is hypothetized or at least overwhelmingly likely); and that's including $p$. In a nutshell: Fermat's little theorem implies that $M^{e\,d}-M\equiv 0\pmod p$ for any $M$ and any prime $p$ dividing $N$. It follows that $M^{e\,d}-M\equiv 0\pmod N$ if $N$ is squarefree. Correct decryption for any $M\in[0,N)$ if $N$ is squarefree follows. See more detailed proof there.

However, encrypting $p$ is a particularly terrible use case of textbook RSA, because revealing the ciphertext allows factoring $N$ by computing $\gcd(\operatorname{Enc}(p),N)$ ; that's $p$, as explained there.

Practical RSA has no problem encrypting $p$ for many common parameters: the RSAES-OAEP encryption scheme in PKCS#1 can encipher octet strings of up to $\lceil (\log_{2}N)/8\rceil-2h-2$ octets, where $h$ is the width fo the hash in octets, and that's enough for $p$ when $N$ is larger than $4h+4$ octets and has factors of equal size, which is typically the case. RSAES_PKCS1_V1-5 has a slightly different capacity. When $p$ does not fit (e.g. 2048-bit RSAES-OAEP with SHA-512 has a capacity of 126 octets, which is typicality 2 octets short for $p$), the plaintext can be split into several cryptograms, or there's hybrid encryption.


Maximum password length in PBKDF2 Haven't found any clear cut answer in Google so its up to you guys:

DK = PBKDF2(PRF, Password, Salt, c, dkLen)

Here, what is the upper limit of password length? I tried up to 16 characters and it works. How far can I go? I read somewhere that salt has no upper limit! Is it really true?

There's no practical limit to password or salt length you can use with PBKDF2.

Theoretical limit, however, is determined by the hash function used by PBKDF2: under the hood, it uses $HMAC(Password, Salt || Counter)$, which in turn will translates to a series of hash function calls:

$K_0 = H(Password)$ (assuming password is longer than hash block)
$HMAC = H((K_0 \oplus opad) || H((K_0 \oplus ipad) || Salt))$

If we assume a very long password and/or salt, then two hash function calls can potentially "overflow": $H(Password)$ and $H((K_0 \oplus ipad) || Salt)$. To avoid such "overflow" $Password$ must be smaller than maximum input size supported by the hash function, and $Salt$ must be shorter than maximum input length minus block size of the function.

TO give some perspective and show why this doesn't really matters in real world, maximum input length for e.g. SHA-1 is $2^{64}-1$ bits or $2^{61}-1$ bytes. Block size of SHA-1 is 64 bytes, so maximum $Salt$ size will be $2^{61}-65$ bytes.


The key size of an ideal block cipher My understanding of an ideal block cipher is as follows:

For a block cipher with block size $n$, there are $2^n$ possible plaintexts. The number of possible keys (mappings) would then be $2^n!$.

The size of a single key would then be $2^n$ because you're choosing one full permutation from the set of all possible permutations.

EDIT: Now that I think about it some more, the key size would be the required number of bits to express the number of possible permutations. So for 24 permutations, that would be a 5-bit key size. For 40,320 permutations, that would be a 16-bit key size.

Is this correct?

Ideally, each key $k$ select a permutation of all possible permutations $2^n!$ for a block cipher with block size $n$. So when we say 128-bit key we expect that they represent $2^{128}$ permutations from possible ones. Some keys might be very bad, maybe just inverting the plaintext or some acts as a counter, we don't know.

Your calculations are correct if the random selection has no collisions, i.e. there may be two keys that represent the same permutations. We don't expect this collision since $2^{128}$ is very small compared to $2^n!$.

In general, we don't talk about the number of permutations that the key-size represents. We talk about the provided security by key length in bits.


Application of MDS matrices in serial and round-based implementations We know that MDS matrices are used in the diffusion layers of block ciphers.

My question: what types of MDS matrices can be applied to serial or
round-based implementations or both of them?

I appreciate you to address some references.

what types of MDS matrices can be applied to serial or round-based
  implementations or both of them?

Serial matrices utilise a trade-off to reduce hardware requirement while incurring additional time cost. Examples of MDS matrices that can be serialized implemented are : cyclic , Hadmard, linear feedback serial (LFS), sparse diagonal serial invertible (DSI), ref. LED, PHOTON, PRIMATES use efficient serialized MDS matrices, ref.

It is possible to transform serial MDS to round-based , as following stated in ref.

  One may also consider unrolling DSI/LFS matrices to simulate round-
  based matrices for comparison with cyclic/Hadamard matrices in a
  round-based implementation scenario. That is to implement k copies of
  DSI/LFS matrices in series to achieve the MDS property in one clock
  cycle. The XOR count of all the matrices would simply be k times of
  what the tables have shown

MDS matrix is defined over $F_{2^n}$ and the choice of basis is important on implementation efficiency. for round-based hardware implementation, the choice of basis is important in lightweight construction. ref

I sugest to read the following papers to obtain deep knowledge:

Lightweight MDS Serial-type Matrices with Minimal Fixed XOR Count
Shorter Linear Straight-Line Programs for MDS Matrices Yet another XOR Count  Paper
Lightweight Multiplication in GF(2n) with Applications to MDS Matrices


When we turn Random shuffle to Pseudorandom Shuffle It's well known that a simple but efficient random shuffle algorithm

can permute a vector of $n$ elements in $O(n)$ time.

In the algorithm, we need to pick a value $U$ uniformly at random where $0\leq U\leq 1$.

However, I need a pseudorandom function (or algorithm) so I can re-generate the same permutation over again.  Thus, I need to use a pseudorandom function to generate $U\hspace{-0.02 in}$.  But the pseudorandom functions usually output an integer but not value $U\hspace{-0.02 in}$, where $0\leq U\leq 1$.

Question:  How can we turn the random shuffle into a pseudorandom shuffle?

or

How can we map the output of pseudorandom function to a value in the interval $(0,\hspace{-0.05 in}1)$

such that the value in that range still is a pseudorandom value?

It is not possible to generate uniform real number of infinite precision.
Therefore, it is not possible to pick a random value $U$ arbitrary precision uniformly at random so that $0 \le U \le 1$, and that any number in the range is possible.

Instead, it is (typically) necessary to generate sequence of uniformly random bits and interpret them as floating point number. For instance, you may generate 32 random bits and represent them as integer and divide the result with 4294967295. [Exception: Some sources have range that is not binary, like ideal dice. They still have limited precision.]

This part actually works the same regardless of if you had truly random source or if you used pseudo random number generator capable of generating bits to generate your random numbers.

However, Fisher-Yates shuffle or Richard Durstenfeld shuffle algorithm you linked to actually does not need arbitrary precision random numbers. It need random numbers, which are in range $0 \le j \le i$. These in theory can be derived from random and uniform arbitrary precision float number between [0, 1), but in practice, you instead need to generate bits (as described above) and use them to select array element to shuffle. Because the range is not always power of two, it is often necessary to use algorithm, which can convert numbers to specific range without generation of bias. FIPS 186-4 provides some algorithms useful to convert bits to arbitrary integer range. See Appendix B.2.1 and B.2.2 for two choices: allowing some bias or testing candidates and rejecting out of range values.


Any good file format alternative to PGP for encrypting data at rest? I'd like to create an encrypted file that:

Can be decrypted on a variety of platforms (mainly Windows, OS X, and Linux) with knowledge of the key.
Can be decrypted with existing tools (perhaps writing a shell script piping together common tools).
Is in such a simple file format such that it'd be relatively easy to write your own decryption function from scratch assuming you had a standard library that included primitives like AES and HMAC-SHA256 without spending days or weeks trying to understand the file format.

So far, I've come up with three alternatives:

PGP - This sounds like a no-brainer, but its file format is quite complex and would require using a library like BouncyCastle. I'd rather have something simpler and not need dependencies.
OpenSSL - It has a very simple file format. I was able to write my own reader and writer in a few lines of code after understanding its key and IV derivation function. However, the format doesn't have a MAC in its standard.
KeyCzar - The encrypted file format does have a MAC in it, but the tools to encrypt and decrypt files aren't nearly as popular as PGP or OpenSSL.

Given these options, OpenSSL sounds very compelling if I could incorporate the MAC in it in an intuitive way. I could run openssl dgst on the encrypted file and then concatenate it to the end of it, but that is a bit hacky and I'm worried that it might be easy to mess up the Encrypt-then-MAC characteristics of the file in custom implementations.

Am I missing an easy answer to this problem?

Thanks in advance.

The more I think about this, the more I think it'd be better to not do this.

I couldn't think of a single file format that would be simple enough for this - they all have atleast some structure that is hard to replicate via shell-scripts and the like. Also, security considerations for the file format crop up very easily, especially if taking passwords in to consideration as well.

From the existing utilities, I suggest a quick look at scrypt. It has a pretty simple on-disk file format and meticulous attention to detail in general. It doesn't do encryption with actual keys, only passwords, though. The problem with that is that the scrypt key derivation function uses Salsa20 internally and isn't that simple to reimplement.

But, never the less, I thought I'd create something akin to what you wanted, but without any password functionality.

genkey.sh:

#!/usr/bin/sh

openssl rand -out $1 64

enc.sh:

#!/bin/sh

KEY=$1
FILE=$2
OUTPUT=$3

HMAC_KEY=`hexdump -v -e '/1 "%02x"' -n 32 -s 0 $KEY`
AES256_KEY=`hexdump -v -e '/1 "%02x"' -n 32 -s 32 $KEY`

openssl rand -out $OUTPUT 16
AES256_IV=`hexdump -v -e '/1 "%02x"' -n 16 $OUTPUT`
openssl enc -in $FILE -K "$AES256_KEY" -iv "$AES256_IV" -aes-256-cbc >> $OUTPUT
openssl dgst -hmac $HMAC_KEY -binary -sha256 $OUTPUT >> $OUTPUT

dec.sh:

#!/bin/sh

KEY=$1
FILE=$2
OUTPUT=$3

HMAC_KEY=`hexdump -v -e '/1 "%02x"' -n 32 -s 0 $KEY`
AES256_KEY=`hexdump -v -e '/1 "%02x"' -n 32 -s 32 $KEY`
AES256_IV=`hexdump -v -e '/1 "%02x"' -n 16 -s 0 $FILE`

SIZE=`stat -c"%s" $FILE`
HMAC_BLOCKS=$(($SIZE/16 - 2))
AES_BLOCKS=$(($SIZE/16 - 3))

HMAC_FILE=`dd if=$FILE bs=16 skip=$HMAC_BLOCKS | hexdump -v -e '/1 "%02x"'`
HMAC_CALCULATED=`dd if=$FILE bs=16 count=$HMAC_BLOCKS | openssl dgst -hmac $HMAC_KEY -sha256 -binary | hexdump -v -e '/1 "%02x"'`
if [ "x$HMAC_FILE" != "x$HMAC_CALCULATED" ]; then
  echo "fuuuuu"
else
  dd if=$FILE bs=16 skip=1 count=$AES_BLOCKS status=noxfer | openssl enc -d -K "$AES256_KEY" -iv "$AES256_IV" -aes-256-cbc -out $OUTPUT
fi

Key format is:

32 bytes AES-256 key
32 bytes HMAC-SHA256 key

Encrypted file format is:

16 bytes AES IV (random generated each time)
x*16 bytes AES-256-CBC encrypted data with PKCS#5 padding
32 bytes of HMAC-SHA256 over the entire preceding file (including IV and padded and encrypted data)

The HMAC is verified first, so no data is decrypted in case the MAC is wrong. The IV is included in the HMAC, so there's no monkey business with that either. To get a less than 2-32 probability of a duplicate IV, the same key can be used a maximum of 248, which should be plenty. A single file is probably limited in length by the HMAC to be maximum of 260 - 1 bytes, which should also be plenty. There should be no attacks allowing forgery, recovery of the key or recovery of the plaintext under 2128 complexity. The entire resulting file should be indistinguishable from random except for the fact that the file size is always a multiple of 16. But no guarantees about security are given, peer review is a must.

The scripts do no argument validation and are in general written just to show how they work, not for safety or actual use. In particular, the actual encryption keys show up in command-line arguments and hence can be seen with ps by any user - so these really shouldn't be used for anything serious.


Constructing a mac scheme secure to regular definition but insecure to special case The mac-forge security game for mac schemes looks like this:

$k \leftarrow \operatorname{Gen}(1^n)$;
$(m,t) \leftarrow A^{\operatorname{MAC}_k(⋅)}(1^n)$;
Let $Q$ denote the set of all queries that $A$ asked to its oracle;
The output of the experiment is defined to be $1$ if and only if $\operatorname{Verif}_k(m,t)=1$ and $m \notin Q$.

So, in this experiment the adversary has acces to a $MAC(.)$ oracle. But let's consider another experiment that where the adversary also has acces to a verify oracle, but otherwise the experiment is the exact same. Let's call the experiment mac-forge*.
If we consider a mac scheme that is secure with respect to both these definitions, can we then make a new scheme from it, that is secure for mac-forge, but not mac-forge*?
I suspect something strange should be done to the verify function, but I really don't know what.
Edit
If I construct vrfy* like:
vrfy*k(m,t) = if tag has correct length, just Mac(m), and if Mac(m) = t

, output true, elif if Mac(m) != t output false
if tag is smaller than it should be, and has length i, output the i'th bit of the key

Using your terminology, if a scheme is secure in the mac-forge game then it is also secure in the mac-forge* game. The formal proof is a bit fussy I can sketch the main idea.
First, without loss of generality, assume that in the mac-forge* game the adversary never queries the verification oracle on $(m,t)$ that was a result of a prior MAC query. This is without loss of generality because we already know what the verification oracle will answer (true) on such an input, so there is no need to query.

Claim: If the MAC scheme is secure in mac-forge then in the mac-forge* game the verification oracle will answer false to all queries.

The proof idea is as follows: Suppose we have an adversary $A$ who breaks security of the mac-forge* game. We will use it to construct a new adversary that breaks the security of the mac-forge game. Suppose $A$'s $i$th query to the verification oracle is the first one that returns true. Construct a new adversary $A^*_i$ which does the following in the mac-forge game:

run $A$
whenever $A$ makes a MAC query, make the same MAC query in the mac-forge game and relay the result back to $A$
when $A$ makes verification queries 1 through $i-1$, give the answer false  to $A$
when $A$ makes the the $i$th verification query $(m,t)$, halt with output $(m,t)$.

So $A^*_i$ plays in the mac-forge game (it never makes verification oracle queries). If $A$'s $i$th verification query really was the first one that returns true, then:

$A^*_i$ provides a view for $A$ that is identical to when $A$ plays the mac-forge* game (identical until we terminate $A$ early)
$A^*_i$ halts with a valid forgery.

So $A^*_i$ breaks the mac-forge security of the scheme.
This is just a sketch, and it somewhat assumes that it is always the $i$th verification query that works. In the real proof, you would choose $i$ uniformly at random and incur a loss in concrete security.


Reordering of multiple signed blocks I would like to refer you to page 430 of the Handbook of Applied Crypto, where the authors said "... reordering of multiple signed blocks presents a security risk..."

This statement was made in reference to not breaking messages into fixed lengths which can then be signed individually using signature schemes with message recovery.

My question is

  How does the security risk arise?
  If I do not want to include a hash function for signature schemes with appendix, can I break the message up into blocks of fixed lengths and sign each block?

Thanks for your help!

How does the security risk arise?

Because you can simply drop or reorder signatures for single block. Assume you have a message $m$ and you split it up in blocks $(m_1,m_2,\ldots,m_n$) and get signatures $(\sigma_1,\sigma_2,\ldots,\sigma_n$). Then you could just drop for instance $\sigma_2$ and get a signature for message $(m_1,m_3,\ldots,m_n)$. You can also replace arbitrary sub-signatures, e.g., $(\sigma_2,\sigma_1,\ldots,\sigma_n)$ which is a valid signature for $(m_2,m_1,\ldots,m_n)$. Now you could say that you introduce increasing sequence numbers, but if you got two signatures you could simply exchange sub-signatures from these two signatures to obtain valid signature for "mixed messages". Ok, now you could say you use unique sequence numbers per message, but there may be too many other attacks that you do not consider.

  If I do not want to include a hash function for signature schemes with appendix, can I break the message up into blocks of fixed lengths and sign each block?

So why introducing such additional assumption where you may overlook something that is specific to your application scenario.

Besides removing these problems it is far more efficient to firstly hash the message before signing and then sign a single block.


Are these functions secure PRFs? Let
$F:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ be a secure PRF (i.e. a PRF where the key space, input space, and output space are all $\{0,1\}^n$) and say $n=128$.
My assignment is to show that the function
$F'(k,x) = F(k,x)$ when $x \ne 0^n$ and $F'(k,x)=k$ when $x=0^n$ is
not a secure PRF, but the function $F''((k_1,k_2),x)) = F(k_1,x)$ when $x \ne 0$ and $F''((k_1,k_2,x)=k_2$ when $x=0^n$ is a secure PRF.
However, I think that both are secure PRFs. Because when the input is $0^n$, above $F'(k,x)$ and $F''((k1,k2),x)$ will return $k$ and $k_2$ which are randomly chosen from their keyspace. So, even though adversary inputs $0^n$ multiple times it can only find out some random $\{0,1\}^n$.
Can you tell me what's wrong with my reasoning?

Informally, the security of a PRF is defined as follows:
The adversary is allowed to ask questions from its oracle.
The oracle choose one of the functions $F$ or $f$ at the beginning, where $f$ is a truly random function with the same domain and image as $F$.
When the adversary $A$ sends a query on $x$, the oracle returns the answer $F(k,x)$ or $f(x)$, depending on which one it has chosen at the beginning.
We say that $F$ is a secure PRF if $A$ can not distinguish which function the oracle has chosen.
Now whit this explanation, for your first function, the adversary sends a query on a nonzero $x^*$, then  a query on zero, when it receives $k$, it compute $F(k,x^*)$ if it was the same as the answer it has received for $x^*$ from the oracle, it distinguishes that the oracle has chosen $F$.
For the second function, the same attack does not work, because the adversary does not know the whole key yet.


Is just a bit of random, "fully random"? I understand that hashing a datetime is a pseudo-random number, and not good in a security context.

But what about hashing a datetime plus a truly-random but constant string (just a string that an "attacker" could not possibly guess)?

This is not a question for a practical implementation, just a theoretical question.

Is pseudo-random plus a bit of "true random", "fully-random"?

(p.s.: I'm not a security specialist, so please don't use overly-complex terms if possible.)

Let's look at this from the bottom ("what is random?") to the top (is that secure?).

When we talk about "random" in cryptography we almost always prefer to talk about "entropy". The intuitive and concise definition of cryptographic entropy is that it is a measure of how much information the attacker does not know about the target message. When you hear about, for example, "128 bits of entropy" in cryptography, it essentially means that the message has 128 bits of information that the attacker is expected to not know about, and thus a total $2^{128}$ possible values that, from the attacker's perspective, could be the one they're looking for. For example, a 100-bit string might be generated by always prefixing a 1 and then having the remaining 99 bits filled in from a perfect random number source. This string would have 99 bits of entropy, since the first bit is known by the attacker to always be 1 and thus all strings starting with 0 are invalid. (This is all fairly simplified, by OP's request.)

So then, what's the entropy of "pseudo-random"? A pseudo-random string is just something that looks random (ie, passes all good tests for randomness) but is deterministically derived from an input. So the amount of cryptographic entropy in a pseudo-random string is actually the amount of entropy in the seed input that was used to create the pseudo-random string. This is because if the attacker can determine the seed, then they too can generate the resulting pseudo-random string. So from the attacker's perspective, the number of possible pseudo-random strings is simply the number of possible inputs that could have been supplied. (This fits with the above notion of cryptographic entropy.)

Why the distinction between "entropy" and "random"? Because we have have strings that look very random but actually have low entropy. (Such as a pseudo-random generator that always looks random regardless of the input.) In cryptography we don't usually care how random a secret looks but rather how hard it would be to re-create, and as far as vocabulary goes, "entropy" is more explicitly a measure of the source of the string, not the content. (However, for what it's worth, the terms "random" and "very high entropy" often seem to be used interchangeably amongst those familiar with the concepts.)

So what does your proposed scheme do with entropy? Your time-stamp will have some entropy, but it's unclear how much. The attacker will likely know something about the time-stamp (such as the year it was generated) but not everything (such as the exact millisecond). So the entropy won't be maximal or minimal for that source. For your secret string, it will have entropy because it has some information unknown to the attacker. If it's a string you hand-designed then it is highly unlikely it has full entropy, but it does likely have some entropy if you put any effort into designing it. (Without knowing more we can't estimate how much entropy your string has.)

The fact that you hash the concatenation of your strings does not change the amount entropy. The attacker still needs only to guess the input to the hash function. The hash will act similar to the pseudo-random generator above in that it will provide random-looking output that conceals the content of the input. But the attacker's job is simply to guess the input to that hash and so the measurement of cryptographically secure entropy is the same despite the use of the hash. The same number of original message possibilities remain, from the attacker's perspective.

To address your italicized question: A message that is "fully random" is going to have entropy the same size as the message. For example, a truly random 128-bit key will have 128 bits of entropy, but 128-bit key with 127 bits of entropy is probably not going to be considered "fully" random.

But practically speaking, we actually don't really care about having full entropy, we care about having enough entropy. A 128-bit string with 128 bits of entropy is, in theory, just as secure as a 500-bit string with 128 bits of entropy, especially if you're going to put it through some sort of function like a hash or a PRG. If security is your goal, be primarily concerned with how much entropy you collect and less so with how many bytes it took to do so.

The summary here is that a string has at least as much entropy as its highest entropy source. If you concatenate a weak string with a strong string, your result is a strong string. If you have a weak string and add a strong string and hash the two, the hash output should be a strong string.


PBKDF2WithHmacSHA512 Vs. PBKDF2WithHmacSHA1? I'm working on a Java authentication subsystem that specs the storage of passwords in the DB as PBKDF2-generated hashes, and I'm now trying to decide whether I should use SHA1 or SHA512 as PFR. I'm under the impression that the consensus is that SHA1 has some theoretical weaknesses, and that SHA512 should be chosen instead. However the standard javax.crypto package does not offer a PBKDF2WithHmacSHA512 implementation, how is that so?

For reference purposes, here’s my code:

private static final int HASH_BYTE_SIZE = 64; // 512 bits
private static final int PBKDF2_ITERATIONS = 1000;

// generate random salt
SecureRandom random = new SecureRandom();
byte salt[] = new byte[SALT_BYTE_SIZE]; // use salt size at least as long as hash
random.nextBytes(salt);

// generate Hash
PBEKeySpec spec = new PBEKeySpec(password, salt, PBKDF2_ITERATIONS, HASH_BYTE_SIZE);
SecretKeyFactory skf = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA1"); // this throws a NoSuchAlgorithmException if I replace with "PBKDF2WithHmacSHA512"
byte[] hash = skf.generateSecret(spec).getEncoded();

// convert hash and salt to hex and store in DB as CHAR(64)...

Hash algorithm strength is important, but it is not so important in key derivation functions. It is unlikely that even if SHA-1 is broken that it would influence the security of PBKDF2. You are better off using SHA-1, and increase the iteration count up to a level that is tweaked for your specific configuration.

If you must, you could use Bouncy Castle to create an implementation of PBKDF2 with SHA-256. The internal security of the algorithm is not that important, if your server is relatively safe against side channel attacks (and for PBKDF2 it likely is). So using a non-certified open source solution would probably not compromise your security.

Your efforts are probably better spend elsewhere. Congratulate yourself on choosing a relatively good password based KDF, choose a 64 bit random salt and use a higher iteration count, and move on...

Note: if you want to protect against hardware accelerated attacks, you may want to consider scrypt instead of PBKDF2.

The Oracle JDK 1.8 contains PBKDF2 implementations for SHA-512 "PBKDF2WithHmacSHA512". This can be used for compatibility with other systems or for deprecating SHA-1 entirely.


Symmetric Exchange Key Sharing Question:
Suppose that there are 10000 = 10^4 banks and 10 payment card organisations (PCOs).

How many secret keys will be needed if each PCO shares a unique secret key with each bank?
How many extra secret keys will be needed if every two banks share a unique secret key?

For question 1, I figured that if there are 10,000 banks and 10 PCOs:
 10,000 * 10 = 100,000.

For question 2, I need to calculate the number of keys if every 2 banks share a key (so I guess for 10,000 banks there would be 5,000 keys?)
 5,000 * 10 = 50,000, right?

I recall that the solution could be calculated differently, something along the lines of 5,000(5,000-1)*10/2 but I don't understand the logic of this.
Could someone please explain?
(I would appreciate explanation of logic or a direction for research to understand because I feel like this should be quite straightforward and I am unsure).
Thank your for taking the time to read this!

The underlying principle here is that of combinatorics. Think of banks and PCOs as abstract parties. Party $A$ has $|A|$ many members and party $B$ has $|B|$ many respectively. For each $x \in A$ we have $|B|$ secret keys which $x$ shares with members of $B$ meaning we have $|A| \times |B|$ keys.
In your first question, we assumed that for all $x \in A$ and $y \in B$,  we know that $x \neq y$. I. e., The two parties $A$ and $B$ don't share any members! In your second question however, that assumption is not true since $A = B$ which means the party of banks sharing keys with the party of banks, id es, among themselves.
The question here is then how many ways to pick unique $\{x, y\}$ combinations from a set $A$. Well, this is just an $n$ chose $k$: $\binom{n}{k}$ problem. In this case $k = 2, n = |A|$.

How many secret keys will be needed if each PCO shares a unique secret key with each bank?

$$|A|\times |B| = 10^4 \times 10 = 10^5$$

How many extra secret keys will be needed if every two banks share a unique secret key?

$$\binom{10^4}{2} = \frac{10^4!}{2!(10^4-2)!} = \frac{10000!}{2(10000-2)!} = \frac{10000!}{2(9998)!} = \frac{9999 \times 10000}{2}$$


From Factorisation of semiprimes to breaching confidentiality If someone or some group found an efficient way to factor large composites with two distinct prime divisors, would this make it easier to decode any messages?

I guess it depends on which scenario you are referring to. If it is RSA, being able to factorize $n = pq$ would compromise the security of that crypto-system.

This is because one could compute $\phi(n) = \phi(p)·\phi(q) = (p-1)·(q-1)$ since $p$, $q$ are two distinct primes and could calculate the private key $d$ from the public key $e$ by using the equation $e \cdot d = 1 \mod \phi(n)$.


How to perform file encryption using 128-bit AES I am confused. How can I encrypt a file using 128-bit Advanced Encryption Standard?
Do I need only to encrypt the file name and it's content or is there something that I need to do to encrypt it? Is there something that I will need to extract to the file to encrypt it?
For example, I want to encrypt an MS Word file or a PDF file.
It is easy to encrypt a file if the file only contains text, but what if there is a image in a file? How do I go about that?

You are right to be confused, because you could just as well have asked "How can I encrypt a file using a CPU that supports xor, shifts and rotates?" The answer is that of course you can, but there is obviously a lot more to it, if you are going to do it right.

AES is just a standard block cipher primitive. The only thing this standard tells you, is how to transform a single 128 bit block using a key, into another 128 bit block. It doesn't tell you where the key is coming from, or how you are going to process any data larger than 128 bits. Those aspects have to be specified as well, and one example would be password based encryption as in PKCS#5 PBES2 with AES-CBC-128 combined with PBMAC1 with HMAC-SHA-256.

When reading the technical specifications of consumer software or business software, it is not that uncommon that the only thing specified is the block cipher primitive, such as "128 bit AES". In my experience this is often due to either of the following reasons:

The software developers don't have a clue about cryptography and are actually using AES-ECB-128 with a key that embedded as a constant in the software.
The software developers are using a proper file encryption scheme but specify only the block cipher primitive because that's the only buzz word that they thought was necessary for marketing reasons.
If the software is based on legacy software that used a scheme with e.g. 3DES, stating that they use "128 bit AES" might simply indicate that they use the same scheme as before, but have just substituted the block cipher primitive.

If you interested in how some existing software is encrypting files, just knowing that the software uses AES-128 is consequently not enough. If you are interested in which schemes and algorithms to look up if you were to write such software yourself, you have to be a lot more specific about your security requirements...

What's the relation between the person or entity encrypting the file and the person or entity decrypting the file?
Exactly what bad things do you hope to prevent by encrypting the file?


What are the weaknesses of Shamir's Secret Sharing? We just learned about this in school but i don't quite get the weakness of this method. If we let's say have used a 64-bit secret key to encrypt a file and then we split the key into 2 pieces of 32-bit. If the enemy managed to find one half and he can use brute force on the other one. Will he manage to find it? Or does it depend on how times the enemy can try per second? What if he can try $10^6$ times per second? but does that mean that trying also counts as trying to combine the two halves? I mean that does he in every time he brute forces, also try at the same time to sum the two parts and unlock the key?

let's say have used a 64-bit secret key to encrypt a file and then we split the key into 2 pieces of 32-bit

That right there is your misunderstanding. Shamir secret sharing does not split a secret into pieces that are smaller than the original secret. Instead, it splits the secret into pieces that are the same size as the original secret.

A simple graphical example typically does the best job describing Shamir's method. Assume that my secret is the number $42$ and that I want to split this into $3$ pieces to give to my friends such that any $2$ of them can get together and recreate my secret. So my threshold is $2$, so I pick a random polynomial of degree $1$ (one less than the threshold) and set the zero term to my secret. So let's say my polynomial is $f(x)=42+17x$. To generate my shares, I evaluate the polynomial at the points $1,2,3$ and get $(1,59),(2,76),(3,93)$.

I then give one share to each friend.

Now, to understand the security of this, you need to think back to the line that we used to generate these shares. If I give you 1 point on the line, what does that one point tell you about the line that was used to share the secret?
 How many lines can you draw through that one point? The answer is infinitely many. So, by having that one share, you have gained no useful information about the secret.

That is the beauty of Shamir's method. Having the less than the threshold number of shares gives you no useful information. It is only when you have that one share that you have any useful information at all.


Is there any problem to reuse the prime p, g and a in Diffie-Hellman? Suppose I always reuse p, g and a in DH and there is someone monitoring my communication. Is there a way this person can use this to perform some kind of attack to me?

I believe that reusing p and g isn't a big issue, however I'm not quite sure about a.

Actually, there is one potential problem to reusing $a$ values:

Background: $g$ generates a subgroup of size $q$; $q$ is a divisor of $p-1$, but it is usually selected as a prime, and is hence less than $p-1$ (which is obviously composite).

What an attacker could do is, for any small prime $r$ which divides $(p-1)/q$, he can potentially learn $a \bmod q$; he does this by negotiating with you, selecting as his share a value $g^b \cdot h$, where $b$ is a value he knows (doesn't matter what it is), and $h$ is a value of order $q$.  Then, when you'll do is generate a shared secret $(g^b \cdot h)^a = g^{ab} \cdot h^{a \bmod r}$; he can easily compute $g^{ab}$, and so he knows the shared secret is one of $r$ different values (depending on the value of $a \bmod r$).

If $(p-1)/q$ has a number of small primes, the attacker can deduce quite a bit about $a$.  One example of such a $p, q$ pair which has been actually proposed is Group 23 of RFC 5114; this particular group has $$(p-1)/q = 2 * 3 * 3 * 5 * 43 * 73 * 157 * 387493 * 605921 * 5213881177 * 352891
0760717 * 83501807020473429349 * C489$$ (where $C489$ is a 489 digit composite), and so the attacker can actually deduce enough to make brute force search of a 256 bit exponent feasible.

Now, there are several ways to protect yourself from this:

When you receive a value $b$, always check to see if $b^q = 1$; if not, someone is playing games.  This works, but it is expensive.
Use a 'safe prime' group; that is, one where $p-1 = 2q$.  This implies that the attacker can learn one bit of $a$ (the least significant bit), but nothing else.
Don't reuse $a$ values; what the attacker learns is the value $a \bmod r$ for the $a$ you used with the exchange with him; if you use different values of $a$ for unrelated exchanges, this doesn't buy him anything.

Also, note that the idea of using $q = p-1$ really isn't a protection; if $q$ has a small factor $r$, the attacker can also learn $a \bmod r$ just by examining $g^a$, hence the same vulnerability is there (except that not reusing $a$ doesn't actually provide protection).


RSA Private Exponent Is it possible to calculate the private exponent when only the RSA public key (e;N) = (9292162750094637473537; 13029506445953503759481) is given?

Yes, since $N=p
\times q$, so we have $13029506445953503759481 = 109217267039×119298960679$,
also the private and public exponent $e$ and $d$ are related by the equation $ed\equiv1\text{ mod }\phi(N)\equiv1\text{ mod }((109217267039-1)×(119298960679-1)) $.
You should then be able to find $d$, the private exponent.


How vulnerable is one-time pad (OTP) encryption, if the OTP is used twice, with a random substitution scheme After reading up on the one-time pad (OTP) encryption method, I could see how it would offer unbreakable encryption if used properly.

Moreover, I looked at how the OTP could be broken if the OTP-key is used on more than one message.

What I now wonder is this: if classically you use a Vigenère Square to substitute letters according to your OTP-key, you can break the encryption by finding cribs and then applying the substitution of the letter in the second message. This is possible since I know the substitution scheme.

Now the interesting point: if I randomize my substitution table, I would think that a decryption using the same OTP-key would no longer be possible, unless I have enough messages to successfully map (almost) each letter to this unknown table.

Correct?

Bad idea (as far as I know & understood).

First, let's make sure you do not confuse Vernam cipher (XOR) with OTP.

OTP (One Time Pad) requires you – as described here – to use (1) a truly random one-time pad value, (2) generated and exchanged in a secure way, (3) at least as long as the message, and (4) only to be used once. So, what you are describing is not a One-Time-Pad.
Vernam cipher applies this concept with a stream cipher (simple XOR)

The best example of “miss-using” a OTP is usually given as:

$c_1 = m_1 \oplus k\\
c_2 = m_2 \oplus k\\
c_1 \oplus  c_2 = m_1 \oplus k \oplus m_2 \oplus k = m_1 \oplus m_2$.

where using the same key twice defeats its purpose and provides interesting information on the plain text (statistical attack).

Why your idea is bad ?

Given Kerckhoffs' principle:

The system must be practically, if not mathematically, indecipherable;
It should not require secrecy, and it should not be a problem if it falls into enemy hands;
It must be possible to communicate and remember the key without using written notes, and correspondents must be able to change or modify it at will;
It must be applicable to telegraph communications;
It must be portable, and should not require several persons to handle or operate;
Lastly, given the circumstances in which it is to be used, the system must be easy to use and should not be stressful to use or require its users to know and comply with a long list of rules.

Therefore you must consider that your Vigenere substitution table has to be publicly known : The secret should only rely on the OTP value. Hence the point of randomizing your substitution table is not that interesting any more.

Therefore, given the known substitution, statistical properties can be found that would defeat the randomization idea.

By the way, this idea is close to the design of Enigma, where the substitution table changes every round defined by an initial key, which is kept over the course of a day. Have a guess what happened during WW2... What would have happened if the Germans had changed their keys between every transmission?

PS: Rolling your own crypto is always a bad idea.


Corelating between the concept of Universal Hashing wrt Algorithms (hash-table use) & the use of Universal Hashing in a one-time MAC Trying to understand the concept of a Universal Hashing function.
From Introduction of Algorithms by Cormen, Rivest et al

We now define the hash function $h_ab$ for any $a \in Z^*_p$ and any $b \in Z_p$ using a linear transformation followed by reductions modulo $p$ and then modulo $m$:

$h_{ab}(d) = ((ad + b) \mod p) \mod m)$

I understand the above from an algorithmic point of view for use in a hash-table. i.e. if you have some data, which you need to hash to get a bucket/index number, you pick a random a & b from the sets & evaluate the function $h_ab$ at d. There is only a single input to the function once you picked the a & b.
But instead if we are using for a getting a hash in cryptography (for e.g. for using in a one-time MAC like Carter-Wegman MAC), then we now have 2 inputs - a key (a cryptographic key rather than a key to be hashed for a hash table) & also the message to hashed. So how does it work here? For simplicity, if I assume a single block of message, then how do I use this universal function to evaluate the hash?
TL;DR - a Universal Hash function has only one input when used with Hash Tables, but 2 inputs when used in Cryptography for a one-time-MAC. What's the relation between these 2 kinds of hash functions. All places (Textbooks, Wikipedia etc) I look at, universal hashing is defined in terms of a single input functions, so how does it differ for functions taking 2 inputs)?

For simplicity, if I assume a single block of message, then how do I use this universal function to evaluate the hash?

We shift some parameters from being part of the concrete function instance into the key.
For your example of $h_{ab}(d)=ad+b\mod p\mod m$ the following mapping is usual:

$d$ is the input to be hashed
$a$ is the secret key of the instantiation, reusable across multiple invocations
$b$ is the whitening value, it must be freshly random and hidden from adversaries for each invocation
$p,m$ are system parameters that depend on in which field you want to work and into which you have to encode your result, e.g. you could pick $p$ to be a relatively large prime and $m=2^k$ for some $k$.

Alternatively, if you insist on having only two non-parameter inputs, you can also force $a$ to have the same usage constraints as $b$ and declare them both "the key".


is there any hash collision attack that is not defeated by adding a salt first? In the references I've read, all the uses of "collision attacks", whether classical collision attack or chosen-prefix collision attack, goes like this: "Alice creates a 'good' document and an 'evil' document that have the same hash.  Alice presents the 'good' document to Bob, who signs it by taking a hash of the document and signing the hash.  Alice now swaps out the 'evil' document and Bob's signature will still appear valid."
But aren't these attacks trivially defeated if, instead of taking the hash of the document, Bob adds a random salt, hashes the document plus the salt, and then signs the concatenation of the hash and the salt?  Is there any set of conditions where this defense would not work?
Because I see lots of sources saying you have to stop using SHA-1 due to the known collision attacks, and by the above reasoning, I don't understand why, when you could just add a salt to whatever you're hashing.
(I have also read about how specific implementations can protect against collision attacks by using the hash function as an HMAC, i.e. adding a salt.  My question is more general -- is there any case where a collision attack is not defeated by adding a salt?)

Suffix salt
If you add the salt after the message, $\operatorname{MD5}(m \mathbin\| salt)$, that doesn't prevent Alice from finding two collisions. Example;
Consider that if the message $m$ of Alice is an exact multiple of the block size of the $\operatorname{MD5}(m \mathbin\| salt)$ then your signature will be vulnerable to hash chosen-prefix collisions. Because Alice can prepare two messages $m_1$ and $m_2$ so that $$\operatorname{MD5}(p_1\mathbin\| m_1) = \operatorname{MD5}(p_2\mathbin\| m_2)$$
Once Alice found the pairs such that
$$strlen(p_1\mathbin\| m_1)=strlen(p_2\mathbin\| m_2) = t \cdot 512$$
then adding your salt, even not known to Alice before, will not prevent Alice to forge. This is due to the Merkle-Damgård construction;

Both messages have the same internal compression values before the length added padding. Adding anything after those will not affect their collision.

If you add the salt after the message $\operatorname{MD5}(m \mathbin\| salt)$, that doesn't prevent Alice from finding two collisions. Example;

Prefix salt
If you add the salt before the message, $\operatorname{MD5}(salt \mathbin)$, this will prevent  Alice from finding two collisions.
We may see this in this way; the salt, especially it is one block, will be like an IV to MD5 since the first call of the compression function will calculate
$$ h_1 = C(salt,IV),$$ then $h_1$  will be a new IV for the rest of the compressions. This can be considered that you are using a family of MD5 hashes with different IV's. Since the IV is no control of Alice this is secure. Actually, this is similar to what HMAC does;
$$  \operatorname{HMAC}(K, m) = \operatorname{H}\Bigl(\bigl(K' \oplus opad\bigr) \parallel
\operatorname{H} \bigl(\left(K' \oplus ipad\right) \parallel m\bigr)\Bigr) $$
Consider the inner hash and, you will have a similar structure to change the IV of the hash function.
Your construction is vulnerable to length extension attack, however, since the resulting hashes will be different after the extension, this will not cause a forgery.
And note that HMAC is proven to be not affected by the collisions of the hash function, even it can be safe for MD5, however, we don't advise, use at least HMAC-SHA256.


What does it mean for an adversary to run in PPT? I've been reading this question where a detailed description of mine is given, I've understood that a polynomial-time adversary is an adversary for which the only feasible strategy are those that take polynomial time to run; anyway, I just can't understand why do we require the adversary to be probabilistic.

In Katz' book is explained that this is natural because the honest parties are required to be probabilistic (in order to generate random keys and so on), actually this isn't very natural for me (the fact that the honest parties are probabilistic shouldn't imply we must consider adversaries to be probabilistic too).

Also, they say that this is useful because the ability to toss coins may provide additional power, and therefore if the scheme is secure against PPT adversaries, then is secure against deterministic polynomial-times adversaries.

Please, someone can explain me why is this a valid argument? Thank you very much!.

An algorithm being probabilistic means that it is allowed to "throw coins", and use the results of the coin throws in its computations. This is reasonable because a realistic adversary has access to certain pseudo-randomness sources (such as the C rand() function). Of course, a probabilistic algorithm is not required to use its randomness source (i.e., throw coins), but even if it were, it could just ignore the results.


Expanding Key Material Is there a way to take key material (for example 256 random bits for an AES key) and "expand" it over to a larger amount of data? Or can I go the opposite way and take a large amount of random data and Xor it down to 256 bits and use that (this looks like secret-sharing, but I do not know if anything changes because the "participants" would all be in the same place)?

I want to store a key, but I don't want it to be just 256 bits since it makes it hard to destroy it on certain types of media. The "key" should be a very large file such that if any portion of it on the media is damaged, the entire key is unable to be retrieved.

Just to be clear, I do not want to have "extra bits" of security. I just want to be able to have 256 bits (or whatever the algorithm is using) of security over a larger amount of storage to make key recovery on the physical storage media harder.

Yes, you could use the HKDF-expand function to expand the bits of the key to a certain size and then use HKDF-extract to derive a key from it again. Note that the resulting key is not identical to the key you've started with. You can use the HKDF-expand again to derive one or more multiple keys with any size from the extracted key material.

HKDF internally uses a hash function (it's a Hash based Key Derivation Function). So it should be fine as long you use SHA-256 or above for 256 bit of input material. The entropy in the output material should be (close to) 256 bits.

Just like a normal hash, you would need all the input data to calculate the correct output, so if only part of the enlarged key gets known you might be still secure, as long as the amount of unknown material is large enough (so brute force attacks are unlikely to succeed).

You can leave the other arguments to HKDF-extract / expand empty if you don't know what to do with them. Using an empty salt seems fine for this kind of purpose.


Build a cipher that is secure against message recovery attack but not semantically secure I know the definitions of both of the securities (against message recovery and semantic), but I don't know how to actually build a cipher that meets these conditions, I mean, I don't know how to define "let $\mathcal{E} = (E,D)$ where $E(k,m) = \;...$ and you can see that it is secury against MR because of ..., but is not semantically secure because of ..." yet.

I would like to know, at least, how to start building such cipher.

Message recovery attack:

Let $\mathcal{E} = (E,D)$ be a cipher. The challenger chooses a random $m$ from message space $\mathcal{M}$, a random $k$ from key space $\mathcal{K}$, computes a random
$c \xleftarrow[]{\text{R}} E(m,k)$ and sends $c$ to the attacker.

The attacker, then, sends $\hat{m}$ back to the challenger.

The attacker wins the game if $\hat{m} = m$. Let $p$ be the probability $Pr[\hat{m} = m]$.

The advantage of this attacker is $\Big\vert \;  p  - \frac{1}{\Vert \mathcal{M} \Vert} \; \Big\vert$

The cipher is secure against MR attack if this advantage is negligible for all efficient attackers.

The basic idea of constructing such a cipher is to exploit the fact (and the main difference between the definitions!) that $m$ is sampled uniformly at random from the message space for message-recovery security and can be chosen very specifically for semantic security.

This means that the easiest solution probably special-cases the encryption output for one specific input and acts securely for all others. The chance of hitting this one special-case is then negligible with message-recovery security, but can be made arbitrarily high with semantic security, allowing the special case encryption to be distinguished from any other encryption.


Is it a good idea to use Lagrange/Newtonian interpolation for encryption? I see that Lagrange interpolation is commonly used for secret sharing, but could it be used for encryption?

The goal is to reduce database I/O and compute new values on the fly. Suppose the use case involves that a client C sends to a server S a message m and a number n that C wants to be appended to m with some encoding. S returns to C the updated message m'. So, over time m becomes a list of numbers. Suppose C must not see the values of those numbers. Would it be a good idea to adopt this approach:

Given a working list of numbers $[e_0,e_1,e_2,\ldots,e_p]$ on S, formulate the equation $y = e_0 + e_1 \times x + e_2 \times x^2 + \ldots + e_p \times x^p$ and compute $p$ points using that equation.
Pick one point and store it in S's database. Encode the remaining $p-1$ points in the message $m'$ and send it to the client C.
When C sends the message back, S decrypts the message by decoding the message and reading the missing point from its database. S applies Lagrange/Newtoian interpolation to retrieve $e_n$.
repeat.

Indeed, the message could just be encrypted, but AFAIK, Lagrange/Newtonian interpolation is $O(n^2)$ (so the proposed decryption is $n^2$) and the encryption part here is only $O(n)$ given that it involves only simple substitutions. In comparison, AFAIK, both encryption and decryption with RSA are $O(n^2)$.

The database will still need to be read each time a message is received (to retrieve the missing number), but I think it's relatively lightweight given that each row only needs to contain two attributes (id and missing_point). In contrast, if every number is to be stored in the database, it'd seem to be rather heavy. Is this approach an overkill? If not, is it sound?

Hopefully my description is clear enough.

I don't think this scheme would make sense, either from a performance or a crypto-design perspective.

From a crypto-design perspective, simply encrypting with a block cipher would be better.  Encrypting with a block cipher, or other suitable symmetric-key encryption scheme, takes running time that is linear in the length of the data to be encrypted (not $O(n^2)$).  You can encrypt data faster than you can send it out over the network.  So, there is no need for such a fancy construction.

From a database performance perspective, I also suspect this won't make sense.  You are not reducing the total amount of I/O; instead of storing data in the database, you are sending it over the network (at least twice, and probably many times).  This seems like a horrible tradeoff.


The logic of preferring PBKDF2 over iterative SHA2 I have studied PBKDF2 for the application of hashing passwords, and frankly I don't understand the justification for the complexity of PBKDF2 over iterative hashing with a cryptographic hash function.

Here is an example: (obviously if you want a longer/shorter hash, choose a longer/shorter digest)

|| - concatenation operator
let password be a user supplied byte sequence
let salt be a random byte sequence supplied by the runtime
let iteration_count be a positive integer in the millions

Algorithm:
iteration = SHA256( salt || password )
for ( 2 to iteration_count )
     iteration = SHA256( iteration )
let hash = final value of iteration
// Store hash, salt and iteration_count

As long as the iterations are tuned to take a target amount of CPU for the security policy, for what purpose justifies using a more complex routine than that?

On my computer with Java, it takes approximately 2 million iterations to fill about 1 second of CPU time to generate the hash.

The biggest advantage to me with this design is, next year when the computer is running faster, I can update my entire user table statically, stretching the iteration count a little further. In fact, if I had a huge operation and performance was going to be a problem, I could run a constant depth extension of the hashes, to wit:

update table USERS set ITERATION_COUNT++, set hash = SHA256( hash )

Besides simply telling me not to roll my own, can some experienced experts please convince me why this security design is poorer than the venerated PBKDF2? Thank you very much in advance. I am eager to learn something new here.

I think you are overstating the complexity of PBKDF2, and also, not matching it feature-wise with your alternative.  Let's dispatch the latter first: as gammatester's comment mentioned, PBKDF2 supports variable output size.  If you built that into your proposal, it would become more complex.

Once we control for that, PBKDF2 is hardly more complex than your iterated SHA-2.  The heart of PBKDF2 is the iterated application of a pseudorandom function (PRF), with the password as its secret key:

$$
F(\mathrm{Password}, \mathrm{Salt}, c, i) = U_1 \oplus U_2 \oplus \dots \oplus U_c
$$

...where:

$$
\begin{align}
U_1 &= PRF(\mathrm{Password}, \mathrm{Salt}\, \|\, \mathrm{INT\_32\_BE}(i)) \\
U_2 &= PRF(\mathrm{Password}, U_1) \\
& \vdots \\
U_c &= PRF(\mathrm{Password}, U_{c-1})
\end{align}
$$

The way that the sequence of values $U_1, \dots, U_c$ is computed is very similar to the way you're proposing to iterate SHA-256, except with the addition that each iteration uses the password as its secret key.  While this isn't necessarily a groundbreaking improvement, it does mean that an attacker who sees an intermediate $U_i$ is not able to pick up from there and compute the rest of the sequence unless they guess the password.  Whereas with your construction, any intermediate value of iteration is sufficient to compute all succeeding ones.

The second difference is that the final value of $F$ is not just $U_c$, but rather the XOR of all the values in the sequence.  This Q&A goes into the motivation of that, and the answers offer several alternative takes.

The third difference is the choice of a PRF as the primitive instead of a hash function like you propose.  This is just conceptually sensible given that we're talking about a scenario where there is a password that plays the role of a secret key; all that PBKDF2 says is that you should iterate a secret-keyed function, using the password as the secret key, and allows for any such choice of function.  The common choice of PRF is HMAC-SHA1, which does make PBKDF2 look a bit complicated if you're missing the observation that it treats its PRF as a black box—it's not concerned at all with HMAC's internal structure.


Alice's forgetful banking Alice has a bank account number, but has forgotten which bank it is for. There are 4 banks, run by Bob, Carlos, David, and Eve.

She could find out by going to all of the banks and asking if they have the account number. However, if Eve learns Alice's account number, then Eve will go to Alice's actual bank and steal all of Alice's money.

Alice could hash the bank account number, and ask about the hash, but since the account number is only 8 digits, Eve could bruteforce the hash anyway. Then, Eve will go to Alice's bank and steal all of her money.

Alice could use a Zero Knowledge Proving Protocol, but how would the bank know which account number to check against without repeating the ZKPP for every account number? Each of them has thousands of customers.

Context: I'm writing a program to retrieve an encrypted copy of one's keys and friends-list for a project called Tox (http://wiki.tox.im/index.php/Proposal:Friendslist_Server). I'd like to make it automatically detect which server has it.

Private Set Intersection

How about a private set intersection protocol?

The banks input is a set of all of their account numbers, the user's input is their account number (a single member set). The output could be given to the user, or the bank, or both, depending on your needs.

You would need a way to protect against guessing account numbers. For example, I could just keep submitting account numbers to one of the banks until I find a valid account at that bank. Or, the bank could put tons, and tons of accounts in their set that they don't actually own with the hopes that your account number will be in there and they can figure out your account.

Both would be fairly easy to protect against if the account numbers are fairly large (say 256 bits) and randomly generated. The probability of success would be greatly limited. You could further limit the bank from submitting overly large sets as I think the size of the set is probably not kept hidden.

Another possibility

Another possibility would be to develop a multiparty set intersection protocol using multiparty computation. Use the paper I linked to as a basis (it only supports 2 parties). That way all parties participate in the protocol at the same time. An MPC framework such as VIFF will be helpful.

The idea is that all banks would input their account databases, the user would input their account number, and you find which set contains the account number and return to the user the ID of that bank. If 2 banks are found to have that account, someone likely falsifying accounts and return $\bot$.


Is a layer of classical encryption plus a layer of post quantum encryption equivalent to a classical/post quantum hybrid? My company builds an encrypted data transfer app that has two layers of encryption.  There is an outer layer of TLS encryption using ECDHE with Curve 25519 that runs between app clients and servers.  There is also an inner layer of encryption that encrypts data end to end between clients using a 1024-bit Diffie-Hellman key agreement (yes we need to replace that)

Our customers are asking for post quantum protection now because of the long term value of the data they want to protect.  Instead of replacing one layer of encryption with a classical/post quantum hybrid scheme (which seems to be popular) we would like to leave the key management for our outer layer TLS protection with Curve 25519 intact and replace the only inner layer key management (the 1024-bit Diffie-Hellman) with a post quantum hybrid scheme like Kyber, New Hope, or SIDH.

Would it be accurate to tell our customers that a layer of classical public key based encryption covering a layer of post quantum public key based encryption is an roughly equivalent to replacing one layer of the encryption with a classical/post quantum hybrid?  We need to replace our inner layer key management anyway and putting in a post quantum solution there would be convenient.

From your description, I am picturing your setup like this:

Outer encryption (server decrypts and re-encrypts):

client1 <----> server <----> client2

Inner encryption (server passed encrypted blobs on)

client1 <----server----> client2

Your question:

  Would it be accurate to tell our customers that a layer of classical public key based encryption covering a layer of post quantum public key based encryption is an roughly equivalent to replacing one layer of the encryption with a classical/post quantum hybrid?

I'm going to go with No. Reasoning: the idea of Classical+PQ schemes was born by considering two separate threat models:

The attacker has a quantum computer.
The attacker knows about a zero-day weakness in Kyber, New Hope, SIDH, wtv PQ crypto you choose. The risk if this is "high" because PQ schemes have not yet had the decades of public scrutiny we would like in a cryptosystem.

The goal of creating hybrids is to couple these two threat models by requiring an attacker to have access to both a quantum computer and a zero-day against the chosen PQ cryptosystem.

Let's see how your proposal stacks up:

An attacker with a quantum computer can successfully man-in-the-middle your classical outer TLS sessions. This doesn't give them access to plaintext messages, but is certainly a partial break of your system, and may have other security implications, for example if any usernames/passwords, or identifying information are sent over this TLS connection.
An attacker with a zero-day against your PQ crypto is not a direct attack, but it becomes a full break if they can compromise the server, or if you are worried about insider threat from your admins.

So it looks like your proposal isn't completely broken, but is certainly not what a customer would expect if you tell them it's a classical/post quantum hybrid, and is a weaker security model then replacing one or both layers with proper hybrid schemes.


Is it possible to fool Miller-Rabin test? It is well known that it's possible to fool Fermat test with Carmichael numbers. But, is it possible to deliberately fool many-rounded Miller-Rabin test by constructing some special number without using brute forcing strategy? I know that one round of Miller-Rabin distinguish with probability 25% that number is prime, but for many rounds brute force will become infeasible.

In fact even brute force does not work, unless you know what random numbers the Miller-Rabin test will use to test the numbers, because in case of each possible non-prime number, some Miller-Rabin test input will reveal it is composite.

FIPS 186-4 C.3 contains recommended Miller-Rabin number of rounds to use to test the numbers. Those amounts of Miller-Rabin tests are expected to catch composite numbers with overwhelmingly large probability. The document contains useful information about Miller-Rabin and how test is supposed to (probabilistically) protect from this attack (fooling it with composite numbers).


Distinguishing Original VS Fake Products Let's assume that we want to distinguish original vs fake products when a customer receives them. I was thinking about using a protocol similar to digital signature.

My question is can this problem be mapped to digital signature?
If not, what other security protocol can we use?

More details:
I was thinking about using the digital signature. Let's assume the original company writes a pair of digital signature and plain text on the product. Then, when customer receives it, (s)he can verifies it using the protocol (you may refer to here (3' 56'') for the protocol), and understands if the item is coming from the original sender or not.
However, the attacker can come in the middle, make a product, and copy the digital signature and the plaintext from original one!

This problem is well defined for supply chain management, and generally you use a challenge-response.  In RFID, you an use asymmetric or symmetric schemes to verify that a product is authentic.  I give RFID as an example because you should be able find a lot of documentation on them.

In the asymmetric case:

A authentic product public key is on the interrogator and the product sends a unique id  (UID).
The interrogator responds with the created signature
The product sends it's signature

In the symmetric case:

The product sends a UID to the interrogator
The interrogator sends a challenge to the product
The product sends a response.

The asymmetric case allows you verify the authenticity of a class of product without a network to know the key for each device.  The symmetric case requires some method to get the key to the interrogator to verify the response because usually the key and the challenge verification are on a server somewhere.

Grab any notes on verifying a supply chain and these schemes will be described in detail.

Update:  An example from NXP.


Is there a problem using Diffie-Hellman over a Mersenne prime? Reductions modulo Mersenne primes are extremely fast, and there are several of a suitable size for modp-based Diffie-Hellman (such as $2^{2281}-1$). Is there any reason such primes are not commonly used for this purpose? Same question also applies to pseudo-Mersenne primes, of the form $2^{n}-c$ for small $c$, which also have fast reductions.

I'm assuming the reason they are not used is that something about the special form allows fast discrete logarithm computations, but I haven't been able to find any references to such an attack.

I'm assuming the reason they are not used is that something about the
  special form allows fast discrete logarithm computations

Yes, the Special Number Field Sieve (SNFS) which is a faster version of the General Number Field Sieve (GNFS). More specifically the best known discrete logarithm computation with the GNFS was with a 768-bit safe prime. The best known result with SNFS is 1039-bit for factoring (which should have comparable work-load as discrete log) and 1024-bit for discrete log (using a specifically crafted prime).

As you can see, while 2048-bit or larger primes aren't feasible with the SNFS either, these primes have a structural weakness, which cryptographers like to avoid. Actually the cost of picking larger primes to defend against SNFS probably would probably far outweigh the gains from the special form and the faster reduction.

  Reductions modulo Mersenne primes are extremely fast

Which is why the "256-bit security" NIST elliptic curve P-521 uses $2^{521}-1$ as the underlying field-prime.

  Same question also applies to pseudo-Mersenne primes, of the form $2^n−c$ for small $c$, which also have fast reductions.

Which was done with Curve25519 which uses $2^{255}-19$ as the underlying field-prime.


DES: How to find the Inverse of the Initial Permutation? I am doing a DES problem by hand and I want to know how you calculate the inverse of the initial permutation. I know what the permutation is, but how do you find it based off the given initial permutation?

The inverse of the Initial Permutation (IP) of DES is the Final Permutation (FP) (in the Standard (NIST FIPS 46-3) FP is called "IP-1").  Number the 64 bits of the input to IP from 1 to 64.  Subject them to IP, so that the 1st 8 bits of the output of IP are bits { 58, 50, 42, 34, 26, 18, 10, 2 } etc. of the input.  Renumber (not reorder) the bits of the output of IP from 1 to 64.  Treat that as the input to FP.


Ciphertext to different plaintext Is there any algorithm for generating the same ciphertext from different plaintexts, depending on the key used? This seems similar to Honey Encryption, but I don't need to have every key give realistic data. I want to specify a set of keys and corresponding plaintext.

For example, "hey" encrypted with key1 and "bye" encrypted with key2 would both become "aaa". Decrypting with key1 and key2 would succeed and return the corresponding plaintext, while decrypting with any other key would fail.

There is one way of doing this using RSA. So if you have n1 = p1 * q1 and also n2 = p2 * q2 and each of them have a key pair pub1, priv1 and pub2, priv2.

Then if you use the Integer group n3 and n3 = n2 * n1 then for every element in the pair (element from Integer group n2; element from Integer group n1) there would be a map to (element from Integer group n3).

This might sound confusing but then something cool happens. Imagine that Bob has a key pair in n1, pub1, priv1 and that Bobby has a key pair in n2, pub2, priv2.

So if you cipher m1 with pub1(using modulo n1) and m2 with pub2(using modulo n2) and then use the map that I said before so that you get an element from n3. (encWithPub1(m1), encWithPub2(m2)) = (cipheredMessages) and cipheredMessages belongs to the Integer Group of n3.

Then if you send this cipheredMessages message to Bob and Bobby. Bob will decipher with priv1 (modulo n1) and get m1. Bobby would decipher with priv2 (modulo n2) and get m2. So by just sending one ciphertext both Bob and Bobby got their respective clear text.

Sorry if this is confusing but i don't know how to write formulas in here...


How exactly is signature verification done in SSH v2 authentication? One of the authentication methods in SSH involves the client signing a message with its private key and sending it to the server for verification.
RFC 4252 (page 9) says:
The value of 'signature' is a signature by the corresponding private
   key over the following data, in the following order:

      string    session identifier
      byte      SSH_MSG_USERAUTH_REQUEST
      string    user name
      string    service name
      string    "publickey"
      boolean   TRUE
      string    public key algorithm name
      string    public key to be used for authentication

The same RFC (page 8) says that all the above information other than the session identifier is passed to the server along with the signature. To verify the signature then, the server would have to recontruct the message (adding the session identifier) and then pass it on to the signature verification algorithm, alongside the received signature and public key.
Is this what happens?

Yes, the server reconstructs the signature pre-image and then verifies that the signature is valid.
From a purely protocol perspective, I think you effectively answered your own question - the protocol defines the format with which the signature is sent to the server and it doesn't contain the session identifier.  On page 1 it mentions:

When this protocol starts, it receives the session identifier from
the lower-level protocol (this is the exchange hash H from the first
key exchange).  The session identifier uniquely identifies this
session and is suitable for signing in order to prove ownership of a
private key.  This protocol also needs to know whether the lower-
level protocol provides confidentiality protection.

This means that not only does the server already have the session identifier, but is specifically using it to connect the communication channel that is being authenticated to the private key.  Since this exchange hash is secret but tied to the current communication channel (as described in RFC 4432), it makes sense to be cautious about sending it unnecessarily.
Regardless, from a protocol perspective this is sufficient evidence that the signature pre-image must be reconstructed.  But for what it's worth, this can also be seen in the OpenSSH source code where the buffer, b, is constructed using a series of sshbuf_put_* operations and then ultimately passed into sshkey_verify.


How to prove identity without revealing identity Let us say Alice publishes a book under the name of Claire. The book becomes wildly popular and now Bob comes along, claiming to be Claire, to reap all the success. How does Alice prove that she wrote the book (and Bob did not) as Claire without revealing that she is Alice? More specifically: what information can she include in her book to be able to later prove this?

I came across "zero-knowledge proof of knowledge" which sounds relevant, but I am not familiar enough with cryptography to understand if this is what I am looking for.

Also, can you point me to any usable implementations of such a scheme?

She can generate a key-pair and include the public key in the book. Having the private counterpart she can at any time proove that she wrote the book by signing an arbitrary statament.


Discrepancy with reported key size for EDE ciphers in Qualys SSL Labs The following two cipher suites were reported by Qualys SSL Labs as being 112-bit:

SSL_CK_DES_192_EDE3_CBC_WITH_MD5
TLS_RSA_WITH_3DES_EDE_CBC_SHA

However, all other references I can find say that they are 168-bit, which aligns with my understanding of 3DES EDE: three independent 56-bit keys.

I trust Qualys to be correct on the matter, and I presume that they have some sort of justification for classifying these suites as 112-bit rather than 168-bit, but I don't know enough about the SSL and TLS implementation of EDE to understand why.

I also have no idea why the CK_DES suite has a 192 in the name.

Are they correct? What's the deal with the discrepancies?

DES has been specified to take a 64 bit key, but only 56 of them are used. The remainder are parity bits.

  The key ostensibly consists of 64 bits; however, only 56 of these are actually used by the algorithm. Eight bits are used solely for checking parity, and are thereafter discarded. Hence the effective key length is 56 bits

For 3DES the nominal key size is $3 \cdot 64 = 192$ bits and $3 \cdot 56 = 168$ of them are used.

The 3DES construction suffers from a meet-in-the-middle attack, which reduces the cost of breaking it to about $2^{112}$ operations, leading to an effective security of 112 bits.


Password-based encryption with small typos allowed I'm trying to write some software to encrypt and decrypt some messages with a password.  I am trying to implement it using this post:  How can I securely convert a "string" password to a key used in AES?

Now, I also want to devise a scheme to allow the user to make small typos when typing in the password, but still be able to decrypt the message even with that small typo.

Is there a way to do this without sacrificing the security of the encryption scheme?

A possible solution:

When encrypting, ask the user to enter a password $p$. Produce a salt $s$. Enumerate the password with all tolerable typos to get array $a$. For each $a_i$, calculate $b_i=hash(a_i)$ to get array $b$. In the output file, write the salt. Generate a random key $k$. And for each $b_i$, write the pair $(hash(b_i||s),b_i\oplus k)$. Write the file to encrypt encrypted with key $k$.

When decrypting, ask user for a password $p_1$. Let $c$ be $hash(p_1)$. If $hash(c||s)$ matches any of $hash(b_i||s)$ in the encrypted file, the key is $k=c\oplus (b_i\oplus k)$. Decrypt the rest of the encrypted file with key $k$.

And you can reduce work when encrypting, but increase work when decrypting by letting array $b$ only contain little or no typos. (If your standard of tolerable typos is having 2 or fewer characters wrong, let $b$ be the array of the password with only 1 character wrong, or let $b$ only contain $p$.) When decrypting, enumerate $p_1$ with typos. If the hash of any of them matches any of $hash(b_i||s)$, it is the right password.


Scrypt not "old enough" to be safe? I just check all the questions with scrypt tag about that and usually it's said that scrypt is nice in theory and theoretically better than bcrypt and PKDF2, but it's too young to be "completely safe".

I understant bcrypt is very old and yet unbroken, but since it uses relatively little amounts of RAM crackers can get around it with specialized hardware. On the other hand, scrypt uses a "lot" more ram (configurable, to a degree) and tries to solve bcrypt's issue of using so little RAM.

So the main question is, if script isn’t "old enough to be safe" – when will scrypt be old enough to be safe for proper use? Maybe even more important: which factors influence “old enough” so that I can tell if and/or when something like scrypt has aged enough to be safe for practical, cryptographic use?

Actually, it turned out that scrypt was not as good as initially advertised under all conditions.

Scrypt was designed to support the specific case of password-based key derivation for full harddisk encryption. Basically, you type your password when the machine boots up (or awakes from hibernation). This is a context where the following apply:

The password processing time can take several seconds, since it is part of a boot-up procedure that will take a lot more time; under such conditions, user's patience is such that 5 seconds of dedicated time is not an unreasonable figure.
While the password is processed, nothing else happens on the machine, so the full CPU can be used for the task, and also the full RAM (so up to gigabytes).

In that context, scrypt totally rules. However, a busy authentication server, e.g. for an active Web server, can be a different beast. In particular, you will probably want to make the per-password CPU cost much lower, not only because there may be several users to handle simultaneously and concurrently with other tasks, but also because the more expensive password hashing is, the more vulnerable you become to basic denial-of-service attacks. For a busy server, a computing time down to 1 millisecond or so would be a more plausible value than the "5 seconds" alluded to above.

When scrypt must run fast, it cannot use as much RAM. In fact, at 1 ms CPU time, it uses so little RAM that GPU-based optimizations become to be worth the effort. In Litecoin, scrypt is used with 128 kBytes of RAM, and GPU implementations can be about 10x faster than CPU implementations (for the same hardware/operating cost), which is technically a function failure. One of the main points of a password hashing function is that attackers with GPU should not gain an advantage over defenders who use "normal" CPU. For fast password-hashing, bcrypt thus turns out to be more secure than scrypt. While scrypt is better than bcrypt when used for what it was designed for.

A further issue with scrypt is that it allows a time-memory trade-off: with more RAM, you can save on CPU, and vice-versa. This kind of flexibility gives some leverage to attackers who try to optimize their effort.

You may want to consult this presentation for some explanations and pointers to further information. The raw conclusion is that while scrypt is reasonably good for what it does, it cannot be said to be a drop-in improvement over bcrypt.

(As a side note, take care that use of a password-hashing function in cryptocurrencies is not the same context as use for protecting passwords in an authentication server. In an authentication server, there is an asymmetrical race between attacker and defender, because the defender uses generic hardware while the attacker can buy special-purpose dedicated hardware. In a cryptocurrency, miners compete against each other and they all buy the same GPU or ASIC anyway, so the 10x GPU speed-up in Litecoin is not a problem for Litecoin; it would be a problem, on the other hand, for an authentication server, where the defender must work with whatever PC he can get from his hosting provider.)

Such things prompted cryptographers to look for better password-hashing functions, and they did so with the usual arrangement: an open competition(*). This resulted in the Password Hashing Competition. The process took a few years and resulted in the choice of a "winner" called Argon2 (along with four other schemes with "special recognition").

The current situation is not ideal in that we now have the choice between:

the old bcrypt, that is reasonably good except against the very serious attackers who think big and use FPGA;
the newer scrypt, which is better than bcrypt in some contexts, but worse in others, and has some extra drawbacks;
the brand-new Argon2, who sustained some rather heavy scrutiny, but only for a limited amount of time, and thus cannot be universally recommended yet.

The bright side here is that the PHC appears to motivate extra research on Argon2, and that is good.

(*) For cryptographers, the most perfect academic process for research is the Thunderdome.


How sensitive to change are elliptic curve formulae In layman's terms? Take for example a curve from a recent question such as #25519:-

$$y^2 = x^3 + 486662x^2 + x$$

It's considered "safe".  What are are the implications of amending it very slightly to:-

$$y^2 = x^3 + 486664x^2 + x$$

I'm trying to get a layman's feel for what this would mean.  For example, is it now entirely invalid and can't be used at all, very easy to break or just a little easier to break? Or does this tiny change suddenly allow specific attacks to come into play?

An elliptic curve equation is very sensitive to any change of its parameters.

That small change result in a complete different curve.
Its security could be good or bad, but you have to check it explicitly and cannot make predictions beforehand.

Specifically, your resulting curve will have a composite order whose largest factor is $833860344743147476600479140946265460420135480673538361531$ which implies your curve's security won't exceed $2^{94.5}$.
I said "won't exceed" because I haven't checked all the other security properties of the curve (twist security, transfers, etc), which could result in a security downgrade.


Can CBC ciphertext be decrypted if the key is known, but the IV not? Let's say that there is a binary file encrypted with AES in CBC mode (i.e. using a key and initialization vector). If key is known, but IV is not, is it easy to fully decrypt the file?

How hard is it?

With CBC (Cipher block chaining) mode, before encryption, each block is XOR-ed with the ciphertext of the previous block, to randomize the input to the block cipher (and avoid encrypting the same block twice with the same key, as this would give the same output, and tell the attacker something about the plaintext).
As the first block has no previous block, here the initialization vector will be used instead.

On decryption, we will apply the block cipher to each ciphertext block, and then XOR the result with the previous ciphertext block (or the initialization vector, for the first block).

As all ciphertext blocks are known, and we have the key, we can reliably decrypt everything other than the first block, even if no or a wrong initialization vector is given.

For the first block, we actually have no information at all, without the initialization vector, other than that it has the same length as any other block (16 bytes for AES): Every 16-bytes plaintext can be reached by supplying the fitting IV. Fortunately (or unfortunately, depending of your point of view), in many file formats the first some bytes are fixed (or almost fixed, or can be guessed based on the rest of the file).

So, with CBC-mode, a secret initialization vector gives almost no protection, if the key is known to the attacker.

This applies generally: Protocols rely on the key being secret, while an initialization vector can usually be public, and often is even transmitted together with the ciphertext.

In CTR mode, a secret initialization vector (there called "nonce") will actually help a bit more to keep the plaintext secret - but if the attacker can guess even one plaintext block (and has the corresponding ciphertext block), he can (given the key) calculate the corresponding counter value, and from this the nonce. Don't let the attacker have the key.