Why do we need to compute message digest of a message first while signing it?

One of the main reasons for hashing is that hashing destroys any algebraic structure that is hidden in the signatures. If you don't hash, then in most signature schemes the messages will satisfy some algebraic relation. A typical example is that

$$Sign(m_1m_2)=P(Sign(m_1),Sign(m_2))$$

meaning that the signature of a product/concatenation/whatever of two messages is a polynomial in the signatures of the individual messages. For RSA, we would have $P(x,y)=xy$. These dependencies can be more complicated and as long as they are efficiently computable, we have problems. What a hash function does, informally speaking, is that in terms of bit strings, $H(m_1),H(m_2)$ and $H(m_1m_2)$ become totally unrelated, therefore it removes any sort of efficiently computable dependency of $H(m_1m_2)$ on $H(m_1)$ and $H(m_2)$.

The point of removing these dependencies is that it prevents us from using previously seen message/signature pairs for forging signatures on new messages. This is what breaks EUF-CMA security. Therefore, hashing is not just an issue of efficiency, but also one of security.

Another issue is of course that the message to be signed needs to be of the proper form before a signature is issued. Since a signature scheme typically operates on elements in some group $G$, there needs to be a function that takes a message $M\in\mathcal{M}$ from the message space and maps it to a group element. Therefore, we need some function $H:\mathcal{M}\to G$ that allows us to transfer messages to a format that we can sign. For RSA we need to take an arbitrary bitstring and then turn it into an integer modulo $N$. The kind of a function that does this in a way you want is precisely a cryptographic hash function.

There is actually a theoretical issue here as well. It's very very hard to build a EUF-CMA secure signature scheme without relying on a hash function (meaning not proving security in the Random Oracle Model). There are some quite efficient structure-preserving signature schemes that are EUF-CMA secure and don't use a hash function, but they rely on the generic group model. To my knowledge, no practical construction is known to date, which only depends on a standard assumption.


If is not possible to reversibly compress a 64-bit RSA key (nor a 64-bit prime) into 10 digits after the fact: there are just too many such keys or primes to assign them a unique 10-digit value. And at this size RSA is totally insecure, I mean breakable in a fraction of a second. Even 640-bit is insecure, see history or factorization records there.
However, that are several ways to use secure parameters for RSA and arrange things such that what's needed to decipher can be remembered as 10 digits (or a short passphrase or sequence of words: that's easier for most humans).

