This was pretty vexing, but for some reason I could only create the "big endian" results given by table 2 in this paper.

I get the same result as you for the first message ($M.$N0) : 8da3a17b43e0e134bdc17557ffef15ff and a different value for the second message.

The following code seems to work for a test vector given in table 2:

<?php

$M0='02dd31d1 c4eee6c5 069a3d69 5cf9af98 87b5ca2f ab7e4612 3e580440 897ffbb8
         0634ad55 02b3f409 8388e483 5a417125 e8255108 9fc9cdf7 f2bd1dd9 5b3c3780';
    $M1='d11d0b96 9c7b41dc f497d8e4 d555655a c79a7335 0cfdebf0 66f12930 8fb109d1
     797f2775 eb5cd530 baade822 5c15cc79 ddcb74ed 6dd3c55f d80a9bb1 e3a7cc35';

$N0='02dd31d1 c4eee6c5 069a3d69 5cf9af98 07b5ca2f ab7e4612 3e580440 897ffbb8
         0634ad55 02b3f409 8388e483 5a41f125 e8255108 9fc9cdf7 72bd1dd9 5b3c3780';
    $N1='d11d0b96 9c7b41dc f497d8e4 d555655a 479a7335 0cfdebf0 66f12930 8fb109d1
     797f2775 eb5cd530 baade822 5c154c79 ddcb74ed 6dd3c55f 580a9bb1 e3a7cc35';

function convert2binary($D) {
      // removes whitespace
      $D = preg_replace('/\s+/', '', $D);
      // reorders 4 bytes at the time
      $D = preg_replace('/(..)(..)(..)(..)/', '\4\3\2\1', $D);
      // hex2bin for older PHP
      $D = pack('H*', $D);
      return $D;
}

$M0 = convert2binary($M0);
$M1 = convert2binary($M1);
echo md5($M0.$M1) . PHP_EOL;

$N0 = convert2binary($N0);
$N1 = convert2binary($N1);
echo md5($N0.$N1) . PHP_EOL;

?>

Which should show the result:

a4c0d35c95a63a805915367dcfe6b751
a4c0d35c95a63a805915367dcfe6b751

I took the liberty to perform the padding manually. There seems little need to creating a specialized method for this (and my PHP skills leave something to be desired).

Note that cryptographers are often pretty sloppy when it comes to these kind of things, the test vectors don't seem very well defined (but at least they are documented).


Block cipher with key longer than block size

A block cipher processes a single block of input and produces a single block of output, where the input and output blocks are the same size. By the pigeonhole principle, if the key size is larger than the block size then there must be some keys that will encrypt the same input block to the same output block.

More formally, a block cipher is defined as the family of encryption functions $E: K \times X  \to  X$ (and their inverse decryption functions), where:

$K$ is the set of possible keys with cardinality $|K|$.
$X$ is the set of possible block values with cardinality $|X|$.

The cardinality (number of elements) of these sets is $2^b$ where $b$ is the length of an element in bits. For example for a 256 bit key, $|K|$ is $2^{256}$ and for a 128 bit block, $|X|$ is $2^{128}$.

If you think of setting the key for the block cipher as fixing the value $k \in K$ to produce a function $e(X) \to X = E(k,X)$, then it's obvious that there are $|K|$ such functions.

It's then easy to see that if $|K| > |X|$, there are more possible encryption functions than there are possible output values, and so for any $x \in X$ there must exist (at least) two keys $k_0 \in K$ and $k_1 \in K$ where $E(k_0,x) = E(k_1,x)$. For a good block cipher, the number of such keys will be very low.


Does it make sense to have long SSH Key with shorter Passphrase?

You're not modeling what information the attacker has.  The strength of the system only reduces to that of the passphrase if the attacker has a copy of the passphrase-encrypted private key.  If they don't, then the strength of the system is the strength of the private key.

You're not supposed to let your passphrase-encrypted private key file fall into adversarial hands.  The passphrase is providing a fallback in case that condition is violated.

Note that the passphrase is optional, and that there also exist non-passphrase mechanisms for protecting the private key. OpenSSH supports using smartcards instead of private key files, and there are apps for smartphone-based SSH authentication, where the private key is protected by the device's hardware.


How to calculate the odds of finding "20" at least three times in a sha256 string?

If we assume that the output of a SHA-256 hash is roughly random, this is ultimately just a combinatorics problem.  That is:

Given a random string of 64 hexadecimal digits, what is the probability that the sequence "20" appears 3 or more times.

We can think of this as having three set items, the three "20"s, and then 58 other hexadecimal characters distributed around them.  That gives us four spots to put the rest of the numbers:
$$ X_1\ |\ 20\ |\ X_2\ |\ 20\ |\ X_3\ |\ 20\ |\ X_4 $$
Where $X_n$ is a string of hexadecimal digits with size ranging 0 to 58, with $\sum_{i=1}^n len(X_i) = 58$ and "|" denoting concatenation.
After seeing kodlu's answers I figured I would include a more complete answer.
The above ultimately led me down the path of counting all possible 58-hexadecimal-digit strings and then counting the ways we can "insert" the 20's throughout it.  The number of random strings is $16^{58}$.  We can insert 20's at the beginning or after any of the digits, and there are 3 inserts required.  Since we want to allow repetitions (sections without any digits between the 20's) we want ${58 + 3 - 1 \choose 3} = {60 \choose 3}$ (see combinations with repetition).  Dividing that by the total number of SHA-256 hashes, we get:
$$ \frac{16^{58} \cdot {60 \choose 3}}{2^{256}} \approx 0.00203967 \approx ~0.204\% $$
Just to see if this made sense, I ran a quick test using bash to see how this panned out:
#!/bin/bash

function next() {
    head -c 32 /dev/urandom | xxd -p -c 64
}

total=100000

count=0
i=0
while [[ $i -lt $total ]]; do
    next | grep -q "20.*20.*20" && let count="$count+1"
    let i="$i+1"
done

echo "$count / $total"

I ran this a few times and got:
$$175 / 100000 = 0.175 \%$$
$$200 / 100000 = 0.200 \%$$
$$187 / 100000 = 0.187 \%$$
So this seems about right.

A couple notes on the properties of this.  As kodlu mentioned, since "20" is not symmetrical, we don't have to worry about things like "FFF" potentially counting as two instances of "FF" if that's what we were looking for.  However, if we don't want to count that as two, my approach should still work, even if we were using a symmetric target string like "FF" or "00".
Also, since we are looking for "at least" 3 occurrences of "20" in the string, we don't have care about whether any of $X_1, ..., X_4$ contain a 20, those are just extra.  In fact, this is exactly why this approach works.  That said, we may end up double counting in cases where our variant placements of 20s don't really change the ultimate string.  For example, if the 58-digit string is "202020202020..." there are many places we could insert our three "20's" without actually changing the resulting string.  Accounting for that could prove tricky, and I'm not sure how to do so at the moment, but given the extremely large number of cases we're looking at I'm inclined to think this is probably relatively small.  Although it's not hard to come up with other examples, so caution is good.  Regardless, this type of thing is exactly why I wanted to include a more empirical approach (i.e. brute-force counting with code).
On that note, I decided to run another, longer test (with 1,000,000 values) to see if it might be closer to my updated probability than my original one.  Or at least further confirm that we're in the right ballpark.  I got:
$$ 1797 / 1000000 = 0.001797 = 0.1797 \% $$
So, for what it's worth, it seems like the answer is at least "somewhere between 0.17% and 0.20%."


Is it possible to get better randomness by using multiple PRNGs?

There are many ways to combine random number generators:

XOR the outputs. Very simple and fast. If they are independent and at least one is strong, the output is strong as well. However, if those assumptions are not true, this can be very broken.
Hash the outputs. With a strong hash you combine the entropy of both. Good if the RNGs have some entropy, but their output is not uniform. Can be significantly slower, if your RNGs are fast.
Seed one using the other. Mostly used for seeding a CSPRNG with a true RNG. If the former is weak or the latter doesn't have enough entropy, the whole is weak as well.
Entropy pool, with multiple inputs combined into a large state, which is iterated to produce the next state and hashed to produce output. Can include pseudo-random inputs, but a normal PRNG is not a good input.

In practice, if you have a CSPRNG, seeding with a random number (3.) is the only one you should be concerned with. If you have poor, non-cryptographic PRNGs, no games you play with the outputs will get you anything better than (or usually even as good as) simply moving to a CSPRNG.

An entropy pool is usually already available in the OS (/dev/urandom or CryptGenRandom), so there are few situations where you should go there yourself. Number 2. is often used in TRNGs for whitening, but that too is not something you should usually need to be doing in software. Maybe, if paranoid about the design, you could be seeding two completely different CSPRNGs with true entropy, then XORing the outputs, but then you are trusting on them to really be independent.


decrypting el gamal encrypted messages in regards to k being used

A sends two messages E(m) and E(2m), but uses a different random k each time. i think she should be worried, but the second message is still safe.

We needn't be worried at all (unless we're concerned about the feasibility of the attack that recovered the first message).  If a decryption of one message allows you to break an unrelated message, then El Gamal itself is broken.  That is, if we have a magic box (called an Oracle in crypto-speak) that, given a public key, an encrypted message with its decryption, and a second encrypted message, and that magic box is able to produce the decryption of that second message, then we can break El Gamal.

Consider this: the attacker (who has such a magic box) gets an encrypted message C to B, which he wants to decrypt. Here's what the attacker can do: he generates a second message, and then encrypt that with B's public key.  Then, he has all the necessary inputs to the magic box, and the magic box will produce the plaintext of the C.  We don't believe that there's such a feasible way to decrypt encrypted messages with just the public key, and so we don't believe there's any such magic box.

  A sends two messages E(m) and E(2m), but uses the same random k for both messages. however, C doesn't know that she didn't change this random value.

Actually, C can easily see that the same $k$ value was used; part of the ciphertexts is the value $G^k \bmod p$; because that value depends only of $k$ (and the group parameters $G, p$), that value will be the same in both ciphertexts.

In addition, assuming that the two messages were to the same public key, if he knows one message, he can easily recover the other.

