What is the relation between x y and r s in an ECDSA signature?

Yes, those encoded values are $r$ and $s$.

The ASN.1 integers are signed big endian values while the two fixed sized values are unsigned big endian. So the value field may be identical or it may not, if:

the value is equal to or larger than $2^{256 - 1}$: encoding this as signed big endian value will result in an additional byte at the left set to 00 to avoid it being interpreted as a negative value;
the value is smaller than $2^{256 - 8 - 1}$: encoding this as signed big endian value will result in fewer bytes.

To convert back and forward between the ASN.1 structure you need two functions: I2OSP and OS2IP, also specified in e.g. RSA PCKS#1.

You can follow the mathematical construct of course, but basically you need to do the following (where $n$ is the minimum required size in bytes to encode the order $N$, i.e. the key size in bytes). The reason to do it this way is that you likely are handed rep(i) - the unsigned big endian encoding of i rather than the number itself.

I2OSP(i, n):

if len(rep(i)) is two larger or more than n then error;
if len(rep(i)) is one larger and the leftmost byte isn't 00 then error;
if len(rep(i)) is one larger and the leftmost byte is 00 then skip this byte and return the rest of rep(i) as answer;
if len(rep(i)) as unsigned integer is identical to n, then copy rep(i);
if len(rep(i)) is smaller than n then left-pad with zero's until the representation is the same size as n.

OS2IP(i)

You may want to skip initial zero bytes of rep(i) and then left-pad with one zero byte in case the result would be interpreted as negative number (i.e. the most significant bit is set, or the initial byte value is 0x80 or higher).

Usually however this kind of functionality is included in big integer libraries.

Unfortunately the BN library of OpenSSL is internalized so you may have to operate directly on the encodings like above.

The ASN.1 encoding is a SEQUENCE of two integers, DER encoded, as follows:

30 LC 02 LR rep(r) 02 LS rep(s)

LR and LS are the size of the following unsigned integer representation, a single byte. The value of LR and LS may differ of course.

LC is usually a single byte length encoding of everything that comes next. However, if the encoding of r and s combined is over 128 bytes then a two byte encoding needs to be used: 81 LC. This is only the case for 521 or 512 bit curves though, so you can almost ignore it :)

I'll let you have the fun to implement it. Finding a BER/DER parser/generator would be recommended though.


Secure instant messaging protocol and implementation for an anonymous end-to-end chat?

I searched here and I found Tox to be the most powerful protocol.

The reason, why I'd advise against Tox and for the Signal Protocol is not a one of features.

Tox has seen not much review, especially not from cryptographers. The core library is also still in alpha. In fact, an audit is still an open issue for them on GitHub, so I don't have too much trust in their security for now.

The Signal Protocol on the other hand, has very wide-spread deployment (in apps like Signal, WhatsApp, Google Allo and Facebook Messenger) and thus has seen a lot of scrutiny. The creators also have conducted security audits of their software and academics have given it a lot of attention.

  What are you think about that ?

From a purely cryptographical stand point this is totally fine, except maybe that ChaCha hasn't yet seen as much scrutiny as Salsa20 (and XSalsa20) have yet. But ChaCha is considered to be just as secure.
However, doing this will make you incompatible with all other existing implementations of Tox which will make it "harder" to integrate support for your product into other, potentially harming adoption rates.
Secondly, I assume you'd use the Tox-core library and changing stuff in those libraries is always dangerous and because of the change you may introduce a new vulnerability.

  A ask for a secure communication to the Server [...]

You don't need a centralized server, that's one of the points going for Tox. Everything can be done peer-to-peer (mostly).

As for your actual protocol there are a few issues:

From what I can tell, it's trivial for the server to serve bad public keys and MitM attack connections (this also depends on whether the UI will allow to verify public keys though)
IP adresses can change over time, not ideal for a chat application (depending on how long they need to stay valid)
Depending on how connection establishment works, users sitting behind drop-all firewalls and NAT routers may also have problems
The server learns the social structures of the users (eg who groups up with whom)
You lack a threat model (e.g. what do you want to achieve? Who is considered a threat?)

Most of these issues can be mitigated server-side using software (like don't store IPs, don't store grouping, keep the incoming connections alive) only the mitm attack mitigation would need client-side action.

And of course this quick check by me doesn't replace a full review by a professional cryptographer.


Is there any Corelation between the SHA256 and SHA512 hash of the same data?

No.

Knowing $h = \operatorname{SHA-256}(m)$ without $m$ doesn't help you to find $h' = \operatorname{SHA-512}(m)$, or vice versa, except insofar as you can use $h$ to test a guess $m^*$ for what $m$ might be, by checking $$h \stackrel?= \operatorname{SHA-256}(m^*).$$

The same goes for all of the SHA-2 functions {SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256}.  It also goes for the fixed-length SHA-3 functions {SHA3-224, SHA3-256, SHA3-384, SHA3-512}.

Note: The extendable-output SHA-3 functions SHAKE128 and SHAKE256 have the property that SHAKE128-$n$ and SHAKE128-$m$ share a common prefix—in other words, SHAKE128 and SHAKE256 produce infinite-length outputs for any input and you just use a finite prefix of the length you requested.  However, they are otherwise independent of the SHA-2 and fixed-length SHA-3 functions, and of the related SHA-3 constructions KMAC, TupleHash, and ParallelHash.

You can make your own family of independent functions in the privacy of your own living room by picking a fixed-length prefix $p$ in some set like {foo, bar, baz, qux, zot} and using, say, $m \mapsto \operatorname{SHAKE128}(p \mathbin\| m)$ or $m \mapsto \operatorname{SHA-512/256}(p \mathbin\| m)$; for each distinct $p$, this can be modeled as an independent uniform random function as in a random oracle, as long as you always use a prefix.*†

