How does this solution guarantee authentication of B and privacy?

Let's assume that T does send A,Kxt(Ra,Ts) to B as you have indicated. In that case upon reception and validating the signature, B would immediately be able to tell that the signature does not belong to A (and should thus not continue the exchange).

To try to take advantage of the exchange, T would have to alter the message from A so that it still looks legitimate (i.e. where the attached originator matches the signature), while substituting it's own identity to A's when interacting with B (so that B would reply with an encrypted message for T instead of for the original A; B has otherwise no reason to encrypt using Kyt as you've indicated in step 2). This could be done by changing the message from A,Kxa(Ra,Ts) to "T,Kxt(Ra,Ts) as T intercepts the message. At that point one of two things can happen:

B already knew A's identity, and would immediately be able to tell that T,Kxt(Ra,Ts) is not from A.
B does not have prior knowledge of A's identity. He then validates the message signature Kxt(Ra,Ts) which look like a valid signature for the attached identity T. Since it looks ok, he proceeds to generate Kyt(Kxb(Ra, Ks,T)) which T could decrypt to obtain the much needed Ks. However, since T cannot forge B's signature to generate Kxb(Ra,Ks,A), T can either send Kya(Kxb(Ra,Ks,T)) (a message properly signed by B which reveals T's identity to A) or Kya(Kxt(Ra,Ks,A)) (a message which attempts to hide T identity, but which is visibly not signed by B) to A. In either case, A knows that the channel is compromised and should not continue the exchange.


Explanation of the EPC Gen2 randomness standard's first rule

All is revealed in the last paragraph of that section, repeated below:-

  A cryptographic suite defines RNG requirements and randomness criteria for cryptographic operations. These requirements and criteria may be different, and in particular may be more stringent, than those defined above for inventory and password operations.

Their three randomness tests are an attempt to create a protocol that works in the real world without too much computational effort.  By crude analogy, it's like a children's test for randomness.  You only have 65536 possible choices anyway (assuming the RNG can reach them all), so there's little point in relying on huge computational effort to generate cryptographic strength Tag codes.  An attacker will just brute force them when appropriate tools are developed.

  Basically it wants a perfect 16-bit entropy.

Actually no. On this forum, entropy is defined as unpredictability within a certain system's defined scope.  There's a EPCglobal test that stipulates that sequential values are only 0.025% certain.  That's pretty poor to protect your bank account or nuclear arsenal.  For perfect entropy, the next value should only be predictable with a 0.0015% certainly, irrespective of prior RN16s.   The first rule is just a lax, perhaps pragmatic interpretation. It allows a ~22% bias in the numbers.
 And yes, that means you can have consecutive identical RN16's.  Prolonged consecutive RN16s might be an issue for the specific protocol implementation (I don't know).

  C#'s cryptographically secure PRNG cannot meet that requirement

Unfamiliar with C#, but if it's like a proper *nix language, then the cryptographic generator should be pretty good.  My interpretation of these rules is that they are much less stringent than those required for cryptographic purposes.  Thus C# might very well fail them in the strict technical sense.  It's just that C# is too good for them.  True randomness (opposite of bad randomness) is a slippery beast.  (It might be useful to flesh out your question illustrating how C# fails the tests).

You don't have these three rules in cryptographic RNDs.  Just that each byte is very exactly 1/256ths certain in the long run.


Application of Non-deterministic Processors in side channel attacks

Non-deterministic processors are generally sold as a method to vary processor timing and power.  To my knowledge they are theoretical as synchronous systems, as I have never seen any literature where one has actually been constructed.  The premise is that if you have varying instruction order, and completion time, you then have some level of robustness to side-channel attacks.  It is important to note that these are still synchronous systems.  The closest work that I know to this where hardware exists was body of probabilistic computing work by Palem, George and Marr.

You could easily make a non-deterministic system with asynchronous logic.  When I make asynchronous systems, creating noise is trivial because of the completion trees, and I do add random noise to the completion logic to slow it down as a verification of robustness against EMI.  This method would make the circuits robust to a side-channel attack due to random completion times for all logic.  Having said that, the dual-rail encoding of asynchronous circuits means that you cannot have a power attack, but only a timing attack.  You could size the completion trees so that they always required the same time; however, that would eliminate the speed gains of the asynchronous circuits.


Is it secure to use the same IV for encrypting a unique private keys?

If you are encrypting keys, then you should use a key wrapping method. The SIV standard is the best for this.

Regarding doing something ad-hoc and without an IV, it really depends on the mode of operation. But, I always recommend against doing something non-standard.


What's wrong with an iterative (with counter) hashed salted KDF?

TL;DR: You put less of a burden an any attacker trying to brute-force this.

And please note: Implementing PBKDF2 shouldn't be much harder than implementing your approach.

Now let's head over to the explanation why "your" scheme is really bad for password-hashing.

The scheme you propose is that each try cost you exactly two hash-function evaluations. One for the first hashing of the password and another for the evaluation of the outer hash.

From a theoretical point of view this is bad because you don't require a certain amount calls to a given function that has a "lower bound" on speed. Memory operations XOR and similar don't count usually. So you have only two evaluations and can only tweak something that doesn't really make a difference.

The last point is that "your" scheme ignores the way how hash-functions work. Hash-functions tend to get faster (measured in bytes / cycle) the more data is fed into the function. So your scheme requires one large invocation with small workload per byte, hence you'd have to feed in much more data (10-1000x) to reach the same workload. PBKDF2 needs less because hash-functions are inefficient for small amounts of data.

To concern your question what would be the disadvantages against PBKDF2 and co.
PBKDF2 is standardized ("your" scheme isn't) and widely accepted for usage (although generally considered the worst option).
bcrypt is generally considered a good choice as it puts a burden on the minimal memory ("you" don't) and is hard to compute on GPUs ("your" scheme seems very GPU-friendly, like PBKDF2)
scrypt is generally considered a very good choice as it puts even more of a burden on the memory side and protects quite good against FPGAs and ASICs ("your" scheme doesn't).


What is the strength and attack vectors of this simple scheme?

Short answer: Sorry, no, unfortunately your concept is neither a secure, practical nor efficient crypto scheme.

Slightly longer answer: To illustrate the impractically of your scheme, let's assume you are sending a completely random bit string $S$ of length $B$. In such case, in order to preserve perfect secrecy, you will at least have to send a list $L$ containing all possible values $[0..2^B)$ in random order, except for $S$ which is fixed at position $M$, where $M$ is the secret key you share with the recipient.

Now, if $M$ is selected completely at random from all possible values, it will also be a random element from $[0..2^B)$ and consequently be exactly as long, and contain as much entropy as, the message $S$ you want to sent.

The cipher text $L$ on the other hand, will be exponentially longer than the plain text message $S$. This is bad, because it means that your effort of sending the message securely, will be exactly as great as the effort you want your adversary to suffer trying to brute force guessing the key or the plain text.

Furthermore, if the plain text $S$ is not completely random, securely executing your scheme gets more complicated, but the conclusion doesn't change. If you maximize security, your effort of encoding and sending the plain text will be no less than the effort you want your adversary to suffer trying to break your scheme.


Is the seed/salt input of a Key Derivation Function confidential?

Now the thing I don't understand completely is that the random seed should be generated with a crypto-safe random generator, but can be uploaded in plaintext to the remote device. Is that true?

Yes. The salt is used to make sure that you do not generate the same device key twice. The session key however still depends on the master key, so an attacker cannot generate the device key.

So the device keys will be unique and secure. The random number generator needs to be secure to assure the uniqueness. You'll need to extract a relatively large salt for that (say, 128 bits or 16 bytes for as good as complete uniqueness or 64 bits in case you like playing on the edge) for that as well.

Using a device-specific unique identifier is more common. The advantage of a (large enough) salt is however that you do not need state. You cannot by - accident or otherwise - use a the identifier for two or more devices. Usually the salt is used in addition to other derivation data, if used at all.

  And is that because from a cryptanalysis point of view, using a deterministic random seed would leak information about the masterkeys?

No, no matter what, a KDF should never leak information about the master keys. This is why KDF's are generally either build on a block cipher - which of course protects the key - or a one-way hash functions / HMAC.

Notes:

I would use the word "salt" instead of "seed" here. If used at all when talking about KDF's, the seed is generally the input seed or key, not the salt or any other derivation data.
The HKDF RFC has a nice section on the use of a salt.
It is strongly recommended - I would even say required - to authenticate the device keys after derivation as an attacker could otherwise distort the salt value or set it to a constant value; for this generate a MAC authentication tag over data known by both parties and return it to the server, which can then verify the data.
Often multiple keys are required. Unless those keys rely on additional transmitted data you can use just the one key to authenticate the device; usually that's a MAC key or - even better - a separate key. Creating a set of device keys takes additional key derivation data, generally an ASCII label such as "MAC", "ENC" and "AUTH" or a number 00, 01 and 02.


Difference between second pre-image resistance attack and collision attack

You are mistaken. A collision attack is where you need to find any $x$ and $y$ such that $hash(x)=hash(y)$. Thus, you have much more freedom in finding the collision. This makes it "easier" for the adversary.


What is transaction capacity of a POS using 3DES DUKPT?

How many transactions? It depends on precisely how the 80 bit KSN has been divided between key set ID, and device ID.  There is freedom on this - the spec does not say how it should be done. In practice usually only 64 bits is used, and it is divided 6-5-5, giving 16 million key sets, 500k devices per key set, and 1 million transactions per device.  But you could easily increase that if you needed less key sets/devices.

No, changing the device's serial number is not standard practice. It is intended to remain the same for the life time of the device. It would need to be replaced (via an RMA procedure), or re-injected.


Stream Cipher Key Stream from Successive Hashes

The Insecurity of Proposed Scheme
It is not as secure as it seems, in modern cryptography standards it is totally insecure. It is vulnerable to basic Known-Plaintext attacks (KPA) and in Modern Cryptography, we want a cipher secure against at least Chosen Plaintext Attack (CPA) or better Ind-CPA.
Now take the idea
$$K' = H(X\mathbin\|K) \mathbin\| H(H(X\mathbin\|K)) \mathbin\| \cdots.$$
If there is a known-plaintext block for the first output $H(X\mathbin\|K)$ then attackers can hash again and again (sometimes written as $H^s(X\mathbin\|K)$ ) to reveal the others without needing a key. So your design fails the next-bit test, i.e. the next bit of your keystream is predictable with 100%. The known block is not restricted to the first block, it can be anywhere except for the last block. All output keystream after the known block can be calculated. The previous blocks are secured with the pre-image resistance of the hash function.
The CTR mode with Hash
Instead, we used the CTR mode ( [1] as it is designed for PRF - Pseudo-Random Function - ( here we assume that the $H$ is a PRF). The CTR mode is CPA secure.
$$H(k,0) \mathbin\| H(k,1) \mathbin\|  \cdots \mathbin\| H(k,\ell)$$ where the $\ell$ is the number that your message size divided into output size $b$ of the $H$ i.e. $\ell = len(m) / b$
The CTR mode doesn't require a PRP (Pseudo-Random Permutation, not proven yet, however, like AES),  since it doesn't need the reverse of the encryption. For example, see the ChaCha20. Some restricted environment saves a lot of space for the implementation.
Transforming this scheme into OFB mode
The OFB mode is also CPA secure (the ECB is not). OFB produce the stream as $O_j = E_k(O_{j-1})$ with $O_0 = IV$. The encryption is performed as $C_j = P_j \oplus O_j$
As noted by SEJPM in the comments; Let define $H'(m)=H(m\|K)$ and produce the keystream similar to OFB.
$$K'=H'(X)\mathbin\| H'(H'(X))\mathbin\| \ldots$$ Note that in every step the key is added again. So the attacker needs the key to process from the known output stream. Assuming the used hash is a Random Oracle (RO) then this converts it into PRF then we can use the security arguments OFB.
Note that the hashes are candidates to Random Oracles.


What is wrong with my Elgamal signature example?

Main problem is: in the question, a generator $g$ of order $q$ is used in the computation of [2.]. Thus if that computation and verification is in $\mathbb Z_{23}^*$ as in the attempted computations, then the modulus to use in [3.] is not $q=23$, but $q=22$ (if we use $g=5$), or rather $q=11$ (if we use another $g$ of prime order, which seems to be the intent: in [1.] it is considered that $\mathbb Z_q^*$ is the set of $k$ with $1\le k\le q-1$, which implies that $q$ is prime, as in the example).
Alternatively, we could use $q=23$ and $p=47$ as in the example (thus using modulo $47$ in the computation of step [2.] and signature verification); but then $g=5$ is unsuitable.

Further, the question misuse notations:

equivalence modulo, where $r\equiv a\pmod n$ means that $n$ divides $a-r$.
the operator $\bmod$, uniquely defining $r\,=\,a\bmod n$ such that $0\le r<n$ and $n$ divides $a-r$.
residue class modulo, where $R=a\pmod n$ means that $R$ is the set of all $r$ such that $n$ divides $a-r$ (this notation is less common, and should not be used without a notice and a good reason; its use in [3.] is accidental and unwelcome).

Note: the question does not follow the standard definition of ElGamal signature, which would use $s\gets k^{-1}\,(h(m)-r\,x)\bmod q$ and verify that $g^{h(m)}\equiv r^s\,y^r\pmod p$.


Can you hash an ssh key to generate a symmetric password?

Yes... Assuming:

That they were generated using enough entropy (probably yes if they were generated securely)
That they are only used for this purpose (I'd guess you can hash private key, but then as soon as it is compromised, your key is too)
It isn't done using public key, if that key is then published

As for hash function, any hash that isn't broken will do.


What is the most secure way to check that a given masterkey is valid?

Let call a user's Master Key for AES as $\mathit{MK}_u$ and generated as;

$$\mathit{MK}_u = \operatorname{PBKDF2}(\mathit{passwd}_u, \mathit{salt}, \mathit{Iteration})$$

where $\mathit{Iteration}$ between 40K to 100K

  1.  To salt and then hash the master key (once). The resulting salt and hash are stored somewhere - for instance in a DB. Later on, when the user has entered his master key, I add the stored salt and compare the computed hash with hash stored in DB.

$$\mathit{hashed} = \operatorname{SHA-256}(\mathit{salt} \mathbin\| \mathit{MK}_u)$$

A passive attacker can look at the DB and;

Password search on $\mathit{MK}_u$ with hashcat.

A better solution is also using;

a pepper which is stored in the application server: this totally prevents the passive DB attacker
$$\mathit{hashed} = \operatorname{SHA-256}(\mathit{salt} \mathbin\| \mathit{MK}_u \mathbin\| \mathit{pepper})$$
Key-Stretching as PBKDF2 or Argon2: this also prevents and make it harder even pepper is accessed from the applications server.

$$\mathit{hashed} = \operatorname{PBKDF2}(\mathit{MK}_u, \mathit{salt} \mathbin\| \mathit{pepper}, \mathit{Iteration})$$

  2. To generate a salt. The salt is encrypted using the master key. I store both the salt and the encrypted salt in a DB. Later on, when the user enters the master key, I try to decrypt the encrypted salt value with the master key and compare it with the salt stored in DB.

$$\mathit{salt}_e = E_{\mathit{MK}_u}(\mathit{salt}),$$
and store $\mathit{salt}$ and $\mathit{salt}_e$ on DB.

For the second approach, the attacker can execute a password search for $\mathit{MK}_u$, this is almost the same as the attack shown against the #1 case since the attacker only deals with one AES encryption. To increase the iteration, one can modify this as in bcrypt.

The modified #2 approach is the winner due to the pepper in the passive DB attacker model.


Question on using endomorphism on secp256k1 and negative results

Do you mean Algorithm 3.77 on p. 129?

The algorithm has an explicit case for whether $k_{j,i} > 0$ or not, in the loop in step 8.2.  Obviously a conditional like this is bad news for fast constant-time arithmetic if taken naively.  But as you noted, you can simply do a conditional subtraction in the coordinate field to negate the point, and then do the point addition unconditionally.


Is it possible to calculate the random factor $r$ from a encrypted message and the private key in a Paillier cryptosystem?

It is strange that Wikipedia propose to choose $r\mod N^2$ while $r^N\mod N^2$ depends on $r\mod N$ only:
$$(r+tN)^N=r^N+r^{N-1}tN^2+\ldots\equiv r^N\pmod{ N^2}.$$ It means that you can recover only $r\mod N.$ In order to do it you can use the formula from the cited answer
$$r\equiv (r^N)^M\pmod{ N}, $$
where $M = N^{-1}\bmod \phi(N)$.


CDH between two groups implies weakness of El-Gamal

You are actually quite close.

Because I'm not sure I understand the stated security notion, I will break IND-CPA security instead, you should be able to adapt the idea.

Let $m_0,m_1$ be our challenge messages with $m_0\neq m_1$. Let $(g,g^a)$ be the public key, $a$ be the private key and $(c_1=g^k,c_2=g^{ak}m_b)$ be the challenge ciphertext. Let $\mathcal O:G^2\to H:\mathcal O(g^a,g^b)\mapsto h^{ab}$. Assume $h$ to be known or to be defined as $\mathcal O(g,g)$.

We shall use $\mathcal O$ to build a Decisional Diffie-Hellman (DDH) oracle for the group G. As the IND-CPA security of ElGamal can only be reduced to DDH and not CDH, breaking DDH suffices to break IND-CPA security.

Let $h^a=\mathcal O(g,g^a)$ and $h^b=\mathcal O(g,g^k)$. Further let $h^{ak}=\mathcal O(g^a,g^k)$. Next compute $c'=c_2/m_0$. Return 0 iff $\mathcal O(g,c')=h^{ak}$ else return 1 as the guess for the challenge bit $b$.

So why does this work? Note how $c'=g^{ak}m_b/m_0$ which is $g^{ak}$ if $b=0$ and something else otherwise. Now $\mathcal O(g,c')$ sends this to $h^{ak}$ iff $b=0$, but as we have already computed $h^{ak}$ using the public keys, we can now make the comparison to verify our guess for $m_0$!


You should definitely read the original paper by Cleve in which this was proven.

To get some intuition, imagine that $2t = m$ and consider the following

For the protocol to be secure, no set of $t$ corrupt parties should be able to "reconstruct" the output by themselves.
For the protocol to be fair, the set of $m-t=t$ honest parties should be able to "reconstruct" the output by themselves.

Now, the problem is that you cannot distinguish which parties are corrupt and which are honest (otherwise the MPC problem would be trivial: simply discard the malicious nodes and work only with the honest ones), so you need to satisfy the two conditions above for any set of $t$ parties, which is clearly a contradiction.


Let $q$ be the base field cardinal; in your case, $q = 2^m$ for some integer $m$. We need $m$ to be prime for a Koblitz curve, otherwise the curve would also be defined on non-trivial sub-fields, allowing for faster discrete logarithm. For a "pairing-friendly curve", we need the curve order to be a multiple of a prime $r$, and the pairing produces outputs in $\mathbb{F}_{q^k}$ for some integer $k$ which is the embedding degree.

That degree $k$ is the smallest $k\gt 1$ such that $r$ divides $q^k-1$. For a random curve, that degree is very high, on the same order of magnitude as $q$ itself, so computing the pairing would entail using values that cannot fit on an existing computer (or in the whole universe, for that matter). This is the case for all "standard" Koblitz curves (K-163, K-233, and so on).

Moreover, since a pairing transforms discrete logarithm on a curve into discrete logarithm in a finite field, you would need that finite field to be large enough for discrete logarithm to be hard. It has been recently shown that discrete logarithm in fields with small characteristic, in particular binary fields, is much easier than the discrete logarithm modulo a big prime; current records include fields of more than 9000 bits in size. Therefore, if you want to use binary fields for pairings, and still retain some decent security, then you need to use a destination field so large that computations will be very slow, thereby voiding any computational advantage from the curve being binary (Koblitz or not).


Examine whether a hash function is collision-resistant

Your proof starts with the correct approach, but $h_1$ is not collision-resistant (CR), and therefore your proof should give you a hint as to why it's not CR.
Edit: I have removed the counterexample, since it should be easy to figure out using the proof attempt below.
Attempt to prove
You want to prove that:
If $h$ is CR, then $h_1$ is CR.
We prove the contraposition of that statement:
If there exists an adversary $\mathcal{A}^{h_1}$ breaking $h_1$,
then there exists an adversary $\mathcal{A}^{h}$ breaking $h$.
We want to assume the existence of $\mathcal{A}^{h_1}$ and use it to
construct $\mathcal{A}^{h}$.
$\mathcal{A}^{h}$ is playing the CR game, and
is supposed to output a collision for $h$.
To achieve that, we let $\mathcal{A}^{h_1}$ run.
Since by assumption $\mathcal{A}^{h_1}$ has a non-negligible
probability of succeeding, it will output a collision of $h_1$ with non-neglibile probability, i.e. a $x^a \neq x^b$ such that $h_1(x^a) = h_1(x^b)$.
We now want to win the CR game against $h$ and construct a collision for $h$ from $x^a$, $x^b$.
We know that $h_1(x^a) = h_1(x^b)$, and $x^a \neq x^b$.
Therefore, using your $g(\cdot)$,
$h(g(x^a)) = h(g(x^b))$.
There are two cases here:
1. Either: $g(x^a) \neq g(x^b)$
then we immediately find a collision:
since $h(g(x^a)) = h(g(x^b))$
and $g(x^a) \neq g(x^b)$,
the pair $(g(x^a), g(x^b))$ is a collision for $h$.
2. Or not: $g(x^a) = g(x^b)$
then we have to look further for a collision.
by $g(x^a) = g(x^b)$ we know that
$\underbrace{(x^a_1 \oplus h(x^a_2 || x^a_2))}_\text{first part}\ ||\ (h(x^a_3 || x^a_3) \oplus x^a_4)
 = (x^b_1 \oplus h(x^b_2 || x^b_2))\ ||\ (h(x^b_3 || x^b_3) \oplus x^b_4)$.
By $x^a \neq x^b$ we know that at least one of these 4 cases must hold:
2.1. $x^a_1 \neq x^b_1$
By $g(x^a) = g(x^b)$,
the first part of the input of the outer $h$ must be equal:
$x^a_1 \oplus h(x^a_2 || x^a_2) = x^b_1 \oplus h(x^b_2 || x^b_2)$.
This is where the proof breaks down. You cannot construct a collision from this.
2.2. $x^a_2 \neq x^b_2$
2.3. $x^a_3 \neq x^b_3$
2.4. $x^a_4 \neq x^b_4$
Hope I could help!


Your second Answer first.
[2] write down the key column wise as shown ,then fill the plain text row by row so you will get the matrix of (len(plaintext)/7 x 7), now for ciphertext, take first row and then start taking the value in ascending order of key,  see below, key and particular row
for ex for
row 1:- {1:e, 2:r, 3:a,4:s, 5:b,6:l,7:e}
row 2:- {1:c,2:a, 3:m,4:s,5:n, 6:a,7:b} and so on..
so your cipher text would be erasb lecam snab.....
-Key:    6   3   4   1   2   5   7
-PT:      l   a   s   e   r   b   e
-PT:     a   m   s   c   a   n   b
[1] In columnar transposition cipher you read column wise, for ex. in  above example, you can write entire characters of column 1 then 2 ...
so cipher text would be ecdtmecae rauooleds ammernena ....


Birthday problem applied to hash function with partition of the input set

Consider the classical birthday problem, where in a group (say, of students in a course) we want to know how (im)probable it is that there are at least two students with their birthday on the same day. A mathematical analysis tells that, under the assumption that the birthday is a uniform random variable (a fair approximation), and with only two inputs: the number $n$ of persons in the group, and the number $k$ of possible birthdays (about 365).

When selecting a partition of that group (say, for a lab class with limited capacity), that mathematical analysis will apply to the subgroup with $n'\ll n$, or not, depending on how the selection is made. If that's from a list sorted by birthday and split in intervals, the analysis can fail miserably. However, if the partition is random, or made with no clue about the birthdays (say from a list initially sorted alphabetically not showing the birthday), the analysis stands.

We can model a hash function as a (uniformly selected) random function from its input/starting set (perhaps, the infinite set of all bitstrings $\{0,1\}^*$ or finite subset of that) to its output set of $b$-bit bitstrings $\{0,1\}^b$ (with $k=2^b$ elements). When partitioning the starting set, if the selection is random, or made with no clue about the hash value of an element selected, then the mathematical analysis of the birthday problem applies (the basics are in this answer).

For a given hash function, it is easy to build a partition of $\{0,1\}^*$ such that this analysis fails, with collisions either much more or much less likely than predicted. To avoid this, we often use hash functions with internal parameter(s) (often called Initialization Vector) and a proof/argument that an adversary ignoring the IV would be unable to build a partition defeating the analysis better than by chance. We then pick the IV as a nothing-up-my-sleeves number, and can be confident that the mathematical analysis applies to any selection method making no reference to the IV (such as: the set of bitstrings that are the binary representation of the square of integers less than a billion).


Not something I have a real life example of, just an idea.

Certain computationally intensive tasks can be done much faster using memoization. Now if the compiler manages to automatically use memoization for some piece of code that code might run much faster than what the language notation suggests. I'm not aware of any compiler actually doing this though.

In C++, for example, any optimization is allowed as long as observable behavior is preserved which includes accesses to volatile memory and calls to I/O library functions. The compiler is allowed to transform the program in any way otherwise.


Why is Pearson hash not used as a cryptographic hash?

Observation:

An individual 1-byte pearson hash behaves like an 8 bit block cipher, encrypting the initial state using the message as key. This means that given a fixed message, each possible initial state produces a different output. This implies that a combined hash will never contain duplicate bytes.

Without this property a hash would forget about the initial state after about 1.5 kB and the combined hash would consist of identical bytes, degrading its quality to that of a single byte hash.

Never producing identical bytes is a trivial distinguishing attack, but in exchange you get a hash that doesn't produce a lot of collisions by accident.

Meet-in-the-middle attack to find pre-images:

Since the mapping between previous and next state is bijective and efficiently computable, a meet-in-the-middle attack, can find pre-images of an n bit hash in $2^{n/2}$ time, similar to how 2DES can be broken by a meet-in-the-middle attack. This is feasible for 64 bit hashes. The sponge construction used in SHA-3 suffers from a similar attack, which is why the capacity needs to be at least twice the desired pre-image size.

Pre-image attack by finding a fixed point:

The message we're targetting is called $m_0$. We're searching for a suffix $m$ such that $h(m_0)=h(m_0||m)$. This is a second pre-image on $m_0$ using that $m$ preserves the state.

We start with $n$ short messages, which we'll call the alphabet. There are $n^2$ different 2-symbol combinations, of which a fraction of $1/256$ will preserve the initial byte. We try to find about $n$ fixed points, so we need $n\approx 256$ (slightly larger $n$ might be required in practice, to compensate for random deviations).

Once we have enough fixed-points for the first output byte, we extend to two output bytes. For this, we look at sequences which consist of two one-byte fixed-points. All of these combinations are one-byte fixed-points as well, and $1/256$ of them are two-byte fixed points.

Repeating this procedure 8 times, produces an $m$ that preserves the full state. Since each iteration doubles the message length, we'll end up with a message that's 256 times the length of or short single-symbol messages (which consists of one or two bytes each).

For a 128 bit Pearson hash this produces a relatively long message ($2^{16}$ symbols or 100-200kB). You can start with $n\approx 256^2$, fixing two bytes of the hash at the same time, which increases the cost to $\approx 2^{32}$ hashes, which is still feasible. In exchange for the higher runtime, it reduces the message length back to 256 symbols or 500-1000 bytes.

As poncho pointed out, this attack can easily be adapted to first pre-images.

A quick and dirty implementation of this attack is available at: https://gist.github.com/CodesInChaos/4a399a26b98221155a92

My code naively enumerates all $n^2$ combinations and filters out the approximately $n$ that produce the desired result. Running the hash function in reverse to execute a meet-in-the-middle attack, it's possible to reduce these $n^2$ hash computations down to about $n$ hash computations. This optimization doubles the length of the hash you can break with a given cost and message size. So breaking 128 bit hash should have a cost of about $2^{16}$ hashes and breaking a 256 bit hash about $2^{32}$ hashes, where each message is about 1 kB.

Concerning your "improved" version:

The second pre-image attack above works without any changes to the attack code. Just replace the hash function with the "improved" version.


What aspect of elliptic curve encryption paradigms makes them especially susceptible to quantum based attack algorithms?

The elliptic curve discrete logarithm—like integer factorization and the classic finite field discrete logarithm—is an instance of the abelian hidden subgroup problem.

Any abelian (commutative) instance of the hidden subgroup problem can be efficiently solved in quantum computers with (variants of) the Shor algorithm; therefore all of the above problems would be rendered weak if large enough quantum computers were actually built. Here is a concrete polynomial-time quantum attack  for the elliptic curve discrete logarithm. See also this question.


Is the ring of octonions "commonly" used in Cryptography?

I can’t remember having stumbled upon them in RealLife™ cryptography either, but I am well aware of a somewhat older, related patent by the same author. (Which might or might not violate your “Please don't mention the mentioned previous version of this scheme.” depending on what you’ve previously been reading. The patent is titled “Schemes for signcryption” and dates back to 2012. The paper published before the one you’ve mentioned was “Fully Homomorphic Encryption without bootstrapping”, published in 2015.)

Anyway…

From what I’ve seen, “patents” related to cryptography are a good way to ensure that no one feels the urge to use your “invention” anytime soon – which might explain the (lack of) popularity of the term.

  Publication number: US20140169556 A1
  Publication type: Application
  Application number: US 13/995,312
  PCT number: PCT/US2012/070369
  Publication date: Jun 19, 2014
  Filing date: Dec 18, 2012
  Priority date: Dec 18, 2012
  Also published as WO2014098807A1
  Inventors: Masahiro Yagisawa
  Original Assignee: Empire Technology Development Llc
  Export Citation: BiBTeX, EndNote, RefMan
  Classifications (10), Legal Events (2)
  External Links: USPTO, USPTO Assignment, Espacenet

  Schemes for signcryption

  US 20140169556 A1

  Abstract

  Technologies are generally described for providing a signcryption scheme. In some examples, a method performed under control of a sender device may include calculating a public key of the sender device based on a system parameter, calculating a temporary public key of the sender device based on the system parameter, calculating a temporary common key of the sender device based on a temporary secret key of the sender device and a public key of a receiver device, calculating a ciphertext from a message based on the temporary common key and generating a signature of the sender device based on an intermediate parameter, the system parameter and the secret key of the sender device. The temporary secret key of the sender device, intermediate parameter and secret key of the sender device are engaged in a non-associative octonion ring.

  In some examples, a method performed under control of a receiver device may include calculating a public key of the receiver device based on a system parameter, calculating a temporary common key of the receiver device based on a temporary public key of the sender device and a secret key of a receiver device, deciphering the ciphertext based on the temporary common keys of receiver device, determining whether the digital signature received is generated by sender device. A temporary public key of the sender device, the secret key of the receiver device and the temporary common keys of the receiver device are engaged in a non-associative octonion ring.


What are the differences between a digital signature, a MAC and a hash?

These types of cryptographic primitive can be distinguished by the security goals they fulfill (in the simple protocol of "appending to a message"):

Integrity: Can the recipient be confident that the message has not been accidentally modified?
Authentication: Can the recipient be confident that the message originates from the sender?
Non-repudiation: If the recipient passes the message and the proof to a third party, can the third party be confident that the message originated from the sender? (Please note that I am talking about non-repudiation in the cryptographic sense, not in the legal sense.)

Also important is this question:

Keys: Does the primitive require a shared secret key, or public-private keypairs?

I think the short answer is best explained with a table:

Cryptographic primitive | Hash |    MAC    | Digital
Security Goal           |      |           | signature
------------------------+------+-----------+-------------
Integrity               |  Yes |    Yes    |   Yes
Authentication          |  No  |    Yes    |   Yes
Non-repudiation         |  No  |    No     |   Yes
------------------------+------+-----------+-------------
Kind of keys            | none | symmetric | asymmetric
                        |      |    keys   |    keys

Please remember that authentication without confidence in the keys used is useless. For digital signatures, a recipient must be confident that the verification key actually belongs to the sender. For MACs, a recipient must be confident that the shared symmetric key has only been shared with the sender.

The longer answer:

A (unkeyed) hash of the message, if appended to the message itself, only protects against accidental changes to the message (or the hash itself), as an attacker who modifies the message can simply calculate a new hash and use it instead of the original one. So this only gives integrity.

If the hash is transmitted over a different, protected channel, it can also protect the message against modifications. This is sometimes be used with hashes of very big files (like ISO-images), where the hash itself is delivered over HTTPS, while the big file can be transmitted over an insecure channel.

A message authentication code (MAC) (sometimes also known as keyed hash) protects against message forgery by anyone who doesn't know the secret key (shared by sender and receiver).

This means that the receiver can forge any message – thus we have both integrity and authentication (as long as the receiver doesn't have a split personality), but not non-repudiation.

Also an attacker could replay earlier messages authenticated with the same key, so a protocol should take measures against this (e.g. by including message numbers or timestamps). (Also, in case of a two-sided conversation, make sure that either both sides have different keys, or by another way make sure that messages from one side can't sent back by an attacker to this side.)

MACs can be created from unkeyed hashes (e.g. with the HMAC construction), or created directly as MAC algorithms.

A (digital) signature is created with a private key, and verified with the corresponding public key of an asymmetric key-pair. Only the holder of the private key can create this signature, and normally anyone knowing the public key can verify it. Digital signatures don't prevent the replay attack mentioned previously.

There is the special case of designated verifier signature, which only ones with knowledge of another key can verify, but this is not normally meant when saying "signature".

So this provides all of integrity, authentication, and non-repudiation.

Most signature schemes actually are implemented with the help of a hash function. Also, they are usually slower than MACs, and as such used normally only when there is not yet a shared secret, or the non-repudiation property is important.


How is the AEScrypt password related to the underlying AES key

I assume AESCrypt uses AES.

AEScrypt uses AES-256 in CBC mode. However, the program also uses SHA-256.

  When a file is encrypted with AEScrypt, there is no limit to the length of the password.

The Linux implementation of AEScrypt limits password to 1024 characters.  This means: it is practically unlimited, and you can use even very long passphrases. (The other versions of the program may vary in password length.)

  What is the relation between the AESCrypt password and the key size of the underlying AES encryption?

Nothing. The AES key will be always 256 bits. However, if the password has insufficient entropy, the AES key although 256-bits long will not be secure against password brute-forcing attempts.

Password security

The program uses salted (128 bit IV) SHA-256 to derive key to use from password. The hash is invoked 8192 times, which is quite small. This means that possible attackers are able to try brute-forcing quite a w few hundred thousand or a million passwords per second. Thus, passwords containing e.g. little entropy or just few dictionary words are likely broken with ease.

It is very likely that password is the weakest link. To have as much entropy as full AES-256 key, passphrase needs to contain around 25 words. Password would need to be somewhere around 50-100 characters. Generally, nobody often uses that long passwords (AEScrypt would allow it, see above).

Key use

The result of key derivation is a key that is used for AES (encryption/decryption) and HMAC-SHA256 (protect file integrity/prevent modifications). The same key is used for both purposes.

Issues (detected when analyzing code)

Ad-hoc salted hashing would be better replaced with scrypt. I'd like PBKDF2 more than hash, because it is well studied construct although it gives little other benefits.
It is not recommended to use one key for different purposes. (It does not seem to vulnerable, though.)
The AES implementation used is not side-channel free.
The /dev/urandom is used much more than is minimum needed. (Works badly together with any software that uses /dev/random.)

None of these appears very bad (i.e. easy to exploit in usual usage).


factorization of an integer $N$ that is in special format

If $p_0$ and $q_0$ are known then so are $p_i$ and $q_i$ by iterating.

To factor $N$, do the following:

$(p,q) \gets (p_0,q_0)$
while ($p \nmid N$) do $(p,q) \gets (next\_prime(p^2+q^2), next\_prime(2pq))$
Return $(p,q)$


Should new applications still use RSA? Is it worth going down the ECDH route for protocols?

Accordingly to a previous thread Why is elliptic curve cryptography not widely used, compared to RSA?, RSA is still widely used compared to ECC because:

RSA is well established
Its public key operations (e.g. signature verification, as opposed to signature generation) are faster than ECC
(most importantly) The RSA patents have expired, while a small company called Certicom holds a number of EC-related patents.

However, according to the NSA website, Elliptic Curve Cryptography provides greater security and more efficient performance than the first generation public key techniques (RSA and Diffie-Hellman) now in use. Thus, they decided to move to elliptic curve based public key cryptography for protecting both classified and unclassified National Security information.


How are all necessary parameters shared between signer and verifier in the ED25519 signature scheme?

Ed25519 is well-defined and requires you to use SHA-512 as internal hash function along with the twisted Edwards version of Curve25519, hence there's no need for a KAC when it comes to questions about the parameters. As for the integrity of the public key, there's not yet a standard for Ed25519 based certificates so there would be a custom solution needed for a given application.


How could Fully Homomorphic Encryption support power operations?

The answer is yes. Say we have an FHE scheme that supports addition and multiplication over an underlying field (so we are not limited to just 0,1). As in your question, assume we want to compute $Y=2^C$ where $C$ is encrypted and $Y$ is encrypted such that $y=D(Y)=2^m$.

We can do this using a basic square and multiply algorithm. Assume that we can do a bit decomposition on encrypted values. In other words, assume that given $C$ we can compute $C_1,C_2,\dots,C_n$ which are encrypted values (either 0 or 1) of the bits of the plaintext encrypted by $C$.

Then to compute $Y$ we would do:

A = E(1) # A is our accumulator
B = E(2) # 2 here since the base is 2
for i from 1 to n:
  A = (A*B*C_i) + A*(~C_i) # typical code for square-and-multiply puts this
                           # step in an if-block. If C_i==1: A = A*B. Since
                           # we can't know the value of C_i, we must do it this
                           # way. The end result is the same. If C_i=0, A=A.
                           # If C_i=1, A=A*B (the multiply step in square-and-multply
  B = B*B  # This is the square step
Y = A
return Y

where ~ is the NOT operation.

Therefore, all we need is bit-decomposition and NOT. The NOT operation is pretty simple. Since $C_i$ encrypts $0$ or $1$, $~C_i$ is computed as $(1-C_i)$.

Bit decomposition is harder. For an example of how it may be done, see the BGV paper.


Post-quantum SNARGs with near-constant verification?

There exists as of today two candidate SNARGs satisfying all your criteria. The first one is a recent proposal by Boneh, Ishai, Sahai, and Wu, which was presented last year at Eurocrypt. They achieve this construction by building upon the notion of linear-only encryption, which had been developed in previous works of some of the authors.

The second one, by Gennaro, Minelli, Nitulescu, and Orrù, is even more recent, it was presented at CCS this year. It generalizes square span programs, which were previously used to build SNARGs under pairing-based assumptions, to the lattice setting. It also comes with a proof-of-concept (unoptimized) implementation.

Both approach suffer from a common downside: they are designated-verifier, which means that a secret verification key is required to check the proof. If you crucially want public verifiability, even though it's theoretically feasible in a quantum-safe setting (as you mentioned, applying the random-oracle-based Fiat-Shamir transform to Kilian's succinct PCP-based proof system does the trick, and leads to logarithmic proof size and verification time), we do unfortunately not yet know of any concretely efficient construction that would meet all of your criteria.


A quick internet search delivered this description of Enigma:

  "This meant that the notches were engaged when Q, E, V, J and Z were uppermost on rotors I, II, III, IV, and V respectively and that therefore the turnover positions were R, F, W, K, A, remembered by the cryptanalysts at Bletchley Park by the mnemonic Royal Flags Wave Kings Above."

So this seems to be the right message yes.


Where should I store the private key (RSA) in a web application?

If you are in AWS, well and paranoid enough, you might want to use KMS. Google has a similar service. As for non-cloud environments, you can use either an HSM or a KMIP key server. Both HSMs and KMIP servers can be built in an High Availability way, and Amazon offer a good option to use SafeNet HSMs in the cloud, the service is called CloudHSM.

I am not a .Net expert, any more, but my understanding is that it has some adapters to plug in an PKCS#11 engine (HSM) transparently, so that you don't have to write any code for this to work. But it's probably a lot of configuration ugly work to get it to work.


By using the file's hash as IV, you also divulge the file's hash. This allows an attacker to make an exhaustive search on the file contents. It is not difficult to imagine situations where there are only a few millions or billions of possible file contents (e.g. the file contents are an encrypted SAN or password), in which case showing the data hash is an intolerable leak.

What you could use as IV is the result of HMAC over the file, using as key the same key than for encryption (or, preferably, derive both the HMAC key and the encryption key with a suitable PRF). The result would probably be quite hard to prove secure in any way, so don't do it for production; but it seems like a promising way to achieve context-free deterministic encryption.

"Context-free" means "without any memory". Some encryption modes require a random, unpredictable IV, while others just need nonces (e.g. a counter); you can obtain the former from the latter by encrypting the nonces with a block cipher, using a specific secret key for that. A counter still requires a bit of memory, which, depending on the situation, may or may not be easy to obtain. Some embedded systems would have difficulty updating a stored counter (permanent storage update draws a bit of current, a scarce resource on passive RFID systems). Since embedded systems rarely own a reliable source of randomness, they need deterministic encryption. Context-free deterministic encryption is thus an important niche functionality. Using HMAC to compute the IV for encryption may be a way to achieve that (with the important drawback of requiring a first pass on the whole file, before obtaining the IV which is need to begin encrypting it).


If you're talking about the S-DES developed by Professor Edward Schaefer of Santa Clara University, I can try to explain you the reason.

The algorithm takes in input a 10-bit key (K) but, using a key generation algorithm, the plaintext is encrypted using two different subkeys (K1 and K2) that are generated by the algorithm.

First, you should pass the 10-bit key through a permutation phase.

To generate K1 follow the following steps:

split the key in two binary string with the same length
pass to a simple left shift function (shift=1) both the keys and then join them again
pass the key (still 10 bits long) through a reduction-permutation function(P8) that simply picks out and permutes 8 of the 10 bits.
The P8 function works according to the following rule: 6 3 7 4 8 5 10 9

An example: assuming that the output of the left shift functions is the 10-bit key 0000111000, then the output of P8 function would be 10100100.

The output of (3) is K1, the key that will be used during the first round of the encryption procedure.

Now, to find K2 the procedure is practically the same:

the input to (1) is not the initial key (K) nor K1, but it is the 10-bits key that comes from the left shift function used to find K1. Thus, after you've splitted this key in two equal length substrings, pass them through the left shift function (shift=2). Note the different shift value
after you've joined the substrings again, pass the resulting 10-bits key to the P8 function to get K2.

Note: the initial permutation phase (P10) takes in input the initial 10-bit key and get us the 10 bits permuted according to the following rule:
3 5 2 7 4 10 1 9 8 6
The difference between P10 and P8 is only that P8 permutes only some bits while, P10, permutes all the 10 bits.

Hope I was helpful!


Hash function from narrower block cipher operated in CBC-encryption mode?

If the motivation is to rely on a DPA protected implementation of a block cipher, hash function constructions based on a block cipher (think of Davies-Meyer for instance with say Rijndael at 256-bit plaintext) could be used.
Alternatively, the issue of using small input size compression function to built secure hash functions with larger output size has been investigated in e.g. Nandi, INDOCRYPT 2005; Hirose, FSE 2006; Peyrin et al., Asiacrypt 2006 and following work, but is not entirely settled.

From an efficiency point of view, CBC-HASH is going to be at least $n$ times slower than any other hash function in the wild. (And practical security is always a balance between practicality, that is resources, and security.) In addition, the hash cannot be computed on the fly: one has to make $n$ passes over the message which is cumbersome in many scenarii (think embedded devices for instance).

Case $n=1$. Assuming the underlying block cipher is denoted by $E$, take whatever you want for the message blocks $M_i=N_i$, $l>i>1$ for some big $l$ and:

$M_0=0$ and $M_1=E_K(R)$,
$N_0=R$ and $N_1=E_K(0)$.

for some $R\neq 0$ if $IV=0$ and $R=IV$ otherwise.
Then, note that the hash output is the same, so that you have a collision for $M$ and $N$. This is possible because $K$ and $IV$ are known values.

Case $n=2$. Choose some index $\xi$ and choose the message blocks $M_1$, ..., $M_\xi$ and $N_1$, ..., $N_\xi$ randomly and choose the remaining message blocks so that $M_i=N_i$, $i=\xi+1, ..., l$. Then, use the trick above to ensure the key for the next round is identical for both messages (i.e. create a collision at stage $\xi$ during the first pass instead of at the beginning). Then, wait for a collision to happen in the 2-nd round at block $\xi$. It happens with probability
${2^{block\_size/2}}$ for a primitive $E$ with block size $block\_size$. This appears to be possible as the first message blocks are randomly chosen.

Case $n>2$. This procedure can be followed up to any round $n$ with complexity $2^{block\_size*{n-1\over2}}$.

Example.
With the 3DES as $E$ and an hash output size of 512 bits, this leads to a collision attack for CBC-HASH with 8 rounds that has complexity $2^{32\cdot 7}$ instead of the $2^{32*8}$ of the birthday paradox.

I am more generally concerned about the small "bandwidth" issue due to the use of an underlying CBC with a block cipher of small output size.


Does knowledge of original file size provide a cryptographic weakness?

Yes, feasibility to guess the plain text size might be a serious vulnerability in real life scenarios. For instance, in traffic analysis the approximate length of the messages in a communication, might reveal enough information about what is communicated, for it to be possible to deduce the gist of it. If such threats exist in your case, however, you will probably have to consider more radical counter measures than just apply a few byes of PKCS#7 padding at the end of your file fragments.


When is AES chosen instead of a stream Cipher (e.g., RC4) during an SSL connection?

I understand that AES would be a better choice for applications where all the data is available at once, permitting the use of large blocks. RC4 on the other hand is more suited for applications where continuous data (that may not be available all at once) is to be encrypted (e.g., real-time data).

No, this is not accurate. The block size of AES is just 128 bits. It makes no difference with practical data sizes on the web, since at most you add 16 bytes to ciphertext size.

And anyway, many modes of operation, like GCM which is one of the more common choices with modern servers and browsers, turn AES into a stream cipher.


OpenSSL des-ede3 not producing same output as test vector implies it should be

It looks like there's an error in the test vector.

The text of Appendix B.1 states:

  P1 = “The quic” = 5468652071756663

... which is incorrect.

The hex encoding of The quic is actually 5468652071756963 (note the transposition of the i/69 to an f/66 in the encoding.

e.g. encrypting the test vector as intended:

$ echo -n 'The quick brown fox jump' | openssl  des-ede3 -nosalt -nopad -K '0123456789ABCDEF23456789ABCDEF01456789ABCDEF0123'  | xxd -c 8 -ps
1ccf23869d09333e
cce21c8112256fe6
68d5c05dd9b6b900

... and encrypting the test vector as hex encoded:

$ echo -n 'The qufck brown fox jump' | openssl  des-ede3 -nosalt -nopad -K '0123456789ABCDEF23456789ABCDEF01456789ABCDEF0123'  | xxd -c 8 -ps
a826fd8ce53b855f
cce21c8112256fe6
68d5c05dd9b6b900

It looks like this error has been in NIST SP 800-67 since version 1 in 2004.


Are non bijective sboxes weaker (on feistel networks)?

No.

It is one of the main features of a Feistel network that both decryption and encryption just need to evaluate the S-box in the same direction. It could potentially be a weakness if you used invertible functions in the S-boxes: First, you are limited to a much smaller set of functions to choose from. And then you might not be able to find a function which has the other important properties, which are actually needed for security, e.g. non-linearity, diffusion and confusion, a balanced output, etc.


Does clustering the AES Sbox look up table to 32 bit entry per index, help reduce vulnerability to cache timing attacks?

The answer to this sort of question would depend greatly on your hardware (both your CPU and cache architecture).

On the other hand, I don't see this adding any protection on common hardware.  When a program on (say) an Intel chip does a byte access, the CPU generally issues a read for a larger segment (often the cache line), and then extracts the desired byte from it.  From the CPU's and memory's viewpoint, reading the entire line is no more expensive than reading a single byte (the memory bus is designed to pull in an entire line at once), so it might as well access it all (and so fill in the entire cache line, just in case you access other parts of that same line in the future).

So, you're doing manually (via explicit instructions) what the CPU is likely able to do automatically (and cheaper; it already has the hardware in place, and so it doesn't spend extra cycles to do so); I would expect that this is a waste of time.


The sign of the correlation in linear approximation

Since $c(f,g)=\sum_x (-1)^{f(x)\oplus g(x)}$, we can write  $$c(u\cdot x, v \cdot g(x\oplus K))=\sum_x (-1)^{u\cdot x \oplus g(x\oplus K)}$$ where the sum ranges over all binary strings of length $n$ which is a vector space over the binary field. Now let $y=x\oplus K$ and note that as $x$ ranges over this vector space so does $y$. Therefore we can rewrite the same correlation as
$$c(u\cdot x, v \cdot g(x\oplus K))=\sum_y (-1)^{u\cdot (K \oplus y) \oplus g(y)}=(-1)^{u\cdot K}\sum_y (-1)^{u\cdot  y \oplus g(y)}.$$
The last sum is just $c(u\cdot x, v \cdot g(x))$ thus giving the claimed result.

This is also related to a shift property of the Walsh Hadamard transform which is after all a Fourier transform.


Why is it important to generate a pseudorandom permutation from a pseudorandom function?

If you applied a PRF directly to the message to obtain cipher-text, you would not have the guarantee that you could actually decrypt the message.

Suppose the PRF maps $n$ bit inputs to some $m$ bit output.

The mental model of a PRF is as follows. You have have a gnome in a black box. When you hand him a string from the input space, he flips a coin $m$ times and outputs the result of these flips concatenated together. He then records this in his notebook so that if you pass the same $n$-bit input to him again, he can give you the same output.

If you think about this model carefully, you'll realise that there's actually nothing to stop two inputs mapping  to the same output. You just have to be lucky enough for a collision to occur. Due to the birthday paradox, this happens more often than you'd expect and there will typical be quite a lot of collisions.

Thus, if we try to encrypt our message directly with a PRF, there's no guarantee we'd be able to invert it!

A PRP is a PRF with the additional restriction that for every input value maps to precisely one output value and that every output value maps to precisely one input. With a PRP we're guaranteed to have an invertible function, which is precisely what we need to construct a block cipher.

In the PRP mental model, the gnome has a list of all possible output strings of length $m$. Every time he is passed an input he hasn't seen before, he selects an item from the list of output strings at random. He then removes this item from the list (so it can't be re-used) and writes in his notebook the input string and which output string he mapped it to. If he ever sees the same input again, he can then give the output he's recorded in his note book.

We can see that this construction is quite a bit more complex than the PRF set-up. The Luby-Rackoff construction is so neat because it gives us a nice way to convert a secure PRF in to secure PRP. There is a similar result for going to a PRF from a PRG, which is called the Goldreich-Goldwasser-Micali construction.

The end result being if you can build a secure pseudo random number generator you can also build a secure block-cipher. This is a neat result, which is why it's so often referred to in the cryptographic literature.


Is there a CSPRNG capable of generating a large sequence of numbers from a single seed?

A PRNG, by definition, outputs a sequence of arbitrary length from a finite state. So you can get as many chunks of 64 bits as you may want from any PRNG. Or, said otherwise: if you have something that gets stuck at some point, then it is not a PRNG.

Such a PRNG is said to be "cryptographically secure" (that's the "CS" in "CSPRNG") if the output bits are unpredictable; that is, given n successive output bits from the PRNG, it is computationally unfeasible to predict the next bit with probability substantially better than 0.5. If you use a 64-bit seed, then there are only 264 possible initial states for the PRNG, a large number, but not practically infinitely so. It is expensive but technologically possible to enumerate all possible 264 seed values, and get the corresponding PRNG output. In that case, it suffices to try all these seed values to pinpoint the one which produces the PRNG output observed so far; afterwards, the future output of the PRNG can be predicted with 100% accuracy, which means that the PRNG is not cryptographically secure.

If you want a really secure PRNG, then you need a larger seed space (typically 128 bits or more). Take care that a big seed is not sufficient to get a CSPRNG; it is merely a necessary condition, to prevent the exhaustive search attack described above.

For some examples of CSPRNG, see NIST SP 800-90A. That document actually separates the "PRNG" part (they call it "DRBG", the "D" meaning "deterministic") from the seeding, and enforce regular re-seeding. You can also get a CSPRNG from any good stream cipher (e.g. the ones from the eSTREAM portfolio) or by running a block cipher (with large blocks, 128 bits or more) in CTR mode.

There are a number of published PRNG (e.g. the Mersenne Twister) which are not meant for cryptography, and fail to be unpredictable by attackers. Such PRNG are good enough for non-adversarial situations (e.g. simulation of physics experiments) but not for anything related to security.


How safe is it to derive MAC key from a hashed password?

As mikeazo notes, PBKDF2 supports the generation of arbitrary amounts of key data.  It accomplishes this simply by appending a running counter to the salt and rerunning the key derivation process to generate new output blocks, so there's no obvious reason why you couldn't apply the same construction to bcrypt.

The scrypt KDF also supports arbitrary-length output, which is not surprising, since it's based on PBKDF2.

Ps. In PBKDF2, each block of the output is computed independently using the full iterated key derivation process.  This has the disadvantage that the CPU time needed to run the KDF scales linearly with the desired output length, whereas the work of an attacker who only needs one of the output blocks doesn't.  (This is not a far-fetched scenario: for example, if you generate two output blocks and use one of them as the encryption key and the other as the MAC key, an attacker only needs to generate the latter to check whether he guessed the right password.)

Given this, it would seem better to generate only one output block with PBKDF2 (using a correspondingly larger iteration count) and then use a lighter-weight KDF (or even PBKDF2 itself with a low iteration count) to expand the output to the desired length.  Of course, given that this seems like such an obvious thing to do, one might wonder why PBKDF2 wasn't specified that way to begin with.

Interestingly, this also seems to be more or less how scrypt uses PBKDF2.  Specifically, scrypt invokes PBKDF2 twice, both times with an iteration count of 1: first to expand the passphrase into input for the memory-hard mixing function SMix (on which the hardness of scrypt is actually based), and again to hash the output of SMix into the desired amount of key material.


Why is this MAC based on secure PRF with ordering and randomization insecure?

$\langle \langle 1\rangle || m_1, 0^n \rangle$ is a valid tag on $m = m_1$


Is the "New Hope" Lattice Key Exchange vulnerable to a lattice analog of the Bernstein BADA55 Attack?

Yes the Bernstein attack is applicable but the impact of the attack is reduced because the party generating the parameter is also going to be a legitimate participant of the key exchange.

Here is why the attack does indeed apply.  Consider a case where Bob and Alice wish to conduct a key exchange using the New Hope Lattice-Based Key Exchange.  Bob will be the key exchange initiator and Alice will be the key exchange responder.  Bob wants to help the internet surveillance authorities run by Bernstein's "heroic" eavesdropper "Eve."  However, Bob does not want to be seen cooperating with Eve by turning over the key for the key exchange or the plaintext information to Eve.  Bob asks Eve for a more subtle way to help her "heroic" cause.

In Bernstein's "White Paper for a Black Hat" he and his co-authors assume that Eve knows a class of weak elliptic curves unknown to the rest of the world.  Eve knows that one would randomly select one of these weak elliptic curves with probability p. To carry this attack over to the New Hope Lattice domain we must assume that Eve knows a class of weak New Hope basepoints that are unknown to the rest of the world.  Let us assume that Eve knows of such a class of weak basepoints and that these weak basepoints occur with probability p.

The New Hope basepoint generation scheme would have Bob generate a random seed and use the SHAKE-128 algorithm and some other processing to produce a random basepoint (polynomial) for the key exchange.  Bob is supposed to do this only once.  Hence the probability that Bob randomly hits a weak basepoint is p.  However, Eve tells Bob not to generate just one basepoint but gives Bob a long list of seeds that will generate weak basepoints.  Instead of generating RANDOM seeds Bob uses a seed from the list that Eve gave him.

Bob and Alice complete the New Hope key exchange as described by its authors.  Eve collects the key exchange and uses her knowledge of the weakness in the basepoints to break the key exchange and recover the traffic.  While it is true that Bob could have compromised the key exchange to Eve in many other ways.  The method pointed to in your question is a protocol weakness that could be corrected.

Fortunately, there is a very easy fix to the New Hope protocol that eliminates this attack.  If the initiator and the responder both generate random seeds, exchange them and a concatenation of these seeds is used in the generation of a random basepoint then the attack only works if BOTH Bob and Alice are colluding with Eve.  The right thing to do in New Hope is to have both initiator and responder contribute to the basepoint generation process.  In protocols like TLS that already have exchanges of random information (the "Hello" messages) this protocol change seems entirely fitting.

Ironically Bernstein has been questioning the underlying security of the cryptography on which the New Hope scheme is based and has referenced a number of large classes of lattice parameter sets that are weak


Is it right about an example of bilinear map $e$?

The simplest construction that I know of is given in Section 6.9 of the book by Hoffstein, Pipher and Silverman (5.9 in the first edition). I also talk about it in Section 3.3 of this (but I do not claim that it matches the book's quality of exposition).

First, you need a prime $p$ with two properties:

You want $p\equiv 2\pmod 3$, this allows you to easily construct a supersingular curve over $\mathbf{F}_p$ (as $Y^2 = X^3 + b$ for any $b \ne 0$). Remember that a supersingular curve is one which has $p+1$ points.
You want $p+1$ to have a large prime factor, ideally $q = (p+1)/6$ should be prime. This allows you to pick a point of large prime order. In fact, it is best to first choose a prime $q$ of appropriate size, and then look for a suitable $p$.

For this example, I take $p = 587$ and $b = 1$. Then $q = (p+1)/6 = 137$ is prime, and the point $P = [332,103]$ has order $q$ on the curve $E$ with equation $Y^2 = X^3 + 1$ over $\mathbf{F}_p$. I note $E(K)$ the goup of points of $E$ with coordinates in $K$ ($K$ will be either $\mathbf{F}_p$ or $\mathbf{F}_{p^2}$.)

The basic tool is the Weil pairing, which I will note $e_q$. All you need to know about it is that it is a bilinear map from the group of $q$-torsion points of the curve (i.e., the group of points $P$ such that $qP = \infty$) to the group of $q$th roots of unity in $\mathbf{F}_p$ (i.e., the group of all $x\in \mathbf{F}_p$ such that $x^q = 1$). You can use many computer algebra systems to compute the Weil pairing, I use Pari/GP:

gp > p = 821;
gp > p%3
2
gp > isprime(p)
1
gp > q = (p+1)/6
137
gp > isprime(q)
1
gp > E = ellinit([0,1]*Mod(1,p));
gp > until(ellorder(E,P) == q, P = random(E));
gp > P
[Mod(332, 821), Mod(103, 821)]
gp > ellweilpairing(E,P,P,q)
Mod(1, 821)

However, the Weil pairing is not suitable as is for cryptographic purposes because it is also alternating, meaning that $e_q(P,P) = 1$ for all $P$, so we need to modify it. What we do is consider the curve as being defined over $\mathbf{F}_{p^2}$, and apply the Weil pairing in this curve. More precisely, it we let $\zeta$ be a primitive $3$rd root of unity in $\mathbf{F}_{p^2}$ (prove that it exists), then for any point $P = [x_P,y_P] \in E(\mathbf{F}_p)$, the point $P' = [\zeta\cdot x_P,y_P]$ is in $E(\mathbf{F}_{p^2})$. Moreover, if $qP = \infty$, then $qP' = \infty$ as well, which means that $P'$ can be an "argument" of $e_q$. Hence, finally, we define our "modified Weil pairing" $\hat{e}_q$ on the original curve (over $\mathbf{F}_p$) as follows: for a point $Q = kP$ (for some integer $k$), we let
$$\hat{e}_q(P,Q) = e_q(P,Q'),$$
where $e_q$ is the ordinary Weil pairing, but applied on the curve over $\mathbf{F}_{p^2}$. In practice:

gp > u = ffgen(p^2, u);
gp > until(z != 1, z = random(u)^((p^2-1)/3));
gp > E2 = ellinit([0,1],u);
gp > ellmodweilpairing(E,P,Q,q) = ellweilpairing(E2,P,[z*Q[1],Q[2]],q);
gp > ellmodweilpairing(E,P,P,q)
562*u + 172

We can see that this pairing is bilinear:

gp > Q = ellmul(E,P,99);
gp > ellmodweilpairing(E,P,P,q)*ellmodweilpairing(E,P,Q,q)
693*u + 108
gp > ellmodweilpairing(E,P,elladd(E,P,Q),q)
693*u + 108


How should I check the received ephemeral Diffie-Hellman public keys?

The check $y_b^q = 1 \mod p$ is there to prevent two possible weaknesses:

Suppose someone gave us (either because of a programmer error or deliberate attack) gave us a $y_b$ value of small order.  If so, then someone listening in can guess the shared secret you derive.
Suppose an attacker gave us a $y_b$ value with an order with a small factor $r$.  Then, by seeing the shared secret value $z$ you derived (which will be one of $r$ possibilities), then the attacker could rederive the value $x_a \bmod r$; whether that is interesting would depend on whether you reuse $x_a$ elsewhere.

Now, for a "safe prime" (one where $q=(p-1)/2$ is prime), neither of these attackers are of much concern; there are no small subgroups other than the trivial order-1 and order-2 subgroups (and yes, you are correct, all group members in $[2, p-2]$ are either of order $q$ or $2q$).  In addition, which the attacker could give us a $y_b$ value with order 2q (and potentially learn $x_a \bmod 2$, that just gives him one bit of your private exponent; as he can't learn anything else, this is not much of a concern (even if you reused $x_a$ in other DH exchanges).

On the other hand, NIST SP800-56 doesn't assume a safe prime.  In fact, a strict reading of NIST SP800-56 would appear to forbid it; if you look at Table A, it specifies the size of $q$ to be either 160, 224 or 256 bits (and not "at least so many bits", precisely that size).

As for your question as to whether the check $2 \le y_b \le p-2$ will always exclude all members of an order-2 subgroup, that is actually true for any prime $p$, not just "safe primes".  For any prime $p$, the only group member with order 2 will be $p-1$.

Also, if you think you want to perform the $y_b^q = 1 \mod q$ check (even though it doesn't appear to be strictly necessary), one optimization that a safe prime allows is that you can compute the Lagrange symbol; that's a short cut for computing $x^q \bmod p$ for $q = (p-1)/2$ (which is a lot faster than computing $x^q \bmod p$ directly)


is this possible to use asymmetric encryption schemes as order preserving encryption

No, because an adversary can pick an arbitrary plaintext, encrypt it using your public key, and then compute whether his plaintext is "less than" or "greater than" the plaintext corresponding to the ciphertext he wants to decrypt. He can do this intelligently several times to "home in" on your ciphertext's corresponding plaintext using binary search, allowing him to successfully decrypt any ciphertext using only the public key and your order relation in time $O(\log n)$ where $n$ is the size of the plaintext/ciphertext space, breaking the encryption scheme.

If this isn't what you meant, please add more detail to your question, including a list of the security properties desired.


Explain the problem that the solution of "chaotic cryptography" is intended to solve

You have the question tagged with encryption, cryptanalysis, and symmetric. So it sounds like it is a method of symmetric encryption.

Explain why other pre-existing solutions are unsatisfactory

e.g. they're slow, not provably secure, not well understood, etc

Make sure these points are actually true and supported by references

Explain the algorithm and how it is an improvement or why it is a better solution than previously listed solutions

Explaining the algorithm may be lost on people who have no experience with cryptography, especially if they have no experience with math or algorithms in general. But the guts of what the algorithm does is not always as useful as what the algorithm accomplishes.

Note

I was going to leave this as a surprise to the user who asked the question, but it has been noted that the answer should state so explicitly:

Attempting to pursue this strategy with "chaotic cryptography" is going to fail at step 2 and step 3.

This is not because the strategy is insufficient, it is because there are no good reasons to pursue "chaotic cryptography".

Currently employed symmetric encryption algorithms are efficient, provide provable resistance to known attacks, are well understood, and importantly are standardized for public use.

To quote Geoffroy Couteau:

  There have been almost no (if any) serious work on chaotic crypto providing any tool to base its security on clear and well-defined fundamental problems which resist cryptanalytic attempts. Today's chaotic crypto is at best a buzzword variant of the security-by-obscurity approach to crypto, which consists into thinking that "well, if we do many complicated stuff, that's probably hard to invert".

"Chaotic cryptography" is frequently coupled with "image encryption", and the latter demonstrates lack of understanding of basic principles of information theory and programming: There are no special requirements when encrypting images as opposed to any other types of information. Symmetric ciphers simply operate on bits.


Can you help me understand this (old) school question related to RSA usage?

As in the other questions: Such low numbers can lead to curious-and-misleading effects. For example in this case: you choose $q=5$, and it happens that this is equal to $\lambda(15) + 1 = 5$. And that is a coincidence of this example, not a general relation.

Now… could you have chosen 5 for e? And follow-up question: Why not? The solution provided has

no

and

because 5 has a common divisior with n

Which question ans answer are you quoting here? Because it's not the one you linked to.
And I would actually say, there is no reason that $e$ has to be coprime to $N$ - except that it would be really terrible if anyone just tried to calculate $gcd(e,N)$. However, the encryption and decryption still work in the sense that you can retrieve the plaintexts (injective function).
Regarding the coincidence in th example: For every modulus, you have that $m^{\lambda(N)} = 1 \mod N$ with Carmichael function $\lambda$, and in turn $m^{\lambda(N) + 1} = m \mod N$.
And then, for two different primes $p,q$ this can be calculated as $\lambda(pq) = lcm(p-1,q-1)$. Alternatively, this is $\lambda(N) = (p-1)(q-1) / g$ for $g = ggt(p-1,q-1)$.
From that, we can see that if $\lambda(N) + 1 = q$, then we know immediately $p-1$ is a divisor of $q-1$.

So the mathematics "work", no information is messed up, but the desired encryption is not reached at all. Is there a reason why 5 is kind of "neutral exponent"? Does such a thing also happen for "real" rsa values?

Yes, it does, but not for either $p$ or $q$. It happens for $k \lambda(N)+1$ for any arbitrary integer $k$.

In this example e=5 is equal to q, is that what makes the encryption become an "Involution Mathematics" (wikipedia)?

Since this is taken from the linked question - this is something similar, but not the same. An involution happens whenever $e=d \mod \lambda(N)$, because then you have that $ed = e^2 = 1 \mod \lambda(N)$. And again, it's pure coincidence in this number example, that it is equal to $q$. That is wrong in general.


Updated answer

The question was changed, so here is my updated answer.

This scheme is not secure against known-plaintext attacks.  It is no better than an ordinary Hill cipher.

If you iterate the recurrence relation you listed, we find that

$$x_k = Bx_0 - Cx_{-1}$$

and

$$x_{k-1} = Cx_0 - Dx_{-1}$$

where $B,C,D$ are matrices given by $B=f(A)$, $C=g(A)$, $D=h(A)$, and $f(\cdot),g(\cdot),h(\cdot)$ are publicly known polynomials that depend only upon $k$.  (For instance, for $k=4$, we have $B=f(A)=A^4 - 3A^2 + \text{Id}$, $C=g(A) = A^3 - 2A$, $D = h(A) = A^2 - \text{Id}$.)

It immediately follows that this scheme is insecure against known-plaintext attack.  Each known plaintext pair gives you $m_0$ (the message), $u_0$ (the initialization vector), $x_k$, and $x_{k-1}$ (from the ciphertext), so we know $x_{-1},x_0,x_{k-1},x_k$.

Therefore, each known plaintext gives us two linear equations, with the unknowns being the elements of $B,C,D$.  If the matrix is $n\times n$, then after $1.5n$ known plaintext pairs, we have enough information that we can probably recover all of $B,C,D$, and then the scheme is broken.

In fact, I expect this scheme might even be breakable via a ciphertext-only attack.  I think we always have $C^2 = BD + \text{Id}$.  Therefore,

$$Cx_k = BCx_0 - C^2 x_{-1}$$
$$Bx_{k-1} = BCx_0 - BD x_{-1}$$

so

$$Bx_{k-1} - Cx_k = x_{-1}.$$

Note that in a ciphertext-only attack, $x_{-1},x_{k-1},x_k$ are all known (from the initialization vector and the ciphertext).  Therefore, each ciphertext gives us a linear equation on the unknowns $B,C$.  After observing $2n$ ciphertexts, we should be able to solve for the matrices $B,C$.  Then deriving $D$ is easy, and we will be able to decrypt.

Therefore, it looks like there is even a ciphertext-only attack on this scheme.  Caveat: I haven't validated this ciphertext-only attack carefully, so check the details yourself.  I might have made a mistake somewhere.

So why do those three papers still study Hill ciphers?  I don't know, that would be an excellent question for the authors of those papers!  Only they will know what was going through their minds.  I wasn't able to read the first two papers (due to the paywall), but I took a quick look at the third paper, and I do not think there is a good reason to study these ciphers.

Keep in mind that there are a lot of papers out there, and quality varies widely.  Just because a paper has been published doesn't mean it is any good.  You will do better by sticking to conferences and journals that are well-reputed; once you start wandering off into obscure conferences and journals that are not well-regarded among cryptographers, the quality might vary tremendously.  Similarly, if you find a crypto paper published in a conference that is not dedicated to cryptography, you might also want to be a bit cautious or skeptical.  My suspicion is that the three papers you have found just aren't very good, and so there is not much more to say.

Original answer

Your proposed scheme is not secure.

If $A$ is public, given $x_{i+1},x_i$ you can compute $x_{i-1}$ via the equation

$$x_{i-1} = Ax_i - x_{i+1}.$$

Everything on the right-hand side is known.  Thus, an eavesdropper can start with $x_k,x_{k-1}$ and iteratively compute $x_{k-2},x_{k-3},\dots,x_1,x_0$.  Once the eavesdropper has computed $x_0$, he knows the message $m_0$.

Another way to see that your proposed scheme is insecure is that there is no secret key.  There is no secret known to the recipient that is not also known to the eavesdropper.  Thus, if the recipient can decrypt, surely so can an eavesdropper.

So, your scheme is trivially broken under ciphertext-only attack.  It is even worse than an ordinary Hill cipher.  The attacker doesn't even need known plaintext.


can you suggest any applicayion for implementing threshold homomorphic encryption cryptosystem(Paillier cryptosystem)

How about this: an electronic voting scheme. Votes are cast onto a publicly readable but append-only bulletin board as encryptions under the system public (Paillier) key. Anyone can homomorphically compute the sum of the cast votes. The vote admins each hold a share in the secret key; they must cooperate in order to decrypt anything. In this way, as long as there is one honest administrator, he can ensure that only the correct ciphertext (the one corresponding to the sum of all votes and not the vote of any one individual) is decrypted.

Basically, this boils down to the CGS scheme (link) but for Paillier encryption. Furthermore, you will want to use zero-knowledge proofs tailored for Paillier threshold decryption and encryption; these are presented in the paper by Damgård and Jurik (link).

Another suggestion is this: multi-party computation for calculating not just the sum of some private inputs, but for calculating any function of the private inputs while keeping those inputs themselves hidden. The BeDOZa protocol (link) explicitly covers using Paillier encryption for the offline part (precomputation phase), even though all values in the online part (actual computation phase) are information-theoretically private.


Defining Symmetric vs Asymmetric cryptosystems

Your definition only covers symmetric encryption since the same "index" $k$ is used in $T_k$ and $T^{-1}_k$ (i.e., encryption and decryption use the same key)

If you want to give a generic definition that covers both types of encryption, you could say that the transformations are $T_k$ and $T^{-1}_{k'}$ and that in the case of symmetric encryption $k'=k$.


Finding tetration in a multiplicative group modulo p

As pointed out in the comments, it's not quite clear what the problem is, but here's an easy algorithm for the (arguably) most natural interpretation.

Given any prime $p$ and integer $a$, the following procedure finds an integer $x\in\mathbb Z_{\geq0}$ such that
$$ x^x\equiv a\pmod p \,\text. $$

Pick some positive integer $e$ coprime to $p-1$. (For example, $e=1$ always works.)
Write the prospective solution as $x=e+k(p{-}1)$ with $k\in\mathbb Z_{\geq0}$.
Since the order of $x$ must be a divisor of $p-1$, the equation becomes
$$(e+k(p{-}1))^{e}\bmod p=a \,\text. $$
Raise everything to the power of $f:=e^{-1}\bmod(p{-}1)$ to obtain
$$ e+k(p{-}1) \equiv a^f \pmod p \,\text. $$
Simply solve this congruence for $k$, that is, compute
$$ k := (e-a^f)\bmod p \,\text. $$
Output $x:=e+k(p{-}1)$.

Note that the expected size of $x$ is approximately $p^2$.


Algorithm for computing square roots in $GF(2^n)$

Yes, there is an algorithm for efficiently computing square roots in $GF(2^n)$.

I don't know if this is the most efficient known, but the existence of an efficient algorithm can be shown by observing that squaring within $GF(2^n)$ is a bitwise linear operation, hence it is equivalent to taking the bit representation of the value, and multiplying it by an $n\times n$ matrix in $GF(2)$ to obtain the bit representation of the sequence.  Hence, it can be inverted by computing the inverse matrix, and multiplying by that.

Also, you have tagged the question with the "quadratic-residuosity" tag; however the field $GF(2^n)$ has the special property that all elements are quadratic residues; that is, for any element $x$, there will exist a unique element $y$ with $y^2 = x$.  Hence, in this field, the quadratic residuosity question is uninteresting.


AESManaged Trade Compliance Issue in United States

I am tempted to say that AESManaged is a class provided by the framework, i.e. you do not ship it: it is already shipped. Then whatever compliance issue may exist is to be handled (and has been handled) by Microsoft, not you.

(I am not entitled in any way to give legal advice, so do not take my word for it.)


Can I use a HMAC for Replay Attack protection?

An old but excellent paper on this topic is Tuomas Aura's Strategies against Replay Attacks.

The simplest version of the "Hashed Full Information" method would be to include the MAC of the previous message in the next message (you may also be able to use this as the nonce).  Then store the most recent MAC along with the session key and check new messages against that.  This would force serialization of messages within each session. (Assuming that is what you were thinking of when writing "use HMAC".)


The concept of indistinguishability from random is one of the most important in cryptography. Not only for hash functions, but for most cryptographic primitives, if not all.

Generally speaking, its importance relies on the fact that something which is not indistinguishable from random might be leaking some private information. Thus an attack might be derived from such a distinguisher.
On the other hand, something that is indistinguishable from random surely is not leaking any private information.

Regarding the special case of hash functions, you must have in mind that many security proofs for cryptographic protocols assume the use of a random oracle during some step of the protocol. In practice, hash functions are used for this purpose. However, as you might know, hash functions are not exactly equivalent to random oracle. But if we can show that they are indistinguishable from each other, then the intended security proof would hold as if a random oracle was used.

Note: As e-sushi mentioned, I am pretty sure there are plenty of material on the web regarding this topic. Please, for the good of the community, make a research before asking here. (Y)


How do I figure out the number of unique combinations

The number of possible unique tables for your application is $255!$.  The key term you will want to look up is circular permutation.

The number of tables you can have without wrapping around is a permutation of the elements (also called a 'linear permutation').  The number of possible tables of a permutation of the elements is $n!$, which is why you (correctly) calculated the number of possible permutations of the table as $256!$.

Because your use is circular, you would need to calculate the number of unique circular permutations, which is equal to $(n-1)!$.  So for the usage in your application where you have 256 elements, the number of possible tables is $(256-1)! = 255!$.


Generating non-supersingular elliptic curves for symmetric pairings

This case for symmetric pairing was mentioned in http://eprint.iacr.org/2001/003.

To sum the results given in that paper, you can get symmetric pairing in a few cases:

Trace 2 ordinary curves over where $p-1$ is square-free. In this case, the Tate pairing is non-degenerate for all points. Unfortunately, there is no known way to build such curves.
Trace 2 ordinary curves where $p-1$ contains a large square factor $\ell^2$. These are the Type E curves you mention, which are constructed using complex multiplication. In this case, depending on the considered parameters, there might or might not exist non-zero $\ell$-torsion points $P$ with $e(P,P)=1$. Note that, even when they exists, there are at most $2(\ell-1)$ such points.
Supersingular curve. Here $e(P,P)=1$ for $P$ defined in the basefield, but you can use a distorsion map $\psi$ and compute $e(P,\psi(P))$. This is the most frequent construction used for symmetric pairings.


It is not secure, because an attacker can "mix and match" the output blocks from different authentication tags on different input messages, or repeat output blocks for repeated input blocks.

For example, if the attacker knows the tag $F_k(m)$ for a one-block message $m$, then it can forge the correct tag $F_k(m) \mid F_k(m)$ for the two-block message $m \mid m$.

Another attack: suppose the attacker learns the tag $F_k(m_1) \mid F_k(m_2)$ for the message $m=m_1 \mid m_2$, and the tag $F_k(n_1) \mid F_k(n_2)$ for the message $n=n_1 \mid n_2$.  Then it can forge the correct tag $F_k(m_1) \mid F_k(n_2)$ for the message $m_1 \mid n_2$.  More generally, it can forge a correct tag for any message that is made by arbitrarily concatenating blocks from $m$ and $n$.


Sorry, I don't want to be trivial, but, aside from different implementations, interpretations, enhancements, splits, forks and fake actors, imho, I think that the foundations are all in the original Satoshi Nakamoto's Bitcoin paper and relative references.

I think that is the best starting point to understand mechanisms under the hood.

Bitcoin: A Peer-to-Peer Electronic Cash System


Padding oracle attack, encrypting your own message

I'm assuming you mean CBC mode, and let's say PKCS7 padding. I haven't heard of this attack before, and can't really find any sources (please link if you have one! How would an attacker end up with the $\operatorname{Dec}(C_i)$'s?), but here's one way to generate a valid ciphertext.

If the attacker is okay with 15 garbage bytes at the end of his message, he could do the following:

Send $IV = C_{i-1}$ and a random ciphertext block $C_r$ to the oracle a bunch of times. For a little more than 1 in 256 times, $C_r$ will end up having valid padding (e.g. 0x01 for PKCS7). The attacker can simply add such a block $C_r$ to the end of his ciphertext ($C_1, \dotsc, C_{i-1}$) to get a valid encrypted message, albeit with (usually) 15 garbage bytes at the end of the decrypted, de-padded message.


AES-128 (CBC) brute force given 90+ rightmost bits of key, known IV and Ciphertext?

We can say that you need to search 37-bit keyspace that is $2^{37}$.

Brute-forcing:

You will set up a counter starting from 0 to $2^{37}$. With the given key part at each step concatenate them givenKeyPart||counter before the key schedule.

Run the key schedule, then perform the encryption to see that the ciphertexts are matching. You don't need to perform the x-or with the IV for every encryption. Do it once.

You can easily reach $2^{37}$ encryption, or say the key search for AES. You have multiple options;

You can parallelize the search over the cores or PC's
You can use AES-NI if available.
Also, if available you can use GPU's

Here a benchmark for 32-bit search with AES-NI. It takes 40.3497s to search $2^{32}$.

In my test computer the 32-bit search with AES-NI took 14.1762s with 8 core.

Performances:
    1477815830 AES128 operations done in 14.282s
    9ns per AES128 operation
    103.47 million keys per second

Therefore the expected seconds for $2^{37}$ key space is $$2^{37}/2^{32} \times 14s = 448s$$

How to identify the plaintext: One general rule when only ciphertexts are given; one can check the result is valid (English) language. Looking at the ASCII range and/or using a function similar to string can enable to eliminate the candidates. However, there might be still many candidates to eliminate. To reach the solution one may need more than one ciphertext blocks (not a new message). There was a historical RSA challanges that gave more information than these contestants. However, your case still achievable in a very short time.

Update for the comment

Given 4 Bytes, IV and 3 Ciphertext blocks, exactly 16*3-byte plaintext with no padding and ASCII range is known.

For each of the candidate key check

All characters of the first decrypted plaintex are in ASCII range
If so check the second and if so check the last.
If all in the range then it is a good candidate.
Otherwise, skip the next key.

You can use a string search mechanism or select by your eyes. If you prefer your eyes better to write all of the candidates into a file with the key information.


Use Cases of Otway Rees key exchange protocol

No, because the protocol is not secure against replay attacks.

In general, this is much closer to Kerberos (secure and state-of-the-art) or Needham-Schroeder (not secure either) than Diffie-Hellman key exchange, which does not rely on a trusted server. (Note DH alone is also not secure, you need an authenticated variant).

That is probably the reason why you didn't find that much information on the protocol, why there are no common standard references and why it isn't used in cryptographic standards. In any case, Kerberos provides the same functionality with better security properties and it is already widely used.


Secret sharing scheme with possibility to change the secret

An obvious solution that handles steps 1–5 (changing the secret) would be for Alice to generate a random encryption key $K$ (of, say, 128 bits), encrypt $S$ with $K$ to generate $P$, and then share $K$ with the other participants using a conventional secret sharing scheme such as Shamir's.

Indeed, if all the shareholders (other than Alice) are always needed to reconstruct the secret, you don't even need to use Shamir's scheme: trivial XOR secret sharing (where Alice gives all but one of the shareholders a random bitstring, and gives the last one the XOR of all the other shares plus the secret) will do the job just as well.

Indeed, with XOR secret sharing, steps 6 and 7 (adding and removing participants) can also be achieved: Alice simply sends random bitstrings to the new participants, computes a new key $K$ by XORing together the shares of all the active participants, and encrypts the secret $S$ with the new $K$ to obtain the new $P$.

In fact, if the key $K$ is (at least) as long as the secret $S$, you don't even really need a separate encryption step: as long as $K$ is random, you can simply XOR $K$ with $S$ to obtain $P$, making this an instance of one-time pad encryption.

This also works with Shamir's scheme, as long the reconstruction threshold equals the number of shareholders; Alice can just send random shares to all the shareholders, reconstruct a (random) key $K$ by applying Shamir's reconstruction algorithm to the shares of the active participants, and use that key to encrypt the secret.

However, note that all these protocols suffer from some fundamentally unavoidable flaws:

if the shareholders can remember old $P$ values, they will be able to reconstruct old secrets even after Alice has changed them, and
if removed shareholders can remember their old shares (and the old $P$), they can still reconstruct the secret (assuming the other old shareholders cooperate) as it was before they were removed.  However, if the secret $S$ is changed whenever participants are removed, the remove participants won't be able to contribute anything useful to reconstructing the new secret.

Edit: Based on the comment below, it seems I misunderstood the question: you want each of Bob, Charlie and Dave alone to be able to reconstruct the secret using $P$.

A simple way to achieve this would be for Alice to distribute different random keys $K_i$ to each of the other participants $i$, encrypt her own key $K$ with each of $K_i$, and combine the ciphertexts into $P$.

Of course, the down side to this method is that the length of $P$ would be proportional to the number of participants, which could be a problem if that number is large.  However, I'm not sure if it's possible to do any better, and I suspect it may not be.


Increased AES key lengths vs keyphrase entropy

I believe that AES is only defined on key sizes of 128, 192 and 256
  bits, but cryptsetup/LUKS does allow me to select a key size of 384 or
  512 bits.

AES itself is only defined for 128, 192 and 256 bits keysize.

However, XTS involves two instances of AES which can (and should) be keyed independently, meaning XTS-AES-256 really is 2 instances of AES-128 and 384 is two instances of AES-192 and 512 is two instances of AES-256.

  Even if using XTS with AES256 (128 bit effective strength), would my
  90-bit entropy keyphrase and 15,000 PBKDF2 iterations of SHA-512 still
  be the weakest link in the chain?

A break of AES by a quantum computer is stil decades away given the current state of quantum computers. Honestly I wouldn't worry about it if I'd need to worry about secrecy for less than say 50 years.

And yes your 90-bit-entropy passphrase will still be the weakest link. After all to brute-force that password, one would need about $2^{104}$ SHA-512 evaluations which is still much faster than even the "weak" $2^{128}$ AES evaluations. To get a comparable security level you either need to pick a (longer) passphrase or increase the iteration count by about $2^{20}$ which is about a million, meaning you'd be looking at 15 billion iterations which will take a lot of time to the point where it won't be acceptable to wait.

  How would I work out how many bits of entropy and iterations are
  needed to make the keyphrase and the AES128 encryption the
  equal-weakest links in the chain?

To brute-force an $n$-bit key, you need about $2^n$ operations. To brute force a password with $k$ bits of entropy you need about $2^k$ operations and you can slow this down by a factor of $t$ which is the iteration count (in this case, you can also use more memory which will make attacks more expensive). So what you want, is:

$$\log_2(t) + k=n$$


Is there a standard one way function that does not produce collision

With a fixed length output (ala today's hash functions)?  No.

You cannot map an infinite space to a finite space, no matter how vast that finite space may be, without the possibility of collisions.