The classical way, used e.g. in PGP/GPG and OpenSSL, is to use a normal RSA key (say, 4096-bit) and encipher it when at rest using password-based encryption, with the 10-digit value used as the passphrase/password. That is symmetric cryptography, with the symmetric key derived from the password (and salt) by a purposely slow hash function, such as Argon2, scrypt…
When the private key is needed, the passphrase-to-key slow hash is run, recovering the symmetric key, then used to decipher the RSA private key (stored in a file, but here that could be in the database). The public key is stored in clear (it's not secret anyway).

A less common option is to generate the primes in the RSA key using a Cryptographically Secure Pseudo-Random Number Generator (CSPRNG) seeded by a key derived as above. When the private key is needed, the passphrase-to-key slow hash is run, recovering the symmetric key, then used to seed the CSPRNG and re-generate the same RSA private key as originally.

The advantage of 2 is that it's impossible to loose the encrypted version of the private key, since none is needed. It's drawback is that it is impossible to change the passphrase, and that we loose the first line of defense against attacks: we normally try to keep the encrypted private key out of reach of attackers.


Does there exist an indistinguishability formal proof obfuscator?

Since you do not give $T$ as an input, the existence of such an $\mathcal{O}$ seems

like it should significant constraints on the is_a_proof_of relation:

For example, if there are proofs P0,P2,P1 and Theorems T0,T1,T2 such that

[for all elements i and j of {0,1,2},  Pi is_a_proof_of Tj  if and only if  i ≠ j ]

then there would have to be a P such that P is a proof of all three of those theorems.

  For the rest of this answer, assume there is a function theor_of_ such that

  for all proofs P and theorems T, if P is a proof of T then  theor_of_(P) = T .

Under that assumption, sure.    For such a function theor_of_, one can

have $\mathcal{O}$ be given by    $\mathcal{O}(P)$  =  lexicographically least proof of theor_of_(P)  .

That $\mathcal{O}$ is in Ptheor_of_[1],NP.

You probably want $\mathcal{O}$ to be efficient, or at least significantly faster than brute force for suitable input lengths, even if NP is hard.  For that requirement, it becomes very significant that

you do not give the security parameter as input
and
you're not relating the lengths of the proofs

.
The distributions thus do not depend on the security parameter, so if they're indistinguishable then they're identical.  Efficiency in particular forces output-length to be not so much longer than input length, so for the resulting distributions to be identical, $\mathcal{O}$ must find a proof which is not so much longer than the shortest proof, regardless of how long its input proof is.

The latter is the much stricter requirement - For example, consider statements of the form "There exists an x such that $\big[\big[$x satisfies $\phi \big]$ or [length(x) = L]$\big]$", and proof systems for which the proofs of such statements are exactly ordered pairs of the statement and such an $x$.

By setting L so that it will be slightly greater than

$\big[\mathcal{O}$'s runtime on proofs of the resulting formula for which $x$ is a satisfying assignment$\big]$ (remember that L is only log(L) bits long) and giving $\mathcal{O}$ a proof with an L-bit $x$, $\mathcal{O}$ must solve $\phi$.

Even for proof systems that are not so insistent on constructiveness, one could try

replacing  length(x) = L  with something else such that $\big[$one also gets a proof but it's

probably hard to find a proof that's not sufficiently longer than assignments to $\phi \big]$.

Even if you [give the security parameter as an input] and [only require indistinguishability against uniform adversaries that must choose equal-length proofs], such an $\mathcal{O}$ for a

similarly-constructive proof system would suffice for inverting candidate one-way functions with probability greater than 1/3  -  Just run it on proofs that give r for statements

"There exists an x such that f(x) is in {$\hspace{.02 in}$y,z}.", where a random one of

of y,z is the target image, the other of them is f(r), and r is chosen

uniformly from strings with length equal to the security parameter.

Thus, if one-way functions exist then for a feasible such $\mathcal{O}$ to exist,

the proof system must not be feasibly constructive.

Now, I'll finally give the positive results:

As warmup, if there is an efficient non-interactive witness-indistinguishable proof system

NIWIP for SAT with deterministic verifier, then for axiomatic systems S such that

a theor_of_ function, as described near the top of this answer, is efficiently computable
and
the proof system includes arithmetic and

[can prove enough about its own provability predicate]
and
there is a poly(k,M)-time algorithm for finding a proof in  S + Con(S)  that

NIWIP with security parameter k is sound for statements of length at most M

then there is an efficient $\mathcal{O}$ that takes as input

the security parameter, in unary
and
a length bound L, in unary
and
a proof in S of a $\Pi_1$ formula

and outputs a proof in  S + Con(S)  of the same $\Pi_1$ formula,

such that the desired indistinguishability will hold when

the security parameters are equal
and
the length bounds are equal
and
the proofs both satisfy the length bound

.
Furthermore, if NIWIP's indistinguishability is perfect,

then $\mathcal{O}$ does not need the security parameter.

(In either case, use NIWIP on the existence of a proof of length at most L, prove the relevant

soundness property of NIWIP to deduce the existence of a proof in S of the $\Pi_1$ formula, and

then use Con(S) and [provable-in-S facts about being provable-in-S] to deduce the $\Pi_1$ formula.)

It's finally time for the full result.  For axiomatic systems S0 such that

a theor_of_ function, as described near the top of this answer, is efficiently computable
and
the proof system includes arithmetic and

[can prove enough about its own provability predicate]

,    with the axiomatic systems  S1,S2,S3,S4,...,S$_{\infty}$  given by

Sn+1 is Sn plus [the schema with one axiom per wff p, where those

axioms are padded (for example, by ANDing with 0=0) to each be longer

than n bits, and otherwise just assert "if p is provable in Sn then p"]
and
S$_{\infty}$  =  S0 + S1 + S2 + S3 + S4 + ...

, if there is $\big[$an efficient non-interactive witness-indistinguishable proof system NIWIP for SAT with deterministic verifier$\big]$ and $\big[$a poly(k,M)-time algorithm for finding a proof in S$_{\infty}$

that NIWIP with security parameter k is sound for statements of length at most M$\big]$,

then then there is an efficient $\mathcal{O}$ that takes as input

the security parameter, in unary
and
a length bound L, in unary
and
a proof in S$_{\infty}$

and outputs a proof, also in S$_{\infty}$, of the same formula,

such that the desired indistinguishability will hold when

the security parameters are equal
and
the length bounds are equal
and
the proofs both satisfy the length bounds

.
As before, if NIWIP's indistinguishability is perfect,

then $\mathcal{O}$ does not need the security parameter.

(In either case, work as follows:    Proofs in S$_{\infty}$ of length at most L cannot use axioms that aren't in SL, so use NIWIP on the existence of a proof in S$_{\infty}$.  From there, prove the relevant soundness property of NIWIP to deduce the existence of a proof in SL of the relevant formula, and then use the relevant axiom from SL+1 to deduce the relevant formula itself.)

I'm not aware of any candidates for that which Shor's algorithm won't break.


Well, if you absolutely had to do a MITM attack, I suppose one could look like:

Rewrite the equation as:

$$x  - x'_{low} = 2^h + 2^{k/2}x'_{high}$$

where $x' = 2^{k/2}x'_{high} + x'_{low}$ and $0 \le x'_{low}, x'_{high} < 2^{k/2}$

For each $x'_{low}$ value in the range, compute $x - x'_{low}$ and place it in a list.
For each $x'_{high}$ value in the range, compute $2^h + 2^{k/2}x'_{high}$ and place it in a list.
Flip the order of the first list (normally, you're supposed to sort them; these are already in sorted order), and then scan through the two lists, and look for a value in common.

Yes, this is a silly way to do it; however it is a Man-in-the-Middle attack of the specified complexity; this might be the answer they're looking for...


Why is Diffie-Hellman considered in the context of public key cryptography?

The Diffie-Hellman key exchange is a public-key technology. It is (by itself) not an encryption algorithm (or signature algorithm), though.

Here is the basic function: (All calculations here happen in a discrete group of sufficient size, where the Diffie-Hellman problem is considered hard, usually the multiplicative group modulo a big prime (for classical DH) or an elliptic curve group (for ECDH).)

Each party choses a private key $x$ or $y$
Each party calculates the corresponding public key $g^x$ or $g^y$.
Each party sends the public key $g^x$ or $g^y$ to the other party.
Each party uses the received public key together with its own private key to calculate the new shared secret $(g^y)^x = (g^x)^y$.

The result of this key exchange is a shared secret, which is usually then used with a key derivation function (using other input known to both parties, such as a session ID) to derive a set of keys for a symmetric encryption scheme and MAC keys, if we aren't using an encryption scheme with integrated authentication. If we are building a bidirectional channel (like in TLS/SSL or SSH), we derive different keys for both communication directions.

This might be what causes confusion: it is an asymmetric technology used to negotiate symmetric keys. But the same is valid for most other asymmetric technologies, like signature or encryption algorithms: At the core there is something asymmetric, but then we use a symmetric algorithm to do the bulk of the work. For example, with most asymmetric encryption algorithms we usually encrypt just a symmetric key for the actual message, with most signature algorithms we first hash a message, then asymmetrically sign the hash.

The values $g^y$ or $g^x$ are named public keys, because they can be transmitted in plain, so anyone listening on the connection knows it.
The values $x$ and $y$ never leave the choosers computer, so they stay private. $(x, g^x)$ and $(y, g^y)$ are the private-public key pairs here. Incidentally, these are the same types of keys as in DSA or ElGamal.

One could have long-term key pairs (and then the public key could even already be in some address book, saving the transmission, or be signed with some certificate), but more usually these key pairs are created on the fly for each connection.

When combining the Diffie-Hellman key exchange (with a long term public key of the receiver) with a symmetric encryption scheme, we get a nice public-key encryption scheme – actually one of the first ones to be proposed at all. It works like this:

The receiver has a private key $x$ and a corresponding public key $g^x$.
The sender somehow securely obtains the public key $g^x$.
The sender choses a temporary private key $y$ and calculates the corresponding public key $g^y$.
The sender calculates $(g^x)^y$ and derives from this a symmetric key $K = f((g^x)^y)$.
The sender encrypts his message: $C = E_K(P)$.
The sender sends $(g^y, C)$ to the receiver.
The receiver gets $(g^y, C)$.
The receiver calculates $(g^y)^x$ and derives from this $K = f((g^y)^x)$. This is the same $K$ as before.
The receiver decrypts the message: $P = D_K(C)$.

This is an asymmetric encryption scheme – to encrypt, the sender needs to know only $g^x$, while for decryption $x$ itself is needed.


Direct Anonymous Attestation to replace CA

I briefly went through the paper - and interesting article you found. Though I see some gaps and assumptions. If someone understands it better, please feel free to comment or improve. So - in Layman's terms (how I understood it):

Once a subject could prove its identity, its identity (attributes, certificate) is written in a blockchain ladder (and assumed it is difficult to falsify).  The identity proof is not explicitly stated, but control over a domain admin addresses are mentioned several times.

What is not explicitly written (and I consider that as assumed knowledge) what would be the blockchain quorum confirming each transaction. In simple terms (very simplified) - it would need mutiple participant to confirm that the identity is ok. Every blockchain participant would become partial CA.

The idea looks good but I see a few issues (at least what I immediately see, unrelated to the math):

it is not related to the paper itself, but more to the blockchain ladder properties. If an organization would be able to take over the blockchain (having more participants, more computing power, ...) the trust would be completely broken. The benefic (and thus incentive) for malitious behaviour would be enormous.
current CA issued certificates have legal value in many countries (the CAs are not only used for validating domain names) for authentication and signing. That would not work with schema where institutions are unable to enforce legal control.


How CL-signature can act as positive & additive accumulator?

Any signature scheme can work as an accumulator: when elements are signed with the manager's secret key, signature works as a system membership witness (positive acc). It is also additive because you can only add elements in the system by signing them, you cannot cancel a signature in the future (to delete them).


In $\mathbb Z/p\mathbb Z$, is $(a+b\cdot r)$ a random value for fixed $a,b$ and random $r$?

Yes. For fixed $a\in\mathbb Z/n\mathbb Z$ and $b\in(\mathbb Z/n\mathbb Z)^\ast$ — note that $b$ must be invertible modulo $n$, which need not necessarily be a prime (but if it is, invertibility is equivalent to $b\neq0$), the map
$$ f\colon\;\mathbb Z/n\mathbb Z\to\mathbb Z/n\mathbb Z,\; r \mapsto a+br $$
is a bijection, hence it preserves uniform distribution. That is: If $R\colon\;\Omega\to\mathbb Z/n\mathbb Z$ is a uniformly distributed random variable, then $f(R)\colon\Omega\to\mathbb Z/n\mathbb Z$ is as well.

The direct argument is: If $\forall y\in\mathbb Z/n\mathbb Z.\;\Pr[R=y]=1/n$, then for any $x\in\mathbb Z/n\mathbb Z$,
$$ \Pr[f(R)=x] = \Pr[a+bR=x] = \Pr[R=b^{-1}(x-a)] = 1/n \text, $$
therefore $f(R)$ is uniformly distributed on $\mathbb Z/n\mathbb Z$.


Brute Force on 3DES with Reduced Keyspace and Unknown IV

My first thought was that I could set the IV to the first 8 bytes of the CT [and] decode the rest[.]

This is exactly how CBC works.

For all blocks but the first, encryption is defined by $C_n=E_K(C_{n-1}\oplus P_n)$ and, therefore, decryption is achieved by $P_n=C_{n-1}\oplus D_K(C_n)$.

Since there is no previous ciphertext for the first plaintext block ($P_0$), we just set $C_{-1}=IV$. So, yes, considering the first ciphertext block the IV will allow you to decrypt all remaining ciphertext blocks.

  [T]hen substitute back to find the IV.

That part is not that easy. The first block of plaintext is $P_0=IV\oplus D_K(C_0)$. If both IV and plaintext are actual text, there might be hope, although 8 bytes of text probably won't be sufficient for the standard tools (e.g., frequency analysis).

If the IV has been generated pseudo-randomly, it effectively acts as a one-time pad. This means that, unless you can deduce the first 8 bytes of plaintext from the remaining plaintext anyway, there's nothing you can do.


Are there any MGF1 and OS2IP functions available in C?

You can find MGF1 in OpenSSL. Source file "crypto/rsa/rsa_oaep.c" has a function called "PKCS1_MGF1" that implements MGF1. The function signature is:

int PKCS1_MGF1(unsigned char *mask, long len, const unsigned char *seed, long seedlen, const EVP_MD *dgst)

See the wrapper function "MGF1" defined right below it for a more general case of using it.

As for OS2IP, I don't see an explicit method for converting to/from it in OpenSSL, presumably because the integers start and end in that format, so they never convert them.

OS2IP and I2OSP are a pair of straight-forward methods of encoding and decoding a large number to an octet string. The idea for OS2IP is that you simply represent the integer in big endian byte order. How you would use OS2IP to encode an integer depends entirely on how the integer is original represented before conversion.

The bottom line for OS2IP/I2OSP is that it's more a function of your original integer than a function of RSA. Find a way to convert the original integer to/from a big endian byte string, either by using a "toBigEndian" / "fromBigEndian" type function for your original integer or by making one manually. I don't think you'll find a generic method anywhere.

To do it manually: If you understand how the original integer format works, you can manually convert bytes to/from the original format and the octet string. If you can do multiplication, division, addition, and subtraction on the original integer, you can just calculate the octet stream manually with a few lines of code and a loop using the OS2IP description.


Does google's Crypto.JS AES encryption use PBKDF2 as default?

The documentation says it's OpenSSL, not PBKDF2:

  When you use a CipherParams object in a string context, it's automatically converted to a string according to a format strategy. The default is an OpenSSL-compatible format

This can be verified in the source code. The implementation of the OpenSSL KDF is in evpkdf.js.

The key derivation function is usually referenced as EVP_BytesToKey which is the higher level function in the API that implements the KDF.


Entropy of system data - use all and hash, or trim least significant bits?

What you are doing sounds a lot like what the /dev/random and /dev/urandom or the PRNGD on many systems already do:
those systems take an arbitrary large sequence of numbers (from a true hardware random number generator if available, or else from environmental noise such as keystroke timing)
and feed it into a CSPRNG.
The CSPRNG internally maintains an "entropy pool",
and thoroughly "mixes" the pool whenever it produces a new output value.
The output is made available via /dev/random and /dev/urandom .

Have you considered possibly using the /dev/random or PRNGD already running and available on your system?
Have you considered possibly downloading the source code to some CSPRNG that has already been written, tested, debugged, and checked for security flaws, rather than writing your own from scratch?

At the moment, I'm just globbing all the data into an array of around 100 bytes. I then hash the array using SHA512, to add a total of 64 bytes to the entropy pool
Would I be better off extracting the least significant bits of each statistic into a bitstream?

Rather than collecting a batch of data, hashing it, and then feeding that into the CSPRNG,
it's better to simply feed the batch of data directly onto the CSPRNG.
(The CSPRNG already handles the "hashing" stuff internally).
At best, your hash operation preserves whatever entropy exists in the source data;
at worst, it is unnecessarily throwing away some of that entropy.
SHA512 is an excellent hash function, so hashing the incoming data with SHA512 is OK but unnecessary.
(The idea of "XOR all the collected bits" seems to throw away too much entropy).
The high-order bits of most of those statistics have very little usable entropy -- however, assuming the CSPRNG is properly written, that doesn't hurt anything.
A properly written CSPRNG is just as secure even when one of the inputs doesn't have any entropy -- such as an input that is always "000000000000000...".
If, hypothetically, you are forced to cut back on the number of inputs to your CSPRNG in order for some reason,
you would want to preserve as much entropy as possibly by cutting out such zero-entropy (all-zeroes) and low-entropy (high-order bits of these other stats) before cutting out higher-entropy sources.

When the pool reaches 64KB...

Wow. That many bits in the entropy pool is overkill in our universe.

Keys are generated by computing a cryptographic hash of the entire entropy pool.

Yes, that's how most CSPRNG produce their output values.

FreeBSD and AIX implement /dev/random using the Yarrow algorithm
OpenBSD implements /dev/random using an algorithm based on RC4 (is this the same as ISAAC ?)
Fortuna
My understanding is that many other CSPRNG implementations have a way to feed in more bits of entropy.

(I'm re-using a lightly edited of a previous answer I wrote,
PRNG taking advantage of very large seed
)


Is PKCS#7 padding generated with a pseudo-random-number generator okay?

If the intent of the padding is to make a passive attacker learn only a range instead of the exact message length, do not use real_len + rand(max_padlen).
It is more efficient to make the length of the padded message a multiple of a given block size instead.

If your protocol has enough latitude to allow large variations of the padding length, you can use a randomized length, but watch out for replay attacks. If for a given question, the same response is always sent, the question can be sent multiple times, so that the actual response length can be eventually inferred.
In order to mitigate this, the padding length should always be the same for a given question. A simple PRF can be used to achieve this.


Searching for a differential characteristic (differential cryptanalysis)

Finding differential characteristic means analyzing the structure of the given cipher(substitution and permutation elements). This analyzing means, we should track the input differentials(Δi) through the different elements of the cipher  and produce related output differential(Δo).

Δx = X' xor X'' =>

                Δx=[ΔX1,ΔX2,ΔX3,....ΔXn]

                 =[X'1 xor X''1, X'2 xor X''2, X'3 xor X''3,...,X'n xor X''n]

We repeat this to round - 1. Each of these paths are called "Differential characteristic" and each of them has its own happening chance(probability).

As mentioned, in the paces of tracking Δi to Δo, we should consider that cipher structure is made of different confusion and diffusion elements which these elements effect the path in each round and leads to activating some SBoxes(called Active SBoxes). But the most important factor is finding the probability of each differential path(differential characteristic) and choosing the highest one(or ones) among them. The rout with the highest probability is the objection of the analyzer.

In order to find these differential characteristics we can use one of these three methods( It is general recommendation but not exact!!!):

choose each differential characteristic in the cipher structure visually and calculate probability for them. However we should mention that this method is not applicable for the most variety of ciphers in that the number of input to the cipher is big( at least 16 bit) and if we want to have a precise estimation of differential status of the cipher,nearly we should test 2^16 input differentials and calculate the probability for each round. In the most situations this way is impossible.
** Use Sage S-box MILP toolkit ** which is developed and intended to calculate the differential characteristics for well-known block ciphers which have Substitution and permutation structure in them. This toolkit can be found in: http://www.swmath.org/?term=differential%20cryptanalysis and in this paper: https://www.esat.kuleuven.be/cosic/publications/article-2080.pdf the way of using them is explained.(I should remark that in the given toolkit, you should make some modifications in order to use them like changing the "coin solver"). This method is a very good way to finding the number of active SBoxes and calculating the differential characteristic of the cipher.

-Implementation on our own code in order to find the differential characteristics with the highest probability among all input differentials. It is not hard and possible. We firstly should define all input differentials (states) and then calculate the probability of each state by considering these two factors:

          -Each SBox has differential property and should  affect in
           each round in the differential characteristic when it is
           activated.

          -Multiply calculated probabilities by the prior probability in
           order to finding  rounds differential characteristics.

A good reference: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf

But I should mention that finding differential characteristic for Feistel structures have a different story and a good reference is in:
http://www.cs.haifa.ac.il/~orrd/BlockCipherSeminar/Lecture2-Differential.pdf


Purpose of expanding then shrinking in SHA-1

Expanding then shrinking in SHA-1 refers to the process, performed for each round (each 512-bit block of padded message), of

message expansion from 512 bits to 2560 bits;
keeping only 160 bits of state for the next round.

The later directly follows from the construction of SHA-1 as a Merkle-Damgård hash of 160 bit. The former occurs because SHA-1's compression function is built from a block cipher using the Davies-Meyer construction, that is with the message entering the block cipher's (512-bit) key input; and, as most block ciphers do, the particular block cipher used in SHA-1 uses a key schedule, expanding the key to 80 subkeys (each 32-bit), one per round.

The expanding in SHA-1 is thus the key schedule of its block cipher, and is there to make SHA-1's internal block cipher secure, making SHA-1's compression function collision-resistant, making SHA-1 collision-resistant.

As an illustration that the key schedule/expansion plays a security role, the short-lived SHA (now known by the retronym SHA-0) differs from SHA-1 by a weaker key schedule (with one less word rotation), and is more badly broken than SHA-1 is (in particular, by  Yusuke Naito, Yu Sasaki, Takeshi Shimoyama, Jun Yajima, Noboru Kunihiro, Kazuo Ohta: Improved Collision Search for SHA-0, in proceedings of ASIACRYPT 2006).


How is an AES Encrypted Message Decrypted with Random Padding?

What are the properties of random padding (and I realize there are different ways to do it but I'm looking for an illustrative example) that allow it to be reliably removed from the message?

You can do random padding with AES, but you'd have to reserve say the very last byte to tell how many bytes of padding were added.

For example, for a 4 byte blocksize cipher, say your message is 04 (in hex). To make it 4 bytes we need to add three bytes, so we add two bytes of random padding, then one byte 02. So what would really be fed into the block cipher would be 04 ac 92 02. The recipient needs to know that this scheme is being used. They would then read the last byte and know that two bytes of random padding were added. Those bytes would be removed and the final message 04 would be returned.

I believe most people using AES do not use random padding though. Deterministic methods are just as secure. RSA, however, needs random padding for security.

  Is it true that in order to decrypt the message you must have information about the padding scheme in addition to the secret?

Yes. Otherwise it would be impossible to strip off the padding. This information does not need to be secret and can thus be specified in a protocol field or upon handshake.


What is the largest bit RSA encryption to be cracked?

TL;DR:
This is not the same kind of attacks. You cannot compare factoring and side channel.

All unfactored parts of the numbers $2^n  − 1$ with $n$ between 1000 and 1200 were factored by a multiple-number-sieve approach in which much of the sieving step could be done simultaneously for multiple numbers, by a group including T. Kleinjung, J. Bos and A. K. Lenstra, [...] n=1199 on December 11, 2014

source

The paper of this attack is RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis by Daniel Genkin, Adi Shamir and Eran Tromer. Given the quality of the article and the names of the researcher, it is really hard to doubt the paper content. But be wary that press tend to make things worse than they actually are. e.g. a year ago, we had a paper on Freestart collision for full SHA-1, immediate press emphasis: SHA-1 is broken, we have a collision!
In the paper you can read:

Modern RSA security standards mandate key sizes of at
least $2048$ bits (i.e., $1024$ bit primes $p$;$q$) in order to achieve adequate levels of security [BBB+12]. For concreteness, in the following we consider even larger keys, of size 4096 bit (and 2048-bit primes), which
should be secure beyond the year 2031 [BBB+12]. We show an attack that can extract whole 4096-bit RSA keys within about one hour using just the acoustic emanations from the target machine.

The choice of the size of the 4096 bit number is more as a Proof of Concept that it is possible to do it with big number. You could assume that they can even do it with 8192 bit keys...
What you must show in your talk, is that even if this 4092 key has been broken, it is not the same kind of attacks. Here we are in the case of a physical attack rather than a factorization attack. It is the same as comparing side-channel attacks on AES as opposed to the usual cryptanalysis.
I suggest you have a look at the RSA challenge and Integer factorization records.
Some graph you might also be interested in:

Also related:

Why has the RSA factoring challenge been withdrawn?
How big an RSA key is considered secure today?


"Serial concatenation" is not a standard term in cryptography.  Without any further information, I would guess that it probably refers to just concatenation.  If that's not what it refers to, then your spec is deficient and ambiguous; you'll need to consult with the author of the spec to ask for to clarify what they meant by that phrase.


How big an RSA key is considered secure today?

Since 2000, on a given $\text{year}$, no RSA key bigger than $(\text{year} - 2000) \cdot 32 + 512$ bits has been openly factored other than by exploitation of a flaw of the key generator (a pitfall observed in poorly implemented devices including Smart Cards). This linear estimate of academic factoring progress should not be used for choosing a key length so as to be safe from attacks with high confidence (or, equivalently, conforming to standards with that aim), a goal best served by this website on keylength.
The current factoring record is the 829-bit RSA-250 in late Feb. 2020, see the summary by the CADO-NFS team. That came shortly after the 795-bit RSA-240 in Dec. 2019, see the detailed paper.
I emphasize that the above is about attacks actually performed by academics. As far as we know, hackers have always been some years behind (see below). On the other hand, it is very conceivable that well-funded government agencies are many years ahead in the factoring game. They have the hardware and CPU time. And there are so many 1024-bit keys around that it is likely a worthwhile technique to be in a position to break these. It is one of the few credible and conjectured explanations for claims of a cryptanalytic breakthrough by the NSA. Also, dedicated hardware could change the picture someday; e.g. as outlined by Daniel Bernstein and Tanja Lange: Batch NFS (in proceedings of SAC 2014; also in Cryptology ePrint Archive, November 2014). Or in the distant future, quantum computers usable for cryptanalysis.
By 2020, the main practical threat to systems still using 1024-bit RSA to protect commercial assets often is not factorization of a public modulus; but rather, penetration of the IT infrastructure by other means, such as hacking, and trust in digital certificates issued to entities that should not be trusted. With 2048 bits or more we are safe from that factorization threat for perhaps two decades, with fair (but not absolute) confidence.
Factorization progress is best shown on a graph (to get at the raw data e.g. to make a better graph, edit this answer)

This also shows the linear approximation at the beginning of this answer, which actually is a conjecture at even odds for the [2000-2016] period that I made privately circa 2002 in the context of deciding if the European Digital Tachograph project should be postponed to upgrade its 1024-bit RSA crypto (still widely used today). I committed it publicly in 2004 (in French). Also pictured are the three single events that I know of hostile factorization of an RSA key (other than copycats of these events, or exploitation of flawed key generator):

The Blacknet PGP Key in 1995. Alec Muffett, Paul Leyland, Arjen Lenstra, and Jim Gillogly covertly factored a 384-bit RSA key that was used to PGP-encipher "the BlackNet message" spammed over many Usenet newsgroup. There was no monetary loss.

The French "YesCard" circa 1998. An individual factored the 321-bit key then used (even though it was clearly much too short) in issuer certificates for French debit/credit bank Smart Cards. By proxy of a lawyer, he contacted the card issuing authority, trying to monetize his work. In order to prove his point, he made a handful of counterfeit Smart Cards and actually used them in metro tickets vending machine(s). He was caught and got a 10 months suspended sentence (judgment in French). In 2000 the factorization of the same key was posted (in French) and soon after, counterfeit Smart Cards burgeoned. These worked with any PIN, hence the name YesCard (in French) (other account in English). For a while, they caused some monetary loss in vending machines.

The TI-83 Plus OS Signing Key in 2009. An individual factored the 512-bit key used to sign downloadable firmware in this calculator, easing installation of custom OS, thus making him a hero among enthusiasts of the machine. There was no direct monetary loss, but the manufacturer was apparently less than amused. Following that, many 512-bit keys (including those of other calculators) have been factored.

Note: 512-bit RSA was no longer providing substantial security by 2000-2005. Despite that, reportedly, certificates with this key size were issued until 2011 by official Certification Authorities and used to sign malware, possibly by means of a hostile factorization.


Differences between using HMAC-SHA1 vs HMAC-SHA256 for data storage?

In a protocol like SSL, if it gets broken tomorrow, we can “simply” turn off all the cipher-suites that use HMAC-SHA1. But what if it is used as MAC protection for encrypted data storage?

This isn't as big a problem as it may seem at first. Even with old data it can still be possible to upgrade the MAC later if you find out about a possible attack, as user4982 mentioned in a comment. Furthermore, the most likely attacks against a MAC would be the ones where the attacker would be able to use an "oracle" to MAC arbitrary messages, which may not exist in practice with data at rest (but is more likely with an interactive protocol).

  Would using HMAC-SHA256 help in that case?

  To be more precise: Is HMAC-SHA256 likely to be much more difficult to break compared to HMAC-SHA1 and are both HMAC-SHA1 and HMAC-SHA256 likely to be broken in the near future?

I would recommend, as in the linked question, using HMAC-SHA256 for new applications. I don't find it likely that either will be broken any time soon, but breaking HMAC with SHA-256 which is still collision resistant is even less likely than with SHA-1, so there is more of a security margin.

However, when designing a long term data storage system, the main thing to keep in mind is making sure that any algorithms are replaceable if they get too weak. I.e. make it possible to transition from whichever MAC is chosen to a stronger one and similarly for ciphers and such. (In an incremental fashion, if keys are held by third parties.)


Are there hash algorithms with variable length output?

Sure.  If you want a $b$-bit hash of the message $m$, then use the first $b$ bits of AES-CTR(SHA256($m$)).  That'll do the trick.

In other words, compute SHA256($m$) and treat the resulting 256-bit string as a 256-bit AES key.  Next, use AES in counter mode (with this key) to generate an unending stream of pseudorandom bits.  Take the first $b$ bits from this stream, and call it your hash.  (Make sure you don't treat the IV as part of this stream, as the IV won't be pseudorandom.  You may need to manually remove the IV first before taking the first $b$ bits.)

Security. This should be secure as long as $b \ge 160$ or so.  In particular, a collision attack is expected to take about $2^{\min(b,256)/2}$ steps of computation, given our current knowledge of AES and SHA256.  So, as long as you don't choose a value of $b$ that is too small, you should be good.  Choosing a value of $b$ larger than 256 does not give you greater security against collisions, but that's irrelevant: the level of security will already be way more than enough for any reasonable application, so you're good.


What key exchange protocols give Forward-Secrecy resisting future progress?

To make key exchange protocols (providing perfect forward-secrecy) robust against quantum computers they need to rely on assumptions that are not susceptible to quantum attacks (post-quantum crypto) like hash based, lattice based or multivariate-quadratic-equations based.

Clearly, quantum key distribution is a candidate for key exchange with all the associated problems.

pqcrypto.org provides a quite updated reference to post-quantum research. It looks like the key exchange issue and in particular perfect forward-secrecy has not really seen much research so far.

At least the paper Smooth projective hashing and password-based authenticated key exchange from lattices provides a construction of an password-based authenticated key exchange for the post-quantum world.

Subsequently, I comment on the below cited part of the question and I only speak of protocols where we use hardness assumptions which do not longer hold in the advent of a quantum computer below.

  ...insuring that an intercept made at a date when the assumption of hardness underlying the asymmetric protocol holds, can't help recovering the ephemeral symmetric key established even after said assumption of hardness no longer holds.

We speak here of key-exchange/key-agreement protocols which allow to parties to compute a common secret over some
public channel where this common ephemeral secret may then be used to compute some common symmetric session key.

Perfect forward-secrecy in the key-exchange context typically means that both parties have some long term-key and on every session they
run some key-agreement to compute a common session key, but the compromise of long-term keys does not compromise the
secrecy of any past sessions.

In order to compute a session key there happens a key-agreement protocol (typically, the long term-keys will
be used to sign the respective ephemeral information of the key-agreement sent by the respective party), where the ephemeral information exchanged to compute the common
key do not deterministically depend on the long-term keys if perfect forward secrecy is provided. Anyways, there always
simply happens a key-agreement irrespective of the perfect
forward-secrecy feature or not.

So if the security of the key-agreement is based on some hardness assumptions $P_1,\ldots,P_n$, it does not make a difference if you consider
key-agreement protocols that provide perfect forward-secrecy or not. If the $P_i$'s do no longer hold, e.g., if we
have a fancy quantum computer, then the transcript of any key-agreement will allow you to recover the respective session key.

Perfect forward-secrecy is concerned with compromise of the long-term secrets (such as private keys for static DH keys), but not
with breaking the hardness assumptions when given the transcript of a key-agreement (clearly, because the key-agreement
only makes sense if the hardness assumption holds).


KDFs can be used for both: key update and re-keying.
As a KDF is usually a Function like this: $KDF(Secret,DerivationParams)$, you can use it to derive keys from old keys (key-update) but you can also use it for re-keying as nothing prevents you from setting a new secret (by the means of the KDF). As there are some KDF that look like this: $KDF(Secret,Salt,Params)$ you can even do a hybrid thing, where you depend on your old key and add new entropy to the new key.


Pairing - Is it possible to map two $r$-torsion points to a $r^2$-torsion point?

No, it is not possible.

By the definition of bilinearity, we have $e( kG, H ) = k \cdot e( G, H )$.  If the order of $G$ is $r$ (that is, $rG = 0$, we have $e( rG, H ) = e( 0, H ) = r \cdot e(G, H)$.  We know $e(0, H) = 0$ (as bilinear functions maps the identity to the identity), and hence we have $r \cdot e(G, H) = 0$; that is, the order of $e(G, H)$ must be either $r$, or some divisor of $r$.


Asymmetric algorithm with indefinite number of public keys

Using tricks

As said by Natanael in his comment to your question: this is maybe possible when using elliptic curve cryptography, and is actually kind of used in Bitcoin to have the so-called "hierarchical deterministic wallets". If you want a rough idea of how this kind of child key derivation works, I refer you to this answer.

While it might also be possible to tweak RSA in order to do it, RSA is considered relatively brittle and I'll avoid venturing into modifying it today. (Maybe another day ;))

The same idea as the one used for ECDSA signatures should be easy to transpose to ECIES.
But please, notice that having multiple public keys might not necessarily help you achieve whatever security goals you have, and without knowing these, my answer might be misleading you! So, please think hard about what kind of security guarantees you'd like to have and double check you're actually going to reach them using any derivation scheme one might present you.

Also, notice the caveat: in the child-key derivation discussed in the linked answer, knowledge of $r$ allows one to compute the "main" public key $ P_k$...
And when Alice is sending Bob her encrypted message, if she wants Bob to derive the right private key, she needs to send him $r$ along with her ciphertext.

Using an established scheme

There is actually a scheme which is doing almost what you're asking already, and that's namely ECIES, because when using ECIES, Alice is computing a "shared secret key" from Bob's public key $P = g^x$ by picking a random $y$ and computing $P^y = g^{xy}$, but Alice only needs to send Bob $g^y$ along with the ciphertext encrypted using $g^{xy}$.

Notice that ECIES is just kind of using Diffie-Hellman to agree on a shared secret key to encrypt stuff. But it works.

To address all of your points

You want to:

  Decrypt/verify data signed with single private key by using any of
  public keys

For the "verification" part, this is entirely covered by BIP-32, and it definitively possible and used in practice in Bitcoin and many cryptocurrencies.
For the "decryption" part, it depends really on what you really want to be able to do. You might simply use ECIES, and then you'll be using "fresh keys" only Bob and Alice can recompute to encrypt your data. You might try to do other things...

  Encrypt data using any of public keys and decrypt with single private key

This seems difficult, without having some kind of "hidden key negotiation" à la ECIES, because for most "straight forward" schemes it might mean one would have a mean to decrypt stuff sent to any public key... Which is obviously not the goal.

  Probably also same stuff vice versa (multiple private keys, single public key)

Well, that sounds more like a key sharing. You could achieve this using Shamir's Secret Sharing, for example... But then if you want any of the private key to be able to decrypt the stuff, it means having a polynomial of degree 1, which is equivalent to just sending the main secret key to everybody, so not really a desirable feature.
I'm not aware of clever tricks to achieve this, I'm afraid.


The scrypt function is specifically designed to hinder such attempts by raising the resource demands of the algorithm. Specifically, the algorithm is designed to use a large amount of memory compared to other password-based KDFs, making the size and the cost of a hardware implementation much more expensive, and therefore limiting the amount of paralleling an attacker can use (for a given amount of financial resources).

It means that some hashing algorithms use few memory, so that specific, custom hardware can be created to brute-force it. Since they use few memory, those hardware aren't that expansive, and can be done, at some extent.

When you require a large ammount of memory, you assure it won't fit in those L1, L2 and even L3 caches of the processor, so external memory (slower) will be accessed. And also means that a custom hardware will require a large ammount of memory, for each processor, and that is very expensive, specially if it is fast...

edit Yes, including PBKDF2.... http://en.wikipedia.org/wiki/Scrypt

edit 2: also read the accepted answer on this: https://security.stackexchange.com/questions/4781/do-any-security-experts-recommend-bcrypt-for-password-storage


For $p=23$, $g=2$, $q=11$ you are given the signature $(18,3)$ in the message $m=2$. Construct a signature in the message $m'=3$

Just read the original paper for ElGamal signatures. Especially one of the attacks in section IV. B should help you out. Alternatively, the Wikipedia article about ElGamals signatures also has a section about existential forgeries.

Since this is clearly homework, I'll leave the rest up to you. One last hint: Use q instead of p-1, since you're actually in a smaller multiplicative subgroup.


Encryption schemes that use IVs will typically use results from previous block (or some counter combined with IV) to generate a pseudo-random bit stream to encrypt or decrypt the next block.

Without an IV, the pseudo-randomness can be based only on the key and the message (because that is the only data that the sender and receiver will both have). Which means it would be relatively easy to get repeated blocks across similar messages using the same encryption key, especially at the start of the encryption. Depending on the mode of operation, it might result in repeated blocks elsewhere too.

In addition, the IV in systems that use it is not combined in a reversible way isolated from the key. E.g. it is not simply XOR-ed into the encrypted text, or fed into the algorithm in a way that is reversible (except if you know the key it is reversible). Instead it is fed into the encryption algorithm as a modifier to the first bock of plaintext in CBC mode (when its influence changes seed generation in all consequent blocks), and/or in other modes as a modifier to the seed to the PRNG creating the bit-stream for encrypt/decrypt. To construct the full seed (and thus successfully decrypt) you need to know the key and IV at the same time - knowing just the IV would not be enough to reverse its influence. In your comment you suggest that the effect of an IV could be removed from an encrypted string, thus rendering it ineffective - because you would then have essentially the encrypted message without any influence from the IV. However, this is not possible with schemes that correctly use an IV - to perform this reversal, you would need to already know the key.

The purpose is therefore to allow re-use of same key, without any chance of exposing similarities in blocks of encrypted data. If all your messages started 'Dear Fred', then without an IV block (or some equivalent additional data to feed the PRNG given the same key), the similarity would show if you used the same key, and this would give away some information about the content of your messages.

As such, it doesn't matter that the IV is public, just that it is unique amongst all messages using the same key. The IV for encrypted messages is serving a similar purpose as a salt used for secure hashing.


Reasonable Password Entropy given a certain Set of argon2 Parameters

You should have ≈128 bits or more entropy in any password you want to remain secure regardless of the password hashing function.

Rationale: slow password hashing functions only add a constant-time factor to brute-force search. Since you don’t know the processing capabilities of any potential attacker, the only safe path is to use a very high-entropy password Such a password would be securely stored even if hashed with a single iteration of MD5 without salt.

So what do fancy iterated, “memory hard” functions buy us?

They help against, but do not prevent, attacks on low entropy passwords, the sort that humans can actually memorize. In effect, they increase the work factor required for a dictionary, brute-force, or hybrid search by a fixed amount. You could view this as “extra bits of security”, but you’ll only know how many bits you still need “to be secure” if you know with fair certainty  the computational abilities of your attacker.

If your adversary is a nation-state’s security apparatus, the number of “bits of entropy you need” in the password differs vastly from that when your adversary is me. So the only truly safe thing to do is to always use a high-entropy input password, which renders the fancy hash function pointless.

Slow password hashes are implemented to mitigate the costs to users of a breach of the password hash database. They cannot make low-entropy passwords “always secure” unless they themselves utilize 2^100 operations, making them completely impractical.


What is the purpose of update() in popular hash APIs?

Being able to generate hashes incrementally (by presenting parts of the string being hashed) is there for basically two reasons:

It's commonly useful in practice.  Quite often, we don't have the entire string in one contiguous segment; instead, we often have parts laying around separately.  For one simple example of this, consider the
HMAC
function; the inner hash is some preprocessed keying material, followed by the message being MAC'ed.  We could create a temporary buffer consisting of the HMAC inner key ("ipad") and the message, but why?
It's actually easy to do with our current hash function (including SHA-1, all the SHA-2 versions and SHA-3).  You appear to think that the Python hashlib library copies the parts of the message being hashed into a buffer, and then runs the hash on the entire buffer.  That's extremely unlikely to be how they implement it; instead, it is easy (with a small amount of side memory) to have the hash process the message in pieces.

So, the answer is: they provide this functionality because people find it useful, and its easy for the library to do.


How reassuring is CRC-then-XTS as authenticated encryption?

No, this does not make a deterministic authenticated cipher, unless you're using a secret CRC as a MAC.

How do you break it?  First, find a pair of messages $m = m_1 \mathbin\| m_2$ and $m' = m'_1 \mathbin\| m'_2$ so that $m_i \ne m'_i$ and $\operatorname{CRC}(m) = \operatorname{CRC}(m')$.  (Finding collisions in CRCs is not hard.)  Then:

Query the oracle for $m_1 \mathbin\| m_2$ to find the ciphertext $c_1 \mathbin\| c_2 \mathbin\| c_3$; assume the CRC is in the plaintext of block $c_3$.
Query the oracle for $m'_1 \mathbin\| m_2$ to find the ciphertext $c'_1 \mathbin\| c_2 \mathbin\| c_{\mathit{garbage}}$.
Query the oracle for $m_1 \mathbin\| m'_2$ to find the ciphertext $c_1 \mathbin\| c'_2 \mathbin\| c_{\mathit{garbage}}$.

Finally, yield $c'_1 \mathbin\| c'_2 \mathbin\| c_3$ as a forgery, for the message $m'_1 \mathbin\| m'_2$ not previously sent to the oracle.


Difference between encryption and decryption for Feistel Cipher

You need to have another look at the picture. The output of the encryption process actually denotes $R_{n+1}$ on the left side and $L_{n+1}$ on the right side. And the input to the decryption function has the exact same order, so you don't have to swap anything manually, they are just 'labeled wrong'.

The reason here is that the last round is actually not exactly like the ones before, because it does not contain swapping the two halves. A more obvious way to express this would have been to do one final step like $L_{out} = R_{n+1}$, etc. and then start on the decryption with Left/Right labeling.

Also, I don't understand what they want to indicate by the green and red arrows. The coloring in both sides is either inconsistent or simply wrong. It also indicates that $n$ is an even number.


Switch from plain to encrypted is marked by a special record type called change_cipher_spec (which is neither handshake, alert or application_data); it is unambiguous. Plus, the moment the switch occurs is quite clear from the client point of view, given the previous handshake messages.

If unsure, have a look at the actual standard, which is quite clear (for a standard). This answer can serve as an introduction.


In coin flipping protocols, why aborting is allowed, and why the non-aborting party flips a coin at the end?

1.
You usually allow parties to abort at will at any stage of the protocol since a malicious adversary can always do that in a real protocol execution, and therefore this is not something we can enforce.
A bit more formally, the best we can simulate (for a tutorial on simulation-based proofs see this) is an adversary that can abort, since that's unavoidable anyway.

2.
I didn't read the details of the paper but I assume that in the description, Bob still throws a coin if Alice aborts.
This is done precisely to break the bias imposed by Alice with the abort.
This works because Bob is honest (since Alice is malicious as she aborted) so the output, that is, the coin tossed by Bob, will have a uniform distribution.


How to determine which type of crypto is used in a text file?

This obviously is not an encryption but a simple coding with Base64 coding:

The decoded text message is:

  Steganography is the art and science of writing hidden messages in
  such a way that no one, apart from the sender and intended recipient,
  suspects the existence of the message, a form of security through
  obscurity. The word steganography is of Greek origin and means
  "concealed writing" from the Greek words steganos meaning "co...

By googling the whole text message, you would find this page in princeton university.

For decoding the message I used this website apparently there are a lot more ways to do that. You may access to more informations about Base64 in wikipedia.

  Base64 encoding schemes are commonly used when there is a need to encode binary data that needs to be stored and transferred over media that is designed to deal with textual data.

You may recognize Base64 encoded messages by the signs "==" and "=" in ending of the message and all other must be simple alphabets in lower and uppercase, and also numbers.


Key and tag lengths matter independently. A short tag allows a random guess to be valid more often, but does not help an attacker in finding the key. Rather than XOR, NIST recommends truncation if you need a shorter MAC tag. SP 800-107 (pdf) says to use at least 32 bits:

  When an application truncates the HMAC output to generate a MacTag to a desired length, λ, the λ left-most bits of the HMAC output shall be used as the MacTag. However, the output length, λ, shall be no less than 32 bits.

However, using at least 64 bits is recommended:

  A commonly acceptable length for the MacTag is 64 bits; MacTags with lengths shorter than 64 bits are discouraged.

Other than that, I would not use HMAC-MD5, although it has not been broken. HMAC-SHA256 (or HMAC-SHA512 if that is faster) can be truncated to the same size.


Is this a sensible cryptographic protocol intending to reduce the impact of compromised security?

I don't think the approach you sketched helps very much.  If the server is compromised, the attacker can pretty easily modify the server-side software to log and record all the cryptographic keys, and then you haven't gained anything.  Therefore, I don't think the approach you sketch is likely to be a great way to spend your limited software development budget.

If you want to mitigate the risks of server compromise, let me suggest two alternative approaches that I think might actually be worth your time:

Privilege separation. Rather than have one server that does everything, split it up into two servers.  One server does just the crypto decryption, and the other does all of the other application functionality.  Install these on two separate servers, with separate passwords etc. so that if the latter is compromised, it won't compromise the former.  The former server is super security-sensitive, but if you also keep its functionality very simple and if you administer it carefully, you may be able to reduce the likelihood of compromise of that server.
Client-side cryptography. Don't ever allow the keys to be on the server.  Do all of the encryption purely on the client side.  The client generates the cryptographic keys, and never allows the secret key to leave the client (never shares it with the server); encryption or decryption with the private key is done entirely on the client side (not by the server).  However, it takes additional work to make this work, and make it secure, and address the resulting key management and usability challenges, so this is not a no-brainer: it comes with some non-trivial disadvantages.


AES-CBC authentication and password validation

Now Bob receives the cipher and would like to authenticate it, so he can tell for sure, that the message really came from Alice (or anyone else who knows the passphrase).

Bob should be using an AEAD mode of AES, full-stop. GCM is the go-to candidate for this, rolling your own CBC+HMAC mode is also possible, but should be used as a last resort and only if you emphatically know what you're doing.

  Another problem I'm struggling with is, how will Bob get the IV and the salt which were randomly generated at encryption time?

IVs and salts are not secret. Send them with the ciphertext.

Besides your direct question, it looks like you're trying to wire together your own transport encryption protocol. I strongly recommend you just use TLS instead. Barring that, I'd recommend using libsodium's out-of-the-box AEAD modes instead of rolling your own.


Is the CBC mode of operation a stream cipher mode?

The exact answer may depend on your definition of "usually" or what would be a canonical source for such a statement.

There are few sources (personal opinion) more canonical than Handbook of Applied Cryptography. In it, Remark 7.25 says the following related to your question:

  The CBC mode may also be considered a stream cipher with n-bit blocks playing the role of very large characters. Thus modes of operation allow one to define stream ciphers from block ciphers.

This was not really the answer I expected to write when I first read your question, but I would say that you professor's statement, being inline with what HAC says, is true.

In referencing this remark, the book says (p.3):

  Whereas block ciphers generally process plaintext in relatively large blocks (e.g., n ≥ 64), stream ciphers typically process smaller units (see Note 6.1); the distinction, however, is not definitive (see Remark 7.25).


Proving I can solve an equation without disclosing the solution (zero-knowledge proof)

For the discrete case, you can just use any zk-SNARK that generalizes over arithmetic circuits.
There is no direct way to do a zero-knowledge proof over the reals. However, you can map linear operations over real numbers to operations in the field you are working in by first proving an upper bound on your inputs. Since the circuit is public the verifier can independently check if the upper bound leads to overflow.


How can I derive an ed25519 key pair from a secp256k1 key pair?

Secp256k1 and Ed25519 are completely different algorithms using different elliptic curves. There is no algorithm that could convert one to the other because the keys cannot match. It's just impossible.


In C, multiplication in the field $\operatorname{GF}(2^8)$ with reduction polynomial $x^8+x^4+x^3+x+1$ can be coded as one of these three functionally equivalent functions:
uint8_t mult1B_compact(uint8_t a, uint8_t b) {
    uint8_t r = 0, i = 8;
    while(i)
        r = (-(b>>--i & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    return r;
}

uint8_t mult1B_fast(uint8_t a, uint8_t b) {
    uint8_t r;
    r = (-(b>>7    ) & a);
    r = (-(b>>6 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>5 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>4 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>3 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>2 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>1 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
 return (-(b    & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
}

uint8_t mult1B_shift8(uint8_t a, uint8_t b) {
    uint16_t r,s;
        r  = (-((s = b+b)&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
 return r ^( (-((s +  s )&256))>>8 & a);
}

Try It Online!. The first two versions extensively uses a generic technique, applicable to many other languages: it

moves a bitof interest to the low-order bit of a byte using right-shift >>
isolates it with & 1 if necessary,
applies the unary operator - to change 1 to 0xFF…FF (leaving 0unchanged),
then uses the outcome as a byte mask.

For most platforms, this generates code free from data-dependent timing variation¹. I know no exception, but still that should be checked, e.g. by inspection of the generated code, and in theory invoking/verifying considerations about what influences the execution time of an instruction on each of the target CPUs.
On many platforms, mult1B_fast (perhaps, made inline) is close to the fastest portable C code free from data-dependent timing variation. However, especially on CPUs lacking a barrel shifter, it may be worth trying the mult1B_shift8 variation, which only shifts by a whole byte: the above technique is applied on the high byte 16-bit variables, hence & 1 becomes &256. Assembly language often allows further gain, including thanks to direct access to the carry bit.
Note: These techniques leave other side channels wide open, in particular power analysis.
Note: demonstrating the absence of data-dependent timing variation is very difficult in some non-compiled languages. The most minute details about the runtime environment in theory needs to be taken into account; like, what heuristic a Java JITC uses.
Note: Bogus compiler/tool warning on the tune of «unary minus operator applied to unsigned type, result still unsigned» can be silenced, perhaps by changing the occurrences of -( to 0-(. Add parenthesis to satisfy any enforced convention.

Is it actually necessary to have (this field multiplication code) in constant time if GF28_Inverse is in constant time?

No, because full field multiplication is not necessary (also see note¹). Except for computation of the S-box, a natural implementation of AES encryption² (including AES decryption in CTR mode) only needs field multiplication by the field element $x$, encoded 2. Using the same technique as above, that can be coded as one of:
inline uint8_t mul1B_x(uint8_t a) {
    return (-(a>>7) & 0x1B) ^ (a+a);
}

inline uint8_t mul1B_x_shift8(uint8_t a) {
    uint16_t r = a+a;
    return ((-(r & 256))>>8 & 0x1B) ^ r;
}

¹ For security, we do not need constant-time code, which is next to impossible to achieve on many modern computing platforms because of the various caches and background interrupt activity. It is enough that any timing variations there may be is independent of the data manipulated.
² One such natural implementation is there. It is typically free from data-dependent timing variation on CPUs without a data cache when the two 256-byte tables are aligned to a 256-byte boundary. One of these tables is replaceable by mul1B_x, the other is the S-box.


Is it possible to combine two hash functions in such a way that cracking the constructed hash would require cracking the constituent hashes?

Suppose we try C(password) = A(password) + B(password) where + is just concatenation of the hashes.
The result of this is obviously a weaker hash: we can preimage C by finding the original password by cracking  A or B.

This is incorrect with the standard notion of preimage resistance.
Because there are many more possible inputs to a hash function than outputs, there are necessarily collisions. Even if $A$ allows you to find a preimage, that is not necessarily a preimage for $B$. For random inputs and unrelated hashes, it very likely is not.
In practical applications this is quite a bit more messy. For example, if you take $A$ to be the truncate function (to e.g. 256 bits, zero-padded), it lets you find a preimage for the concatenated hash if the input is short enough. For the vast majority of possible inputs it does not directly give you a preimage, but that is cold comfort if hashing e.g. typical passwords.

If you want a provably robust combiner, you could look into the thesis linked from an answer to the previous question: Anja Lehmann: "On the security of hash function combiners" (pdf). It offers good combiners that are unfortunately rather complex.
For a simpler combiner, you could use XOR like TLS does. You do not get a nice proof from only the preimage resistance of the hash, but it is provably PRF if either of the two password hashes is PRF (and they are independent). That is a practical choice that is probably good enough if you take care to use different hashes.


Maybe Interactive, Not Zero-Knowledge, Arguments of Knowledge

The zero-knowledge property is not the core feature, in the sense that it's already very challenging to come up with a construction satisfying 2-4, and once it's done, adding zero-knowledge usually comes almost for free.

The property 4 is necessary, as it is implied by the property 3: if you want succinctness, you cannot hope to get unconditional soundness. The intuition between this is that if we have a proof of size $n$ for (say) 3-SAT, then we can slove 3-SAT in time $2^n$, by doing exhaustive search over possible proofs (the formal result is a bit more involved as it also considers interactive proofsm but that's the main idea). Therefore, $n$ cannot be much smaller than the witness size, otherwise we would get a subexponential time algorithm for 3-SAT (which would be a major breakthrough).

The property 2 is essentially the one you want to keep: succinctness usually means that the size of the proof and the computation time of the verifier are sublinear in the witness size. And this is exactly what is hard to get :)

Eventually, non-interactivity is usually not the core issue if you are ok with working in the random oracle model - although that's not always the case, most constructions of succinct proofs can be made non-interactive in the random oracle model.

From your question, I guess that what you are looking for is not a succinct proof for all NP language, but only for proofs of languages in P, where the verifier could in principle redo the entire computation himself, but this would be too expensive. Proving correct computation is easier than proving all statements in NP. This was studied a lot (I'm giving keywords here) in the context of delegation of computation. I think one of the seminal papers in this area (you can also look via Google Scholar the papers that cite it) is this one. A more recent, really cool paper in this area is this one. If you provide us more details about the exact specifications of your problem, I might also be able to give you more pointers; delegation is an active research area, with many papers providing efficient solutions in many settings.

Summing up, if you only want succinctness and languages in P, this is indeed easier than building a zk-snark for all of NP, but that remains far from easy.


They're equally safe. HTTPS is designed against most MITM-related attacks, including replay attacks, so the only thing you have to ensure is that your client has the pre-shared key.

For the first method, it is ensured by the HMAC hash. For the second one it is ensured because only the client can decrypt the token.

However, storing keys reversibly on a server is not recommended because your server might be hacked. This can be solved by storing the hash of your client key on your server with some secure password hashing algorithm(bcrypt, PBKDF2, etc).


Edwards / Montgomery ECC with Weierstrass Implementation?

If I understand your question correctly, you are essentially asking if points in Edwards and Montgomery curves can be represented in Weierstrass coordinates. This is true; in fact, any elliptic curve over a field of characteristic $\neq2,3$ can be represented in Weierstrass form $\mathcal{E}_{w}^{a, b} : y^2 = x^3 + ax + b$, and by extension its points can too.

The question, then, becomes “how easy is the conversion”?

For Montgomery curves of the form $\mathcal{E}_m^{A, B}: By^2 = x^3 + Ax^2 + x$, it is surprisingly straightforward. You can map the point $(x, y) \in \mathcal{E}_m^A$ to the Weierstrass curve $\mathcal{E}_w^{1/B^2-A^2/3B^2,A(2A^2 - 9)/27B^3}$ via the map $((x + A/3)/B, y/B)$. The inverse map is obvious, $(Bx - A/3, By)$. If $B=1$, which is the case for every Montgomery curve used in practice, this simplifies substantially.

For twisted Edwards curves $\mathcal{E}_{e}^{a, d} : ax^2 + y^2 = 1 + dx^2y^2$ (where Edwards curves are the subset where $a = 1$) there also is a simple map to a Weierstrass curve, which consists of converting the curve to Montgomery format first. In particular, we can map $\mathcal{E}_e^{a, d}$ to $\mathcal{E}_m^{2(a + d)/(a - d), 4/(a - d)}$ via $(x, y) \mapsto \left(\frac{1 + y}{1 - y}, \frac{1 + y}{x - xy}\right)$, with inverse $(x, y) \mapsto \left(\frac{x}{y}, \frac{x-1}{x+1}\right)$. Composing theses maps with the above, we get maps to the appropriate Weierstrass curve $\mathcal{E}_w^{a, b}$. None of these conversions are terribly expensive compared to the cost of a scalar multiplication.


Hash email address with a non-random salt for moderate security?

There's absolutely zero need to have the token tied to the user's email address.

Just add a column in the database for the token, generate the token randomly, and send it out to the user. If you want to go one step further, send the user the token, but only store $H(token)$ in the database, where $H$ is a sound cryptographic hash function of your choosing.


Proof that user public key corresponds the curve equation (secp256r1)

It is on the curve. Used the sageMath code supplied here for the NIST P-256 curve ( aka secp256r1). Test it online here
# Finite field prime
p256 = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF

# Curve parameters for the curve equation: y^2 = x^3 + a256*x +b256
a256 = p256 - 3
b256 = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B

px = 0x7d550bc2384fd76a47b8b0871165395e4e4d5ab9cb4ee286d1c60d074d7d60ef
py = 0x8cc6dd01e747ccb8bedaae6e7fb875d036ce7e4e6231b75b93993b15202829ac

print("The x-coordinate =", px)
print("The y-coordinate =", py)
print(py^2 % p256 )
print((px^3 + a256*px + b256) % p256)

outputs:
79438795822128695252942075663504569320626776578533931102248002205388342529032
79438795822128695252942075663504569320626776578533931102248002205388342529032

Note 1: The u2f standard can be found FIDO U2F Raw Message Formats
Note 2: there is no need to take the square root. Just compare both sides in the modulus of the curve. This eliminates extra square root calculations on the field.
A little elliptic curve;
In the finite field based Elliptic Curve, we take a finite field $F$ (prime field or finite field extension) and define a curve equation by $$y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6$$ This is Weierstrass equation.
If the field $F$ has characteristics different from 2 or 3 then the Weierstrass equation can be turned into the short form.
$$y^2 = x^3 + Ax +B$$
The equation is the standard short Weierstrass form. We don't want a singular curve so we check that the curve discriminant is non zero by $$2A^3-27B^2 \neq 0.$$
The points of the curve form an abelian group under the geometric interpretation with an identity element call $\mathcal{O}$, it can be the point at infinity like in secp256r1 or $(0,1)$ as the Edwards curves. The geometric interpretation of point addition turned into arithmetic over the field $F$.


As already indicated in the other answer $A$ and $B$ in the video are the public keys of Alice and Bob. The public keys are part of the key pair generation by each one of the parties, usually denoted $\operatorname{Gen}$. With ECC the keys can be generated from the private key at any time, as the public key is generated after the private key within the $\operatorname{Gen}$ function, namely by multiplying the private key value with the base point $G$.

The base point is part of the domain parameters agreed upon by client and server during the handshake and is not expected to change for ECDH. When performing ephemeral-ephemeral key agreement a key pair is regenerated by each party. In that case the key agreement does not perform authentication of any party as the public key cannot be trusted by the other party; authentication is performed separately. That authentication could be performed using any means, including ECDSA with a different, static key pair. In that case the static public key is commonly within a certificate signed by a certificate authority.

What you are generating is a static or key which has the life time displayed in the certificate (after which it isn't trusted anymore, it doesn't self destruct). That key is still just the the private key $s$ multiplied with $G$ of the domain parameters. This is a deterministic calculation: there is therefore only one public key per key pair. The parameters used for this key can be different from the parameters used for the ephemeral key pair used for key agreement; the parameters are indicated by the encoding of the public key in the certificate.

So no, the term "public key" is not used "loosely" here.

There is also ephemeral-static and even static-static Diffie-Hellman, although neither of them is often used. In that case the static public keys can be part of a certificate and trusted. So the entities holding the static keys are then authenticated. A party with an ephemeral key pair isn't authenticated and may need to log in, in case it is a website user, for instance.

As indicated, this isn't used as much; ECDH certificates are not commonplace and static Diffie-Hellman doesn't offer forward secrecy - the session data will become known if the confidentiality of the static key is compromised.

You're generating a static key pair which can be used for authentication. When using a ECDHE ciphersuite you'll need to generate a ephemeral key pair as well, but this is hidden in the TLS implementation. Fortunately generating ECC key pairs is relatively fast: just randomization and point multiplication. This is one of the main benefits of using ECC.


If a permutation $f$ is not one way, what can we say about $f^{p(n)}$?

If a permutation $f$ is not one way, we can not conclude about the one-wayness of $f^{p(n)}$. In fact, even $f^2$ could be one-way, if there are one-way length-preserving permutations that is.

Constructive proof: assume $g:\{0,1\}^*\rightarrow \{0,1\}^*$ is a length-preserving OWP, not invertible starting with rank $m$. Define $f$ from $g$ such that, for any bitstring $x$,

$$\begin{align}f(x\mathbin\|0)&=x\mathbin\|1\\f(x\mathbin\|1)&=g(x)\mathbin\|0\end{align}$$

$f$ is a permutation. It is trivially invertible for half its inputs of any fixed width, thus is not a OWP.

$f^2$ is also a permutation, with

$$\begin{align}f^2(x\mathbin\|0)&=g(x)\mathbin\|0\\f^2(x\mathbin\|1)&=g(x)\mathbin\|1\end{align}$$

An hypothetical algorithm that inverts $f^2$ starting at width $n>m$ could be used to invert $g$ at width $n-1\ge m$. With $g$ being a OWF, there is no such algorithm. Hence $f^2$ is one-way.


I started with books on amazon, such as Understanding Cryptography: A Textbook for Students and Practitioners and open public documents such as FIPS-PUB-197 and 180. I found everything to be pretty easy along my way up. I still cannot calculate or prove anything mathematically, that you want to dig into mathematical reasoning, but I have no problem implementing any algorithms and mix match them to suit my needs.

-- me, 2017-02-14

EDIT:
2 years later, I'm back with a few college level crypto courses in my bag. I want to add that "implementing any algorithms and mix match them to suit my needs" was a terrible idea I want to steer you all clear from. Why? Because this field, cryptography, is full of vulnerability landmines and trip wires, and implementing your own crypto for any production system is asking for trouble. Correctly implementing crypto is hard even for professional groups of people who are intensely experienced and employs in-depth code review.

The solution is to rely on reputable, low-level crypto libraries. Such as OpenSSL. That being said, don't let this stop you from implementing crypto for fun! The sense of achievement is immense when you do so. Happy learning!

-- me, 2019-05-07


Gimli is an unkeyed permutation, mapping a 384-bit input to a 384-bit output, $\{0,1\}^{384} \rightarrow \{0,1\}^{384}$. It is not a cipher by itself as you can reverse the output if you have it in its entirety, so it is not sufficient for security by itself. Instead, it is used to create a secure construction, e.g. using the sponge function. This function gets its security by keeping a portion of the permutation's output a secret, making it impossible to reverse without guessing the unknown (too large to brute force) portion of the output.

XooDoo appears to be another unkeyed permutation, with a slightly different design. There's very little we can say about its security right now, however, because it is relatively new. It often takes many years of analysis for the cryptographic community to feel comfortable about a new design. I will say, though, that it was made by reputable cryptographers, including one of the designers of Keccak-f, a heavily-analyzed and secure unkeyed permutation which is used in SHA-3, a NIST-endorsed hash function.

You can't compare an unkeyed permutation to a keyed permutation like AES because they have different purposes. Although you could build a regular block cipher out of it, that's not typically done. A keyed permutation like AES can be thought as a function which selects a permutation at random based on a key. Without knowing the key, you don't know the permutation and cannot reverse the output even if you have it in its entirety. And ChaCha is even harder to compare it with, as it is a stream cipher.

So, is a keyed permutation (block cipher) or an unkeyed permutation better? Typically, a block cipher has been considered a universal cryptographic primitive. Numerous constructions have been built around a block cipher to create things like hashes (for example, using the Davies–Meyer compression function). Recently, unkeyed permutations like Keccak-f and Gimli have gotten significant attention as potentially superior universal primitives because not only are they easier to analyze, but the sponge construction that they are useful to build can be easily adapted for a stream cipher, hash, or authentication function.

Simply put, block ciphers are older and more research has been done into utilizing them, but unkeyed permutations are more flexible and easier to analyze, and are starting to gain serious traction. XooDoo is a result of this trend towards unkeyed permutations. The Gimli paper mentions that there's no reason to doubt the "new conventional wisdom" that a permutation is a better unified primitive than a block cipher.


The difference between MAC algorithms and what to use

First the theoretical explanations:

Integrity and authenticity are different goals to achieve, but both are achieved (for symmetric encryption) with a MAC.
You should probably be using encrypt-than-MAC or an authenticated cipher unless you have very good reasons not to. No blanket statements can be made though.

HMAC: HMAC is a often used construct. It is recommended to use a separate key for the HMAC but you may get away with using the same key as used for encryption as I haven't heard of any attacks that could attack a scheme with one key for HMAC (but if anybody switches it to CBC-MAC you're in trouble). HMAC, as noted, relies on a hash. A hash function could either be faster or slower than a cipher.

GCM: GCM is an AEAD cipher that has very good performance on (Intel) 32 / 64 bit processors, especially if hardware support can be utilized. As it uses the GMAC construct it may be faster than performing a separate MAC function. It's also pretty easy to use, but it may be hard to get right on embedded systems. Because of the speed it's also known as a 1.5 pass authenticated cipher (as in: the data is processed 1.5 times, 1 time for encryption and 0.5 times for authentication/integrity).

CBC-MAC: is an insecure construct that uses a block cipher (usually the one also used for encryption, of course). There are attacks on CBC-MAC, it should only be used on data of known length and you should use a separate key.

There are other MAC constructs, notably:

CMAC which is basically a fix for the length-related deficiency of CBC-MAC
Poly1305-AES - which is often combined with one of the stream ciphers from Daniel J. Bernstein

And there are many AEAD ciphers as well:

OCB mode (multiple versions) a patented single pass mode, very efficient
CCM mode, a packet based AEAD cipher that uses a 128 bit block cipher with fun peculiarities
EAX an AEAD cipher that uses a 128 bit block cipher, brought up as a candidate to replace CCM at NIST because of the fun peculiarities

MAC algorithms alone are not authenticated ciphers, so if you need encrypt as well, you'll have to specify your own protocol on how to do this. There are efforts to create an authenticated cipher (AEAD cipher) out of CBC and HMAC. Basically EAX mode has done the same with CTR and CMAC. Don't include the IV in the calculation. AEAD ciphers will automatically include it.

Finally note that AEAD ciphers are very much a topic of research.

There's a lot more to be said about MAC algorithms and AEAD, but this is as broad as I would like to go.


Optimal bit-change-probability of the avalanche effect for hashes

Consider a function $H:\{0,1\}^m\to\{0,1\}^h$ (that is, from the set of $m$-bit bistrings to the set of $h$-bit bitstrings). Define $D_n=0^n\mathbin\|1\mathbin\|0^{m-n-1}$ (that is, the $m$-bit "disturbance" bitstring with only bit $n$ set).

By a possible definition, $H$ satisfies the Strict Avalanche Criterion when for each of the $m\cdot h$ pairs $(n,i)$ with $0\le n<m$ and $0\le i<h$, the arithmetic sum of bit $i$ of $H(M\oplus D_n)\oplus H(M)$ computed for all $M$ in $\{0,1\}^m$ is $2^{m-1}$ (that is, exactly 50% of the number of terms summed).

That can be extended to functions with variable-size input (such as usual hashes) by stating that for each input size $m\ge2$ supported, the function satisfies the SAC (Note: when $m<2$ and $h\ne0$, no function satisfies the SAC).

  Is a 50% bit-change-probability optimal for any hash or is it just the minimal value to satisfy the strict avalanche criterion?

Neither.

50% is not the minimal value to satisfy the strict avalanche criterion. For the SAC to hold, the probability that a 1-bit change in input changes any particular bit of output must be exactly 50%, where that probability is computed over the $2^m$ inputs.

The optimal for a cryptographic hash is to behave like a random function, and a random function is extremely unlikely to satisfy the SAC (for $m=2$ that has probability $2^{-h}$, and that goes further down very fast when $m$ grows). If a practical cryptographic hash ($h\ge128$) satisfies the SAC for some $m$ with $2\le m\le50$, that's easily detectable and a weakness in some possible applications. For large $m$ and practical secure hashes, it is computationally impossible to test if $H$ satisfies the SAC or not. Otherwise said, for large messages, a practical secure hash behaves as if it met the SAC for all computational purposes, even though it most likely does not.

Mildly interesting problem: up to what $m$ is it possible to get experimental evidence that a practical hash does not meet the SAC?

  What if a hash-algorithm had a 100% bit-change-probability?

Such function must produce the XOR of its $m$ input bit(s), repeated $h$ times to form a $h$-bit vector, then XORed with a $h$-bit arbitrary value dependent only on $m$. It is not a secure cryptographic hash by any measure. Independently, it does not meet the SAC.


Understanding Meet-in-the-Middle attack on block ciphers

We really only need one plaintext-ciphertext pair, but the second can be used as a way to check candidate keys.

Make a guess to the final subkey (ie guess all of them).
Decrypt the final round of your ciphertext using your key. Store this result and the subkey you used.
Repeat for all 2^16 candidates for the final subkey.
Make a guess for the first three subkeys.
Using these keys, go through the first three rounds of encryption of your plaintext.
If there is a collision between your intermediary encrypted result and your partially decrypted ciphertext, good! You (probably) found the key! You can double check using your other ciphertext/plaintext pair.

Alternatively, if you have enough storage space, you could build your storage of partially-decrypted-ciphertexts by going through the first two rounds of decryption (which are the reverse of the final two rounds of encryption). In this case, you'd bruteforce all candidates for the final two subkeys instead of just the final one. This requires storing 2^(16 * 2) partially decrypted ciphertexts, but has a speedup of 2^16.


What is the difference between RCCA and CCA2?

Informally, CCA2 does not permit any kind of modification of ciphertexts, while RCCA permits some alteration as long as it does not alter the original message. For example, think of a publicly randomizable encryption scheme, that is, a scheme that permits to alter the original randomness used during encryption.  CCA2 would consider these ciphertexts as invalid, while RCCA would accept them.

In the indistinguishability game (IND), this difference is translated in the restrictions to the use of the decryption oracle in phase 2. In CCA-2, the adversary is not allowed to ask for the decryption of the challenge ciphertext $c^*$, while in RCCA, if the adversary asks for the decryption of any ciphertext that decrypts to the challenge messages $m_0$ and $m_1$, he will only receive a special symbol $\mathsf{test}$.


How do I generate a session key using the Diffie Hellman algorithm?

If the nodes can send messages to each other ( via any number of hops/ intermediate nodes) then you can do straight standard diffie-hellmen even if they don't have a prior relationship. Indeed, thats the point of diffie-hellmen.

However, any one of the intermediate nodes could launch a man in the middle attack and could then impersonate either node to the other. There is no way to stop this if the nodes actually don't know anything about eachother. If they do know each other, you can used authenticated diffie-helmen key exchange or a public key crypto system. Agian, these only work if the nodes know each other's public key before hand.


How to encrypt a string and decrypt a string but public can never figure out how to encrypt/decrypt a string

If I understand your question correctly, I (the user) know the image s97dgfubYVd80fzhgdfufg0894rf was generated from the string 1234,2423,1231, but I should not be able to craft another valid parameter.
On the server side, you need to turn the parameter back into 1234,2423,1231.
You have two basic options (and likely more):

with a database available on the backend: just generate a UUID and have a database entry matching 1234,2423,1231 with the image UUID.
without per-image DB entries: encrypt the string with authenticated encryption to provide privacy and data integrity

The former is simple but at the cost of storage. The second means being very careful with how you handle the keys, IVs, and authentication tag sizes.
One algorithm you can use is AES-GCM which provides the following:

given a string, the user cannot generate the corresponding parameter (that's the AES part)
the user cannot generate a random parameter and have it decrypt into a valid string (that's the GCM part)

You seem to only be asking for the first part but the second part is equally important or users could be DOSing your service by submitting random parameters.
It doesn't have to be AES, any modern authenticated encryption mechanism that works for the data sizes you are talking about will be acceptable.


There are many sources presenting the test vectors.
But you can also extract it from sourcecode implementations as opencores.org et al offer them…

 Plaintext: 0000000000000000

 Key: 00000000000000000000 (80-bit)

 Round key 1: 0000000000000000
 Round key 2: c000000000000000
 Round key 3: 5000180000000001
 Round key 4: 60000a0003000001
 Round key 5: b0000c0001400062
 Round key 6: 900016000180002a
 Round key 7: 0001920002c00033
 Round key 8: a000a0003240005b
 Round key 9: d000d4001400064c
 Round key 10: 30017a001a800284
 Round key 11: e01926002f400355
 Round key 12: f00a1c0324c005ed
 Round key 13: 800d5e014380649e
 Round key 14: 4017b001abc02876
 Round key 15: 71926802f600357f
 Round key 16: 10a1ce324d005ec7
 Round key 17: 20d5e21439c649a8
 Round key 18: c17b041abc428730
 Round key 19: c926b82f60835781
 Round key 20: 6a1cd924d705ec19
 Round key 21: bd5e0d439b249aea
 Round key 22: 07b077abc1a8736e
 Round key 23: 426ba0f60ef5783e
 Round key 24: 41cda84d741ec1d5
 Round key 25: f5e0e839b509ae8f
 Round key 26: 2b075ebc1d0736ad
 Round key 27: 86ba2560ebd783ad
 Round key 28: 8cdab0d744ac1d77
 Round key 29: 1e0eb19b561ae89b
 Round key 30: d075c3c1d6336acd
 Round key 31: 8ba27a0eb8783ac9
 Round key 32: 6dab31744f41d700

 Round Output 1: ffffffff00000000
 Round Output 2: 80ff00ffff008000
 Round Output 3: 4036c837b7c88c09
 Round Output 4: 73c2cd26b6192359
 Round Output 5: 41d7be58531e4446
 Round Output 6: 182ef861ad62fd1c
 Round Output 7: 0ea0a5b67effc5a4
 Round Output 8: bba0b848a113e080
 Round Output 9: fa943423a9142338
 Round Output 10: 69f2e22d63684d54
 Round Output 11: 548a4b63c330a59d
 Round Output 12: d75f955fa228e4ca
 Round Output 13: 44255864103841f9
 Round Output 14: e2cc9004363f6c12
 Round Output 15: c36682c5cd375421
 Round Output 16: 597db55cc2a5d9b6
 Round Output 17: e67ce40e71b8b713
 Round Output 18: 751df6d6807b5b59
 Round Output 19: b948414e23332c93
 Round Output 20: 5b75890dcfb3d563
 Round Output 21: 5679203168278f5a
 Round Output 22: 17c377c413fa45a3
 Round Output 23: 262a2de73b5f3ecd
 Round Output 24: d3a053128b4d7bb3
 Round Output 25: 7db29209c28a20fa
 Round Output 26: 62050c9940f400b9
 Round Output 27: 65d50da21fbcc09f
 Round Output 28: 6a50663c540d862f
 Round Output 29: c79b8ff00a48df35
 Round Output 30: 4a38c5e00283fba1
 Round Output 31: 38d2f04c34635345

 Ciphertext: 5579c1387b228445


Encryption of big files in Java with AES/GCM

There is nothing in the GCM cipher that prevents it's use it in streaming mode. You should however not use the resulting plaintext during decryption for anything that requires security before you have verified the authentication tag.

The authentication tag is not to prevent you from decrypting the ciphertext. It is there to provide for integrity and authenticity. You should never decrypt where an attacker can see the plaintext. If possible, you should even try and make it hard for an attacker to perform side channel analysis.

Note that GCM is bounded to encrypting about 68 GB ($2^{39} - 256$ in bits) of data for a single IV. The amount of invocations is $2^{32}$ but you should be advised to stay well away from those limits. Note that repeating the IV for two separate encryption invocations is a catastrophic event for GCM.

CipherInputStream in general is horrible. I would suggest to reprogram it using Cipher and memory mapped files and ByteBuffer itself. The Java implementation (where the tag is automatically put at the end) and CipherInputStream make for this horrible buffering mess.

I'm rewriting the Bouncy Castle implementation and I see a code & complexity reduction of about 30% when I separate the tag from the decryption, plus it enables to decrypt each byte separately. In other words it restores the online properties of the underlying CTR cipher.

With Java 8 however you may want to stick to the Java 8 implementation as GCM may be sped up using intrinsics (for the server VM on the latest Intel processors). Note that according to archie below this functionality is not yet present.


What's the meaning of “family” in “family of hash functions”?

In general, having a family of functions means that you have a function definition with a small detail, change, parameter or other tweak that can vary from function to function.

An (insecure) example would be if you'd parametrize the S-box in AES. Then you have a family of functions, and you select a particular member of that family by specifying the S-box. If you'd specify the S-box to be equal to the AES S-box you'd have AES.

Selecting a member of a function family at random means that you select the parameter at random. An example would be to randomly generate the S-box byte by byte.


Fast cryptographic hash function for short inputs

Did you try SipHash, especially the reduced-round version SipHash-1-3?
It was explicitly designed for short input, doesn’t require key expansion, is fast on pretty much all kind of architectures, and can output 64 or 128 bit.
The name might be confusing, though: a key is required, but since you mentioned that it wasn’t an issue for your use case, give it a try.


Is this test result sufficient to steer clear from this RNG for cryptographic applications?

No test is needed to stay clear from srand for cryptographic purposes, including when a pseudo-random generator is thought. The definition of srand is enough to disqualify it.

That definition states:

  void srand(unsigned int seed);

  The srand function uses the argument as a seed for a new sequence of pseudo-random numbers to be returned by subsequent calls to rand. If srand is then called with the same seed value, the sequence of pseudo-random numbers shall be repeated.

Problem is: the key is an int, and that's not wide enough. int is typically 32-bit, sometime 16-bit, rarely more than 64-bit, and 80-bit is a bare minimum for a modern key (we want more like 128-bit, or 192-bit when considering multi-target attacks, or 256-bit for extra peace of mind when considering the possibility of quantum computers).

Poncho beats me at first stating that the test is misapplied, since the output is not supposed to consist of uniformly random bits, which likely SmallCrush expects. Problem is,

  The rand function computes a sequence of pseudo-random integers in the range 0 to RAND_MAX.

  The value of the RAND_MAX macro shall be at least 32767.

and RAND_MAX is often INT_MAX. It's then likely that for sizeof(int) bytes written, one byte has its high-order bit stuck to 0, which should be caught by many statistical tests.

CSPRNGs can not be validated by statistical tests. Failure of such test only indicates (with high certainty) that the PRNG or/and test procedure is flawed (here, both are). Success does not prove anything, and indicates very little. Image: it's like validating a road bridge by having an ant cross it, when the actual things to test are high load, wind-induced oscillations and long-term corrosion of metal parts.

Also, many cryptographic applications need a True RNG (with output unpredictable from the code). That's not even touched by either srand or the test.