* Note that if you use $H_p\colon m \mapsto \operatorname{SHA-256}(p \mathbin\| m)$, you have the property that knowledge of $H_p(m)$ lets you compute $H_p(\operatorname{pad}(m) \mathbin\| m')$ for any suffix $m'$, which is quite improbable for a uniform random function.  This is called a length extension attack.  The SHA-3 functions dispense with this property, as do SHA-512/224 and SHA-512/256.

† Actually the set of prefixes need not be fixed-length—it is sufficient that it be prefix-free, meaning that if $p \ne p'$ are in the set of possible prefixes, then neither one is a prefix of the other.  For instance, length-encoded tags like 3 foo, 4 quux, 11 hello world would work too, as long as the length is encoded uniquely.


What could be the problem with this TLS 1.2 Client Finished Message approach?

The sequence_number resets at CCS, so for Finished it's zero (for 8 bytes). Also record type for handshake is 0x16,
and to be clear the record length is 2 bytes, in this case 00 10, and "the IV" should be random for each record.
As a mnemonic, the RHUL group's Lucky Thirteen attack uses the fact that the HMAC pseudoheader is 13 bytes.

That said I agree with @Maarten's comment: debug against another implementation. Especially an open source one like OpenSSL/LibreSSL/BoringSSL or GnuTLS or Java.


How to ensure that a "received value" is not altered?

From my point of view, multi-hashing will slow down things, but it won't add the security you are looking for in this case.

  Is cryptography able to solve this problem?

Yes. What you need is a message authentication code (MAC), which is a short piece of information used to authenticate a message and to provide integrity and authenticity assurances on the message. Integrity assurances detect accidental and intentional message changes, while authenticity assurances affirm the message's origin.

For your further research endeavours, "MAC" and "HMAC" are the relevant keywords.

Nota Bene: In bis comment, @fgrieu hints at practically using a HMAC with SHA256... which indeed seems to be the most logic choice (because it's pretty minimal while currently offering expected security).


How is the MJH double-block-length hash function constructed?

I had a look at the paper introducing the MJH construction (MJH: A Faster Alternative to MDC-2).

It actually presents a different diagram than the one in the paper Efficient hashing using the AES Instruction Set your referenced – there $V_2$ and $M$ are swapped. I'll describe the original one here, and the variation below.

The core of MJH is a compression function, using a similar construction like the JH hash function (one of the SHA-3 finalists), hence the name.

The JH construction

Given a (non-compressing) function $F : \{ 0,1\}^{2n} \to \{0,1\}^{2n}$, we define the compression function $JH[F] : \{0,1\}^{3n} \to \{0,1\}^{2n}$ as
$JH[F](V_1, V_2, M) := (Z_1, Z_2)$, with $(X_1, X_2) = (V_1, V_2 \oplus M)$, $(Y_1, Y_2) = F(X_1, X_2)$ and $(Z_1, Z_2) := (Y_1 \oplus M, Y_2)$.

In the JH hash function, F is a specially-made (fixed) permutation.

MJH's $F[\sigma, \theta]$

Given a $n$-bit-blockcipher $E$ with keysize $k = n$, $\sigma : \{0,1\}^{n} \to \{0,1\}^n$ an involution (i.e. $\sigma \circ \sigma = \mathrm{id}$) without fixed point (i.e. $\sigma(X) \neq X$) – an example would be an XOR with a non-zero constant –, and $\theta \in \mathbb{F}_{2^n} \setminus\{0,1\}$ a constant (so multiplication with $\theta$ is another non-trivial permutation).

We define $F[\sigma, \theta] : \{0,1\}^{2n} \to \{0,1\}^{2n}$ as $F(X, K) = (L, R)$, with $L = E_K(X) \oplus X$ and $R := \theta(E_K(\sigma(X)) \oplus \sigma(X) ) \oplus X$.

(The $E_K(X) \oplus X$ part is essentially the Davies-Meyer construction to make it one-way, even if $K$ is known. It is actually used twice here.)

The final Hash function

Combining these ideas, we get our compression function $\tilde F[\sigma, \theta] := JH[F[\sigma, \theta]] : \{0,1\}^{3n} \to \{0,1\}^{2n}$.

We then apply the known Merkle–Damgård caining construction on this compression function, receiving our final hash function $H[\sigma, \theta] = MD[\tilde F[\sigma, \theta]]$.

(This image is from Wikimedia Commons, the others are made by me.)

In practice we now also have to choose some specific $\sigma$ and $\theta$, a specific block cipher, as well as an initialization vector and padding for MD - the security proof still applies for all of them (if the block cipher is good).

Longer key variant

The paper also describes a variant of the compression function to be used when the key length $k$ is greater than the block size $n$. Then we use message blocks of size $k$, and split these blocks into two parts $z, z'$. $z$ (of size $n$)is used as before to be XOR'ed into the left half of the state before encryption and right half after, while $z'$ (of size $k-n$) is appended to the right half of the state to form the key for the block cipher.

By using a larger (hash) block size, this longer variant can be more efficient than the original one.

The variant depicted in Efficient Hashing

For $n = k$, this is the same compression function as the original one, but it is used in a different way in the MD-construction: Here the message blocks are passed in the key position, instead of being XOR'ed into the parts of the state before and after encryption. (This XOR'ing instead uses one half of the original state.)

This gives a more obvious generalization into the $k \geq n$ case, as we don't have to split the message block and compose the key, but simply can pass the longer key to the block cipher.

I didn't check if the proofs given in the MJH paper also apply to this variant, though, and I don't know which version the authors of Efficient Hashing actually measured.


How many attempts does it take to crack a 32-bit password hash with this scenario?

Correct me if I'm wrong, but to crack a 32-bit password hash would take roughly 2^31 attempts, while the math for matching a 32-bit hash from 4 million hashes should take (2^31)/4M ~ 537 attempts.

It would take on average $2^{32}$ attempts to crack a single 32-bit hash.

If you've got 4 million unique hashes to test against then then each hash you generate you've got a $4,000,000(\dfrac{1}{2^{32}}) \approx \dfrac{1}{1073}$ chance of finding a matching one. So you're going to need to try on average $1073$ times.

Unless you know the distribution of passwords and which ones are more common than others and you incorporate that into your guessing, this is as accurate as it's going to get.


Are there simple, cryptographically safe one-way hashing functions?

Designing a conceptually simple one-way function is a very hard challenge in itself - and conceptual simplicity is not such a well defined concept, so the answers you will receive might be a bit opinion-based (and in particular, so will be my answer).

One of my favourite candidate OWF regarding conceptual simplicity is Goldreich's local one-way function. It is more a vast class of possible functions than a specific one, but here is the core idea:

You fix some simple predicate $P$ that acts on a small number of inputs $d$.
You fix $m$ random subsets $(S_1, \cdots, S_m)$ of $[1,n]$, such that each subset is of size exactly $d$. $n$ represents the input size of the function, and $m$ is the output size.

Now, the function simply does this: on input $x \in \{0,1\}^n$, output $y = y_1y_2\cdots y_m \in \{0,1\}^m$ where $y_i$ is computed by evaluating $P$ on the $d$ bits of $x$ indexed by the subset $S_i$.

As you can see, the high level idea of the function is extremely simple. The hard part is choosing a good predicate $P$, and studying the conditions that must be satisfied by the sets $S_i$ to be able to withstand existing attacks. And indeed, both problems have been intensively studied in the theoretical community in the past ten years. But this does not affect the extreme simplicity of an implementation: to implement it, fix once for all a list of subset $(S_1, \cdots, S_m)$ (if you want a compression function, take $m = n/2$), picked at random in some setup phase, and store it in some file. For $P$ and $d$, take something widely regarded as good in the theoretical community - e.g., you can take $d = 5$ and $$P : (x_1,x_2,x_3,x_4,x_5) \mapsto x_1+x_2+x_3+x_4\cdot x_5 \bmod 2$$ (see e.g. this article). The code for evaluating the function is extremely simple: to generate the $i$th bit of the output, it retrieves $S_i$ from the stored file (a random subset of $[1,n]$ of size $5$), and applies the above $P$ on the bits of $x$ whose index are in $S_i$. Moreover, all the output bits can be generated in parallel.

Now, if your sole purpose is understanding how OWF are built - well, looking at a very specific example will hardly help, as OWF functions can be constructed from a huge variety of designs. But if you only wanted to see a conceptually simple one, with some detailed explanations on why this family of functions can be conjectured to be one-way (see Goldreich's paper, which I find fairly easy and pleasant to read), this might satisfy your need.


How to handle authenticated encryption for big files?

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

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

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

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

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


Safety of AES ECB when used with openssl_seal function

ECB is not secure even with per file keys, because if two blocks of the file are identical, this is visible in the ciphertext. The only * cases where ECB is secure is encrypting completely random data or encrypting a single block per key.

You should pick something more secure if your can help it.

If there is literally no other option than RC4 and AES ECB, you could use first RC4 and then AES ECB. RC4 would make it almost random and AES ECB would hide the biases. However, general concerns with cascaded ciphers would apply.

* Ok, fine, or if plaintext blocks are known to be unique, but that's rare and not the case here.


Randomness re-use in LWE encryption scheme

I give another simple proof using the leftover hash lemma.
The proof goes as follows, where I'll abuse the notation and assume that q is prime.

Game0

The adversary can see
$$(A,b,c,u,v,w,s)
= (A, As+e, At+f, rA, rb+x\lfloor q/2 \rceil, rc+y\lfloor q/2 \rceil, s).$$

Game1

The view is changed as
$$(A,b,c,u,v,w,s)
= (A, As+e, c, rA, rb+x\lfloor q/2 \rceil, rc+y\lfloor q/2 \rceil, s),$$
 where we change $c = At+f$ with random $c$.
From the LWE assumption, Game0 is indistinguishabe from Game1.

Game2

The view is changed as
$$(A,b,c,u,v,w,s)
= (A,As+e,c,u,rb+x\lfloor q/2 \rceil,z+y\lfloor q/2 \rceil, s)$$
where we replace $rA$ and $rc$ with random $u \gets \mathbb{Z}_q^n$ and $z \gets \mathbb{Z}_q$.

In this game, $y$ is completely hidden, since $z$ is chosen uniformly at random.

Game1 vs Game2

If the term $v=rb+x\lfloor q/2 \rceil$ disappears,
 then we can invoke the leftover hash lemma as Regev originally did.

We can still invoke the generalized leftover hash lemma in [DORS08] even if the term $v$ remains.
Very roughly speaking,
 if $m \geq (n+2) \lg{q} + 2(1/\epsilon) + O(1)$,
 then we can say the distance between Game1 and Game2 is at most $\epsilon$.

Generalized leftover hash lemma

Let us define the average min-entropy of $R$ given $I$ as follows:
$$\tilde{H}_{\infty}(R \mid I)
 = -\log\left(\mathrm{Exp}_{i \gets I}\left[
  \max_{r} \Pr[R = r \mid I = i]
  \right]\right).
$$
Intuitively speaking, this entropy is the logarithm of predictability of $R$ given $I$. As we expected, if $I$ leaks the information of $R$, the average min-entropy of $R$ given $I$ decreases.

Let us consider the average min-entropy of $r$ given $v = rb + x\lfloor q/2 \rceil$.
By invoking  [Lemma 2.2 (b), DORS08], we have that
$$
 \tilde{H}_{\infty}(r \mid v)
  \geq H_{\infty}(r) - \lg{q}.
$$
That is, the average min-entropy of $r$ given $v$
 is at least the min-entropy of $r$, which is $m$, minus $\lg{q}$.

Now, let us review the generalized leftover hash lemma in [DORS08]:
For a family of universal hash functions $\{H_d : \{0,1\}^n \to \mathcal{S}\}$
for any random variables $R$ and $I$,
we have
$$
\Delta\Big(
 (H_{D}(R),D,I),
 (U_{\mathcal{S}},D,I)
\Big) \leq \frac{1}{2} \sqrt{2^{-\tilde{H}_{\infty}(R \mid I)} \cdot \#\mathcal{S}},
$$
where $U_{\mathcal{S}}$ is a random variable distributed according to the uniform distribution over $\mathcal{S}$.

By replace $D$ with $(A,c)$, $R$ with $r$,
 $H_{D}(R)$ with $(rA,rc)$, and $I$ with $v$,
 $\mathcal{S}$ with $\mathbb{Z}_q^{n+1}$,
 we obtain the upperbound of the statistical distance as $\frac{1}{2} \sqrt{2^{\tilde{H}_{\infty}(r \mid rb)} \cdot q^{n+1}}$, which is at most $\epsilon$ if $m = (n+2)\lg{q} + 2\log(1/\epsilon) + \Omega(1)$.

[DORS08] Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin and Adam Smith: "Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data" in SIAM Journal of Computing, 38(1):97--139, 2008. (Prelim. version is Dodis, Reyzin and Smith in EUROCRYPT 2004).


What cipher(s) can or should I use for attribute based encryption?

I am assuming that you are asking which encryption scheme is used to encrypt the actual data (file, stream data etc.) while using ABE. To encrypt the data, you can use any block cipher such as AES. Then, use ABE to encrypt block cipher key (AES key).


How to generate a key using any $m$ passwords out of total $n$?

One option would be to generate a random key, split it using Shamir's secret sharing, then encrypt each of the split parts individually under a key derived from each user's password.

So for example:

key = read from os.urandom()
d1,d2,...d5 = split(key=key,n=5,k=3)
e1 = encrypt(d1, KDF(PW1)), e2 = encrypt(d2, KDF(PW2))...

key can then be derived from all of the encrypted shares (e1, ...) and user's passwords (PW1, ...). You could store the encrypted shares in the application and be confident that without at least three of the passwords you wouldn't be able to derive the key.


What is the probability of un-authenticated messages to go through CCM because of channel errors?

Is there any probability that channel errors make the change in a frame go un-detected through CBC-MAC?

For any Message Authentication Code, there is always a probability [1] that the modified message will just happen to verify against the modified tag.
In your extreme "worse possible case" scenario, it's quite simple to compute; your communication channel effectively replaces the message/tag with a completely random message/tag.  And, if we compute the MAC on a random message, the probability that it matches a random tag is $2^{-32}$ for a 32 bit tag.

[1]: Unless the errors are tightly constrained.  For example, with CBC-MAC with a full length tag, we will always detect any error if the error is constrained to be always within one block, with all the other blocks being transmitted correctly.  However, random errors (and active attackers) are generally not so accommodating with how they modify the message.


Is Triple DES still considered safe to use?

Well, yes and no.

Triple DES using 3 different keys is still considered secure because there are no known attack which completely break its security to a point where it is feasible nowadays to crack it.

The Triple DES algorithm provides around 112 bits of security against bruteforce attacks (when taking into account the meet-in-the-middle attack).

For reference, the insane computation power used to find the first SHA1 collision is estimated at a bit more than $2^{63}$ operations. So we still have a security margin of $2^{49}$, which is plenty, but still far less than other standards such as AES.

Triple DES with 3 different keys is still recommended by NIST as per their latest recommendation in NIST SP 800-57.

Triple DES is also the de facto fall-back algorithm for PGP: that is the algorithm all OpenPGP compliant software must implement and use if no other commonly supported algorithm is advertised in the public key of the recipient.

However, Triple DES has a really "small" blocksize with only 64 bits, which led to attack such as Sweet32 against TLS session which allows to break the security of the system thanks to "block collision". This attack led to the removal of Triple DES from the DEFAULT cipher list in the 1.1.0 release of OpenSSL. The attack can also be mitigated by rekeying after a given amount of encrypted data.

As a consequence of that, Triple DES was still in the TLS1.2 standard, but has not made it into the TLS1.3 one.

So in the end, Triple DES is still considered secure if you just want to encrypt something with it, but if you are running a protocol based on it, then you should be worrying about its small blocksize leading to the Sweet32 attack.


Is it possible to generate a message using the mac and the key?

This depends on the MAC algorithm.

Two examples:

With HMAC based on a secure hash function, no, there is no known way to construct a message fitting the MAC other than brute-forcing it. (If you want to find a specific message, like when you have a MAC of a message containing a password and some fixed text, brute-forcing the password might be quite feasible.)

With CMAC (a MAC-algorithm based on a block cipher), given the key and MAC value, it is usually quite easy to construct a fitting message, you even can chose all but one block of your message freely.

In general, MACs based on hash-functions are usually safe, MACs based on block ciphers not.

Have a look at the CMAC algorithm, assuming we have a full-length message (multiple of block size). In the image the length is 3 blocks.

             +-----+     +-----+     +-----+
             | M_1 |     | M_2 |     | M_3 |
             +-----+     +-----+     +-----+
                |           |           |    +--+
                |     +--->(+)    +--->(+)<--|K1|
                |     |     |     |     |    +--+
             +-----+  |  +-----+  |  +-----+
             |AES_K|  |  |AES_K|  |  |AES_K|
             +-----+  |  +-----+  |  +-----+
                |     |     |     |     |
                +-----+     +-----+     |
                                        |
                                     +-----+
                                     |  T  |
                                     +-----+

(Image modified from RFC 4493, page 5.)

Assume we know the key $K$ and the tag $T$, we did choose $M_1$ and $M_3$ arbitrarily and we now want to produce a message by finding a fitting $M_2$.

This is the formula:

$$T = E_K(E_K(E_K(M_1) \oplus M_2) \oplus M_3 \oplus K_1)$$

($K_1$ is derived from $K$.)

We can apply the decryption function on both sides:

$$D_K(T) = E_K(E_K(M_1) \oplus M_2) \oplus M_3 \oplus K_1$$

Next move the XORs over:

$$D_K(T)  \oplus M_3 \oplus K_1 = E_K(E_K(M_1) \oplus M_2)$$

Apply decryption again:

$$D_K( D_K(T) \oplus M_3 \oplus K_1) = E_K(M_1) \oplus M_2$$

One more step:

$$D_K( D_K(T) \oplus M_3 \oplus K_1) \oplus E_K(M_1) = M_2$$

Of course this also works with more than three blocks and if the last block is not a full block (then we pad and XOR with another key $K_2$ at the end), as long as one block is free to choose according to the result.

The general idea is that we can move through our diagram from both sides (replacing encryption by decryption if going in the other direction) until we arrive at the one unknown block.

The moral is that a MAC with a known key doesn't give us a secure hash function, where such a result would count as a preimage-attack.


How do P2P clients like uTorrent maintain authenticity of files?

The only thing that always happens in BitTorrent is that the chunks (pieces of files) are checksummed/hashed with the SHA1 algorithm and compared against the values in the .torrent file. If all the chunks match their hashes, the file is correct – unless there's an SHA1 collision.

Additionally, some .torrent files contain MD5 hashes for each of the files which the client may or may not verify.

Finally, many clients support protocol encryption, where the traffic between peers is encrypted using Diffie-Hellman key exchange, SHA1 and ARC4. This does nothing to guarantee the integrity of files, it is mostly meant to avoid throttling by ISPs and make it more difficult for eavesdroppers to see what you are up to.


A lot has changed recently in this area. Now the only ciphersuites Chrome considers non-obsolete (those that use AES-GCM or ChaCha+Poly1305), do use Carter-Wegman MACs.

So, I would say that there is no disadvantage and that any low popularity has been just an artifact of historical decisions in standardization. Secure hashes were the first to be openly standardized and exportable, so they were used for MACs as well.


CBC - a canonical mode, even though there are streaming modes

OFB and (to a lesser degree) CFB are malleable: an adversary knowing a selected portion of the plaintext and able to change the ciphertext can trivially change the alleged plaintext to something chosen, e.g. "no!" to "yes". CBC has a (small) degree of resistance to that.

OFB does not allow efficient decryption of an isolated segment of ciphertext (we need to know the IV, run the cipher for all previous blocks, and know or guess the position of the segment). CBC (and CFB) allow that (only the first block of the isolated segment is undecipherable).

CBC can be introduced as an improved version of ECB (the simplest mode), while CFB and OFB are a radical departure.

I conjecture this has conspired to make CBC popular.

Note: a previous version of this answer mixed OFB and CFB. That's fixed, thanks to Henrick Hellström.


Signature scheme against an unbounded rival

Actually, the conclusion you drew doesn't follow from the theorem; the theorem says "if you have a OWF, then a secure signature scheme exists"; it doesn't say "if you don't have a OWF, then there are no secure signature schemes".  As far as the theorem goes, there might be another way to generate a signature scheme; the proof implied by the theorem doesn't work, but there might be another proof that does.

However, it turns out that your conclusion is indeed correct; if you have an unbounded rival, then with the public key, he can forge the signature for any message he wants.

The proof needn't be fancy; all the unbounded adversary does is consider all possible signatures, check each one against the public key, and selects the one that validates.  This obviously works no matter how the signature algorithm works internally.


Does 52 round sha-256 simply ignore the elements $53..64$ of $W$?

Yes; rounds 53-64 don't happens, and we don't actually use elements of $W$.

One alternative way of looking at $W$ is that it's an iterative algorithm to generate the next text-dependent constant for the round function (based on the constants generated for the previous rounds, or the actual message text for the first 16 rounds).  With this formulation, there is now no need to specify a magic number '64'; the number of rounds can be decreased or increased without significantly modifying the block scheduling algorithm


Lets use the text from the protocol for reference:

  After verifying the server's certificate, the client encrypts a
     pre_master_secret with the server's public key.  By successfully
     decoding the pre_master_secret and producing a correct finished
     message, the server demonstrates that it knows the private key
     corresponding to the server certificate.

  When RSA is used for key exchange, clients are authenticated using
     the certificate verify message (see Section 5.6.8).  The client signs
     a value derived from the master_secret and all preceding handshake
     messages.  These handshake messages include the server certificate,
     which binds the signature to the server, and ServerHello.random,
     which binds the signature to the current handshake process.

And your question is:

  Why the public key of the client is not used like it used for the server?

The method of establishing the secret is kept identical for SSLv3 with client authentication. The client authentication is added to the protocol. This way the implementation of the key agreement can remain the same, with or without client authentication. There is no need for a second pre_master_secret or random either, one is sufficient to derive the session keys.

Now the server is authenticated by being able to decrypt the pre_master_secret send to it by the client. This shows it has the private key that belongs to the public key within the (verified) server certificate.

The client on the other hand does not perform any operations with the private key in this protocol. On the other hand, the private key must be used over session specific data; if this wasn't the case the private key operation would be vulnerable against replay attacks. So a signature over the session data is used instead. No additional random values or challenges are required.


Symmetric encryption vulnerable when encrypting and decrypting are the same?

The short answer to your question is yes, but the devil is in the details of "(i.e.  can be considered a cryptographically secure source of randomness)".  For one thing, the "entropy stream" or any portion of it must never be reused within the same (periodicity) or any & all other input data streams.  For another, it is in principle impossible to prove randomness.  OTOH, "cryptographic security" is more tractable.

Interestingly (at least to me) there is another binary primitive that has the same reflexive property as XOR: complementation, or double subtraction.  Consider this C fragment:
    Output_byte = (512 - Input_byte - Key_byte) & 0xff;

There are other (faster) ways of doing it using logical inverse & the properties of two's complement representation, but it's still nowhere near as fast as XOR. It does, however, have the same self-inverse property that XOR does.


RSA public key and private key calculation: multiple answer

[M]ust public and private key always be a prime number?

No, they don't have to be. Usually the public key is chosen as an odd prime though because it must hold that $\gcd(e,\lambda(n))=1$, which simplifies to "$e$ must not divide $\lambda(n)$" if $e$ is prime.

  How can there be multiple suitable instance of private key such as
  59/11/47?

Recall that all we need for correctness for RSA is that for each possible $m$ it holds that $m^x\bmod n=m$. It turns out that the smallest possible $x$ here isn't the euler-phi function $\varphi(n)=(p-1)(q-1)$ (in the two-prime case) but rather the carmichael function $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ (in the two-prime case), because it is defined to be the smallest such $x$.

Now what does this mean? It means that if $ed\equiv 1\pmod{\lambda(n)}$ then $e,d$ is a valid pair of RSA exponents. As you can individually reduce each factor in modular arithmetic this also means that for a fixed choice of $e,d$ for any integers $k,l$ the following is also a pair of valid exponents: $e+l\lambda(n),d+k\lambda(n)$ because $(e+l\lambda(n))(d+k\lambda(n))=ed+ek\underbrace{\lambda(n)}_{0}+dl\underbrace{\lambda(n)}_{0}+\underbrace{\lambda(n)}_{0}\lambda(n)\bmod\lambda(n)=ed$. What you have experienced was the choice $e=11,d=11$ and $k=0,3,4$.


What is the difference between anomalous elliptic curve and ordinary elliptic curve?

Let $E$ be an elliptic curve defined over a field $K$. Let $n$ be a positive integer.
$$E[n] = \{P \in E(\overline{K}) \,|\, [n]P = \infty\}$$
Where $\overline{K}$ is the algebraic closure of $K$ and $E[n]$ include the point with coordinate $\overline{K}$, not just from $K$. The above is the set of  $n$ torsion points on the curve, namely the points of finite order $n$. In Elliptic curves over a finite field, all points are torsion points.

An elliptic curve $E$ in characteristic $p$ is called ordinary curves if $ E[p] \backsimeq \mathbf{Z}/p\mathbf{Z}$
An elliptic curve $E$ in characteristic $p$ is called supersingular curves if $ E[p] \backsimeq 0$, and we know that those curves are not secure.
An elliptic curves $E$ over $F_q$ with  $\#E(\mathbf{F}_q ) = q$ are called anomalous curves. This is suggested to use against the MOV attack. Unfortunately, the discrete log problem for group $E(\mathbf{F}_q )$ can be solved quickly.

Ref: A good textbook: Elliptic Curves Number Theory and Cryptography, Second Edition, by Lawrence Washington.


Inverse of a function $f_k(x) := f (x ⊕ k) ⊕ k$

Assuming $f^{-1}$ exists (i.e., that $f$ is injective), then $$f_k^{-1}(y) = f^{-1}(y \oplus k) \oplus k.$$ To see why consider an $x \in \{0,1\}^4$ so that $f_k(x) = y$. Then you have that $$y \oplus k = f (x \oplus k).$$ Now by applying $f^{-1}$ on both sides of that equation you have $$f^{-1}(y \oplus k) = x \oplus k.$$ And finally by XOR'ing $k$ on both sides you get the above result.


The bcrypt algorithm generates a 192-bit password hash by encrypting three 64-bit blocks using a password-derived blowfish key. The common format for storing bcrypt hashes, however, only includes 184 of the output bits.

If bcrypt was a "perfect" 184-bit hash, finding a some preimage would take the same amount of work as a brute force attack on a 184-bit key. So if you had random binary tokens, a token longer than 184 bits would be useless. Similarly, with a random hex token, length over 46 characters would be useless, etc.

Many bcrypt implementations also have a limit on input length. This is usually at least 51 bytes, so if your input format is hex, base 64 or binary, the above limit would be reached first. If you were hashing some less dense encoding, like decimal numbers (or indeed passphrases...), it might not be.

However, if your tokens are high entropy (e.g. 128+ bits) there is no need to use bcrypt. Bcrypt is useful for slowing down a brute force or dictionary attack, but 128 bits is enough that such an attack would be infeasible. A key derivation function such as HKDF, or even a simple salted hash, would be sufficient.


Of course, since the domain of a hash function is infinite and its range is finite, it cannot possibly be injective, i.e. there is at least one hash with more than one string that is being mapped to it.
This is called the pigeonhole argument: if the domain of a function is larger than the set that it maps to, at least two values are mapped to the same thing. (In fact, one can even show quite easily that in the case of infinite domain v finite range there is one hash that has infinitely many input strings associated to it)

So injectivity, or “uniqueness”, if you will, is, of course, a goal one cannot possibly hope to achieve for a hash function. If that is what you call an “ideal hash function”, then that is doomed to fail.

So what can we hope to have in a hash function?
There are a number of properties that hash functions should have. A common way to define these properties is to state that certain problems concerning the hash function should be computatinally hard, such as:

Collision resistance: it should be difficult to find a collision of the hash function f, i.e. to obtain two different values x₁, x₂ such that f(x₁) = f(x₂)
Second-preimage resistance: for any value, it should be difficult to find another value with the same hash. Formally: for any x₁, it should be difficult to find an x₂ such that f(x₁) = f(x₂)
Preimage resistance: given a hash, it should be difficult to find a message that has that hash. Formally, given y and some x₁ with f(x₁)=y, it should be difficult to obtain x₂ with f(x₂)=y

(There is also the related notion of a universal one-way hash function, but I shall not explain it here.)

It can be seen that collision resistance implies second-preimage resistance and that again implies preimage resistance. Now, do SHA and MD5 have these properties? Well, nobody really knows. The problem in cryptography is that it is very difficult to prove that a cryptographic scheme is correct. There are many relative security results, i.e. “Scheme A is secure if some assumption holds”, but the only cryptographic scheme that is proven to be secure is the One Time Pad.

In particular, it is not even known whether things such as “safe” (practical, i.e. not OTP) ciphers, good hash functions and so on exist in the first place – essentially, if the (still unresolved) P = NP? question has a positive result, i.e. P = NP, all these ciphers and hash functions are basically worthless.

However, it is widely thought that P does, in fact, not equal NP. Cryptographic primitives such as hash functions and ciphers are designed by people who are very knowledgeable in this area and have to withstand many attempts to break them before they are tentatively declared probably secure.

To come back to MD5, there are a lot of papers that describe efficient attacks on MD5. MD5 is definitely not collision-resistant. SHA-2 still seems to be quite good. But generally, the natural progression is that as hash functions grow older, more flaws and corresponding new attacks are discovered and they are gradually replaced by new hash functions, which were developed with the lessons learnt from the flaws of the old ones in mind.

I just realised this post got a lot longer and more detailed than I had initially planned; nevertheless, I hope it answers your question.


There are a number of things to watch due to signed arithmetic:

If the hardware was not using 2's complement arithmetic (representing range $[-2^{k-1},2^{k-1})$ on a $k$-bit word, with negative integer $x$ represented as $x+2^k$ is in binary), then it would be difficult to use the full word width $k$. It would then likely be a better idea to keep everything non-negative and less than $2^{k-2}$.
That is easy for Speck-$n$ (where $n$ is the block width) when $k\ge n/2-2$. E.g. for Speck-32, $k\ge18$ allows to compute $(x+y)\bmod 2^{16}$, as required, using (x+y)&0xFFFF, without depending on the representation of negative numbers.
Or, another option is using multiple-word arithmetic. That's what a compiler does on an 8-bit CPU to implement wider arithmetic types, and how large integers are usually implemented in asymmetric cryptography. It reduces speed and increases code size by a factor like 3 when going from one to two native words, thus is best avoided.
Fortunately, 2's complement arithmetic is common. That would make Speck-$n$ with $k=n/2$ feasible without multiple-word arithmetic, baring the next issue.
Some industrial controllers detect overflow (e.g. when $2^{k-2}+2^{k-2}$ is attempted). When using words to their full width, overflow will occur often, and its detection should be disabled. An alternative is to avoid overflow by keeping everything non-negative and less than $2^{k-2}$ as above.
Speck requires rotation by constants, often implemented with a combination of left and right shift followed by bitwise OR, e.g. For Speck-32 (x>>13)|(x<<3). Right shift by $b$ positions on signed variables sometime replicates the sign bit $b$ times rather than introduce $b$ zero bits. That would require extra masking, e.g. ((x>>13)&7)|(x<<3). With $k>16$ make that ((x>>13)&7)|((x&7)<<3) when needing to avoid negatives and overflow.

To watch also, but not directly related to signed arithmetic:

Speck is a block cipher, thus needs an operating mode to become a cipher, and for more than a single use a True Random Number Generator to generate its IV (or at least persistent storage for a counter), before it can be used to encrypt arbitrary data.
Most of the time, when encryption is thought, integrity/proof of origin is functionally needed also (sometime, only). That's authenticated encryption, and while it can be implemented with a block cipher, there are a few catches.
Industrial controllers need to be reliable, not fast. Speed might be an issue, especially if multiple-word arithmetic has to be used due to signed arithmetic.
For security, the implementation should have execution time independent of data if an adversary can time execution (which should be the default assumption), and a number of things (like overflow detection, and more) could introduce timing dependencies.
Industrial controllers are usually not designed to keep secret the data they manipulate; I've met one (emulating relay logic) that blinked a led according to the state of its (one-bit wide) data register! And there could be much more subtle side-channels.


Which data encryption mechanism to use for data transfer?

You should use AES. If you have the AES-NI instruction (which most modern chips have), then this performs very fast. For most applications today, AES-128 is certainly sufficient. However, I want to stress that it's not just the algorithm, it's also the mode of operation. You should use GCM. If you use OpenSSL then with AES-128-GCM you'll get speeds of about 0.7 cycles per byte for encryption (with AES-NI).


You can use the Frequency test of the NIST statistical random number test suite. ( see http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf, chapter 2.2).
In that chapter is also stated the recommended sample size.

I would propose to encrypt a block of zeroes with different randomly selected keys.

Another test would be to fix the key and use random plaintexts $t$, encrypt it $c= enc(t)$ and fit $t \oplus c$ to the frequency test.


First, remember that we can write each of the ciphertext bits $$c_i = f_i(m_0,\ldots,m_{63}, k_1,\ldots, k_{63})$$ as the output of a non-linear functions $f_i$, $f_i \neq f_j, i \neq j$. If we remove the non-linear part from DES than this $f_i$ will be linear functions $f^l_i$. Now, turn back to matrix $B$;

How do we build $B$ matrix?

Once we constructed the linear $f^l_i$ 's than the construction of the matrix $B$ is easy. Write the $f^l_i$'s a row vector so that the inner product with $[m,k_1,k_2,\ldots,k_{16}]$ will give out $c_i$s. To construct them, we need the actual definition of the new linear S-boxes, then we can write a program over the linear-DES to find $f^l_i$'s and then the vectors.

But why should we use $[m,k_1,k_2,\ldots,k_{16}]$ column?

The non-linear DES version is now represented by a matrix $B$. Each $c_i$ is nothing but linear combination of $\{m_0,\ldots,m_{63},k_1,k_2,\ldots,k_{16}\}$. If you multiply by the column vector, it will give the ciphertext.

Where does 832 comes from

$832 = 16\cdot 48+64$, the 16 rounds of the DES, 48-bit key per round, and 64 is the plaintext size.

Why we have round keys $[k_1,k_2,\ldots,k_{16}]$ not the key bits in the equation.

The key generation of DES is not linear. To keep the equation in linear form the author of your document, preferred the round keys for the equations to keep the linearity.


How can a random salt for a hash function work in practice?

Usually, when the user registers, you will generate a random value to become the salt. Then, in the user database, you store the user's name, salt, and hash generated using the password and salt (and whatever else is relevant for a user table).

Note that doing it this way allows each user to have a unique salt. Each user having a unique salt greatly increases attack difficulty. An attacker is forced to do a brute-force attack per user instead of precomputing per-password-scheme rainbow tables (no salts) or a per-database rainbow table (a system-wide salt). It is still your responsibility to make sure the brute force attack is actually slow enough to be costly to an attacker in these days of massively parallel GPU hash implementations.

Ideally, an attacker would not even be able to see the salt on the database, but it does not have to be private if worse comes to worse.


Questions regarding random values in Schnorr authentication

Your first question: $r$ is taken from the group $Z_q$ ranging from 0 to $q-1$, and $q\equiv 0 \bmod q$, i.e. $q$ is the same as 0 in this group. Thus if you allow $q$ to be chosen, then $r$ is not uniform: you get 0 with a probability $2/(q+1)$ and all other elements in $Z_q$ with a probability $1/(q+1)$. Not really a big deal since the difference in probability is anyway negligible, but it is enough to annoy cryptographers.

Your second question: it really depends on what kind of zero-knowledge property you want. If you want zero-knowledge (without restriction), you have to have a small $t$; if you just want honest verifier zero-knowledge, then you can choose $c$ from $Z_q$. The reason is that when you use $c$ from $Z_q$, you will run into big trouble when trying to prove zero-knowledge because there is not a way to construct a simulator to handle such a big $c$. The usual simulating strategy is to let the simulator guess $c$ randomly until it is the one chosen by the verifier, which does not work when the probability of guessing correctly is negligible (if $t$ is small then the probability is high). But if the verifier is honest, you don't need to simulate it, so it is fine.


Why can't Homomorphic encryption schemes support algorithms with conditions/branching?

I think you have a misconception.  Fully homomorphic encryption can support algorithms with conditions and branching.  Any such efficient algorithm can be unrolled to be implemented as a circuit (say, with just AND and NOT gates), removing all conditions and branching, and thus can be implemented on encrypted data using fully homomorphic encryption.

Of course, fully homomorphic encryption schemes are hardly practical right now; search this site for more details.


How to estimate the maximum computational cost bound for Key Derivation Functions (KDFs) before it becomes useless security-wise?

Generally we look at strength by looking at the order $O$ that it adds to the password search when an attacker is trying to guess passwords. That's just the same as the number of iterations basically, assuming a salt and correct password hash. Often it is simpler to just use bits, which is basically the $\log_2$ of the order.
So if a password strength is an average of about 40 bits, then you'd take the $log_2$ of the number of iterations and simply add the values together to get the resulting strength. So given 1048576 iterations, we'd get around $40 + \log_2(1,048,576) = 40 + 20 = 60$ bits of strength. Given the average weakness of passwords, there is no higher limit that is not entirely impractical. Obviously performing $2^{88}$ operations to allow for even average passwords to have 128 bits security is out of the question. So generally you should aim for the highest value possible for a specific service.
For the same reason it is very important to take other measures than just using a password hash with large iteration count. Possible measures are a max number of retries, an added delay before testing each password, requiring a good password with (likely) high entropy or using a password manager of some kind. Browsers nowadays offer internal password managers including generation for a good reason.
Note that some of password hashes such as bcrypt use a two-exponential "work factor" instead of an iteration count to give a better idea of the strength added to the password entropy in bits.


Is AES easier to crack when the input is small?

Assuming that encryption is performed correctly:

Using a modern cipher (AES)
An appropriate mode of operation
With no bugs in the implementation

then the nature of the plaintext has no effect on the security of the ciphertext.

  If not would it at least be significantly easier to crack than the cyphertext from a larger input:

Actually, a longer ciphertext is technically easier to "crack" than a small one.

The reason being that the larger cryptogram provides the adversary with more known plaintext-ciphertext pairs. Attacks that do exist against modern ciphers typically require very large numbers of plaintext-ciphertext pairs.

That being said, this effect is still negligible in pretty much any realistic use case. The quantity of plaintext-ciphertext pairs required for cryptanalysis is frequently obscenely and prohibitively large.


Does IKEv1 support multiple combinations of a source IP range?

No, IKEv1 does not support negotiating multiple combinations of source IP ranges (or subnets) within a single SA.

The IKEv1 RFCs (specifically, 2407 and 2409) constrain the negotiated source IP to be either a single IP address, or an IP subnet (that is, an IP address and a mask; this is typically used to handle things such as 10.0.0.0/8; it can also handle "any" IP address) [1].  As for ports, you can ask for a specific port, or any port; nothing inbetween is allowed.  And, no, a single SA cannot have multiple; if you need to protect multiple subnets, you need to negotiate separate SAs.

It is possible that the Strongswan implementation of IKEv1 attempts to go beyond what the RFC permits (at least, when negotiating with other Strongswan implementations); however, I personally find that unlikely

[1]: Note: this is a subnet, not a range; it can't negotiate, say 10.0.0.1-10.0.0.6; the closest you can do is 10.0.0.0/29 (which also covers 10.0.0.0 and 10.0.0.7).  It could negotiate "discontiguous" subnets, such as 10.0.X.1 (for any X); I wouldn't be surprised if many IKEv1 implementations didn't support such an oddball thing...


The security of Zero knowledge proof performance

I don't know the term "safety". But when it's written 'the process is more secure'. It means that the probability for an adversary that doesn't know the secret (here how to go through the door) decreases "exponentially".

For example, to solve 4 challenges the adversary has to choose the side door $4$ times, so it has the probability $\frac{1}{2^4}$ to win the game.


Cryptography - Perfect secrecy => adversarial indistinguishability - proof

Hopefully I'm able to at least give a partial answer. In the first step of the three equalities, there are three simultaneous steps taken:
$$Pr[M=m_0]=Pr[M=m_1]=\frac{1}{2}$$ and $$Pr[b'=b|M=m_0]=Pr[c\in\mathcal{C}_0]$$ and $$Pr[b'=b|M=m_1]=Pr[c\in\mathcal{C}_1].$$ (Yes it seems the second 0's should be 1's). The first one is clear why it's true, as the messages are randomly chosen. The second two however, are not so obvious.

Let's just look at $m = m_0$. What should be clear, is that $b'=b$ if and only if ${\tt Enc}(m_0)\in\mathcal{C}_0$, by the definition of the game and the strategy explained before the equations. So we can say that
$$Pr[b'=b|M=m_0]=Pr[{\tt Enc}(m_0)\in\mathcal{C}_0|M=m_0].$$
Writing $c={\tt Enc}(m_0)$, what remains to prove is that
$$Pr[c\in\mathcal{C}_0|M=m_0]=Pr[c\in\mathcal{C}_0].$$
Now compare this to Theorem 2.2 of the document you cite, which gives a criterium for perfect secrecy. It is not exactly the same, but it is very similar. This last equality I stated is really a consequence of perfect secrecy, and does definitely not hold in general.

Suppose for example that our encryption scheme gives our ciphertext the same least significant bit as the plaintext, and suppose that $m_0$ has lsb 0 and $m_1$ has lsb 1. Then we can easily choose $\mathcal{C}_0$ and $\mathcal{C}_1$ such that
$$Pr[c\in\mathcal{C}_0|M=m_0]=Pr[c\in\mathcal{C}_1|M=m_1]=1.$$
On the other hand, not both $Pr[c\in\mathcal{C}_0]=1$ and $Pr[c\in\mathcal{C}_1]=1$.


How do herding attacks on hash functions work?

Herding attack is introduced by Kelsey and Kohno in 2005. The attack is applicable to hash commitments. Nostradamus's example from the article is key of the idea. First Nostradamus produces the MD5 (MD is enough) hash of the future prediction of S&P500 before the business year finishes. After Nostradamus publish his message with precise closing prices of the S&P500's companies with some garbage text after it. The message has the same hash the committed hash.
At first, to achieve this, Nostradamus need pre-image attack on MD5, which has still $2^{123.4}$ complexity achieved after this work in 2009 (Finding Preimages in Full MD5 Faster Than Exhaustive Search). Instead of pre-image attack, this work introduces a new required property; Chosen Target Forced Prefix Pre-image resistance.

In the first step, Nostradamus has a Chosen Target by committing n-bit Hash value, $H$.
In the challenge step, the challenger provides $P$ to Nostradamus as Forced-Prefix so that the hash $H = Hash(P\mathbin\|S) $ where $S$ is the suffix (garbage).

The Herding
The herding attack uses a diamond structure to find the hash. The below figure uses 8 different starting messages, one can consider this all possible outcome of the prediction of the Nostradamus prediction.
Remember that, this attack utilizes the Merkle-Damgard structure of the hash function. MOD constructions divide the hash into the block ( for example 512-bit blocks for MD5) after the appropriate padding. Each block then used in the compression function in order.

In the above figure, the first 512-bit part of each message is hashed. Then the crucial part begins. This is actually internal collision on MD construction. Randomly generating 512-bit block to see that $C(h[0,0], m_i) = C(h[0,0], m_j)$ where the $C$ is the internal compression function. With the generic collision, this has $8 \cdot2^{n/2}$ complexity. And as mentioned in the article A diamond structure is essentially a Merkle tree built by brute force.
The committer actually can do better than this instead of a fixed structure for collision finding, one can go dynamically. In the generalized form mapping $2^k$ hash nodes in the diamond structure to $2^{k-1}$ they generate $2^{n/2+1/2-k/2}$ candidate block parts and looks for the collisions altogether. This has  $2^{n/2+k/2+2}$
This attack can also be applied to longer messages - elongated Diamond structure.
The complexity of the attack on MD5 with 41 diamond width and 48 suffix length requires $2^{87}$ complexity. On impractically long suffixes the attack on MD5 with 5 diamond width and $2^{55}$ suffix length requires $2^{69}$ complexity.

Andreeva at al. go beyond this work on Herding, Second Preimage and Trojan Message
Attacks beyond Merkle-Damgard, 2009.


Composition of weak one way function is not a strong one way function

Obviously, composing $T$-times a weak OWP can give a strong OWF: simply consider the case where $f$ is already a strong OWP (hence in particular a weak OWP). Now, what you want is to show that it is not necessarily the case; i.e., you want a function $f$ which is a weak OWP, but such that $f^T$ is not a strong OWF (i.e., an example where security does not "amplify through composition").

I'll give you such a candidate; I let you prove that it satisfies what you want, that is a quite simple exercise. Let $g: I \mapsto I$ be an arbitrary (strong or weak) OWP, and let $J$ be some arbitrary set such that $|J| = |I|$, and $I$ is disjoint from $J$. Consider the following function $f$:

$f:I \cup J \mapsto I \cup J$ is defined as follows: $f(x) = g(x)$ if $x \in I$, and $f(x) = x$ if $x\in J$.

Claim: $f$ is a permutation (that's quite obvious), and also a weak-OWP (you should be able to check that easily). Yet, $f^T$ is still a weak-OWP, but not a strong OWF. Can you see why?

(if you're stuck in the analysis, just ask for more hints in the comment section)


What are the time considerations with regard to security against birthday attack?

When designing security for a physical safe, one of the critical specifications is how long will the safe resist attack, this tells you how quickly you must detect and respond to an attack on the safe.

Yes, however there's a key difference between physical safes and cryptography.  With a physical safe, the attackers must be present on site (if they could drag the safe off to their own lair, then any safe can be defeated eventually).  This physical presence is what allow the defenders to detect and respond.

Cryptography isn't necessarily like that; it may be that the attacker (for example) intercepts a packet flowing over the internet, and we have no clue that he has done so.  He can then spend as much resources as his budget allows, and we have no idea that he is doing so.  Hence, cryptography is scaled to resist attacks for an extended period of time (at least, until we don't care about whatever it was that the cryptography was protecting).

  As I understand it for hash functions about 80 bits is considered minimally secure

Actually, if the hash function needs to resist a collision attack, 80 bits are quite insufficient for anything above "kid-sister-proof".  An $n$-bit hash function can be attacked with a birthday attack with about $2^{n/2}$ hash operations; a single PC core might be able to do this many hashes in a week.

Unless there's a strong reason not to, we typically use hashes that are at least 256 bits in length (yes, SHA-1 is shorter; it's also being phased out).  This implies that a birthday attack would require around $2^{128}$ hashes; we are fairly confident that no plausible adversary can do this.

  is there a time consideration as well?

Yes, the $2^{128}$ hash evaluations is time...


Use of Same Key for CTR and CBC-MAC in CCM Mode of Operation?

Basically you should never reuse a key and neither should you use CBC-MAC. CCM is considered secure because the designer knew about the issues of reusing a key and CBC-MAC length extension issues. The scheme is designed to be secure regardless of these issues.

In a general sense you should always use two keys unless you can prove your scheme to be secure regardless of the fact that the key is reused. The same goes for CBC-MAC, CMAC or HMAC should be preferred instead - CBC-MAC is only secure if the size of the message is known in advance and CCM does take this into consideration.

Also note that if changes are made to your scheme, e.g. supplanting CTR by CBC by another designer/developer then reusing a key may cause your scheme to fail spectacularly. So if you do decide to go this route when creating a secure scheme / protocol then make sure you document it thoroughly.

CCM is a cipher with it's own packet format. This makes it suitable for low level packet encryption / decryption where speed is important. The choice of one key and CBC-MAC was likely inspired by this. For a more generic authenticated cipher mode I'd recommend EAX mode or GCM mode instead.


A CSPRNG is really just a name for an algorithm that, given a specific seed (where the seed has a certain amount of entropy) generates a pseudo random stream from that. A stream cipher that generates a key stream independent from the plaintext can be thought of as a CSPRNG in that sense.

So say you have a fully random 128 bit seed, then you can use that seed to generate an almost endless amount of key stream. This key stream can then be split up into separate keys.

In practice you should not confuse this with a CSPRNG or random number generator that is supplied by the system itself. The problem is that the internal operation and reseeding-strategy may introduce changes between different streams: generally such algorithms are only used to generate random values after all.

To be honest this seems more a good application for a ratchet scheme than one for a random number generator as you know it. Of course, if you take the theoretic approach, somebody could argue that - from a theoretical standpoint - the ratchet scheme constitutes CSPRNG.

Directly related to this is also the notion of KDF's, key derivation functions, which can calculate multiple keys from one specific master keys. However, in this case the key not dependent on the previous keys. It could be that a key management scheme requires one or the other, or both.


Delayed tag checks in AES-GCM for streaming data

You can have AES-GCM and streaming at the same time.  But:

Do not operate on unauthenticated data!

Treat unauthenticated data like nuclear waste.

The fact that the AES-CTR out of which AES-GCM is built technically can provide access to data before the authentication tag is verified is a red herring.  Allowing access to the data before verifying the tag, and requiring a separate API call to verify the tag, is a loaded semiautomatic foot-pointed gun.  Don't do it!

Do not allow arbitrarily long messages before you verify authentication tags!

Arbitrarily long messages will tempt you to act on the content of the message before you can verify the authentication tags.

Resist the temptation!  Al you have to do is break long messages into chunks of bounded size so that you aren't even tempted to do this.  You can even use a chunk sequence number for the AES-GCM nonce, or you can use a scheme like miscreant that handles chunking for you.

Fogeries are bad news!  Every program is an interpreter for a programming language that is its input—sometimes that language is Turing-complete, or even if not you may still enable an adversary to control a weird machine you never even thought existed in ways you never imagined.  The cryptography lets you ensure that only the peer you're trying to have a conversation with gets to program your program, and not anyone else on the internet.

If the governor of Arkansas acted on a series of forged execution orders, and only afterward checked all the judges' signatures on them, people would be even more upset than they already are about the lethal carceral state.  Don't let your program be that governor!

See an earlier answer about xsalsa20poly1305 for elaboration on the performance and denial-of-service implications of bounded-size chunks in a cryptosystem of the same type as AES-GCM.


Dancing confusion with Daniel J. Bernstein's stream ciphers

XSalsa20 uses the same cryptographic core as Salsa20 and comes with a security proof that it's secure if Salsa20 is secure. It doesn't use the core of ChaCha and thus has worse diffusion.

The way XSalsa20 works is that it hashes its 256 bit key and the first 128 bits of the nonce using HSalsa down to a 256 bit key and then uses that key together with the remaining 64 bits of the nonce in Salsa20. You can find the details in the paper Extending the Salsa20 nonce.

The problem with nonces is that you must be sure that you never reuse one. With a 64 bit nonce a counter works well, but a counter is stateful. If you want a stateless nonce, the usual approach is to generate a random one, and assume that collisions are sufficiently unlikely to happen. Assuming uniqueness with a random 128 bit value is pretty safe, but with a random 64 bit value collisions become likely even with a moderate number of messages. So you can't use random 64 bit nonces. But if you have a 192 bit nonce, you can randomize it.

Thus the increased nonce size isn't a security improvement, but a feature that allows random nonces.

In principle it's possible to use the same nonce extension technique with ChaCha, but Bernstein didn't publish a specification. In my answer to Can I use the ChaCha core as a 256-bit to 256-bit one-way function? I describe how to construct HChaCha from ChaCha, in the same way HSalsa20 was built from Salsa20. Combining HChaCha and ChaCha into XChaCha is straightforward.


Vigenere Cryptosystem is as follow:

You chose a key $(K_0,...,K_{m-1})$ consisting of elements in $Z_{26}$.
Then a ciphertext for the message $(M_0,...,M_{n-1})$ is $$(M_i+K_{i\mod m}\mod 26)_{i \in [0..n-1]}$$

It is easy to see that you can generate a ciphertext for the message $(M_0+1,...,M_{n-1}+1)$ by adding 1 to each letter. It is therefore by definition malleable.


How do I find out whether a message in CBC has padding?

Actually, that is depending on the padding applied. Maybe there is no padding at all. The implementation defines the padding applied. Check the code or documentation!
The last 22, at first, indicates that might be PKCS#5 or PKCS#7 since PKCS#7 most common with CBC implementations. While PKCS#5 is limited to 8 bytes like DES, PKCS#7 works from 1 to 256 bytes. PKCS#7 appends octets like

For such algorithms, the method shall be to pad the input at the trailing end with $k - (l \bmod k)$ octets all having value $k - (l \bmod k)$, where $l$ is the length of the input.

However, that is 0x02,0x02. The 2s in your last 22 is the character 2 that is in hex 0x32.
To see that has PKCS#7 padding check the last octet and maker sure that the value $k$ of the last octet repeat $k$-times. Example for a 16-byte block cipher where each position is a byte. 1 means 0x01, 2 means 0x02, etc.
xxxxxxxxxxxxxxx1
xxxxxxxxxxxxxx22
xxxxxxxxxxxxx333
...
xFFFFFFFFFFFFFFF
xxxxxxxxxxxxxxxx full block append a new block that contains 16 times 0x10

To see other padding candidates see Padding in Wikipedia


If Kerckhoff's Principle holds, why do we need a cipher at all?

...why go through the trouble of creating a cipher in the first place? Why not simply use a ridiculously long key, if you're gonna create a cipher that only takes as long as an exhaustive key search anyway?

Designing a cipher is significantly less hassle then using a ridiculously long key.

Designing a cipher only needs to be done once by a competent professional.

Using a ridiculously long key would need to be:

Done by all parties

"all parties" includes everyone with a networked electronic device
Almost all of them are not competent professionals
Requires a pre-existing secure channel, or more likely a face-to-face meeting

"secure channel" must not use encryption, otherwise the problem is circular

Done pairwise for each group of communicating parties

e.g. You have to go through the key establishment process for every particular site you want to visit
A web site with 1000 users that each have a 1GB key would need to have access to 1TB of reliable, secure storage just to store the key material (that's a small website)

Done repeatedly

You will eventually run out of key material
Your keys could become compromised

Updating them in a useful time frame will be next to impossible

Destroyed securely after use

Re-using any part of the key will lead to a practical lose of confidentiality

In a practical scenario (e.g. HTTP requests) known-plaintext attacks apply, which will allow trivial recovery of the key

It simply would not work in practice. A proper cipher will.


Is there a hash function whose security can be extended by length?

Note: this answer assumes that this is about secure hash applications, not password-hashing which is a different set of algorithms with other properties.

There are a few assumptions in your question that may not be fully applicable:

Some old hash functions have been proven to be unsafe. This is mainly due to two reasons:

The computation power of machines are increasing.
People have discovered algorithmic flaws in those hash functions.

We're still struggling with finding a collision in SHA-1 even though it is considered broken in the theoretical sense. The hash output size of MD5 is not considered large enough for most applications, but it would still be quite a problem to find a pre-image or even a collision using brute force.
SHA-2 and SHA-3 output sizes are out of reach - and will be out of reach - for the foreseeable future, even though the security provided by SHA-224 is below 128 bits (which many believe is about the minimum security you should strive for nowadays).
The amount of computing power required for collision attacks increases exponentially (doubles for each two bits added to the output size). So the amount of computing power does not really threaten the security of secure hashes with large output size.

Hash functions are usually based on simpler cryptographic primitives, and there should be provable reductions from the security of the hash function itself to that of the underlying primitives. Thus I'm wondering whether there exists a hash function whose algorithm design is provably secure (given that the underlying primitives are secure), and its overall security only depends on the length of variables. Such an algorithm can be easily extended to cope with increasing computation power without much effort.
Is there such an extendible algorithm? If so, what is it?

Most of the hash constructions are build up the way you've described. Merkle-Damgärd is used for SHA-2 while SHA-3 uses a sponge construction (using the function $f$ as underlying primitive).
The underlying primitives can usually not be extended to any length / size of the internal state by simply altering a variable. The functions use constants and algorithms for specific word sizes. What is possible is to create multiple versions of the underlying primitives for different sizes of the internal state and output size. This is exactly what has happened for SHA-2 and SHA-3 (Keccak).
It is however unnecessary to go beyond 256 bits of security. Either the underlying primitive / hash construction is broken or the construction stays secure for forever.

And why do people keep inventing new algorithms instead of extending this algorithm?

Because we have doubts on the underlying primitive and the construction itself. Even a secure block that we consider secure (we cannot prove that either) may not be secure for use in a secure hash function. Furthermore there may be specific properties of the construction that become problematic even if the hash is still formally secure. SHA-2 is vulnerable to length extension for instance, while SHA-3 is not.
And don't underestimate the curiosity and drive of individual researchers. There does not need to be any theoretical reason for new hash functions to be published.


Why do block ciphers need a non-linear component (like an S-box)?

If a block cipher is linear with respect to some field, then, given a few known plaintext-ciphertext pairs, it is possible to recover the key using a simple Gaussian elimination. This clearly contradicts the security properties one expects from a secure block cipher.


Consider using Noise.  If that's too heavy, consider using NaCl crypto_secretbox, at least.

Now that we've got that out of the way: Write down a design document that articulates what you're trying to enable the legitimate parties to achieve with what resources, enumerates the powers of an adversary, and identifies the security properties you hope to guarantee in the face of an adversary.  Do this without mentioning cryptography!  You need to be specific about what resources the adversary can subvert and how—read packets on the wire, replace them, act maliciously to peers in some way—and specific about what you want to guarantee they can't do in spite of those powers.

Then you can use that design document decide what cryptography to use to provide those security properties, and anyone else studying your system can use that design document to assess whether you did it sensibly.  Simply putting the letters A-E-S or D-T-L-S in your application means approximately nothing other than that you used everyone's favorite pseudorandom permutation family or the unloved cousin of a protocol whose family gave us Heartbleed.


Can the key-generation algorithm always be uniform?

For any symmetric encryption scheme, it is not a loss of generality to assume that the key is uniformly distributed: you can let the key be the random coins of the key generation algorithm $\mathcal G$, and incorporate the deterministic part of $\mathcal G$ (i.e., how it generates the key from its random coins) into the encryption and decryption algorithms.

For asymmetric encryption schemes, the same applies to the private key.


How to generate backup key for PBKD functions?

This kind of key management problem is a big reason why encryption is not more widely used for everyday data.

I see a single easy way to do this, I think it is similar to the way disk encryption systems work, and it may not work for your uses.

For each file, a random key $kf$ is generated. 2 copies of the key are encrypted, one with a key derived from the password ($kp$), the other with a key derived from the backup code ($kb$). The original key is used to encrypt the file, and the 2 encrypted copies of this key are stored with the file.

$EncFile = E_{kp}(kf) \ || \ E_{kb}(kf) \ || \ E_{kf}(File)$

This can also be done on a per user basis. The encrypted keys are not stored with each file, just one copy with a group of encrypted files, and backed up somewhere else.

This scheme allows decryption of the files using either the password or the backup code, and also allows the password to be changed without changing the backup code or reencrypting the files, only the encrypted file key is changed, which is the first few bytes of the encrypted file, or stored in a separate file. It also slows down brute force attacks slightly, thanks to the additional encryption operation.

The scheme would store the 2 encrypted keys with the encryption software, and decrypt the file key from the password when encrypting new files, so that the user or the software does not need to know the backup code. There should be some way of knowing that the file key is decrypted correctly before using it, here is one of many methods:

We have a 16B random plaintext block $P_r$, and a known hash of $E_{kf}(P_r)$. Once the password key is derived we generate:
$kt = D_{kp}(E_{kp}(kf))$
$ht = Hash(E_{kt}(P_r))$
Then $ht$ is compared to the known hash, a match means the password is correct. This may seem a little more complex than just comparing it against an encrypted copy of the block, but it eliminates a plaintext/ciphertext pair an attacker could use for key recovery attacks.


Concatenation of multiple shorter hashes vs a single long hash

TL;DR: We don't know how secure your construction is with regards to collision resistance. We do however know that it isn't a cryptographically secure hash.

  I permanently need to hash lots of data quickly, but the result only needs to be collision resistant ... So I do not even need to really use "cryptographic" hashing algorithms (CRC32 is perfectly fine here I guess).

If you require collision resistance you generally require a hash with large output. CRC32 would certainly not be fine. You would normally use a cryptographic hash to achieve this; you definitely need a large output size of the hash (i.e. 160 bits or over).

  Is there any negative side-effect of using multiple (say 2) algorithms providing a shorter digest (e.g. RIPE-MD-128 and Tiger128) versus using an algorithm providing a digest of the added length (e.g. SHA256).

Well, yes, it won't provide as much security. How much less may be tricky to calculate though. MD5 and SHA-1 concatenation was used by SSL for a while. However, a paper by Antoine Joux: Multicollisions in Iterated Hash Functions has shown that these constructions aren't very secure when it comes to finding collisions. If the input cannot be manipulated then the chance of a collision happening should still be high though (i.e. finding collisions implies an active attack).

  More specifically my idea is to use multiple REALLY FAST algorithms (clhash performing at over 4 gigabyte per second on my testsetup, xxhash performing at over 6GB/s, ...) and simply concatenate them to improve collision resistance.

You don't use any cryptographically secure algorithms, so the result is unlikely to be secure as well. At the very least it is probably impossible to prove security as the algorithms may be mathematically linked somehow.

With regards to collision resistance: it is likely that it will provide about 192 / 2 = 96 bits of resistance in case active attacks are not considered. It would be very hard to provide that it does because the algorithms may be somehow related.

It could be equally hard to find a way of showing that it does not provide 96 bits of resistance as proving that the algorithms are related may be hard as well.

A method of speeding up hash calculations is to use a Merkle- or hash tree. This will enable parallel processing to calculate the hash values.


Say $F_K(x)$ = $M \bmod K$.

Then after $K$ is announced choose arbitrary $M$ and compute $M' = M + K$.


What does signed fixed window method mean in ECC?

In the basic fixed window method of performing point multiplication, we compute the value $nP$ (where $n$ is the integer we're multiplying by, and $P$ is the basis point) by finding the base $b$ representation $n = d_k b^k + d_{k-1} b^{k-1} + ... + d_1 b^1 + d_0 b^0$ (where $0 \le d_i < b$), and then computing first $1P, 2P, ..., (b-1)P$ and then $nP = d_0 P + b ( d_1 P + b ( d_2 P + ... + b(d_kP))) ...)$ (where the computation of $d_iP$ is done by a lookup of the precomputed values).

There are a number of tweaks we can do to that basic method, but most of those are irrelevant for this discussion.

One is, not, though.  It turns out that Elliptic Curves has one cheap operation that the group $Z_p^*$ does not; it is cheap to compute the inverse.  So, one improvement to this basic method we can do is represent $n$ in balanced notation, where we allow negative digits; $-b/2 \le d_i \le b/2$.  We then compute the values $1P, 2P, ..., (b/2)P$, and then when we need to do a lookup of a value $d_iP$, and $d_i < 0$, we just use the value $-(-d_i)P$, which is a lookup and an inverse.

What this allows us to do is double the size of $b$ at essentially no cost; the table we need to precompute is the same, and the number of additions we need to do is reduced.


Multi-secret sharing (Packed secret sharing) - Some questions

I believe there is a typo in the paper: instead of $k$ elements $a_1, \dots, a_k$ there should actually be $n$ fixed public elements, i.e. $a_1, \dots, a_n \in \mathbb F$. To secret-share, first determine $p(x)$ based on the dealer's secrets. Then, give $p(a_i)$ to player $i$ for each $1 \leq i \leq n$.


Can we use witnesses generated by OpenSSL's Rabin-Miller primality test to help factorization?

does that mean that OpenSSL has found a strong Rabin-Miller witness?

Yes, it does.

  if we could get OpenSSL to output the witness(es), how might that help us in the factorization of the value?

No, it wouldn't help; for most composite numbers, the vast majority of values are Rabin-Miller witnesses (it's provable that at least $\frac{3}{4}$ always are, but for most composites, the ratio is very close to 1).  By far the most frequent for the Rabin-Miller to claim compositeness is that the random value $x$ is a value for which $x^{n-1} \ne 1 \bmod n$ (and so you never hit a 1 or a -1 in the sequence); such a value $x$ proves that $n$ is not prime, but gives no indication of the factorization of $n$.  Now, if you found an $x$ for which you fail for the other reason; because Rabin-Miller hit a 1 without hitting a -1 first, such an $x$ would immediately yield a factorization.  However, such values of $x$ occur only extremely rarely in practice.


Why Victor must not know which tunnel Peggy chooses?

The description of this "kid zero knowledge" example follows the strucure of how interactive proofs that are
zero-knowledge usually work:

The prover sends a commitment (walks into one of the two sides)
The verifier challenges the prover (tosses the coin to decide which side the prover should walk out)
The prover gives a response (walks out the side the verifier has told him).

An essential part of interactive proofs that are zero-knowledge which seems to be the source of your misunderstanding is the
zero-knowledge property. This means (informally) that a verifier can efficiently simulate a transcript of a proof without having
access to the prover (and thus only knows the statement to be proven but not the information the prover has) and such
 a transcript cannot be distinguished from a real transcript from a real proof run.

Note that this fact that an interactive proof is efficiently simulatable without having access to the prover, nicely captures the fact that the proof can not leak any information beyond the validity of the statement to be proven. In a real interaction, the verifier can be convinced that the prover knows what he wants to prove, but the transcript can not leak any further information since it can be efficiently simulated. So this idea of indistinguishability of real and simulated transcripts is a nice way of formally modeling the zero-knowledge property.

So now lets look at your example:

  Let's try a much simpler experiment. Victor and Peggy walk together down the primary tunnel until the fork. Peggy goes alone in one side and come out the other. Victor did not hear the secret to open the door, but he is now convinced that she knows it. Peggy presented a proof of her knowledge without Victor learning anything apart the fact that Peggy has this knowledge.

In this example you CAN NOT simulate such a protocol without having access to the prover. You will never succeed in
producing such a transcript without having access to the party knowing the secret (PIN).

However, in the original example you can just throw away all the runs of the protocol where the verifier wants the
prover to come out the other tunnel (where the coin toss does not yield the same choice as Peggies choice for the tunnel to walk in) and only keep those where Victors coin toss says that Peggy has to come out the same tunnel she went in
(and thus does not have to know the secret).

Your other approaches

  Victor sends a plaintext to Peggy and ask her to send it back signed with her secret key. He verifies the result with Peggy's public key. Proof that Peggy has the private key.

As in your modified Alibaba example, you cannot simulate a transcript without having access to the prover (who knows the signing key - assuming that
you work with a secure signature scheme).

  Victor encrypts a piece of data with Peggy's public key and asks Peggy to send back the hash of the data. If the hash match, he has a proof that Peggy knows the private key.

This protocol is efficiently simulatable, but you would have to prove all properties required by zero-knowledge proofs to hold that you can show that it is an interactive proof that is also zero-knowledge.


No, it is not safe to authenticate the BIOS in that way. CRC should be used as checksum only, i.e. to avoid random bit flips. For larger random changes you should use CRC32 at the minimum.

If you want to protect against malicious change you need a cryptographically secure hash. the reason for this is that any attacker can create a malicious BIOS that calculates to a particular CRC.

SHA-1 is under attack although it is not broken yet. If it is broken, it will be broken exactly for the purpose you are using the hash though. So it is better to upgrade to SHA-256 and/or SHA-512 (whichever is faster on your machine).

Note that cryptographic hash functions do not take a key. So for authentication you need additional measures. You could rely on signature generation (e.g. PKCS#1 v1.5 padding + modular exponentiation for RSA) or - for symmetric keys - a HMAC. Both of these rely on an underlying hash function for security. With HMAC you could use SHA-1 by the way.

As lightweight software hash Blake2b is often mentioned here, but this requires a bigger understanding of hash functions. If possible stay with SHA-2.


Getting a random number on an STM32L0x1 device for SRP6a

Would a "bad" random number seed (like reading values from ADC) negatively affect the security of SRP6a?

Yes. At least, a reused random on the server side enables replay of a captured session. On the client side, I think (without detailed analysis) that a predictable RNG can be used to extract secret information allowing login, or even the password if it is weak.

How to get a "good" random number (random enough for SRP6a) on STM32L0x1?

That's a generic microcontroller with 32-bit CPU, RAM, Flash, EEPROM, ADC. This gives at least two options:

The one outlined in the question: use a Cryptographically Secure Pseudo Random Generator, seeded with a secret random value at factory, and it's state kept in permanent memory (e.g. EEPROM) from one invocation to the other. The difficulties are

Keeping the state secret (including, setting it up initially). If an adversary can use a JTAG port, poof goes security. There are other avenues of attack, e.g. power analysis.
Going from one state to the other atomically including in the event of power loss, perhaps at a moment chosen by an attacker. That's EXTREMELY difficult. That's significantly easier with RAM, if there is a battery backup of that.
Update per comment: problem with atomic EEPROM update is that the underlying hardware does not provide it. When a byte erase or write gets interrupted by a power loss, what's read there (until another erase or program) is unspecified. Experience shows that it often is neither the old nor the new value, and sometime varies from one re-read attempt to the other, as a function of power supply voltage or temperature, and time. This is because individual bit cells of the EEPROM byte are left incompletely erased or written, giving no noise margin to the read comparator. Reliable atomic update is possible despite that, but hard to get right and test well. A prerequisite is to obtain some assurance that physically re-erasing (and/or over-programming) a byte that appears erased or (successfully programmed) is possible, rather that blocked by some driver (or worse hardware) trying to reduce EEPROM wear.
EEPROM eventually wears, and perhaps adversaries or just Murphy will induce repeated updates. I've witnessed contactless Smart Cards powered-up and activated with a sub-second cycle merely by being stored next to an NFC mobile phone, and have heard mildly credible anecdotes of bank Smart Cards destroyed in the process.
Choosing the CSPRNG correctly; not the hardest!

Leveraging some physical source of randomness, e.g. sample the 12-bit ADC (it can run at over 1 M sample/s) and post-process that (e.g. feeding enough samples into a hash and using the result as the random). The hardware can boil down to a single trace connected to an existing point at an appropriate voltage. The main difficulty is evaluating the appropriate number of samples, which can vary depending on environment (in particular temperature, nearby EMI source). Taking a lot of headroom is good, but often not enough: if an adversary has some level of access to the hardware, the approach often can be made to fail (e.g. by forcing the input of the ADC to a slightly higher voltage than the maximum, thus making the output of the ADC fixed to all-one; or by pouring liquefied gaz, lowering the temperature dramatically, making the ADC malfunction or/and reducing the amount of noise).

The two approaches can be combined, making a successful attack more difficult. But designing a robust random number generator, especially when an adversary has access to the device, is notoriously difficult.


RSA - What's to stop someone from using the same ciphertext to mimic private key holder?

If Alice is sending the encrypted messages then her public key isn't involved at all. She encrypts the messages for each recipient's $(n, e)$ pair individually, and sends them tailored messages.

In reality she probably sends the message encrypted with AES and only uses RSA to send each recipient their copy of the decryption key, a la PKCS#7's EnvelopedData.

The recipients have no way of knowing that the message actually came from Alice in this scheme. What she needs to do is sign the message (post-encryption, for best results), which does use her private key.

At this point, as you observe, there's still a replay vector. So the message would need to contain some way of identifying its freshness. A monotonic time stamp is an easy way, a monotonic message counter is another, or some sort of pre-arranged keyword from a shared code book (if you like whimsey).

So the recipient does:

Verify the integrity of the ciphertext and encrypted key using Alice's public key. (Prove it was sent by Alice)
Decrypt/derive the message encryption key using their private key.
Decrypt the ciphertext to reveal the original message.
Verify the time stamp / counter. (Prove it isn't a replay)
Respond appropriately to the contents.

The time stamp could have been signed but not encrypted, it just depends on whether or not that is itself sensitive data.


This can be trivially achieved by sharing twice.
First share your secret $S$ using a $2$-out-of-$2$ secret sharing scheme into $S_1$ and $S_2$. (E.g. choose $S_1$ at random and set $S_2:=S\oplus S_1$.)

In the next step you now share $S_2$ using a $(k-1)$-out-of-$(n-1)$ secret sharing scheme into $S_{2,1},\dots,S_{2,n-1}$.

Give $S_1$ to $P_1$ and $S_{2,i}$ to $P_{i+1}$ for $1\leq i <n$.

The secrecy of the $2$-out-of-$2$ secret sharing scheme guarantees that both shares $S_1$,$S_2$ are required. $S_1$ is only known to $P_1$, and $S_2$ can only be recovered by at least $k-1$ of the other parties collaborating.


Information Theoretic Oblivious Transfer?

It is impossible to achieve (fully) information theoretic oblivious transfer (OT), since OT is complete (and so can compute all functions). Since many (most) functions cannot be securely computed information theoretically with two parties, this means that it's impossible. Having said that, we do have OT protocols that provide information-theoretic security for a corrupted sender and computational security for a corrupted receiver, and other OT protocols that provide information-theoretic security for a corrupted receiver and computational security for a corrupted sender.


Yes, using random.org to randomly select students is appropriate, since random.org creates truly random numbers from atmospheric noise.
But for cryptographic purposes you shouldn't rely on random.org as this post explains.


Will two KEK's provide the same KCV or should these be different?

The KCV generally consists of a single encryption of a block of all zeros using the key itself - and then taking a number of leftmost bytes, usually displayed as hexadecimals.

That means that the KCV doesn't change. The whole idea of a KCV is that it is deterministic; if it would be different for an identical key then it would lose its function.

Note that I didn't see any KCV calculation in the EMV specifications. Other methods may use e.g. a hash over the key value - but this isn't common. So in the end it depends on how it is specified outside of the EMV standards - if at all. However, the KCV should only be determined by the key value.

For 3DES keys the usual encryption of a zero block makes more sense, as some implementations ignore the parity bits, while others do not. This means that a functionally identical key could lead to different KCV values if hashing would be used. The KCV of 3DES keys that only differ with regard to the parity bits will be identical.

However, the use of a zero valued block encryption is dangerous as well: if a zero block encrypt is ever used in the protocol then the KCV will leak information about the value (e.g. when CTR mode encryption is used with a zero IV).


Linear functions when expressed as polynomials only have terms of degree 1 or 0.  Non-linear functions have at least one term of degree 2 or higher.  For example, here is a linear boolean function: $y = ax + bz + c$, where $y$ is the output bit, $x$ and $z$ are input variables, and $a$, $b$, and $c$ are constants. Notice that none of the variables are multiplied by each other -- they are only ever multiplied by constants in a linear function.

But with non-linear boolean functions, there can be terms with more than one variable in them, e.g.: $y = axz + bx + c$.  The number of variables in a given term (including when a variable is multiplied by itself) determines the 'degree' of that term, so in this example there is a term of degree two in the polynomial.

Edit to add: So your question is now what is the Hamming distance?  Take two strings of equal length and xor them together, then count the number of 1's in the resulting string -- the more 1's, the greater the 'distance' between the two strings.  When you take the truth table of a non-linear function (truth tables can be thought of as just another binary string) and the truth table of any linear or affine function and xor them together, there will always be at least one 1 in the result, no matter which linear or affine function you are comparing the non-linear function with.  The greater the 'distance' from all linear functions, the more non-linear the function.


Does XORing a random block into a layer of CBC encrypted message add some bit strenght?

In general: No.
You have to assume the attacker knows what you are doing. That's Kerckhoffs' principle.
If your random blocks are actually a real One-Time-Pad on top of the block cipher, then it would be stronger - but you could achieve the same without the block cipher. If all your blocks use the same pad, this is true if the length is 1 block,  the pad is truly random, only used once and communicated using another secure channel.
If you just mesh different things together to make it more complex - that does not add security at all.
As a side note: The IV in CBC is not secret. If you consider it secret, you need to clarify how the sender and receiver both know it. And following that - do you consider that secret as static and reuse it? That would violate the requirements of an IV.


How can one detect if a hash function doesn't have a full image?

No, you can't tell whether $H$ has a full image or not in a reasonable amount of time, if $n$ is large (say, $n\ge 160$).  Distinguishing the case where its image is of size $2^n$ vs of size $2^n-1$ would require on the order of $2^n$ evaluations of $H$, which is infeasible for normal values of $n$.

No, you can't distinguish $H$ from $H \circ H$ in a reasonable amount of time, if $n$ is large (say $n\ge 160$) and you have no information on $H$.  Distinguishing the two requires on the order of $2^{n/2}$ evaluations of the black box ($F$), which is infeasible for normal values of $n$.

The technical fine print:
I am assuming you are asking about generic attacks, i.e., black-box attacks, where we can only evaluate the function at points of our choice but are not given any information about its internal structure.
If you know the internal structure of $H$, you might be able to prove something, but this requires more than a black-box attack (more than simply evaluating $H$ on some values of your choice and looking at the output).  For instance, it is easy to distinguish $\text{SHA256}$ from $\text{SHA256} \circ \text{SHA256}$ in a single query, for trivial reasons: send the input x to your black box, and if you get back 2d7116..81, you're dealing with $\text{SHA256}$, otherwise you're dealing with $\text{SHA256} \circ \text{SHA256}$.  But this is not the kind of attack you are talking about.