That's because the other parts of the two ciphertexts are $H^k \cdot M \bmod p$ and $H^k \cdot M' \bmod p$ (where $k$ is the shared $k$ value, and $M, M'$ are the two messages).  If he divides the two (modulo $p$, the operation of performing modular division is considerably different than division in the reals), and multiply the message $M$ he knows, he gets $M \times (H^k \cdot M') / (H^k \cdot M) \bmod p = M \cdot (M' / M) \bmod p = M'$


One of the issue in sending out the XORed value is to disclose the PSK length

This is only an issue if you consider the length of the PSK to be a secret and not just the value. In that case you probably should redesign your system to not depend on the length of the PSK being secret, e.g. by always sending an upper-length PSK and also sending the amount of bytes used if you need secret variable length.

  The only way to crack this should be brute forcing, correct?

Assuming an adversary only gets to see $K\oplus B$ with $K$ being your PSK and $B$ being the one-time buffer, this is a one-time pad and an adversary cannot infer anything about the PSK they didn't already know. In particular an adversary cannot infer the concrete value. However this guarantee is void if the same buffer $B$ is used more than once - even with the same key as then the adversary knows the key has been re-used which you may or may not want to leak. And of course note that receiver of this value also has to know $B$ which at this point becomes a one-time-use PSK itself which begs the question why one doesn't use $B$ as the key directly potentially with a more standard symmetric key-exchange protocol to get a fresh session key - which can be as simple as encrypting a monotonic counter and a new key under the PSK.


Feistel networks were broken in DES but not triple DES. Some final AES candidates not approved also used Feistel networks $2^{36}$ plain text attacks. Reduction of $2^{16}$ possible keys for single DES: $4^{48/6} = 4^{8} = 2^{16}$.

First for a one round Feistel network: $R_0$ and $f (R_O, k_1) = R_1 \oplus L_0$, $k_1$ becomes known.

For two round Fiestel: Use the same method twice: $$(R_0, f(R_0,l_1)=L_2 \oplus L_0) \ (L_2,f(L_2,K_2)= R_2 \oplus R_0)$$

A nice reference would be CryptoLecture 04 (PDF) from Daniel Boneh's crypto course on Coursera.


Calculating amount of time for brute forcing ciphertext depending on the size of the key

Your approach is too simple to give an accurate rating of the cryptographic systems. For any system that does not inherently suffer from short key lengths it is first and foremost its resistance to cryptanalysis that makes or breaks it.

The Vigenère cipher for instance is hundreds of years old and can easily be used with a very long key if so desired. That however does not prevent it from being a very poor algorithm by modern standards. It leaks so much information that if you know what to look for and have a decent length of message to work with you don't even need a computer to break it.

There can be no single way to compare wildly different cryptographic schemes, the very nature of their weaknesses differ. The best thing you can do is to list the requirements for breaking a given scheme, like:

Vigenère cipher:

A guess about the contents and words likely used in the message.
One or more messages using the same key, combined at least around double the length of the key.
A person who is reasonably good at performing basic algebra.
Some hours of that person's time.

Or:

One or more messages using the same key, combined at least around double the length of the key.
A person who understand and can use pattern frequency analysis of the language in which the message is composed.
Some days of that person's time.


I'll precisely define the problem, and propose a solution based on AES-128, requiring about 13 instructions on many modern CPUs for something academically secure in a model where the hashes leak, down to about 8 instructions if we trust my intuition that we can in practice reduce the number of rounds in a model where only the number of collisions leaks.

It is asked a function changing a 64-bit input $m$ into an hash suitable as primary index in a hash table, avoiding malicious choice of $m$ intentionally causing collision at that stage (we ignore later collision resolution). The number $n$ of hash table entries is a public parameter, with $\log_2(n)\ll64$, perhaps $\log_2(n)\approx24$ (good for 16 million entries in the table). The function will also have a secret key parameter $k$. We'll note $h=f_{(n,k)}(m)$ where $f_{(n,k)}$ is the desired function, $m$ is the 64-bit input, and $h$ is the hash output, with $0\le h<n$. Evaluation of $f_{(n,k)}$ for additional values of $m$ must be fast, and compact (it is duplicated many times to avoid function call overhead).

The minimum desired security property, handling counting of collisions by timing measurement, is that an adversary not knowing $k$ (because it was chosen randomly at hash table creation, and not revealed) and able to choose up to $n$ distinct $m_u$, can can not cause significantly more collisions than for a random choice of function $f$, with knowledge when choosing $m_u$ of the number of collisions for each $v<u$, that is of the number of $w<v$ with $f_{(n,k)}(m_v)=f_{(n,k)}(m_w)$.

A simpler and stronger security property, handling the case where the results of an in-order hashtable traversal are leaked, would be that the adversary can not distinguish $f_{(n,k)}(m_u)$ from random, including in an interactive setup where the adversary chooses $m_u$ with knowledge of $f_{(n,k)}(m_v)$ for each $v<u$.

The stronger security property is met by any MAC reduced modulo $n$; that however is neither fast nor compact if we chose, say, HMAC-SHA-256. But if there is hardware support, a good option, also secure with cryptographic certainty under the stronger security property, is to built the MAC around AES-128:

pad $m$ to 128-bit (e.g. with zeroes)
apply AES-128 encryption with key $k$
reduce result modulo $n$.

Note: that works fine for $m$ of any fixed size up to 128 bits, or $m$ of variable size up to 127 bits with some injective padding to 128 bits.

For even more speed at the expense of academically recognized security, we can arguably reduce the number of AES rounds, from 10 down to some debatable minimum, perhaps 5 if we are content with the minimum desired security property handling timing attacks only (I would not consider 4 without extra precautions, see note below). That's not conservative; but getting to know only the collisions rather than the AES ciphertext, for a limited number of queries, make things hard for the adversary.

If the CPU has the AES NI instruction set, $r\le10$ AES-128 rounds cost $r+1$ instructions (one initial pxor, $\max(r,9)$ aesenc, and when $r=10$ one aesenclast) which can each reference a pre-computed AES 128-bit subkey stored in memory at initialization of the hash table.

For simplicity and speed, and when $n\ll64$, the reduction modulo $n$ can be made over only half of the AES result, with only minor security impact (entries at the end of the tables will be slightly less hit). Modern 64-bit CPUs compute the remainder of the division of a 64-bit quantity by a 32-bit quantity with a single instruction.

Note: when we push things towards speed and heavily venture in the round reduction route, it seems worthwhile to slightly bend the problem definition by choosing $n$ odd (or better $(n\bmod8)\in\{3,5\}$), which allows the reduction step modulo $n$ to add some final diffusion; and, assuming we can keep the exact choice of $n$ secret (including: the adversary can not reliably measure our allocated memory), choose $n$ random in a small public interval (like from the targeted $n$ to 105% of that), in order to make that extra step keyed.

If we want something that can be coded in portable C, or without aesenc, we'll want to replace AES with some other primitive, likely of the ARX variety; considerations impacting its choice include compiler support for wide wordsize and fast rotation.


Why in one time pad must the key distribution to be truly random

For an OTP to provide perfect secrecy it is required that the key stream is indeed purely random. A pure OTP is largely a theoretical construct because it is almost impossible to generate a key stream that is provably random. Any kind of information on the key stream may leak information on the plaintext, which means it is not perfectly secure. Practical OTP's that provide close to perfect secrecy on the other hand are, on the other hand, relatively common, see the comment from Paul below my answer.

Note that leaking information does not necessarily mean decryption; for instance if I encrypt the same message twice with a block cipher you won't know the input, but you can tell that the same message was encrypted because the resulting ciphertext blocks are identical. Any kind of information about the plaintext is enough for perfect secrecy to be broken.

Of course it is perfectly possible to use a pseudo random stream while maintaining practical security. Basically, this is what a stream cipher or block cipher in stream mode (e.g. CTR mode) does. However pseudo random streams indicate that there is some kind of mathematical relationship between the bits of the key stream. And this could be exploited by an attacker. The fact that such a relationship exists in itself is enough to break perfect secrecy.

There are obviously secure stream ciphers right now. We can however not prove them secure. So we cannot guarantee that they won't be broken in the future. Hence the perfect security premise doesn't hold, so they do not represent OTPs. Fortunately, if they are secure enough they don't need to.

It is possible to use a PRNG to create a practically secure key stream. PRNG and stream ciphers are closely related. Stream ciphers however have been especially designed to provide this functionality; they have advantages with regards to the API (treating the input key as key, having an explicit IV) and efficiency.

Beware that some random functions in programming applications may have implementations of PRNG's that are definitely not suitable for this kind of functionality. The shenanigans around "SHA1PRNG" in Java / Android should provide enough of a warning to anyone.

Way TL;DR: use a secure stream cipher


Encrypted key- determining type and properties

In general, if the file has been encrypted using a secure modern cipher and contains no metadata to indicate the encryption method used, you cannot determine the method just by examining the file.  See e.g this answer by Thomas Pornin for more information.

At best, the size of the file may put some constraints on both the length of the encrypted key and on the encryption method used (since different encryption methods have different amounts of overhead), but such constraints are necessarily rather broad.  If you know that the file is very old (say, from the 1980s or earlier), that may also narrow down the possible options.

Probably your best bet, however, in the absence of actual documentation about the encryption used, is to try to reverse engineer the software (or hardware!) that knows how to encrypt and/or decrypt the key file.  After all, something must know how to decrypt the file, for it to be of any use to anybody at all.


Should text be hashed before being used as an encryption key?

Considering that someone will probably end up supplying a password for that argument at some point, it would be better to use a proper slow key derivation function like pbkdf2/scrypt/argon2.

Even if they don't end up sticking a password in there, meaningful/arbitrary text and passwords should be treated the same in regards to an adversary's ability to guess the string. If the string is not actually a random value - meaning it's not the output of /dev/urandom - then it will not have 8 bits/byte of entropy, parts of it are guessable, and it should not be used directly as a key. Hashing an easily guessed value with SHA256 does not make the result unguessable - all it will do is make the output more appropriately sized.

Note

With that being said, if the option is available, you should prefer to use pre-existing crypto libraries such as libsodium. They have already handled all of these sorts of details (as well as all sorts of obscure pitfalls, side channels, and other black magic) and produced a succinct interface that more or less removes all of these sorts of questions for the developer.


On an elliptic curve as used in crypto, we can add any two points $P$ and $Q$ of the elliptic curve, yielding a new point of the elliptic curve: $X\gets P+Q$. It holds $(P+Q)+R=P+(Q+R)$, making $P+Q+R$ unambiguous.

For any integer $k>0$ and point $P$, that lets us define $k$ times $P$, noted e.g. $k\times P$, as the result obtained by adding $k$ copies of $P$, that is $k\times P\;\underset{\text{def}}=\;\underbrace{P+\ldots+P}_{k\text{ times}}$

We can efficiently compute $k\times P$ per the following (recursive) method:

if $k=1$ then return $P$
otherwise, if $k$ is even, compute $Q=(k/2)\times P$ and return $Q+Q$
otherwise, compute $Q=(k-1)\times P$ and return $Q+P$

This efficient computation method for $k\times P$ takes time proportional to the number of bits in $k$, whereas applying the definition would take time proportional to $k$. The $k$ used in crypto are often about $2^{256}$, which is many times the conjectured number of atoms in the universe, but the computation still takes a fraction of a second with the efficient method.

Now, consider the problem of finding $k>0$ such that $Q=k\times P$, given $P$ and $Q$. A basic method is to start from $P$ and, while $Q$ is not reached, add $P$. The desired $k$ is one more than the number of additions made. Problem is, that takes time proportional to $k$.

We know better methods that take time proportional to $\sqrt k$. The main ones are baby step/giant step¹ and Pollard's rho². But when $k$ is about $2^{256}$, $\sqrt k$ is about $2^{128}$, and we can't even count to that number: collectively, all the computing devices ever made by man did not count to that, much less made that number of elliptic curve operations.

We know³ no better method than those requiring time proportional to $\sqrt k$, and that explains the difficulty of reversing multiplication on an elliptic curve with the parameters used in cryptography.

Extra meat for thought:

¹ Baby step/giant step works as follows:

chose an $l$ large enough that we'll have $k\le l^2$
store the point $Q_0\gets Q$
for $i$ from $1$ to $l-1$

compute and store the point $Q_i\gets Q_{i-1}+P$ (these are the baby steps)

compute the point $R\gets l\times P$
initialize the point $S\gets R$
for $j$ from $1$ to $l$

search $S$ among the $Q_i$ (this can be done without scanning all the $Q_i$, much like we can find a book in a library), and if there's a match

compute and output $k\gets j\,l-i$, done!

update the point $S\gets S+R$ (these are the giant steps)

² Pollard's rho replaces the systematic search of baby step/giant step¹ by a pseudo-random walk, and replaces the impractically large array $Q_i$ by a detection that the walk goes along an already explored path. The point where the paths merge yields the solution.

³ Q: But why can't we find a better method, when we have efficient methods to solve the similar problem of finding $k>0$ such that $v=k\times u$ given ordinary integers $u$ and $v$ ? $k$ is the quotient of $v$ divided by $u$ in Euclidean division, and that's feasible for numbers with million bits.
A: Euclidean division relies on comparing integers and finding the smallest, for a definition of smallest compatible with addition, in the sense that if $a<b$, then $a+b<a+c$. But there can't be any such notion of order on a large but finite set like an elliptic curve as used in crypto, hence Euclidean division won't cut it⁴.

⁴ Q: But that argument does not hold water! We have efficient methods to solve the similar problem of finding $k>0$ such that $v=k\times u$ given $u$ and $v$ when working in some large but finite sets. For example, in arithmetic modulo $p$, there's a systematic method published in 1621 by Bachet, using an extension of the so-called Euclidean algorithm, which uses Euclidean division.
A: This does not cut it either, but for a different reason: in arithmetic modulo $p$ and all cases where similar methods are known, it is relied not only on addition of elements $a$, $b$, $c$ of the set, but also on multiplying them in a way compatible with the premise that $a\,(b+c)=a\,b+a\,c$ . When in elliptic curve arithmetic we can add points, but not meaningfully multiply them together.


Chaum undeniable signature - justification for probability of misleading the verifier?

OK, let me try to expand on Chaum and van Antwerpen's proofs a bit.  Please let me know if there's still something that doesn't convince you.

I'll start by rephrasing Chaum and van Antwerpen's theorem 1 using your notation:

  Theorem 1: Even with infinite computing power, the probability that Sally can verify an invalid signature $s \ne m^k \bmod p$ is at most $1/q$.

To verify $s$, Victor chooses two random numbers $a$ and $b$ from $\mathbb Z_q = \{0, 1, \dotsc, q-1\}$ (see note below).  However, the important bit is that Sally doesn't know $a$ and $b$; she only sees $c = s^a y^b \in G$.

Now, it's not hard to see that every value of $c$ seen by Sally corresponds to $q$ possible $(a,b)$ pairs: in particular, for any $a$ and $c$, we may solve for $b$ as follows:

$$\begin{aligned}
s^a y^b &= c \\
y^b &= s^{-a} c \\
b &= \operatorname{dlog}_y(s^{-a} c)\\
\end{aligned}$$

(This works because, in a cyclic group of prime order, the discrete logarithm is unique for any base not equal to 1; equivalently, $b \mapsto y^b$ is a bijection, and in fact a group homomorphism, from $\mathbb Z_q^+$ to $G$ for any $y \in G$, $y \ne 1$.  The case $y = 1$ cannot occur, since $k \ne 0$ and $g \ne 1$ by construction.)

Now, assume that $s \in G$ and $m \ne 1$ (which Chaum and van Antwerpen's paper mandates).  Then there exists some $x \in \mathbb Z_q$ such that $s = m^x$.  If $x = k$, then the signature is valid, so an invalid signature must have $x \ne k$.

I'll now show that, if $x \ne k$, then for each of the $q$ different $(a,b)$ pairs corresponding to the $c$ sent by Victor, Sally would have to reply with a different $r$ to have it accepted.  Like Chaum and van Antwerpen, I will do so using proof by contradiction.  Specifically, assume that there exist two pairs $(a,b)$ and $(a^*,b^*)$ corresponding to the same $c$ and the same $r$.  Then:

$$\begin{aligned}
m^{xa} g^{kb} =& c = m^{xa^*} g^{kb^*} &&&
m^{a} g^{b} =& r = m^{a^*} g^{b^*} \\
m^{xa} m^{-xa^*} =& g^{kb^*} g^{-kb} & \text{and} &&
m^{a} m^{-a^*} =& g^{b^*} g^{-b} \\
m^{x(a-a^*)} =& g^{k(b^*-b)} &&&
m^{a-a^*} =& g^{b^*-b} \\
\end{aligned}$$

Taking the base-$g$ discrete logarithm and letting $\mu = \operatorname{dlog}_g(m)$, we get $\mu x(a-a^*) = k(b^*-b)$ and $\mu (a-a^*) = b^*-b$.  Substituting the latter into the former, we get $\mu x(a-a^*) = k \mu (a-a^*)$, and thus $x = k$.  But this is only possible if the signature is, in fact, valid!

Thus, we've shown that, if $s \ne m^k$, any value of $r$ that Sally returns can only be valid for one $(a,b)$ pair.  But since there are $q$ possible such pairs, each of which is equally likely, Sally has only a $1/q$ chance of guessing the correct one.

Note: This proof involves a few corner cases in which the version of the Chaum–van Antwerpen scheme given in the Handbook of Applied Cryptography differs from that in Chaum and van Antwerpen's original paper.

First, Chaum and van Antwerpen explicitly require that $m \ne 1$.  This makes sense, since if $m = 1$, $s = m^k = 1$ regardless of $k$!  I assume this is most likely just an oversight in the Handbook, but it may be important if the message $m$ might be chosen by an adversary.

Second, the Handbook says that $a$ and $b$ should be chosen at random from $\{1,2, \dotsc, q-1\}$, whereas Chaum and van Antwerpen also allow $a = 0$ and $b = 0$.  Admittedly, these are somewhat peculiar cases — in particular, $a = 0$ implies that $c$ (and thus $r$, if Sally is honest) is independent of $s$ (and thus $m$)!  Even so, these cases don't actually present a weakness, since they each occur only with probability $1/q$, and, importantly, Sally can't tell when they occur.

In fact, excluding $a = 0$ and $b = 0$ means that, at least in principle, Sally can exclude two of the possible $(a,b)$ pairs (or one, if $c=1$).  Thus, the maximum probability of verifying an invalid signature may actually be as high as $1/(q-2)$.  Of course, for practical values of $q$, that makes no real difference.

Also note that, in practice, one would usually use the compact representation recommended by Chaum and van Antwerpen, in which $G$ is mapped to $\{1, 2, \dotsc, q\} \subset \mathbb Z_p^*$ by the map $f(x) = \min(x, p-x)$, and the map $f$ is reapplied after any sequence of arithmetic operations in $\mathbb Z_p^*$.  (This works because $p-1 \equiv -1 \bmod p$ is the generator of the order-2 subgroup of $\mathbb Z_p^*$.)  Not only is this representation more compact than naively storing elements of $G$, but it makes it easy to map arbitrary messages to elements of $G \setminus \{1\}$ and avoids issues with bogus signatures outside $G$.


How can we define $\epsilon$-differential privacy for non-deterministic algorithms?

I find that question very interesting. They are arguing that there is not a notion of diferential privacy for all non-deterministic algorithms. Some non-deterministic algorithms could be $(\varepsilon,\delta)$-differential private. But not every non-deterministic algorithm is $(\varepsilon,\delta)$-differential private, they give the example of the algorithm.
Algoritm:
Input: Database $D$
Output: $f(D)$ dropping a row/register from D (non-deterministically), where $f$ is the query function (median,sum,etc).
Note this algorithm is non-deterministic but it is possible to know all the information from the databases if you use this algorithm repetitively. Consider the worst case, the attacker knows all the database except one row (That's why is a condition that $|D-D'|\leq 1$). Therefore you can't guarantee privacy for all or some the rows/registers.


What is a 'secret key factory'? What precisely is it doing?

SecretKeyFactory is a class from the javax.crypto library. This class is used for generating secret symmetric keys. In other words, it generates a SecretKey object from the input key specification (e.g. PBKDF2WithHmacSHA1). Note that your SecretKey instance inherits from java.security.Key which is Serializable and uses a default RAW encoding format.

Hence, you should not just toString() directly. As mentioned by Maeher, there is actually a getEncoded() method which returns the key as a byte array in its primary encoding format for viewing.


Does your embedded device have access to a random input source and a bidirectional channel?

If not, then there will only ever be as much entropy on the chip as you put on it to begin with, so there's no purpose in updating the key.

If so, then just do an authenticated key exchange and generate a new shared symmetric key occasionally.  ECC is best for bandwidth starved devices and lattices are best for computation starved devices.


In terms of marketing hype, that statement rates about a 9 in a scale from 0-10.

The reason is that we don't choose the encryption algorithm based on how many bits the CPU can handle at once.  Instead, we choose a secure algorithm, and then implement it using the resources that the CPU provides us.  There aren't any algorithms we cannot implement on a 32 bit CPU; hence a 64 bit CPU does not allow us to use new ones.

Now, there is a tiny kernel of truth there (and so doesn't rate a perfect 10 on the scale); sometimes a 64 bit CPU allows us to implement an algorithm more efficiently than a 32 bit CPU.  However, the delta is usually not large enough to influence an 'can-we-encrypt' decision.


What is the size of codomain of a function $G(x) = F^A(x) \oplus F^B(x)$, where $F(x) = \text{Keccak-}f[1600](x)$?

Let $\pi$ and $\sigma$ be two independent uniform random permutations, and $f$ a uniform random function.  The best advantage of any $q$-query algorithm to distinguish $\pi + \sigma$ from $f$ is bounded by $(q/2^n)^{1.5}$[1].  In this case, the expected fraction of distinct outputs of $\pi + \sigma$ can't be too far from the expected fraction of distinct outputs from $f$, which is $1 - e^{-1} \approx 63\%$.

What about $\sigma = \pi^2$, or $\sigma = \pi^k$ for $k > 2$?  Then $\pi$ and $\sigma$ are not independent.  Nevertheless, it would be rather surprising if this situation were substantially different.

What about $\pi^{2^{3456789}} + \pi^{2^{987654321}}$ instead of $\pi + \pi^2$?  This is the same as $\pi + \pi^{2^{987654321 - 3456789}}$.  It's not clear why you would be worried about uncomputably large exponents like this unless you were flailing around without principle trying to make a design that looks complicated.


How secure is MD5 for one way authentication?

Every 10 min S1 publish the hash value of PS+the current time which is used as public identifier (PI). Every one can see the value of PI in the internet. As S2 has the value of PS, he also use MD5 to get the hash value of PS+the current time and compare it to the value published by S1 and therefore identify that the value provide from S1.

Essentially, you would be using MD5(M + K) as a MAC. That is insecure.

The construction where you append the key to the message and then hash is not a secure MAC when the hash function lacks collision resistance, like MD5 does. (Technically, you need a collision attack on the compression function.)

Even though using a collision resistant hash (like SHA-256) would likely make what you are doing secure, I would recommend using a real MAC. For example, HMAC, for which you ought to find an implementation in almost any programming environment.


The way to break Diffie-Hellman(small nonprime number)

If we want to find shared secret, we need to find private key $a$ or $b$ first

No, for two reasons:

$a$ is not needed. Having found what the question notes $x_p$ and $x_q$, it is easy to compute the shared secret reduced modulo $p$, and modulo $q$, and then use the straight Chinese Reminder Theorem to find the shared secret. It tells when $p$ and $q$ are coprime (including, distinct primes as here and in RSA), and $0\le m<p\,q$, it holds
$$\begin{align}
&m_p=m\bmod p\quad\text{and}\quad m_q=m\bmod q\\
\iff&m=\left(\left(\left(q^{-1}\bmod p\right)\,(m_p-m_q)\right)\bmod p\right)q+m_q\end{align}$$
We can't find $a$ for certain, for there can be several equivalent $a$ (just as there are several equivalent private exponents $d$ in RSA). The best we can aim at is finding a working $a$, or best the smallest positive working $a$.

Hint if we want to find an $a$:

use Fermat's little theorem to define a modular equation involving only $a$, $x_p$ and $p$; and a similar one involving only $a$, $x_q$ and $q$. The question nearly does that, but extra parenthesis are required to fix the equations if we stick to proper notation as explained below, and the same quantity is designated by two different letters, creating confusion.
then solve for $a$ using a slight variant of the Chinese Reminder Theorem, applicable when the moduli are not coprime: we first divide one of the moduli by the Greated Common Divisor of the moduli, adjust the equation accordingly, and are back to the straight CRT.

Note: $u\equiv v\pmod n$ is a notation meaning that $n$ divides $u-v$, for some integer $n>0$. Whereas $v\bmod n$ without an opening parenthesis immediately before $\bmod$ is the uniquely defined integer $u$ with $0\le u<n$ and $u\equiv v\pmod n$. And $v^{-1}\bmod n$ is the uniquely defined integer $u$ with $0\le u<n$ and $u\,v\equiv1\pmod n$, assuming $\gcd(v,n)=1$. Baring parenthesis, operator $\bmod$ is understood to be evaluated after addition of what's on its left (stopping at the first $=$), but it is best to use explicit parenthesis when the modulus is a sum, as in $u\bmod(n-1)$. Also it is best to avoid $u\equiv v\bmod n$ and use \pmod instead of \bmod if  $u\equiv v\pmod n$ is meant, or use $u=v\bmod n$ if $0\le u<n$ is additionally implied.


What is a pre-shared key in TLS/SSL and why does master key is not used instead of session key?

What is the pre-shared key here ? Is it the pre-master key or it is the random number that is generated by server and client.?

Neither. In SSL/TLS 'Pre-Shared Key' (PSK) is a specific type of key-exchange different from the common RSA or DHE/ECDHE key-exchanges, and practically never used on the public net. (There are similar, but not identical, PSK options in some other protocols like IPsec.)
The premaster secret is not called a key and not used as a key, although it has some key-like properties. It is secret, and it is shared, but it is shared during the handshake and not before, so it is not pre-shared. The premaster secret and the two 'random' values are used to derive the master secret, and the master secret with the 'random' values again is used to derive the working or session keys and IVs, plural, see next.

get it that the session key is used to maintain the session but how does it so that in TLS/SSL
how master key is different than session key

There is not one session key; there are at least two and usually four or six if you count the IVs (or nonces) handled as keys. See What is the purpose of four different secrets shared by client and server in SSL/TLS? and rfc5246 (or previous versions) sections 8.1 6.3 and 5


The collision rate probability decreases when using compression?

No. On the contrary, if we model $H$ as a random function chosen independently of $Z$ and $S$, then $P_c[H\circ Z](S)=P_c[H](S)$.

Argument is that $P_c[H](S)$ is dependent only on the width of $H$ and the number of elements in $S$, as long as $H$ is modeled as a random function chosen independently of $S$. Define $S'$ as the set of $Z(s)$ for $s$ in $S$. It holds that $P_c[H\circ Z](S)=P_c[H](S')$, and because compression is reversible, $S'$ and $S$ have the same number of elements.


Did you RTFM?  It's right in the link you provided above: "The secrets module provides access to the most secure source of randomness that your operating system provides."

If you trace is back it uses os.urandom() which "... returns random bytes from an OS-specific randomness source. The returned data should be unpredictable enough for cryptographic applications, though its exact quality depends on the OS implementation. On a UNIX-like system this will query /dev/urandom, and on Windows it will use CryptGenRandom()."


Not Using RSA In OT1/2 Oblivious Transfer?

A:Xb+k-X1, Xb+k-X2 -> k1, k2

  A:m0+k0, m1+k1 -> m'1, m'2 -> B

B knows Xb+k (transmitted it in a previous message), X1, X2 (A sent those), hence he can compute k1, k2.

Hence, he can reconstruct both m0, m1, hence the protocol doesn't have the security properties we're looking at...

Now, you don't have to use RSA, however you really do have to use something that has some cryptographical properties.  After all, Oblivious Transfer is provably impossible between two computationally-unbounded entities, hence for OT to be possible, we need to use something that a real entity can't solve (but an unbounded entity can); RSA is one such problem (but certainly not the only one).


Changing SHA-1 constants an functions: Does it affect security?

I wouldn't suggest heuristically changing constants. However, there is a method with rigorous foundations that considered using randomized hashing in digital signatures. This method has the advantage that one can assume less from the hash function, and thus if the hash function is not "fully" collision resistant, the signature scheme can still be secure. In the method described in Strengthening Digital Signatures via Randomized Hashing by Halevi and Krawczyk, one only needs target collision resistance, which is much weaker than full collision resistance. Of course, this only helps in the context of signatures.


Can the hash of one message be used to make it easier to find the hash of a very similar message?

Knowing secretA; that it what obtained as sha256(passphrase + "a") -> secretA; and that passphrase is easy to remember; is enough for a password cracker to find passphrase. From that, secretB succumbs.

Thus yes, what's known gives the attacker an easy time figuring out secretB. If there are $n$ bits of entropy in the passphrase, the attacker's work is on average $2^{n-1}$ SHA-256 hashes. For many definitions of an easy to remember passphrase, that's feasible with readily available hardware and software, and technical progress is making that easier every year (by perhaps 0.2 to 2 bit of entropy, depending on what one thinks the state of Moore's law is). Morality: hashing something a human can remember does not turn it into a key. For this, use scrypt (or another Key Derivation Function intended for passwords, such as the lesser bcrypt or PBKDF2); and add salt at the KDF input, if at all possible.

No weakness in SHA-256 was involved in the above, only its excessive speed for the application. As far as we know (we have no proof), SHA-256 has properties close enough to a random function that in the application, a practical adversary (unable to perform work comparable to $2^{256}$ hashes) can not exploit that SHA-256 was used for producing both secretA and secretB with only 2 bits different in the input (assuming ASCII), other than by guessing that input.

That property of SHA-256 (that nearly equal input induce no exploitable similarity in outputs) was not one of SHA-256's primary design goals, and does not follow from these goals, stated as: "The hash algorithms specified in this Standard are called secure because, for a given algorithm, it is computationally infeasible 1) to find a message that corresponds to a given message digest, or 2) to find two different messages that produce the same message digest").

If we wanted something with that property, and a strong argument (which would be useful if passphrase was replaced by a true key), we could use a MAC of an arbitrary constant for each desired secret. That could be HMAC with SHA-256 rather than just SHA-256, used as HMAC(key,"a") -> secretA and  HMAC(key,"b") -> secretB.

Update: on second thought, in the setup in the question, and given the internals of SHA-256, we can argument in favor of that property (which is better than having no known evidence of the contrary): the two inputs to SHA-256 differ in the same block, thus any relation between the two outputs would amount to a related-key attack on the cipher from which the round function of SHA-256 is built. This argument is still much weaker than the modern argument for HMAC using SHA-256.


What's the difference between substitution and permutation in DES?

You pretty much answered your own question:

Substitution replaces a section of data with another chunk of data
Transposition moves data from one place to another

Substitution is usually responsible for non-linearity or "confusion", while transposition is useful for "diffusion" and ensuring that changes in one bit propagate to the rest of the state.


Debug client certificate authentication on path with openssl

I thought this would be a (probably cross) dupe, but the best I can find is https://unix.stackexchange.com/questions/29402/most-straightforward-way-of-getting-a-raw-unparsed-https-response or https://unix.stackexchange.com/questions/370932/openssl-command-s-client-always-says-400-bad-request . So:

What is an HTTP request? The original version of HTTP used a very simple request format: one line of text consisting of 'GET', a space, and what was originally called the document address (now generalized to resource identifier (URI) locator (URL) name (URN) or path), followed by a line terminator. Because of its severe limitations 0.9 was quickly replaced, and now is often not supported.

HTTP/1.0 in ~1995 expanded this to allow several methods (not just 'GET') and the first line (request line) also includes another space and the protocol version 'HTTP/1.0', and it is followed by zero or more headers each in the form 'name: value' and then (always) one empty line, followed for some requests by a body or 'entity' whose format depends on the headers (and possibly method). In 1.0 none of the headers are mandatory, only the request line and the empty line.

1.0 was quickly superseded by 1.1, which remained predominant, with some tweaks and evolution, until recently, and although formally superseded by 2.0 is still widely used and almost universally supported. 1.1 adds numerous options which can be ignored, but one mandatory request header, namely Host: to specify, you guessed it, the logical host, allowing multiple websites on one physical server, a practice that is now very common -- enough so that some servers still accept a specification of 1.0 and otherwise follow 1.0 rules but require the Host header to work correctly. (rfc1945 section 19.5 'major differences [from 1.0]' has only one subsection, about requiring the Host: header and allowing absoluteURIs.)

All of these standards specified the line terminator(s) to be the common Internet standard of CRLF (not just LF), but implementations vary on whether they enforce this; see more below.

The simplest way to send an HTTP request over TLS with openssl s_client is to use its default interactive mode and simply type the HTTP request on the terminal, and wait for the response. If the server chooses to do so, it can renegotiate at this point. An example on my test system, lightly redacted and with comments added:

$ openssl s_client -connect virt2.localdomain:443 -servername virt2.localdomain \
>   -CAfile trustvirt2 -cert certs/clix.pem -prexit
          <- some servers require SNI and some don't; openssl below 1.1.1 only sends SNI if you specify -servername
          <- even though the client cert won't be requested initially I must provide it on the commandline
          <- on Unixy systems may need to add -crlf; on Windows don't because it results in CRCRLF which is wrong
CONNECTED(00000003)
depth=0 CN = virt2.localdomain, L = here, C = XX
verify return:1
---
Certificate chain
 0 s:/CN=virt2.localdomain/L=here/C=XX
   i:/CN=virt2.localdomain/L=here/C=XX
---
Server certificate
-----BEGIN CERTIFICATE-----
[snip]
-----END CERTIFICATE-----
subject=/CN=virt2.localdomain/L=here/C=XX
issuer=/CN=virt2.localdomain/L=here/C=XX
---
No client certificate CA names sent
          <- server doesn't do client auth on initial handshake
Server Temp Key: ECDH, prime256v1, 256 bits
---
SSL handshake has read 1550 bytes and written 399 bytes
---
New, TLSv1/SSLv3, Cipher is ECDHE-RSA-AES256-GCM-SHA384
Server public key is 2048 bit
Secure Renegotiation IS supported
Compression: NONE
Expansion: NONE
SSL-Session:
    Protocol  : TLSv1.2
    Cipher    : ECDHE-RSA-AES256-GCM-SHA384
    [snip]
    Verify return code: 0 (ok)
---
GET /secur/good.txt HTTP/1.0
Host: virt2.localdomain

          <- I typed those two lines and the empty line
depth=0 CN = virt2.localdomain, L = here, C = XX
verify return:1
          <- this output from verify callback shows there was a renegotiation
          <- but it is NOT dumped in detail like the initial handshake
read R BLOCK
HTTP/1.1 200 OK
Date: Tue, 05 May 2020 16:27:40 GMT
Server: Apache/2.2.15 (CentOS)
Last-Modified: Mon, 04 May 2020 07:21:53 GMT
ETag: "8066f-7-5a4cd62a20c85"
Accept-Ranges: bytes
Content-Length: 7
Connection: close
Content-Type: text/plain; charset=UTF-8

secret
          <- that was the response header and body sent by the server
closed
          <- that was output by s_client because my server closed the connection
          <- some 1.1 servers might not close immediately here, but will usually timeout fairly soon
          <- now s_client -prexit prints the _final_ session data, including the renegotiation:
---
Certificate chain
 0 s:/CN=virt2.localdomain/L=here/C=XX
   i:/CN=virt2.localdomain/L=here/C=XX
---
Server certificate
-----BEGIN CERTIFICATE-----
[snip]
-----END CERTIFICATE-----
subject=/CN=virt2.localdomain/L=here/C=XX
issuer=/CN=virt2.localdomain/L=here/C=XX
---
Acceptable client certificate CA names
/CN=demoCA2.mytestdomain
/CN=demoCA2b.mytestdomain
          <- including the CAnames you want
Server Temp Key: ECDH, prime256v1, 256 bits
---
SSL handshake has read 4252 bytes and written 1909 bytes
---
New, TLSv1/SSLv3, Cipher is ECDHE-RSA-AES256-GCM-SHA384
Server public key is 2048 bit
Secure Renegotiation IS supported
Compression: NONE
Expansion: NONE
SSL-Session:
    Protocol  : TLSv1.2
    Cipher    : ECDHE-RSA-AES256-GCM-SHA384
    [snip]
    Verify return code: 0 (ok)
---
$

There are 2-3 disadvantages to this method:

you must type the request exactly correct, with no mistakes. s_client sends each line as you enter it, and once sent it cannot be corrected.
depending on the server, you may have to type quickly. Due to widespread denial-of-service attacks, many webservers today only allow a limited time, often 30 seconds or less, to receive the request. This makes the previous bullet even harder.
on Unixy systems, terminal input lines end with only LF, not CRLF. If the server is strict, either you must manually enter the CR, typically as control+V control+M although this can vary depending on your tty driver settings, or (much easier!) add -crlf to s_client and it adds CR for you.

The less simple way is to supply the request data automatically: from another command (piped), or a file or heredoc. This avoids the problems of making a manual typing mistake, or being too slow. On Unixy systems where scripts and most commands are LF-only, and files may be, you again have the issue of either adding CR explicitly or using -crlf. But now after sending the request, you must make s_client keep the connection open long enough to process the renegotiation -- and maybe, but not necessarily, the server HTTP-level response; this can be done by waiting for terminal input (which you don't immediately provide), by an explicit sleep (at least on Unixy systems), or by adding -ign_eof to s_client. Combining these options, some possibilities:

(printf '%s\r\n' 'GET /resource HTTP/1.1' 'Host: myhost' ''; cat) | openssl s_client ...

(echo GET /resource HTTP/1.1; echo Host: myhost; echo; cat) | sed 's/$/\r/' | openssl s_client ...

(echo GET /resource HTTP/1.1; echo Host: myhost; echo; cat) | openssl s_client ... -crlf

(printf '%s\r\n' 'GET /resource HTTP/1.1' 'Host: myhost' ''; sleep 5) | openssl s_client ...

(echo GET /resource HTTP/1.1; echo Host: myhost; echo; sleep 5) | sed 's/$/\r/' | openssl s_client ...

(echo GET /resource HTTP/1.1; echo Host: myhost; echo; sleep 5) | openssl s_client ... -crlf

printf '%s\r\n' 'GET /resource HTTP/1.1' 'Host: myhost' '' | openssl s_client ... -ign_eof

(echo GET /resource HTTP/1.1; echo Host: myhost; echo) | openssl s_client ... -crlf -ign_eof

openssl s_client ... -crlf <<END -ign_eof
GET /resource HTTP/1.1
Host: myhost

END

printf '%s\r\n' 'GET /resource HTTP/1.1' 'Host: myhost' '' >>filewithcr

(echo GET /resource HTTP/1.1; echo Host: myhost; echo) >>filenotcr

cat filewithcr - | openssl s_client ...

(cat filewithcr; sleep 5) | openssl s_client ...

(sed 's/$/\r/' filenotcr; sleep 5) | openssl s_client ...

<filewithcr openssl s_client ... -ign_eof

<filenotcr openssl s_client ... -crlf -ign_eof


If the inputs you're hashing aren't long enough with enough entropy, the hashes can be inverted by an adversary who is willing to brute force the entire range of possible inputs.

For example, hashing abc provides little barrier to those who are dedicated at deobfuscated your program, as it takes almost no time to calculate hashes for all possible 3 character strings.

The adversary can build a table of all inputs up to a certain size and proceed to crack your obfuscated data in negligible time. If your adversary has financial motivation, this probably will not protect your code.

You could opt for additional protection by using slow, salted hashes, which are usually employed to protect passwords. Using a salt can prevent your adversary from precomputing the table before he has access to your source code. The downside is that using a slow hash in an effective manner will cause a non negligible performance hit to your application.


My doubt is, what is the actual worst case for integer factorization problem?
...
Provide reference stating the worst case for integer factorization with particular values of k

Such a statement can not be done for any class of algorithms at all, only a specific algorithm can have a worst case runtime.
In general, worst case estimations are barely used in cryptography at all, because the average case matters much more. Here's an example for that: Assume you had a new, hypothetical factorization algorithm, which has linear runtime for composite numbers on almost all inputs, but for values of the factorial function it has exponential runtime. Now the worst-case runtime is exponential, but the average is barely more than linear. And even worse: In the cases of $x!$ as input,the input is divisibly by $2$ when $x>1$, so just run the algorithm on $x!/2$ instead, with its linear runtime. This would make factorization entirely useless for cryptography - but the algorithm has exponential worst case runtime. Worst case assumptions are only useful if you can somehow reduce the average case to the worst case (possibly under randomized reductions, etc.) - for example in lattice-based cryptography these methods apply.
When looking at known factorization algorithms, there are some which scale with the size of the smallest prime factor, some scale with the total length of the numbers and some on "closeness of prime factors". In order to counter them all, suggestions like the ones you found are often made. However, those suggestions are made in reference to known algorithms not proven in any way whatsoever.
In order to get actual current state-of-the-art recommendations, keylength.com lists the recommendations of various sources with the publication date. The latest one references the BSI publication of Feb 2017 here: Publication in German, edit: found the English Verison
It has the following suggestion in the subsection RSA:
$\epsilon_1 < |\log_2(p) - \log_2(q)| < \epsilon_2$
And the suggested values for the boundaries are: $\epsilon_1 \approx 0.1, \epsilon_2 \approx 30$. The value $0.1$ for the metric would imply that $p/q$ differs from $1$ by at least a factor of $\approx 1.07177346$, which implies roughly if given the smaller prime $p$, that $q > (1+\frac{1}{14})p$, which in return means for length $b$ primes, the difference should be at least $b-4$ bits (which would mean the difference is $1/16$, but it should be $1/14$ or more).


Inserting a backdoor into a cryptographic hash function

Here is a "backdoored" hash function:

Let $p = 2q + 1$ be a big prime of length $2048$ bits, such that $q$ is also prime. Let $a$ be an integer of order $q$ modulo $p$, i.e. $a \neq 1$ but $a^q = 1 \pmod p$; it can be shown that $a = 4$ is always a valid solution. Let $s$ be a (secret) integer between $1$ and $q-1$, and let $b = a^s \pmod p$.

Then define operation $\phi(x, y)$ such that input $x$ is a sequence of $2048$ bits, and $y$ is a sequence of $2042$ bits (not $2048$); the output is a $2048$-bit value:

Concatenate $x$ and $y$ and split it back into $u$ and $v$, such that $u$ and $v$ both have length $2045$ bits each: $$u || v = x || y$$
Interpret $u$ and $v$ as unsigned big integers, using some convention (e.g. big-endian). Note that both $u$ and $v$ are lower than $2^{2045}$.
Compute: $$z = a^u b^v \pmod p$$
$\phi(x, y)$ is the encoding of $z$ over exactly $2048$ bits (there again, using a fixed convention).

Note that $\phi(x, y) \neq 0$ for all $x$ and $y$.

Now that you have $\phi$, define a hash function $h$ as follows:

For input $m$, pad it with some "removable" padding sequence (e.g. a Merkle-Damgård compliant padding) so that the total length of $m$ is now a multiple of $2042$.
Split $m$ into $n$ blocks of $2042$ bits (denoted $m_1$, $m_2$, ... $m_n$).
Define $x_0 = 0$ (a sequence of $2048$ bits, all of value $0$).
For $i = 1$ to $n$, define: $x_i = \phi(x_{i-1}, m_i)$
Define the hash output $h(m)$ to be SHA-256($x_n$).

Let's see the security of this construction:

Preimages: for a given $t$, finding $m$ such that $h(m) = t$ implies, in particular, finding some $x_n$ such that SHA-256($x_n$) $= t$, so our function $h$ is at least as much preimage-resistant as SHA-256.
Second preimages: second preimages are a special case of collisions, so $h$ will resist second preimages at least as well as it resists collisions. Ideally we would want something better (i.e. resistance up to $2^{256}$ for second preimages, even though collisions can be found in effort $2^{128}$), but since collisions should be infeasible anyway, this is probably acceptable.
Collisions: suppose that $m \neq m'$ and $h(m) = h(m')$; $m$ yields a sequence of $n$ words $x_1$ to $x_n$, while $m'$ yields $x'_1$ to $x'_{n'}$. We suppose, without loss of generality, that $n' \geq n$. Then one of the following holds:

$x_n \neq x'_{n'}$ but SHA-256($x_n$) $=$ SHA-256($x'_{n'}$). We have found a collision on SHA-256.
There is an index $i$ such that $x_{i-1} \neq x'_{i-1}$ but $x_i = x'_i$. This means that we know integers of at most $2045$ bits $u$, $v$, $u'$ and $v'$ such that $(u, v) \neq (u', v')$, but $a^u b^v = a^{u'} b^{v'} \pmod p$. This implies that $a^{u-u'} = b^{v'-v} \pmod p$. Since $a$ and $b$ have order $q$ (greater than $2^{2046}$) and $u-u'$ and $v-v'$ cannot be both $0$, then $u-u'$ and $v'-v$ are invertible modulo $q$, and we can write $b = a^g \pmod p$ with $g = (u-u')/(v'-v) \pmod q$ (i.e. $g$ is the secret value $s$). We just solved discrete logarithm.
There is an index $j$ such that $n \lt j \leq n'$ and $x'_j = x_n$. By "rewinding" the steps this implies that either we find an instance of the previous situation ($a^u b^v = a^{u'} b^{v'}$ for $(u,v) \neq (u',v')$), or we have $x'_{j-n} = x_0$, which is not possible since $x_0 = 0$ and $x'_{j-n} = \phi(x'_{j-n-1}, m_{j-n}) \neq 0$.

Therefore, finding a collision on $h$ requires either finding a collision on SHA-256, or solving discrete logarithm modulo $p$. Since both are computationally infeasible (as far as we know), this function $h$ can be deemed "secure" as a hash function.

The backdoor is the knowledge of $s$. In all of the above, we used the $a$ and $b$ values "as is". The value of $s$ is not needed anywhere. However, if you know $s$, then you can compute collisions at will:

Generate two random blocks $m_1$ and $m'_1$. Compute the corresponding $x_1$ and $x'_1$.
Let $u$ be the first $2045$ bits of $x_1$, and $u'$ be the first $2045$ bits of $x'_1$.
Compute $k = (u-u')/s \pmod q$
If $k$ is less than $2^{2045}$, or greater than $q - 2^{2045}$, then you can find $v$ and $v'$ of $2045$ bits each, such that $v'-v = k \pmod q$, from which you can infer two blocks $m_2$ and $m'_2$ that match $(u,v)$ and $(u',v')$, respectively. You have your collision.
The condition on $k$ works with probability at least $1/2$. If you were unlucky, just try again with new random blocks $m_1$ and $m'_1$.

The above is thus a hash function with a backdoor. However, mind the fine print:

The backdoor is explicit. While the knowledge of $s$ is necessary to exploit the backdoor, everybody knows that it is there. Conversely, if you generate $a$ and $b$ as NUMS numbers (thus with $s$ convincingly unknown to everybody), then the hash function is "backdoorless" (but also useless).
When you exploit the backdoor, you produce two colliding messages $m$ and $m'$, from which anybody can recompute $s$. Thus, the backdoor is "one-shot".
The backdoor allows finding collisions, not preimages. A hash function designed to have a backdoor for preimages would need something else. Ideally you would use a one-way trapdoor permutation, but (to my knowledge) no such object is currently known, that would yield an output of suitable length (e.g. 256 bits).


What can be learned from the ciphertext of LibSodium's crypto_box_detached()?

I'll answer the related questions in order:

No, because a ciphertext (generated from a key stream generated by a stream cipher)  should be indistinguishable from random data, and a MAC should be as well.
No, because #1 depends on the secret, and the secret was derived using a Diffie-Hellman key agreement algorithm, using the given curve. To know information about the secret, it is required to obtain one of the private keys.
No, because that follows directly from #1 and #2.

Notes:

traffic analysis is not taken into account for this answer as it is outside the scope of the cryptographic properties;
the size of the ciphertext (equal to the plaintext size) + MAC size may leak some information to an attacker.

It seems that the detached variant was explicitly defined to separate the tag and the ciphertext, so it seems a bit strange to talk about ciphertext + MAC (only the order of ciphertext and MAC seems different from the non-detached variant of the same method).


AES+CTR+HMAC Encryption and Authentication on an Arduino

Yes, authenticate the IV. If an attacker changes the IV while keeping the rest of the ciphertext intact, they'll change the message. Just because they can't change the message to an arbitrary value doesn't mean they can't cause harm (if nothing else, they can send random junk until they hit a valid command or a bug in your parser, or feed you invalid data).
SHA-256 doesn't authenticate anything whatsoever. Its use for integrity is that if a message changes, so does its SHA-256 digest, and it's easier to ensure the integrity of 256 bits than of a gigabyte-long message: a giest allows you to do integrity by proxy. But you still need to ensure the integrity of the digest somehow.
HMAC, in contrast, incorporates a secret key, and can only be produced with the knowledge of the secret key, so it provides authenticity. Note that authenticity doesn't imply integrity: an attacker could replay an older, equally valid message.
I'm nowhere nearly a competent enough cryptographer to know whether using the same key for the HMAC and the encryption is a problem, but my gut reaction to “use the same key for” is don't do it. Either keep two separate keys, or if you only have 128 bits of key material, derive two 128-bit keys from these 128 bits.
If you never send the same message twice, then it is valid to use the first (or last) 128 bits of the SHA-256 of the message as an initial nonce (IV) for CTR mode. CTR mode absolutely requires a unique nonce per message; the nonce is commonly generated at random, which ensures unicity even if the messages are identical, but that isn't a requirement unlike some other block chaining modes.
If you send the same message twice with the same IV, the ciphertext will be the same, and eavesdroppers can find out. The only way to remedy this is to have a source of uniqueness. Ideally, you run a cryptographic PRNG on the Arduino, making sure to seed it either with sufficient hardware entropy (I don't know what the Arduino's capabilities are) or with entropy provided securely (with both authentication and confidentiality) from some more capable machine. Another alternative is to send a unique token from the server before the Arduino sends each message, and include that in the message; the token has to be integrity-protected but doesn't need to be confidential.

Now that I've answered your questions, let me answer your question.

Don't do this. Use authenticated encryption (GCM or EAX).

  authenticated encryption is "combined traditional encryption and independent MAC, done properly".


The confusion comes from the choice of representation. I'd a quick look to the referenced paper, where the autors use a 2-radix representation. Then you shoud initialise $e=\frac{m+15}{w}$ instead of $e=\frac{m+1}{w}$ as you use a 16 bit adder!
The best is to read again the seminal paper of P.L. Montgomery:http://web.itu.edu.tr/~orssi/dersler/cryptography/Montgomery.pdf

ANd this remak explain the additionnal word set to ZERO in the modulus.

The method introduced by Montgomery is clever and require a change or representation as explained in the paper. the method allows also to overlap mul and ReduC process.
I confirm also than C represent the carry which require 2 bits to be holded. The interest compared to the classical method, is that carry propagation is moving from right to left, exactly of the direction of scanning operand. This is the reason why the Mult-ReduC can be overlapped, and which is of great importance in hardware design.


You want to talk about format-preserving encryption. One of the main motivations for FPE is the ability to encrypt messages which lie in a short space, with an output which is in the same space.

The ideal encryption model on a space of size $S$ (e.g. $S = 10000$ for four-digit PIN codes) is that the encryption systems implements a permutation chosen randomly and uniformly among the set of $S!$ possible permutations. Or at least that the cipher is indistinguishable from such a randomly chosen permutation.

An extreme security model is then the following: assume that the attacker is given a black box which implements the encryption (and decryption) algorithms. He can ask for the encryption or decryption of the almost complete code book, i.e. $S-2$ requests. The attacker gets to choose the contents of each request, adaptatively. So at that point, the attacker can simulate the complete encryption function, except for two input values: he knows the two inputs (let's call them $p_0$ and $p_1$) and the two corresponding outputs ($s_0$ and $s_1$), but he does not know whether $p_0$ encrypts to $s_0$ or to $s_1$. His goal is to predict the encryption of $p_0$ with probability substantially better than pure luck (i.e. $1/2$).

A commonly quoted solution for FPE is the Thorp shuffle. It is an unbalanced Feistel cipher, with enough rounds to make it secure. The good part of it is that it is possible to prove security while keeping the number of rounds low enough to be practical (say 100 rounds or so). The bad part is that it does not realize the extreme model explained above. You have to relax a bit the model, because a Feistel scheme always implements an even permutation; so if you know all the code book except the encryptions of $p_0$ and $p_1$, then you can decide whether $p_0$ goes to $s_0$ or $s_1$ with 100% success rate, because only one of the two choices leads to an even permutation. However, the relaxation is not a big deal: if you give to the attacker only $S-3$ requests, then you can have the best possible under these conditions (attacker cannot predict the mapping of the three remaining inputs, except that they will have to comply to the "even permutation" rule).

To reach the "ideal" model with $S-2$ requests, you have to do heavier thing, like generating the complete permutation in a big array (this is certainly doable with only 10000 entries; for bigger spaces, memory-conscious solutions exist, but the CPU price is quite high). For a practical solution, use the Thorp shuffle.

For verifying PIN codes, encryption is probably not the right tool anyway. Indeed, as you notice, the space of PIN codes is so small that there must be a locking mechanism somewhere, which blocks the attempt after three wrong tries. You cannot have that from cryptography alone. In fact, you will get locking by using dedicated hardware: either a smart card (the smart card is tamper-resistant and locks itself after three wrong PIN codes) or a remote server (that enforces the locking policy).

FPE is used to realize other features, e.g. serial numbers with verifiable validity: you define an 8-digit number which embeds a 5-digit counter value, and you want to have a tool which can verify whether a given sequence of 8 digits is one of the 100000 sequences that you have issued; but you don't want anybody else to be able to generate random "valid" sequences with success probability higher than 1/1000. Solution is to encode the 5-digit counter as 8 digits by appending three zeros, then encrypting the whole lot with FPE. To verify, decrypt, and see if the three zeros are there.


Are there any misuse-resistant asymmetric encryption schemes?

Both require random elements for security, and it seems to me that both would not achieve semantic security (IND-CPA) if these repeat as RSA is otherwise deterministic.

Actually, that would be true of any potentially misuse resistant system.  As long as you don't fold in fresh randomness, and as long as you don't update long term state during the encryption, then encrypting the same message a second time will result in the same ciphertext.

Doing an SIV-like trick wouldn't help; if you encrypt the same message with the same private key, the PRF would generate the same nonce, and everything becomes deterministic.

What the PRF would help you if there are weak nonces (for example, in ECDSA, if you use the same nonce twice for two different messages, you leak the private key).  If there was a similar weakness in the public key encryption scheme, that would help.

On the other hand, I don't believe RSA-OAEP has such a weakness; hence the PRF idea doesn't make anything better


Is every output of a hash function possible?

There is no proof that every output of common hash functions is reachable for some input, but it is expected to be true. No method better than brute force is known to check this, and brute force is entirely impractical.

By the coupon's collector argument, it is expected to require $2^n\cdot(n\cdot\ln(2)+\gamma)+1/2+o(1)$ random values to reach all $n$-bit values, with $\gamma\approx 0.577216$.

Translated to hashes, about $2^{134.5}$ (for MD5) or $2^{166.8}$ (for SHA-1) distinct messages are expected to be required to reach all output values, on the assumption that these hashes behave as random functions. This assumption is reasonable, as it is the design goal of the round function of these hashes.

Update: as stated by Jon Callas in an other answer, it is possible to construct hash functions which demonstrably do not reach all their output; and even some that are computationally secure. One example is $\mathcal{H'}=\mathcal{H}(\mathcal{H}(m)|1)$ where $|$ is bitwise OR, and $\mathcal{H}$ is a common hash function. $\mathcal{H'}$ reaches markedly less than half of its output space, but is likely as fine as $\mathcal{H}$ by all other experimental metrics except speed.


Please note that official test suite is long unmaintained and known to be buggy, not fully consistent with its documentation etc. There are some reimplementations (I can recommend the reimplementation made by David Johnston in Python, but maybe some other is even better) which should be probably the way to go.
AFAIK the tests mostly just try to verify that input numbers used in given way give mostly results in given range expected for truly random numbers. You could possibly use exactly the same tests, just put in another expected ranges of results, as for biased generator the expected ranges are different. That's simple modification from programmer's viewpoint, but actually computing (or just measuring from simulations?) what are the new proper ranges could turn out to be a considerable (math?) work.
And of course, the crucial question is why do you want to actually use the test suite and why do you consider the tests chosen by NIST to be the ones that should be used to evaluate the generator. The consensus today is probably that "universal" test suites are of limited use when it comes to cryptographic RNG, as any of them can check just limited amount of possible non-random patterns. The tests included in the batteries are just trying to cover most common non-randomness, so you can effortlessly prove many badly designed generators to be indeed bad. Once you are trying something more, like proving some generator to be actually good, or trying to understand some generator better, the situation is different. You should already know something non-universal about your generator (like that it is biased and at least some hypothesis why it is biased) and  you should probably design your own tests based on your knowledge and check NIST suite just for inspiration.


Can we determine a security parameter in the hybrid argument where the number of hybrids is polynomially bounded but not known?

a function "polynomially bounded" means there exists $d\in \mathbb{N}$ such taht
$f(\lambda)\leq \lambda^d$ asymptotically.
You don't have to know $f$, but if you want to bound the advantage of your adversary asymptotically, you have to know a such $d$ which verifies this inequality.
If you don't, then you can't deduce anything. But in general, if you look the proof in details what is $n$, and why it has been claimed polynomially bounded, it's easy to find a such $d$, such that $n\leq \lambda^d$ asymptotically.


Can you help me understand hash-preserving encryption?

A generic construction could be something like this:

$\def\Enc{\operatorname{Enc}}$ Take a simple hash function $H$ and encryption function $\Enc_K$.

Then define $E = (\Enc_K(H(A)), \Enc_K(A))$ as the encryption, $hashA(A) = H(A)$ and $hashE(x,y) = x$.

Then we have $hashE(E) = \Enc_K(H(A))$, which of course is easy to check against $H(A)$, given $K$.

Of course, this in no way satisfies your unforgability requirement: Only someone with access to both $E$ and $K$ can check if the hash part of $E$ matches the rest of it.


Why does the Bombe not consider the Ringstellung when determining stecker pairs?

I didn't want to delete this question, but it seems like after pondering this for a week I finally understand right when I seek help online. When the ring setting and the rotor position all increase by the same amount, they cancel and so the ring pretty much stays the same. Although the contact points of the ring to the alphabet ring is different, it makes no difference, since it's not the contact on the alphabet ring that matters but instead the contact of the pin with respect to the next rotor.


What's wrong with this digital signature scheme?

Regardless of the possible answers here, which probably focus on some technical difference between the signature scheme for authentication vs the signature scheme for non-repudiation, the practical way to prevent this is to have at least two key pairs for the different use cases.

Alice would have a private key and matching certificate to perform the authentication. Preferably she would even have multiple ones for each use case, with access conditions matching the use case. Although this scheme uses signatures, it uses them just to authenticate Alice at a particular time and the signatures do not need to last.

Alice would have another private key and matching certificate to perform the signatures for non-repudiation. Non-repudiation is used for documents to show that a specific person has signed it; that person nor others cannot repute the signature: it must have been set by somebody who has access to the private key. These signatures are stored with the document so that they can be accessed later.

The private keys for non-repudiation generally need higher security than those for authentication. Signatures are stored, so the key size needs to be future proof. This difference is reflected in the certificate, which may for instance have to adhere to an established Certificate Practice Statement to be accepted - a self signed certificate created on your computer cannot be used to buy a house.

Old style Government ID cards commonly have three private keys and matching certificates on them: one key for authentication (to the OS, TLS or applications), one key for non-repudiation (a digital signature to replace the written signature you are used to) and one for decryption (to keep messages send to you confidential).


How should I define order according to domain parameters in elliptic curve pairing groups?

I think you should probably specify more details about the current curve, or give more insight about the parameters you are choosing, eg: is this a curve over $GF(p)$ or is this a curve over $GF(2^m)$. What is your $r$ value? Without such detail I can't give a very accurate answer but the order of the subgroup generated by a given point $P$, $<P>$ can be calculated from a combination of bruteforcing and checking the divisors of the number of elements inside the original curve (Since these are cyclic groups you really only need to apply lagrange theorem and check if the current divisor $d$ of $n$ satisfies $P^d = O$). There are polynomial time algorithms to retrieve the order of the original curve group (check Schoof's algorithm).


In Microsoft Password Monitor implementation using HME how do they perform ComputeMatch Function?

Let the client have public and private keys $k_{pub}, k_{prv}$ of a secure FHE (Fully Homomorphic Encryption). Now clients want to check that their password $pwd$ is on the breach list or not.
As stated on the MS site, to prevent the user from querying dictionary attacks on the server, they use hash $H$ of the form Oblivious Pseudo-Random Function (OPRF). The client calculates $h(pwd)$ then uses their public key and encrypts as $ = E(k_{pub},h(pwd))$. Now the client sends the $(c,k_{pub})$ to the server.
Now, the server, for each breached password $p_i$ calculates $c_i = E(h(p_i), k_{pub})$. Using the FHE equality circuit $C$ they compare each breached password's hash and the user's to get the result. Note that this result is encrypted and only the client can decrypt it. Now instead of sending each value to the user, they execute OR operation on the result to get only one value $v$.
The value $v$ sent back to the user and the user decrypt the single bit $b \stackrel{?}{=} D(k_{prv},v)$. If the $b=0$ mean not in the breach list, if $b=1$ mean it is on the breach list.
###Client
c = FHE_encrypt(k_pub, h(pwd)
send c to the server

###server
### Encrypt each password on the list
for each p in breachedList

    c[i] = FHE_Encrypt(k_pub, p)

###Calcualte the equality of the ciphertext
for i in sizeof breachedList

    eq[i] = FHE_Equality_Circuit(k_pub, c[i], c)

v = E(k_prv, 0)

###Combine the results to reduce the bandwidth
###Not to reduce the dep a binary tree calculation must be preferred.
for i in sizeof breachedList

    v = FHE_OR_Circuit(k_pub, v, eq[i])

return v

###
Client
b = FHE_Decrypt(k_prv,v)
if b = 1
   print ( "Change your password immediaately, it is on the breach list")
else
   print ( "Your password is not on the breach list")


I have a 16MB image that I'm encrypting and authenticating using AES-GCM. I obtain a 16MB encrypted image and a MAC. From what I could tell, this should provide me both confidentiality, authenticity, and integrity. I might be wrong on this.

This is correct; AES-GCM is designed to offer confidentiality, authenticity, and integrity.

More details

You need to define who is supposed to be able to both verify the authenticity/integrity of your image, and who is supposed to be able to create authentic images.

In the case that you are the sole party that will be creating and accessing the image(s), then using ECDSA (or any signature algorithm) does not offer you any advantages. It will increase implementation complexity, and require more resources for no real benefit.

This situation applies if you are storing the image for personal use.

In the case that you are sharing that image with 1 other party, and both parties are allowed to create authentic ciphertexts, then AES-GCM is still sufficient by itself.

An example of this type of situation is secure instant messaging*.

If you want the world at large to be able to verify that a given ciphertext was created by yourself, without giving them the ability to create authentic ciphertexts themselves, then you would need to use ECDSA. Considering that the information is also encrypted, this seems like a relatively uncommon use case.

An example of this situation might be that you are forming some kind of cryptographic commitment to the image, which will only be revealed at a later date.

*Note: To set up a secured communications channel would likely involve the use of digital signatures; This appears to be beyond the scope of your question


Bleichenbacher 1998 "Million message attack" on RSA

I implemented this padding oracle attack some time ago in Python and remember this part being a bit confusing to wrap my head around, my code is as follows:

newM = []
for (a, b) in M:
    # util.ceiling rounds arg1 / arg2 to the next highest integer
    rlow = util.ceiling((a*s - 3*B + 1), n)
    rhigh = (b*s - 2*B) / n

    for r in range(rlow, rhigh + 1):
        newa = max(a, util.ceiling(2*B + r*n, s))
        newb = min(b, (3*B - 1 + r*n) / s)
        newM.append((newa, newb))

M = list(set(newM))

So basically for each (a, b) pair in the set M you have to calculate the range of possible r values and create a new pair for each r. Since the pairs (a, b) are such that a <= b, calling max for the first element and min for the second element ensures that for any (a, b) the new value of a can only increase and b can only decrease. Said another way, you never increase the range, you are always narrowing it down. So while the amount of pairs in M does increase for a while it eventually does decrease back down to one pair (a, b) where a = b.

Hope that is somewhat helpful. :)


Could a crypto system that uses non-FIPS crypto but then upgrades complete to FIPS be FIPS certified?

Yes, a device that is FIPS certified need not be restricted to using only FIPS-approved algorithms.  For example, in your case, FIPS has no problems with you supporting Curve25519, as long as the user can turn it off.  That is, the device will need to be able to be set in a mode that it performs only FIPS approved algorithms (and the FIPS approval documentation will have to explain precisely how to do that).

You specifically asked about 'crypto system'; if you're asking about a protocol, a protocol is not FIPS approved; FIPS approved devices, not protocols.


I am using AES-CBC, authenticating using HMAC-SHA512 and I was wondering whether my thought process and implementation are correct.
The message send over the network is: HMAC(64Bytes),IV(16Bytes),Ciphertext The MAC is calculate as follows: HMAC(sha1(secretKey),Plaintext)

No, that's not correct.
The HMAC should be calculated over the IV and ciphertext values, not over the plaintext. If you send the HMAC over the plaintext then an attacker will be able to distinguish identical plaintext.
If this is used for transport security (as you seem to indicate) then you may be vulnerable to padding oracle attacks on the CBC mode AES. If you want to use a good scheme you could take a look at this draft RFC.
If you want to use it as application level protocol you may (also) want to read about the order of encryption and MAC. If push comes to shove you could use MAC-encrypt-MAC of course.
SHA-1 in this scheme only reduces the amount of key material if a 192 or 256 bit key is used.

Is there a significant reason to use SHA-512 over SHA-256?

Probably not for generating an authentication tag for a MAC. Note that SHA-512 is generally faster than SHA-256 on 64 bit machines, so if you can spare the bandwidth then it might be a good idea to use SHA-512. Otherwise you could use SHA-512/256 - if that's available on your target runtimes of course.

Should I treat the secretKey differently or generate a complete new pair entirely for the authentication of the ciphertext

You definitely should not put SHA-1 in the mix.
You could use the same key for encryption and HMAC if you're feeling dangerous. It's unlikely (but not theoretically impossible) that this will compromise the symmetric key.
If you want to do it nicely then you should use two keys. You could use a key derivation function such as HKDF to calculate two keys out of the master key. If that's not available you could fall back to the PRF used to generate the sessions keys within TLS.


Using a blockchain for secure communication

Secure communication doesn't need blockchains. We have AES and digital signatures for that.

Correct, though we also require tools other than block ciphers and digital signatures. But that is besides the point, as "blockchain" is not on that list.

  Blockchains are only useful for documentation. Not for securing anything.

Blockchain is a distributed, append-only ledger. That in itself does not provide confidentiality, integrity, or authenticity. However, availability is one of the pillars of information security, and it is arguable that blockchain could be used towards that end.

  Am I missing something here?

Probably not. It has become trendy to try and attach blockchain to everything:

  Long Island Iced Tea Corp., now called Long Blockchain Corp., received an ultimatum from Nasdaq in October, when the exchange threatened to delist it unless the market value rose above $35 million for 10 business days in a row. It achieved that on Friday, flaunting one of the hottest buzzwords of the year to get there.

Often times by people who don't/barely know what cryptography is, how it works, or what is is useful for.


Choice of the one-way function (OWF) for Lamport signatures

(Q1) Assuming that you talk about the size of the secret key elements which equals the input size of the OWF when you talk about the "input", this should be at least as much as the output size.

Consider a function $f: \{0,1\}^m \rightarrow  \{0,1\}^n$.The thing to worry about when you choose $m < n$ is a brute force search for a preimage, which in this case takes about $2^m$ queries to $f$. The second thing is the collision probability, i.e. the probability of choosing the same value for two different secret key elements. As these are sampled from the uniform distribution, the probability for this is $2^{-m/2}$. Please note that this is a constant probability that an adversary cannot influence, so you are perfectly fine if this is, e.g., $2^{-64}$. Moreover, you can also let your implementation check that this doesn't happen. So, $m = n$ is perfectly fine.

Also, a $128$-bit output is fine as Lamport does only rely on the one-wayness of the "internal" hash function. However, as you mentioned, the hash function used to compress the message still needs collision resistance and hence has to be at least $256$-bit (or you use some kind of randomized hashing).

Summing up: For OWF $f: \{0,1\}^m \rightarrow  \{0,1\}^n$, $m = n = 128$ is fine for classical security (if you want security against quantum attackers you need to make it $256$ bit because of Grover's algorithm).

(Q2) Good question, as proposed in the XMSS paper, you can use AES and  the Matyas-Meyer-Oseas construction to build a $n$ to $n$ bit hash function. This works with any block cipher that has same key and block size. The advantage of AES is the available hardware acceleration on many different platforms, incl. modern general purpose CPUs and many smartcard micro controllers.


Proof for the SHA3 claim that 256 bit security is "post-quantum sufficient"?

Well, cryptographers have been contemplating a post-quantum world for some time now.

Quantum computing, although in its infancy as far as real-life computers go, has been studied in a theoretical sense for a quite a while. Shor's algorithm was published 19 years ago; Grover's, 17 years ago. These are the two most-famous quantum algorithms, I think, but the field goes back further than that: according to Wikipedia, the field was born somewhere in the 1980s.

The point is that even though quantum computing hasn't produced a usable, useful real-life quantum computer yet, it has been considered for quite a long while now. So while huge breakthroughs are still very possible, it's likely that researchers have exhausted all of the easy lines of attack. Further, since it doesn't seem that in the last 16 years any new, cryptography-threatening quantum attacks have surfaced (at least, none that I am aware of), it seems relatively safe to talk about post-quantum strength.

More to the point, the real threat against hash functions in a post-quantum world would be Grover's algorithm. Using Grover's algorithm, mounting a brute-force preimage search on an $n$-bit random oracle has time $O\left(2^{n/2}\right)$.

Although direct application of asymptotic bounds is rather imprecise, this would lead to a preimage attack in time $2^{128}$ for a 256-bit (preimage-resistant) hash function. This is still secure, and I think this is what the authors were intending when they said "post-quantum sufficient." For more information, see the question What security does Keccak offer against quantum attacks, specifically Grover's algorithm?.


Reason for difference in assumptions for practical private-key and public-key crypto

AES is not a one-way permutation; it is a permutation, for sure, but whoever can apply it can also apply its inverse. Crudely said, the AES decryption key is identical to the AES encryption key. A one-way permutation would be like a hash function: everybody can compute it in one direction, with no secret value, but nobody knows how to do it in the other direction.

Right now, we do not know how to make one-way trapdoor permutations without resorting to number theory. It is not that it is impossible; only that we did not find any. On the other hand, we have some good candidates for one-way functions (practical hash functions) which are considerably more efficient; therefore, for practical cryptography with systems that only need one-way functions, we use hash functions, not number theory. A hash function based on number theory has been tried but its performance is so abysmal that nobody is really interested in it.

Historically, the whole world was secret-key-only with no number theory; algorithms had evolved as ways to make big jumbles of bits. At best, some of these scrambling systems were designed to be permutations: these are modern block ciphers. We seem to know how to mix bits together so that the result cannot be unravelled (i.e. AES seems to be secure as a block cipher, and that's not for lack of trying to break it); but we don't know how to do it and disassociating the powers to encrypt and to decrypt. In other words, when we design a block cipher, we can inject the key, which selects the actual permutation, but we don't know how to inject it in such a way that the inverse permutation is not revealed as well. The only tools we have found yet to do that involve algebra and number theory, and they are slow.

On the other hand, the same algebraic tools open extra possibilities, namely asymmetric encryption and signatures. These extra features are so useful that we tolerate the performance issues implied by the use of these algebraic tools. So that's the historic point of view: the question is not why we don't make symmetric cryptography with number theoretic tools; rather, it is why we use the slow, cumbersome number theoretic tools at all. And the answer is that we don't know anything better for asymmetric crypto.


How is the recommended NIST modulus for DLP chosen/calculated?

How is the 3072-bit modulus derived?

Find the smallest $c$ such that $$p = 2^n - 2^{n - 64} - 1 + 2^{64} (\lfloor 2^{n - 130} \pi\rfloor + c)$$ and $q = (p - 1)/2$ are prime, and $p \equiv 7 \pmod 8$.  In this case, $n = 3072$ and so $c = 1690314$.

Use $g = 2$ as the generator.

(Here $\pi = \int_{-1}^1 dx/\sqrt{1 - x^2} = 4/[1 + \mathrm K_{i=1}^\infty i^2/(2i - 1)]$ as is customary.)

Why this shape?

This follows the procedure of RFC 2412, Appendix E, and matches Group 15 of RFC 3526:

We choose $p$ to be a safe prime—that is, choose $p$ so that $q = (p - 1)/2$ is also prime—so that the only subgroup orders are $\{1, 2, q, 2q\}$, which limits Lim–Lee active small-subgroup attacks.
We choose $p \equiv 7 \pmod 8$ so that, by the law of quadratic reciprocity, $g = 2$ has prime order $q$, since $g = 2$ is a convenient base, and a composite-order subgroup would leak some of the secret exponent.

(If your key is $h \equiv g^x \pmod p$ and $g$ generates the whole group or a composite-order subgroup rather than a prime-order subgroup other than $\{-1,1\}$, then it is easy to tell whether $x$ is even or odd by testing whether $h^{(p - 1)/2} \equiv 1 \pmod p$ or not; the same idea generalizes to composite $q$.)
We choose a shape with no particularly nice pattern to prevent SNFS attacks.
We choose specifically the semi-rigid RFC 3526 groups from the RFC 2412 process with the particular nothing-up-my-sleeves constant $\pi$—rather than $e$ or $\sqrt 2$ or $\cos 1$ or, worse, randomly chosen bits—to give slightly more confidence that there is no back door in the prime choice.

Actually, even better, we just use the elliptic-curve-based X25519 which is faster, safer, and free of magic constants like $\pi$!


Is there any probabilistic version of RSA?

Using randomization on the RSA key before encryption doesn't work as easy as a simple XOR: the key (or actually, key pair) has some complicated mathematical structure, and the public part of it (the modulus and the public exponent) need to be known by the encrypting party.

What might be possible would be to randomly chose the encryption exponent, and transmit it with the ciphertext. The receiver, knowing the factorization of the modulus, can then calculate a fitting decryption exponent and do the decryption.

Alice chooses randomly big primes $p$ and $q$ , calculates $n = p · q$, and publishes $n$ (but not $p$ nor $q$). (Alice might also calculate and store $\varphi(n) = (p-1)·(q-1)$.)
Bob gets to know $n$, and has a message $m$.
Bob chooses a random $e$, and calculates $c = m^e \bmod n$.
Bob sends $e$ and $c$ to Alice.
Alice calculates $d$ from $e$ and $\varphi(n)$ with $d · e \equiv 1 \pmod n$, e.g. using the extended euclidean algorithm.
Alice calculates $m = c^d \bmod n$.

I'm not sure if this would work quite reliably: with normal RSA a condition on $e$ is $\gcd(e, \varphi(n)) = 1$, which is easy to ensure knowing $\varphi(n)$, but less easy if it is not known. (But at least we know we need to choose an odd $e$, as $\varphi(n)$ is even.) I guess if we restrict $p$ and $q$ to safe primes ($p = 2x+1$, $q = 2y+1$ with $x$, $y$ also prime), $\varphi(n) = 2·2·x·y$, and other than multiples of $x$ and $y$ all odd numbers work for $e$.

The actual public key would then be just the modulus $n$, and the private key would be the factorization $n = p · q$.

This RSA-like cryptosystem (I wouldn't name it RSA) would likely be quite a bit slower on encryption (as you can't use a usual "small" exponent like 3 or 65537), as well as on decryption (since you first need to derive your decryption exponent, instead of using the same as always), without really offering much advantages.

The common way to make RSA encryption non-deterministic (which is needed for some formal security properties) is to use a random padding for the plaintext before encrypting it.

So the actual encryption is
$$ c = \textsf{pad}(m)^e \bmod n,$$
and the encryption is
$$ m = \textsf{unpad}(c^d \bmod n),$$
with a probabilistic padding function $\textsf{pad}$, and its (deterministic) inverse $\textsf{unpad}$.

This padding function can be something simple as prefixing the plaintext with some random bytes, or doing this followed by some (reversible) shuffling function, so all plaintext bits are affected.

In practice RSA is usually not used to encrypt a plaintext directly, but encrypts a randomly generated key for a symmetric cipher, which is then used to encrypt the actual plaintext.

In that case, you don't really need a randomization, as the plaintext is already random by itself.