Definition of secure computation with more that two parties

It is not enough to be able to simulate the view of a single party, because corrupted parties may cooperate. As mentioned in the book, it may be easier to view all the corrupted parties as a single entity. It is the view of this single entity that we must simulate.

If $m$ is fixed, the order of quantifiers does not matter, because the number of subsets $I$ is fixed and so a single simulator $S$ can of course incorporate the code of the simulator $S_I$ for each $I$ (since $S$ is given $I$, it knows which of the $S_I$ to run as a subroutine).

(Edited after a comment.) If $m$ is not fixed, this may not be possible (for example if $m$ grows polynomially with the security parameter, the number of subsets grows exponentially), so you get two possibly different definitions depending on the order of the quantifiers. The one with a single simulator is stronger (if there is a single simulator that can generate a valid view, there trivially is a family of simulators that can, but not the other way around), so it is the one that was used. In practice, no protocol is known which is secure for the first definition and not the second.


Security of OFB mode if PRP is used instead of PRF

I think the final negligible term depends on the way you prove the rOFB security. If you construct OTP in the ideal word based on random functions, then use PRF; if based on random permutations, then use PRP. Note that in the latter case, replacing block ciphers with random permutations cannot guarantee that no collisions happen among the block cipher outputs. In other words, such collisions are not the same as those considered in PRF/PRP.

The attack surface for PRP is not negligibly higher. It seems higher just because you first prove the security with PRF and wants an easy reduction based on the advantage difference between PRP and PRF. Btw, any negligible difference should not matter in the security proofs.


Why is AES encryption decryption not platform agnostic?

No, it isn't.

As a C++ programmer you'll realise that the source code can be environment dependant - such as the 32 /64 bit thing.  Or memory capacity.  But you should also realise that an algorithm is OS agnostic.  Isn't this actually intuitive? One way to look at it are all the IOT devices out there.  They often use AES for encryption and they manage to talk to each other and control your hot water from your phone.  Those devices are all different, and some might  be 8 or 16 bit affairs. And some might even run on batteries like your phone.

See  the Advanced Encryption Standard Algorithm Validation System for test vectors.  This document shows you what should come out of your AES code.  You've just messed up either your native code implementation or the library API. If you can't understand section 6, Modes of Operation then you need to do some additional fundamental research regarding block ciphers.  Remember that AES itself is only the block primitive that accepts a key and a (plain/cipher/IV)text input.  Nothing else.

To reinforce what I've said, look at the referenced document, appendices B to E.  There is absolutely no mention of operating system, programming language,   hardware type or battery voltage.  AES is totally abstracted from it's environment.  If you have a problem with compatibility, it's an implementation issue.


tripartite diffie hellman with Weil pairing

This does indeed appear to be a typo. Using that $e_m$ is bilinear and alternating, one calculates
$$\begin{align*}
F_W(a,P_b,Q_c)
\;&=\; e_m([b]P,[c]Q)^a
\\&=\; e_m(P,Q)^{abc}
\\&=\; e_m(Q,P)^{-abc}
\\&=\; e_m([b]Q,[c]P)^{-a}
\\&=\; F_W(a,Q_b,P_c)^{-1}
\text.
\end{align*}$$

(However, note that these are only different if the order of $e_m(P,Q))$ does not divide $abc$; in particular, we need $e_m(P,Q)\neq1$.)


Reversible Decryption in Symmetric Key Algorithms

Why are encryption and decryption so similar?
Block ciphers are designed with reversibility in mind. Of course, to maintain data privacy, they are only reversible with the proper key. This is because a block cipher with a given key is a permutation. It is a bijection of all possible block-sized inputs to all possible block-sized outputs. This makes it possible to reverse, if given the key. The exact permutation is selected by the key, so what ciphertext block a given input maps to depends on the key. They are designed with this in mind to keep decryption simple.
Take the following permutation of a set of four different elements, chosen at random:
$\pmatrix{0&1&2&3\\1&3&2&0}$
Because it is a bijection, there always exists an inverse:
$\pmatrix{0&1&2&3\\3&0&2&1}$
As you can see, the permutation maps $1$ to $3$, so the inverse permutation maps $3$ back to $1$. A block cipher does just this, except the permutation is not fixed. Rather, it is "chosen" by the key. Each key selects a different permutation from all possible permutations. Additionally, there are far more than four elements. AES encryption permutes a set of $2^{128}$ different elements, chosen by the key. Decryption simply gives you the inverse, allowing you to recover the plaintext. All the complex math behind block ciphers is necessary because it would be impossible to store every bijection ($2^{128}! \times 2^{128}$) in a table.
Is this a property of all symmetric ciphers?
Block ciphers are not the only symmetric ciphers. Stream ciphers do not need to be reversible, as all they do is generate a pseudorandom stream of data, called the keystream, which is XORed with the plaintext. Decryption does not require running the stream cipher in reverse, but generating the same keystream (by selecting the same key) and XORing it with the ciphertext.
It may be interesting to note that it's possible to turn a regular block cipher into a stream cipher by using a mode of operation like counter mode, or CTR, which generates the keystream by encrypting an ever-increasing counter. Decryption with CTR mode actually involves using the block cipher in the encryption direction, so it's possible to implement CTR (or any other mode that turns a block cipher into a stream cipher) without ever needing to implement decryption. See the following diagram from Wikipedia:

Is this a property of all symmetric permutations?
Also no! Although it's pretty common for block ciphers to be designed to make the inverse permutation easy to implement, not all permutations do this, even if they are technically reversible. This is common for public permutations. That is a permutation that is fixed and does not require knowledge of a secret key to invert. They are common in sponge constructions, which get their high security by ensuring a substantial portion of the input to the permutation is secret, alleviating the need for a key. An example of a public permutation is Gimli, which was designed only in the forward direction:

Like Keccak, Ascon [15], etc., we evaluate performance only in the forward direction, and we consider only forward modes; modes that also use the inverse permutation require extra hardware area and do not seem to offer any noticeable advantages.

In addition to being easier to implement, there is no need to cryptanalyze its inverse. While it may not be intuitive, the fact is that sometimes the inverse of a permutation is less secure than the permutation in the forward direction. This was the case for the FROG block cipher. It was an AES candidate during the NIST AES competition which did not make it past the first round. It displayed slower diffusion in the decryption direction (the inverse permutation for a given key) than in the encryption direction.


How to construct a collision resistant hash function that is not a one-way function?

It is going to be pretty hard to achieve collision resistance without one-wayness. Indeed, negation of one-wayness means that for a given output, you can find a corresponding input. So a collision is easily obtained by simply choosing a random input m, hashing it into output x, then finding a preimage m' for the obtained output x. The only way for such a method not to work is to have an output space at least as large as the input space, so that, with high probability, the input m' is identical to m. However, since hash functions have a much larger input space than output space (e.g. SHA-256 output space has size 2256, but its input space has size 218446744073709551616-1, which is substantially greater), chances are that the m' you get from leveraging the non-one-wayness will be distinct from the m you started with, and that yields a collision.


Is there any known malleability of scrypt outputs?

Non-malleability of Scrypt w.r.t. to salt (as well as passphrase) follows from the definition of Scrypt (which simply pass that salt to that input of PBKDF2); the definition of PBKDF2 (which uses the salt followed by a non-malleable encoding of an integer as a massage passed to HMAC_SHA256); the non-malleability of HMAC_SHA256 w.r.t. the message; and perhaps some reasonable assumptions also critical to Scrypt's soundness. Non-malleability w.r.t. to salt and passphrase should be a design goal of any good PBKDF.

Non-malleability of Scrypt w.r.t. workfactor is more difficult to argument, and hard (if possible) to prove, depending on how rigorous the argument needs to be, and how one maps the term workfactor to the three security parameters of Scrypt (number of iterations, amount of RAM used, and allowance for parallelization). In my opinion, no attack better than brute force is feasible: this is an issue of provable security only, and entering the workfactor(s) in the salt would restore that.

Beware that in some protocols, independently of any weakness in Scrypt (or whatever PBKDF is used), it could be necessary that a legitimate party holding the passphrase enforce a minimum workfactor, for fear of being abused into a fast passphrase-checking oracle.

I do not know any established PBKDF improving on Scrypt.


Finding $x$'s parity in the discrete log problem


ECDSA is a digital signature algorithm
ECIES is an Integrated Encryption scheme
ECDH is a key secure key exchange algorithm

First you should understand the purpose of these algorithms.

Digital signature algorithms are used to authenticate a digital content. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, such that the sender cannot deny having sent the message (authentication and non-repudiation) and that the message was not altered in transit (integrity).

Integrated Encryption scheme is a hybrid encryption scheme which provides semantic security against chosen plain text and chosen cipher text attacks. ECIES uses different types of functions:

Key Agreement function
Key Derivation Function
Symmetric Encryption scheme
Hash function

Secure key exchange algorithms are used to exchange our keys securely via a non secure channel.

Here you are interested in Elliptic Curve variants of those algorithms. Your requirement is to exchange some data. So you can use ECDH to share the secret key and ECDSA to sign the content. Because ECDH does not provide authentication we can use ECDSA for that purpose. Once the secret key is shared, you can securely exchange your data through a non secure channel. Strength of the secret key can be defined by considering the level of security you need and amount of computation power you got.


Can a commutative block cipher be indistinguishable from a random permutation, for fixed key?

It can't be achieved under the assumptions you are making, because the attacker can distinguish it by selecting an arbitrary $k'$, and checking if $E(k')$ commutes with the permutation in question.  That is, to check a permutation $P$, we pick an arbitrary $x$, and check if:

$E(k', P(x)) = P(E(k',x))$

This equation always holds if $P = E(k)$ for some value $k$, and rarely holds if $P$ is a random permutation.


Can an AES-256 key be generated for a large number of cribs?

Just the most basic research on this site would have told you, the answer is NO.

From all known cryptanalysis on AES, the answer is simply there are no useful plain-text attacks. (Which is essentially what your "cribs" are.

It's not going to be possible to break AES-256 in your clients scenario. Full key recovery is out the picture even with a terrible implementation, unless there's a weak way that key is stored. Finding the AES key on the computer itself (encrypted using more vulnerable techniques) is your only shot in hell.


Yes. They provide different things.

The reason you hash a password is so you compare it later on without ever exposing the plaintext. A salt is used to make a large collection of hashes harder to bruteforce.

Encrypting a hash does nothing to make the hash harder to bruteforce. If you're compromised to the point your hashes are leaked, there is a good chance the attacker will also be able to figure out the encryption method and the key.


GCM is authenticated encryption. As such, it is secure against chosen-plaintext attacks and against chosen-ciphertext attacks. Thus, there is no problem whatsoever with the adversary having access to an encryption oracle. It will not help it at all to break any of the encrypted messages.


Is Type I lattice trapdoor hard to find even given oracle access to compute inverse of trapdoor function?

If the adversary is a classical algorithm, then the answer  to your question is not known. But if the adversary is a quantum algorithm that can query the oracle in superposition, then the answer is yes: by making queries to the oracle on certain (efficiently produceable) quantum states, it can recover a Type-I trapdoor for $A$.

For classical algorithms, the difficulty is that we do not know how to generate a valid output of $g$ (that the oracle is obliged to succeed on) except by choosing $s,e$ ourselves and feeding them through $g$. But then the oracle’s answer is useless to us, because we already know the answer before querying it.

For quantum algorithms the situation is different. We can prepare a certain superposition over “all” valid $s,e$, feed it through $g$ to get a superposition over outputs, and invoke the oracle to get back $s,e$. Critically, this allows us to uncompute (or “forget”) our original choices, leaving us with a useful quantum state. Specifically, by taking its quantum Fourier transform we get a superposition over short vectors $x$ such that $Ax=0$. By measuring the state we get such an $x$, and can repeat to accumulate many linearly independent ones, yielding a Type-1 trapdoor.

The difficulty in the classical setting, and the quantum strategy for dealing with it, are from Regev’s original paper on LWE. The connection to SIS/LWE was first described in the GPV paper.


IMHO the best option to mitigate the maleability is using the authenticated encryption. So every scheme that includes the authentication tag should not be malleable (when done properly). Examples - the GCM mode, CCM, etc..


Will elliptic curve cryptography be weakened?

From: https://plus.google.com/+DavidRoberts/posts/KcjNn99tYaa

  David Hansen

  The result announced by Taylor has absolutely nothing to
  do with elliptic curve cryptography, and no effect thereon.


There are close to $2^{256}$ ECC keys while there are only $2^{160}$ 20-byte hashes, so the pidgeonhole principle shows that there exist collisions. On average there there are $2^{96}$ keys for each 20-byte hash.

Since SHA-256 is a strong hash function, the only way to find a collision is brute force, which involves $2^{80}$ hash computations. But collisions are not a relevant attack for bitcoin addresses, since stealing your own money is rather pointless.

What an attacker needs to do is a multi-target preimage attack, which is ridiculously more expensive than the expected rewards ($2^{160}$ hash computations to steal 67 billion USD, which means more than $2^{120}$ hash computations for each dollar you steal).

It's clearly better for the attacker to attack the address with a known ECC public key and the highest balance, since that costs $2^{128}$ operations, but reaps all bitcoins from that address.


Solving for a One-time pad cipher help ; crib dragging doesnt work (no surprise)

Take the ASCII values of each letter , convert them to binary and xor them with characters you think it may be. You can do it manually or have the internet tell you each characters values. Just from what I read from the link posted it above it shouldn't be that difficult to do. Since this cipher you have has a lot of repeats, you should be able to crack it fairly easy follow the previous posts guide.


Is it possible to obtain the value committed to by Pedersen commitment given the blinding key?

Recovering $v$ from $\alpha$, $G$, $H$ and $P=\alpha\cdot G + v\cdot H$ requires solving the discrete log problem to find $v$. Specifically, note that $v\cdot H = P - \alpha\cdot G$ so you need to find the discrete log of this value with base $H$. As such, if $v$ is small then you can find it.

It is crucial to understand that although it is hard to find $v$ in general, it does not mean that revealing $\alpha$ is OK and $v$ is still securely committed. This is because some part of $v$ may be revealed by $v\cdot H$. Thus, this is neither a secure commitment, nor possible to obtain $v$ efficiently.

On the note of working modulo $p$ or over Elliptic curves, this makes no different essentially.


What is the implication for differential privacy if $\epsilon = 0$?

Yes.

$\varepsilon$-differential privacy with $\varepsilon=0$ implies that the output of the mechanism must be independent of the input -- i.e., it provides no information whatsoever.


Secret sharing - no dealer, modifiable, verifiable

The "simple" answer to your question is that all of the above can be achieved using secure multiparty computation (see this review article on Secure Multiparty Computation for a more detailed overview). The best way to abstract this is to define an "ideal functionality" $F$ which is run by a trusted third party, receiving inputs from the parties and providing outputs. The theory of MPC then tells us that any such functionality can be securely computed by the parties interacting. (There are details of early abort, fairness, etc. However, I believe that this is orthogonal to what is in the question.)
According to the above, we can define each of the required features as an ideal functionality:

For setting up the sharing without a dealer, one has to assume that they are generating a sharing of some random value (otherwise what are they sharing). Assuming that they wish to share a random $s\in\mathbb{F}$ according to some access structure $\cal Q$, the ideal functionality can be defined to receive the description of the field and the access structure from all parties. Then, assuming they are all the same, it samples a random $s\leftarrow\mathbb{F}$, locally computes the secret sharing according to $\cal Q$, and sends each party its share.
The parameters can all be changed by defining an ideal functionality that receives the shares from all parties (or at least a quorum) and the new parameters. The trusted party then reconstructs the secret $s$, generates a new secret sharing according to the new parameters, and sends each party its new share.
Verifiability follows automatically from the fact that if the MPC protocol is secure against malicious adversaries, then it is guaranteed that all outputs are correct.

Having said this, one issue that may arise is that parties may send incorrect shares to the trusted party for the second item. This can be solved by either assuming that the threshold is strictly less than the number of parties participating. This suffices since if the secret sharing is Shamir, for example, then all shares must lie on the same polynomial, and any incorrect value is detected. However, if you wish to prevent an abort, then you need enough redundancy (e.g., if $t<n/3$ then you will always have enough honest shares to "correct" any corrupt ones). Another, more general, way of ensuring that nothing is changed is to have all parties hold commitments of all shares, or the like, and the trusted party verifies that all inputs used are unchanged.
Having said all of the above, what one often wants is something more complex. First, not all parties may participate in all phases. Second, you want to find an efficient MPC protocol that deals with the above. In general, this is all possible. However, exactly specifying how to do it is beyond the scope of this answer, and depends very much on exactly what setting you are in. The best source to understand more specifically about this would be the book Secure Multiparty Computation and Secret Sharing. However, there are many techniques that are relevant that can be found in the MPC literature.


Is RSA vulnerable to the padding oracle attack?

Yes, and it's devastatingly effective, too. See OAEP and other RSA/asymmetric-function padding standards. OAEP is what you should use these days so far as I am aware. PKCS#1 has other defined padding schemes also (eg PSS, PKCS1.5), only some of which are effective.


With a 64-bit known polynomial, future output of an LFSR can be trivially predicted from the last 64 bits output. Even if the 64-bit polynomial is unknown, the last 128 bits are enough, using the Berlekamp–Massey algorithm. Thus indeed, the LFSR-based PRNG in the hardware described in a section 27 of the document linked to in question, with some additional info here, is unusable as a CSPRNG, just like any pure LFSR PRNG is.

It is possible to make a passable CSPRNG by combining LFSRs. One very simple example is the Alternating Step Generator, proposed by C. G. Günther in Alternating step generators controlled by de Bruijn sequences (Eurocrypt 1987). One LFSR decides which of two other LFSRs is clocked, and the output is the XOR of these two LFSRs. The three LFSRs are customarily non-stationary, maximal length, and of distinct but comparable size. The ASG has no published attack (that I know) that can be interpreted as claiming an effort better than $O(2^{n/6})$, where $n$ is the total number of bits in the three LFSRs (assumed of about equal size); and in fact I'm not sure this attack beats this one, which I read as more like $O(2^{2\cdot n/9})$.

I can't however recommend the ASG, or any generator easily described as a combination of LFSRs, because we now have better constructs, with more conjectured security per bit, and easier software implementation, like Trivum.

Addition (updated): If the 64-bit seed is from a good TRNG; and the LFSR is maximal-length, that is with a primitive polynomial; and the LFSR is reseeded after 64-bit; then the 64-bit output of the LFSR is not worst (or much better) than the 64-bit output of the TRNG. It is actually easy go from one 64-bit value to the other, with knowledge of the polynomial.

My understanding of the PIC32MZ PRNG is that it is more applicable to generating specific sequences defined using a prescribed LFSR, as might be desirable in some pre-existing protocols or applications, e.g. test sequence, CRC, or spread-spectrum radio; than it is as a CSPRNG.


What is the fastest elliptic curve operation f(P) in affine coordinates such that f^n(P)=P only if n is large?

With your curve, you can use the Gallant-Lambert-Vanstone (GLV) method to answer your question. Indeed, the equation of your curve is: $$y^2=x^3+7.$$ Since $p$ is congruent to $1$ modulo $3$, there are cube roots of unity modulo $p$. Let:
$$j=55594575648329892869085402983802832744385952214688224221778511981742606582254 \pmod{p}.$$ You can check that $j^3\equiv 1\pmod{p}$. The complex multiplication by $j$ sends $P=(X_P,Y_P)$ to $P'=(jX_P,Y_P)$.

Moreover, $P'=J\cdot P,$ where $$J=37718080363155996902926221483475020450927657555482586988616620542887997980018.$$

Finally, multiplication by $J-1$ can be performed efficiently (one application of complex multiplication and one addition) and has high order. Don't use $J+1$: it has order $6$.

EDIT
 $J^3$ is $1$ modulo the order of the curve, while $j^3$ is $1$ mod $p$.

This endomorphism of the curve is the projection of the complex multiplication of the curve $y^2=x^3+7$ over the rationals to the curve reduced mod $p$. This is why is is usually called the complex multiplication.

All in all, this gives a reasonably fast way to generate random looking multiples of $P$.

The full GLV method is much more than that since it speeds up multiplication by an arbitrary constant compared to regular double and add, but its basic idea relies on having an endomorphism that can be computed quickly.


Negative correlation in image cryptography

A negative correlation simply implies that your encrypted image resembles the negative of the original image more than one would expect if the two images were completely unrelated.

Of course, the measured correlation between any two random sets of data is rarely if ever exactly zero, even if the values are actually completely independent.  However, if the correlation appears consistently and/or is large enough (in absolute magnitude) to be considered statistically significant, it indicates that your encryption scheme leaks information about the original image, and is therefore not secure.

(Also, note that zero correlation between the original and the encrypted image is not, by itself, sufficient to demonstrate security.  For example, an encryption scheme that simply inverted the colors of every second pixel in the image would achieve very close to a zero correlation for most typical images, but would be trivially easy for anyone to decrypt.)


Verilog simulation & synthesis of Diffie-Hellman key exchange

Look on opencores within the vhdl section.

There are some older dos-era vhdl programs on simtel that have parsed-out statements so it might be more trouble than it is worth, but at least you could look under the hood of each function, grab what you need, run a lint checker etc, then perform verification.


Encrypting twice with same key gives back plain text

These block ciphers are called involutional ciphers, after the (mathematical) involution property of a function. This article shows a cryptographic analysis of two of them: Khazad and Anubis.

Neither Khazad nor Anubis  seem to be broken at the time of writing, basically they use the same internal structure for normal block ciphers, replacing the inner components with involutional ones.


Difference of full codebook and non full codebook

In full codebook, data complexity equals to all input of cryptosystem and in non full codebook is less than it.

For example in SIMON 32/64, if data complexity=2^32, the attack is full codebook,
and if DC < 2^32, the attack is non full codebook.


$n - \phi(n) = p + q - 1$.  $p$ and $q$ are secret uniform random 1024-bit prime numbers.  Is a difference of near $2^{1024}$ ‘close’?


Graphically representing points on Elliptic Curve over finite field

None of the above answers see the mistake in the question. The point $P=(1,5)$ is not on the curve $E\colon y^2=x^3-4x+20$ over $\mathbb{F}_{29}$. To see this, place $x=1$ and $y=5$ into the curve equation.
\begin{align}
5^2&=1^3-4+20\\
25& = 1-4+20\\
25& \neq 15\\
\end{align}
Therefore $P = (1,5)$ is not on the curve. But it is on the curve $E'\colon y^2=x^3\color{red}{+}4x+20$ over $\mathbb{F}_{29}$.
Now, let us continue to the second equation as $E \colon y^2=x^3\color{red}{+}4x+20$
The curve $E$ has 37 points; the below lists them in projective coordinates;
$[(0 : 1 : 0), (0 : 7 : 1), (0 : 22 : 1), \color{red}{P =(1 : 5 : 1)}, (1 : 24 : 1), (2 : 6 : 1), (2 : 23 : 1), (3 : 1 : 1), (3 : 28 : 1), (4 : 10 : 1), (4 : 19 : 1), (5 : 7 : 1), (5 : 22 : 1), (6 : 12 : 1), (6 : 17 : 1), (8 : 10 : 1), (8 : 19 : 1), (10 : 4 : 1), (10 : 25 : 1), (13 : 6 : 1), (13 : 23 : 1), (14 : 6 : 1), (14 : 23 : 1), (15 : 2 : 1), (15 : 27 : 1), (16 : 2 : 1), (16 : 27 : 1), (17 : 10 : 1), (17 : 19 : 1), (19 : 13 : 1), (19 : 16 : 1), (20 : 3 : 1), (20 : 26 : 1), (24 : 7 : 1), (24 : 22 : 1), (27 : 2 : 1), (27 : 27 : 1)]$
Visualizing a curve is easy when the curve is defined over the Rational Field.

Where all the arithmetic-geometric relation work almost flawlessly; that is $$P+Q-R$$ is on the same line;
When we turn in to finite field case, we have a discrete plot;

The blue line is drawn to show the symmetry since if $(x,y)$ satisfies a point therefore $(x,-y)$ ( in the plot $ = (x,29-y)$) also satisfies the equation.
Now we can see the point addition with $P=(1,5), Q=(5,7)$ and $R = P+Q = (16,2)$ is drawn on the figure.

The proof of the connection of this figure with the ECC point addition is performed by Fgrieu for this question : Must a line hitting two points on the elliptic curve over a finite field hit another point by continuation?
As we can see from these figures, the point of infinity is missing here. Consider the summation of $R$ and $-R$, there it should be $\mathcal{O}$ on the vertical line! nope!.
Another visualization is the Torus shape. Any rectangle image can be map into a torus shape.

This is a vector image with Asymptote and the points that cannot be seen directly are set to be opaque. This is calculated by ray-tracing. The $R$ and $-R$ on the background. This 3D can be best viewed within HTML. A snapshot from the bottom;

The HMTL is interactive, you can zoom and rotate in 3D, you can download it from Github and view it locally.


Is it possible to reverse Ansible vault data?

There are technically two ways:

brute-forcing your way to a valid passphrase
having a valid passphrase and using that to decrypt the data

The use of 256-bit AES is cryptographically sound as far as I can tell as a (cryptography) layperson, so there are no other ways.

That said, for Ansible vaults the way I have used them, you have to enter a passphrase. While the actual key is probably still derived from that passphrase, brute-forcing a passphrase may be easier than brute-forcing a lengthy key.

As for the two ways one thing can be encrypted using the same passphrase, this may be owed to salt. For example the current date and time may be part of the encrypted data and the actual vault data gets extracted from that.


There are practical side-channel attacks against implementations of AES, but there are not any practical cryptanalytic attacks against the abstract algorithm.

The best cryptanalytic attack against the complete cipher in a reasonable attack model is probably the biclique attack, which only knocks a few bits off the key. The related key attacks against AES have attack models which are unreasonable when using AES as a block cipher to preserve confidentiality, and so are less/non applicable even though the bottom line of the computational cost of the attack is more pronounced.

For more information, you might investigate the following question/answers: How is encryption broken today? While that question/answer(s) is not specific towards AES, most if not all of the information is relevant.


What message M is the author talking about? Is this TLS session establishment? Can someone shed more light on this section 3.5

First of all, you need to understand what the Bleichenbacher attack is (by the description in your answer, you don't).

What it is is a way of, given a value $EM$, computing $EM^d \bmod N$, given an Oracle that will, given a value $EM'$, telling you whether $EM'^d \bmod N$ has value PKCS #1.5 encryption padding (which is different from the signature padding).  The attacker can often find an Oracle by using a protocol where he sends an encrypted value to the system under attack, and observing how the system reacts (whether he acts as if the decryption failed, or whether he acts like he got some valid value).

When the attack was first published 20 years ago, it would require a huge number (circa a million) different $EM'$ values to actually work; later refinements significantly reduced that number, to circa 10,000 messages IIRC.

Now, on to TLS and your actual question, and while the paper does look at protocols beyond TLS, I'll focus on TLS.

When the TLS server establishes a connection, it sends both its certificate (showing that it owns a public key), and something signed with that public key.  If the signature doesn't verify, the client rejects the connection.

So, in order to masquerade as the server, you'd need to do the same thing; you need to send a certificate (which this attack reuses the valid server's certificate), and then the signature of something; that something is the message M.

Now, if you look into the TLS protocol, this $M$ is the transcript of the TLS negotiation up to that point; the details aren't actually relevant to the attack, except that they aren't known until the negotiation actually happens (as it includes unpredictable values chosen by the client).

So, what the paper proposes we do is masquerade as the server up until the point where it actually has to generate the signature.  It knows $M$, and so we able to compute $EM$.  Then, by quickly performing the Bleichenbacher attack against the real server, it recovers $EM^d \bmod N$ before the client times out.  This $EM^d \bmod N$ value is the correct signature for $M$, and so the attacker can present that to the client, and the attack succeeds.


If I understand right, your operation effectively is
$$\forall i:  c_i = p_i \oplus k_0 \oplus k_1 \oplus k_2 \oplus \dots \oplus k_n,$$
whith $c_i$ the ciphertext bits, $p_i$ the plaintext bits, and $k_j$ the key bits.

As $\oplus$ (this is XOR) is associative, this is equivalent to

$$k^* :=  k_0 \oplus k_1 \oplus k_2 \oplus \dots \oplus k_n,$$
$$\forall i:  c_i = p_i \oplus k^*.$$

Now $k^*$ is either 0 or 1 - in the first case this operation is the identity, in the second case it is simple negation. Neither of those can be considered an encryption, and you effectively have a key space of 2 (= 1 bit).

Whoever told you this either wanted to play a joke with you, or knows nothing of cryptography (or both). Or I misunderstood your presention of the algorithm.


AES-encrypted 128-bit null block: lookup table?

In practice we use something called a block mode.

The traditional block mode is cipher block chaining (see image). In this block mode we XOR the ciphertext of the a block with the plaintext of the next block. The first plaintext block will be XOR'd with a public initialization vector. This way we make sure that every ciphertext is different.

  How isn't this a weakness?

It is. In your case the block mode that is used is ECB, basically applying the block cipher to each block independently. ECB is considered insecure for normal use.

  Could you make a lookup table for all blocks of only zeros?

No. Because almost always keys are generated randomly, we would need to store $2^{128}$ entries in our lookup table. Our universe will never have enough disk space to store it.


Is there proof to the relation between the gap Diffie-Hellman problem and the the Cha-Cheon signature scheme?

I have to make two assumptions regarding your question first.

I assume you speak of the ID-based signature scheme from "An Identity-Based Signature from Gap Diffie-Hellman Groups".
You mean "If the computational Diffie Hellman problem (CDHP) is easy..." (the scheme works in Gap Diffie Hellman (GDH) groups, but the security proof relies on the CDHP.

Ok, now we briefly recall the scheme (I use the notation of the paper): In this scheme we have a GDH group $G$ of order $\ell$ generated by $P$. Note that in a GDH group the decisional Diffie-Hellman problem is easy, but the CDHP is assumed to be hard (such groups can for instance be realized using pairing friendly elliptic curve groups).

The master public key is $P_{pub}=sP$ where $s$ is random element in $Z_\ell$ and $s$ is kept secret by the system.

A users secret is $D_{ID}=sH_2(ID)$ and $ID\in\{0,1\}^*$ the users identifier and $H_2$ maps strings to $G$. The users public key is $Q_{ID}=H_2(ID)$.

A signature is the tuple $(U,V)$ with $U=rQ_{ID}$ for random $r\in Z_\ell$ and $V=(r+h)D_{ID}$ with $h=H_1(m,U)$ where $H_1$ is a hash function maps to $Z_\ell$.

Now signature verification amounts to checking whether $(P,P_{pub},U+hQ_{ID},V)$ is a valid Diffie- Hellman tuple. Now, this means that it is of the form $(P,aP,bP,cP)$ with $c\equiv ab\pmod \ell$.

Let us rewrite $(P,P_{pub},U+hQ_{ID},V)$ to $(P,sP,rQ_{ID}+hQ_{ID},(r+h)D_{ID})$. Now, we see that the last element can be rewritten to $(r+h)D_{ID}=rsQ_{ID}+hsQ_{ID}=s(rQ_{ID}+hQ_{ID})$, which shows the correctness. This means that a honestly computed signature is a valid Diffie-Hellman tuple.

Now forging would require to break the CDHP in $G$, i.e., one can efficiently compute $abP$ given $P,aP,bP$.

Forgery:

Observe, that $U$ and $hQ_{ID}$ can be computed by anybody. Now let us view $(P,sP,U+hQ_{ID})$ as an CDHP instance. Now, assume the $CDHP$ in $G$ is easy. This means that we can compute $s(U+hQ_{ID})$ given $(P,sP,U+hQ_{ID})$.

Now lets us inspect $s(U+hQ_{ID})$. We see that

$s(U+hQ_{ID})=sU+hsQ_{ID}=srQ_{ID}+hsQ_{ID}=rD_{ID}+hD_{ID}=(h+r)D_{ID}$.

Note that this is exactly a $V$ for a valid signature.

Total break:

Note that one can also totally break the scheme if the CDHP is easy, as one can compute $D_{ID}$ from $P_{pub}$ and $Q_{ID}$. Then you can also compute any signature you want.

Consequently, if the CDHP is easy, the signature scheme does not work anymore.

Hope that helps.


Forward Secrecy when using non-ephemeral DH

Ephemerality does not refer to "a new session key being made each time a new session is set up", it refers to both parties' key pairs (and group elements) being freshly chosen. These Diffie-Hellman key pairs are should be ephemeral for forward secrecy; the session key is always ephemeral, even if static-static Diffie-Hellman is applied.

Any nonces are used as part of the session key calculation should be known at both sides. This means they have to be communicated in plain or they should be part of the key agreement algorithm. That means that the nonces are either known to the attacker or that they can be retrieved by reapplying the DH calculations (in the future, when the static DH private key is leaked). If ephemeral key pairs are used then DH cannot be reapplied because the private exponents are lost.

So the nonces may become available to an attacker for static-static and ephemeral-static Diffie-Hellman even when the sender and receiver have discarded the values long ago.

Note that there is a difference between the raw/textbook DH calculation and the DH scheme specified in e.g. NIST 800-56A: "Scheme Using No Ephemeral Key Pairs".

If you just apply the calculation then two static keys would result in a static key seed. The NIST scheme on the other hand includes a nonce send in plain so the resulting key seed will be ephemeral.

The answer assumes that the key seed is ephemeral.


What does this Authentication protocol achieve and what information is shared?

From my understanding, this protocol makes use of a trusted third party in order from A and B to exchange a symmetric key, $K_{AB}$. For the protocol to work, it is assumed that both A and B must share a master key, $K_{AS}$ and $K_{BS}$ respectively with the trusted S and A wants to communicate with B but they has no shared secret. Since there is no MAC/signature appended so it is implicit that the underlying encryption scheme also provides integrity checks. And a plaintext attack resistant encryption scheme should be used since the encrypt plaintext in step 4 is known. Thus,

A sends a random nonce, $N_A$ to B in step 1.

B sends its own nonce, $N_B$ and encrypt A's nonce before sending them to S in step 2.

Next, trusted server S will generate a symmetric key, $K_{AB}$ (which I guess should be a session key) and encrypts $K_{AB}$ separately with the keys shared with A and B in step 3. A can then decrypt $\{B, N_A, K_{AB}, T_B\}K_{AS}$ using the master key shared with S and verify that the nonce $N_A$ and timestamp is correct (for freshness) and B's ID is correct (to prevent MiTM attacks). Now A has knowledge of the assigned session key $K_{AB}$ and he computes an Authenticator (as called in Kerberos) which is actually the encryption of $N_B$. This allows user B to verify that user A does indeed have knowledge of the session key $K_{AB}$.

If everything is correct then A will forward the second part $\{A, K_{AB}, T_B\}K_{BS}$ to user B and also send the Authenticator in step 4. Similarly, user B will be able to decrypt $\{A, K_{AB}, T_B\}K_{BS}$ with the master key shared with S. B checks if A's ID and the timestamp is valid and retrieves the session key $K_{AB}$. Next, B uses $K_{AB}$ to decrypt the Authenticator to authenticate user A.

Currently, only unilateral authentication is provided. But an extra step
$B \to A : \{N_B +1\}K_{AB}$ may be added for mutual authentication.

The well establish Kerberos protocol uses a similar albeit more complicated concept to issue tickets for authenticated users.


Default algorithm for scalar multiplication of elliptic curve points by the MIRACL Library

It depends your compilation options but the function ecurve_mult in MIRACL/source/mrcurve.c seems to use the w-ary non-adjacent form (wNAF) method.


What is the theoretical and practical status of mental poker?

All the know problems have been solved and currently there is, at least, one practical and secure Mental Poker protocol.

Check this patent application:

METHOD AND APPARATUS FOR EFFICIENT AND SECURE CREATING, TRANSFERRING, AND REVEALING OF MESSAGES OVER A NETWORK
Application number: 13/086,208
Publication number: US 2011/0202766 A1
Filing date: Apr 13, 2011

The protocol described is called MPF (Mental Poker Framework).

Detailed answers to your points:

  What are the remaining open problems/challenges?

The main problem still unsolved is how to enforce players to act (show a card, bet, pass) before a certain time limit, in a purely peer to peer network, since a timestamping service would add a TTP to the protocol.

Also I have my own unproven conjecture: Semantic security is incompatible with abrupt drop out tolerance (without a threshold scheme). Both cannot be present at the same time in a MP protocol.

  Can we call it solved? For example, has the "dropout" problem been solved (e.g. 1 suggests so, but has it been verified?)?

Since a deck that is encrypted with players private keys cannot be recovered if a player quits (at least not without a threshold scheme), one way to solve the drop out problem (as shown in the patent) is to create a fresh new deck, where the cards that were in possession of the player that has left return to the new deck.
This is done by creating a new shuffled deck and then removing the cards that were in possession of the players, without revealing which cards are removed. This is the best possible solution.

  Have the performance problems been solved?

Yes, it takes less than 10 seconds to shuffle a 52 card deck by 6 players using the algorithm published in the patent.

  Is there an implementation of the algorithms / protocols?

I have my own implementation, but it's not tidy enough to put in public domain. I should.

  What is the latest performance improvements (e.g. is [2] up to date to the fastest protocols known)?

IMHO the last performance improvements come to what I called Simultaneous Zero Knowledge Proofs. In SimZNK all parties cooperate to prove their private operations (shuffle and re-encryption) are correct.

If a player tries to cheat, then the player having cheated is detected at the end of the shuffle stage (when all players have shuffled the deck, but before the game starts).
Afterwards, the process can be restarted without having leaked any private information of any value.

This verification scheme is much faster than verification (either by interactive or non-interactive ZNPs) after each player shuffle and re-encrypts the cards.


How does the HOTP dynamic truncation function generalize to longer hashes?

I managed to find it out by reproducing the test vectors.

TL;DR: The standard assumes that you use the low 4 bits of the last byte of the hash, regardless of its length. So replace 19 in the original DT definition with 31 for SHA-256 or 63 for SHA-512 and you are good to go.

Finding this out wasn't completely straightforward, as the standard only has a single test secret listed:

  The test token shared secret uses the ASCII string value
     "12345678901234567890".  With Time Step X = 30, and the Unix epoch as
     the initial value to count time steps, where T0 = 0, the TOTP
     algorithm will display the following values for specified modes and
     timestamps.

If fact, to reproduce the test vector values for SHA-256 and SHA-512 you have to extend that secret to 32/64 characters. I.e. use the ASCII strings "12345678901234567890123456789012" and "1234567890123456789012345678901234567890123456789012345678901234" instead.


Padding schemes for asymmetric encryption with provable security in the standard model

To the best of my knowledge, there is no padded scheme for RSA (or general trapdoor permutation) that has been proven secure in the standard model. To be exact, let's call a padded scheme one where a padding transformation is carried out independently of the public key, and then the trapdoor permutation is applied once to the result.

Of course, as noted, we can do this to encrypt log(k) bits. However, for more than that, we don't know much. There is a very interesting result by Smith and Zhang that shows that under a "lossy" assumption about RSA, it's possible to prove security for about 1/4 of the bits of RSA. Concretely, you can encrypt 249 bits using a 2048-bit modulus. This is quite good.


How is a ciphertext encrypted using random numbers decrypted using a symmetric key algorithm

Usually the symmetric key is exchanged with Public-key cryptography (which is asymmetric).

Quote from Wikipedia:

  Because of the computational complexity of asymmetric encryption, it is usually used only for small blocks of data, typically the transfer of a symmetric encryption key (e.g. a session key). This symmetric key is then used to encrypt the rest of the potentially long message sequence. The symmetric encryption/decryption is based on simpler algorithms and is much faster.

Concerning random-number-generators in cryptography:

Cryptographically secure pseudorandom number generators are typically used when the design of a cryptographic scheme needs a random number. These include i.e:

One-time pad
Elliptic Curve Digital Signature Algorithm
Cryptographic nonce


Are pairings still the most efficient implementation for identity and attribute-based encryption?

I am just going to answer regarding identity-based encryption (IBE): I don't know much about the situation for attribute-based encryption.

Also, I am just answering based on today's situation: recent IBE constructions may prove to be very efficient (or not) in the future, and if you want to consider only post-quantum schemes you will have to discard IBEs based on pairings, Diffie-Hellman and factoring.

Pairings

So first, pairing-based IBE is arguably the most studied and mature kind of IBE. The wireless sensor networks (WSN) community has shown great interest in using IBE (there even is a book on it), and there exist many implementations of IBE targeted for WSN: you can for example google TinyTate, TinyPBC or TinyPairing. Dan Boneh's company, Voltage (which has been bought by HP), also proposes pairing-based IBE.

Lattices

There exist a few IBE constructions, but as far as i know, only one public implementation
 (full disclosure: I am a co-author of this paper). It is faster (by an order of magnitude) but less efficient space-wise (secret keys and ciphertexts are about 4 KB).

Also, the encryption and decryption operations can be efficiently implemented on embedded devices (as they are based on Ring-LWE, they have been implemented, just not under the "IBE" tag). For key extraction, I know of no public implementation.

Other technologies

As far as I know, IBEs based on other technologies are less efficient than either pairing-based or lattice-based IBE (depending on the metric of efficiency you choose). This seems clear for IBEs based on quadratic residuosity. Very recently, IBEs have been introduced based on codes or the Diffie-Hellman assumption. There is no implementation proposed yet, so it is hard to give an educated opinion on their efficiency.

Conclusion

If your metric of efficiency is space, the most efficient solutions are pairing-based, but depending on what you consider "efficient" there exist alternatives.
If your metric is speed, it is not true that no other efficient implementation exist (lattice-based ones are faster).
If your metric is "the implementation must be on an embedded device", that leaves just pairings (and lattices if and only if you only need encryption and decryption to be on an embedded device).


Where can I find the standard definition for GPG ECDSA signature?

An ECDSA signature in PGP is indeed encoded as MPI(r) MPI(s)
This is confirmed by RFC6637 which refers back to RFC4880. This is made more clear in draft RFC4880bis which incorporates the former.

Multiprecision integers (MPI) format is itself described in RFC4880, section 3.2


Sender and receiver having different moduli conflicts with encryption and signing in RSA

With public-key algorithms, you don't do encryption and signing of the message using the public-key algorithms themselves.  Instead, you use traditional symmetric algorithms for encryption and hash algorithms for signing, then apply the public-key algorithms to those results.

What you're asking for here can actually be thought of as two entirely-different processes.  The first is to encrypt the message to the public key of the recipient.  The second is to sign the encrypted message with your private key.

As you noted, RSA can only handle encrypting and signing message sizes up to the sizes of the modulus.  However, it's actually worse than that: using RSA on messages larger than a certain percentage of the modulus size is actually also insecure.  Proper use of RSA requires dedicating a certain portion of the input space - actually, most of it - to data called "padding".  You fill in the low part with the encryption key or hash you're encrypting or signing, then fill the upper part with padding according to the specification you are using.  The recipient then validates that the formatting and padding is as expected on the other end.  You must do this, or your encryption system will be broken by attackers if they want.

A proper implementation is going to require secure random number generation.  Generating the public and private keys has to be done using secure random number generation, but encryption is going to require this as well.  Don't try to implement secure random number generation yourself; let your operating system do that for you.  In Windows, use CryptAcquireContextW and CryptGenRandom; on UNIX systems such as Linux and Mac OS X, open the fake file /dev/urandom and read bytes from it.

To encrypt a message with RSA, select a symmetric encryption algorithm.  I recommend 128-bit AES (Advanced Encryption Standard) in CBC (Cipher-Block Chaining) mode, a very typical setting.  For each message you encrypt, generate a 128-bit (or 16-byte) random encryption key and a 16-byte IV (Initialization Vector).  The key and IV are for this message specifically, and shall never be used again.

Combined with the key and IV, encrypt the message using AES.  AES is a block cipher with a block size of 16 bytes; this means that it can only encrypt messages whose size is a multiple of 16 bytes.  To handle messages that are not a multiple of 16 bytes, a technique called Ciphertext Stealing can be used.  Because we're going to send the IV inside the RSA-encrypted area, you're allowed to change the IV as part of the ciphertext stealing technique if the whole message is smaller than 16 bytes.

With the message encrypted, we now do the RSA encryption step.  With RSA, we can only encrypt a small message, but what will it be?  In this design, our message is 32 bytes: the key, and the IV.  This means that you need a key size of at least 1024 bits (128 bytes).  Let $C = AESCBC(IV, M)$ be the symmetrically-encrypted message.

Look up RFC 2437 and find "RSAES-OAEP".  "Optimal Asymmetric Encryption Padding" is a good choice of how to fill out the number $m$ given the message $K$ $||$ $IV$; that is, $K$ and $IV$ concatenated.  Once that's done, you calculate $c = m^d$ mod $n$ for RSA as you've known.  The total encrypted message is $c$ || $C$.

Next, we sign the combined message $V = c$ $||$ $C$ using the sender's private key.  Since $V$ is probably too long, given that $C$ is the same length as the unencrypted message, instead of signing $V$ directly, we sign the hash of $V$.  Choose a good hash algorithm; SHA-256 is a good choice.

Once again, consult RFC 2437, this time the RSASSA-PSS section.  This section describes a method to generate a signature from a private key and a "message", which in our case will be $M = SHA256(V)$.  This generates the final signature, $S$.

Send $S$, $c$ and $C$ to the recipient.

The inverse on the recipient's side should be straightforward to understand if you've implemented the above.  First, the recipient calculates $SHA256(c$ $||$ $C)$, which is equivalent to $SHA256(V)$ and $H$.  Next, the recipient applies RSASSA-PSS-VERIFY to check the signature.  As on the sender's side, $H$ is the message $M$ when it comes to RSASSA-PSS.  If RSASSA-PSS succeeds, $S$ is an authentic signature of $c$ and $C$.

Now the recipient does an RSA decryption of $c$ to recover $m$ using RSAES-OAEP-DECRYPT.  The low 32 bytes are $K$ and $IV$.  Use key $K$ and initialization vector $IV$ to AES-CBC decrypt $C$ back into the original text; don't forget about ciphertext stealing if you used it.  (You can tell whether the sender used it by whether the number of bytes in $C$ is a multiple of 16.)

If an error is detected at any time, abort.  Don't tell the other side any specifics of why.

I would have given more links if my reputation were high enough to allow it.


What are the popular modes-of-operation (AES-GCM, AES-SIV, AES-GCM-SIV, etc.) geared for?

I went through this decision process about 2 years ago and ended up going with something very conservative: encrypt-then-MAC with AES-256-CBC and HMAC-SHA-512 truncated to 256 bits.

Why SHA-512 over SHA-256?  SHA-512 is faster on 64-bit machines.  (Though recent AMD processors' SHA-256 instructions yield a 4x speed-up: link).
Why AES-256 over AES-128?  https://blog.1password.com/guess-why-were-moving-to-256-bit-aes-keys/

This was fast enough for my use cases, but is much slower than many of the alternatives.  The AES part is fast on Intel processors; hashing ends up taking ~80% of the time on long messages.
Alternatives worth considering today:
Replace HMAC-SHA-512 with keyed BLAKE3 (~2.5x faster for long messages).  BLAKE3 itself is very new, but has a somewhat mature lineage.
XChaCha20-Poly1305 (~2x faster for long messages).  Nonces can be up to 192 bits, so there's less of a risk of collisions.
AES-GCM-SIV (~5x faster for long messages).  Doesn't seem to be widely implemented yet.
Note: These performance estimates are vaguely based on a "typical" 2016 x86-64 processor, which has dedicated AES instructions and some general-purpose SIMD, e.g. AVX.


What are the coordinates of a generator point?

Elliptic curves live on a plane, each point having two coordinates. However, all points on a curve must fulfill the curve equation, which allows recomputing (most of) one coordinate from the other.

Let's see what it does for Curve25519. I am using notations from RFC 7748, as explained in sections 3 and 4.1. The two coordinates are then called $u$ and $v$, and the curve equation is:
$$ v^2 = u^3 + Au^2 + u $$
for constant $A = 486662$. Everything is computed modulo $p = 2^{255}-19$.

The generator point has coordinate $u_P = 9$. From the equation, we know that its other coordinate $v_P$ is then such that:
$$ v_P^2 = u_P^3 + Au_P^2 + u_P = 39420360 $$
Modulo $p$, that value has exactly two square roots, which can be computed with the Tonelli-Shanks algorithm; the values are:

v1 = 147816194475895447910205935684099868872 \
     64606134616475288964881837755586237401

v2 = 431144251710685529207648989359339670393 \
     70386198203806730763910166200978582548

Thus, when you say "$u = 9$", you narrow the choice down to exactly two points, $(9, v_1)$ and $(9, v_2)$. Conventionally, the first one is the actual generator.

As a further twist: it so happens that which of these two points you choose as generator does not matter, at least for the intended usage of that curve, i.e. to support Diffie-Hellman. Indeed, the two points $P_1 = (9,v_1)$ and $P_2 = (9,v_2)$ are such that $P_1 = -P_2$ (they have the same $u$ coordinate, and opposite $v$ coordinates). When doing Diffie-Hellman, the involves parties do the following:

Charles chooses a random secret $c$ and sends point $cP$.
Denise chooses a random secret $d$ and sends point $dP$.
Both compute $c(dP) = d(cP) = cdP$.
The shared secret is, conventionally, the $u$ coordinate of the latter point $cdP$.

Now, if Charles chooses $P_1$ but Denise works with $P_2$ has generator, Charles computes point $cdP_2$, while Denise makes $cdP_1$. But since $P_1 = -P_2$, we have $cdP_1 = -cdP_2$, and both points $cdP_1$ and $cdP_2$ have the same $u$ coordinate. Charles and Denise then end up with the same shared secret. Therefore, the exact choice between $P_1$ and $P_2$ does not matter.

This is the reason why the Montgomery ladder algorithm does not actually bother with the $v$ coordinate. All computations are done using $u$ only. Conceptually, when you do things with $u$, you are doing things with two points $(u,v)$ and $(u,-v)$ which are somehow mirror of each other. Since you keep only the $u$ coordinate at the end, the $v$ coordinate can remain implicit throughout.


Blind signatures can be constructed from a ordinary "textbook" RSA signature by seperating the blinding/unblinding operations from the signature operation. The problem is that we do not use textbook RSA signatures in practice. Rather RSA signatures are padded, which increases the security of the signature but also destroys the ability for blinding.

Some libraries, OpenSSL included, do allow you to do a "raw" RSA signature. The Wikipedia article contains how to do a blind signature with RSA –– I'm not sure how much I can add. Essentially, you choose a random integer $r$, raise it to the power of the public key (integer) $e$ mod integer $N$, and multiply it (mod $N$) by the message you want signed. Instead of submitting the message itself to the signature algorithm, you submit the result of multiplying it by $r^e$. The signtuare algorithm will return a signature $s$. Multiply s by $r^{-1}$ and this will be a valid RSA signature on your message.


Your requirements include the following:

S can decrypt the token.
C cannot decrypt the token.

Since S must be able to do something that C cannot, it needs to know something that C does not.

Your approach of signing the token with A's signature is fine for ensuring its integrity (C won't be able to modify it) as long as S knows A's public key through a trusted method (e.g. provisioning when you install your application). To encrypt the token, you will need something else.

The most obvious solution is that S generates a key pair and submits the public key to A (in a way that other parties cannot tamper with — TLS would be fine, as S already has A's public key).

A does not need to trust S in any way (unless there is some authorization mechanism and not just anyone can obtain a token, but that would be a different problem which you don't mention in your question). If S submits a self-signed certificate, just accept it, and identify S by its public key. If that certificate is invalid (i.e. S does not know the associated private key after all), then S will not be able to decrypt the token. S already has the power to refuse to decrypt the token, so this attack vector does not have any security impact.

Be careful in your protocol about replay attacks. Depending on what goes into the token, it may be reusable for other purposes, so make sure that all relevant information (identity of S, identity of C, purpose of the token, …) goes into the signature.


How to calculate inverse affine transform in AES from forward affine transform?

The affine transformation is defined as a degree 7 polynomial multiplication modulo $x^8 + 1$.

In the format of the question, the terms are the right hand column, top to bottom.
$A = x^7 + x^6 + x^5 + x^4 + 1$, and $B = x^7 + x^5 + x^2$.

The inverse can be determined through several methods. Since there are only 254 valid polynomials (omitting 0 and 1), you can just multiply them together until you get 1. Additionally, they happen to be cubes of eachother:

$$(x^7 + x^6 + x^5 + x^4 + 1)^3 ~~mod~~ x^8 + 1 = x^7 + x^5 + x^2$$
$$(x^7 + x^5 + x^2)^3 ~~mod~~ x^8 + 1 = x^7 + x^6 + x^5 + x^4 + 1 $$

This is because of the period of the affine transformation, which happens to be 4. The period is how many times you need to perform the transformation to arrive at the original input. Any affine transformation in $GF(2^8)$ will have a period of $2^0$ through $2^4$ in succeessive powers of 2, or {1,2,4,8,16}.

Therefore, since $A^4 = A^0$, $A^{4-1} = A^3 = A^{-1}$, and since $A^3 = B$, $B = A^{-1}$


Multilinear Extension Polynomial: Compute the coefficients of the expanded polynomial

This can be done in $O(n2^n)$, where $n$ is the number of variables (naive expansion would take $O(2^{2n})$ in the worst case).
This is a standard technique called "sum over subsets/supersets/submasks/supermasks". A usual example is the ANF computation, which does it in $GF(2)$ so it uses the XOR operation. Here it is basically the same but since we work with integers, we have to care about the sign now.
The idea is to apply recursively the matrix
$$
M=\begin{pmatrix}
1 & 0\\
-1 & 1\\
\end{pmatrix}
$$
which corresponds to applying the matrix $M^{\otimes n}$ to the input.
To illustrate the idea a bit further, see what happens when we apply the transformation for one bit (variable), say $x_1$. We have
$$
f_a = 10(1-x_2)(1-x_1) + 32(1-x_2)x_1 + 57x_2(1-x_1) + 81x_2x_1.
$$
What $M$ tells us to do, is to consider coefficients for terms containing $(1-x_1)$, and subtract those from coefficients of terms which are the same except that $(1-x_1)$ is replaced by $x_1$. For the example above, it tells to subtract 10 from 32, and 57 from 81. It is easy to see that this action corresponds to expanding the term $(1-x_1)$. By repeating this procedure for all variables, we obtain the desired result.
Here is python code.
def ext(a):
    if len(a) == 1:
        return (a[0],)
    n = len(a)
    h = n // 2
    l = ext(a[:h])
    r = ext(a[h:])
    return l + tuple(vr - vl for vl, vr in zip(l, r))

a = [10, 32, 57, 81]
b = ext(a)
print(b)  # (10, 22, 47, 2)

To clarify the notation.

in the input array $a$, $a_i$ is the coefficient of the product of: $x_j$ if $j$-th bit of $i$ in the binary representation is 1 or $1-x_j$ otherwise;
in the output array $b$, $b_i$ is the coefficient of the product of $x_j$  if $j$-th bit of $i$ in the binary representation is 1 or $1$ otherwise.

Bits are counted starting from the most significant bit. E.g. for $n=3$, $i=3$ in the input corresponds to $(1-x_1)x_2x_3$, and $i=3$ in the output corresponds to $x_2x_3$.


How a sender will ensure that the public key used for encryption is the key of intended reciver?

This is usually guaranteed by a Public Key Infrastructure (PKI). Typically a certificate authority (CA) signs and issues certificates that bind public keys with the associated entities' (e.g., Bob's) identity. A CA is a trusted third party such that everyone can verify the CA's signature on a certificate to see if it is valid or not. Such a verification algorithm (or the CA's public key associated with its signing secret key) has already been distributed to Alice and any other users who trust the CA (e.g., pre-installed on a laptop).


The Rationale behind NIST's counter/LFSR recommendation on deterministic IV constructions on SP 800-38D

I can't tell whether this is what motivated NIST, but I found a paper that has an argument for LFSR counters in some applications:

Mukhopadhyay, Sourav and Palash Sarkar. 2006. "Application of LFSRs for Parallel Sequence Generation in Cryptologic Algorithms." Cryptology ePrint Archive: Report 2006/042.

Abstract. We consider the problem of efficiently generating sequences in hardware for use in certain cryptographic algorithms. The conventional method of doing this is to use a counter. We show that sequences generated by linear feedback shift registers (LFSRs) can be tailored to suit the appropriate algorithms. For hardware implementation, this reduces both time and chip area. As a result, we are able to suggest improvements to the design of DES Cracker built by the Electronic Frontier Foundation in 1998; provide an efficient strategy for generating start points in time-memory trade/off attacks; and present an improved parallel hardware implementation of a variant of the counter mode of operation of a block cipher.

As I mention in one of the comments to the question, NIST SP 800-38a ("Recommendation for Block Cipher Modes of Operation," 2001 Edition) also mentions LFSRs as an example of an allowable incrementing function for counter blocks (p. 18), so the technique predates both GCM and this paper.
RFC 3686 ("Using Advanced Encryption Standard (AES) Counter Mode With IPsec Encapsulating Security Payload (ESP)," January 2004) also allows the use of LFSR counter blocks. It says LFSR are a common IV generation method (p. 5) and obliquely appeal to similar motivations as Mukhopadhyay & Sarkar for allowing them:

[p. 14] Allows adders, LFSRs, and any other technique that meets the time      budget of the encryptor, so long as the technique results in a unique value for each packet.  Adders are simple and straightforward to implement, but due to carries, they do not execute in constant time.  LFSRs offer an alternative that executes in constant time.

Saying that LFSRs execute in constant time does counterintuitive to us software folks, who are biased into thinking more generally that addition is "simple" but LFSRs "complex."


Find the key to a Vigenère cipher, given known ciphertext and plaintext

Yes.

Remember that, in a Vigenère cipher, the $n$-th ciphertext letter is calculated by adding the $n$-th plaintext letter and the $n$-th key letter (where the key is repeated as many times as necessary to make it as long as the plaintext) modulo 26 (for the standard English alphabet), i.e.:

$$c_n \equiv p_n + k_n \mod 26 \tag1$$

(Here, I'll assume the usual conversion between letters of the alphabet and numbers modulo 26, i.e. $\rm A = 0$, $\rm B = 1$, $\rm C = 2$, $\dotsc$, $\rm Z = 25$.)

Conversely, to decrypt the message, the key is subtracted from the plaintext: $$p_n \equiv c_n - k_n \mod 26 \tag2$$

Note that the decryption rule $(2)$ is obtained from the encryption rule $(1)$ by simple algebraic manipulation: we merely need to subtract $k_n$ from both sides of the equation.  Conversely, if we know $p_n$ and $c_n$, we can solve for $k_n$ simply by subtracting $p_n$ from both sides of $(1)$:

$$k_n = c_n - p_n \mod 26 \tag3$$

Note that similarity to the decryption rule $(2)$.  Basically, to find out the key, given the ciphertext and plaintext, you simply need to decrypt the ciphertext using the plaintext as the key.


Distribution of the Difference of Uniformly Random Elements

Firstly, why is this true?

This is easy to see, if we consider the finite field as a finite group with the addition operation (and ignore the multiplication operation)
If we consider the value $X - Y$, where $X, Y$ are uniformly and independently distributed elements of the group, then there are $n^2$ equiprobable $X, Y$ pairs possible (each with a probability $n^{-2}$.
For any group value $Z$, we have $Z = X - Y$ for $n$ possible $X, Y$ pairs (if we select any value for $X$, we see that the unique value of $Y$ that them sum to $Z$ is $X-Z$); each possible pair has probability $n^{-2}$, and so the probability for the sum to be $Z$ is $n^{-1}$.  This holds for all group members, and so the sum is equidistributed.

Secondly, what happens when you relax the algebraic conditions on the sample space?

As long as the relaxation still leaves us with a ring (that is, the addition operation is still a group), the above argument still holds.


Given $v_1$ and $v_2$, can the server learn anything about $a$ and $b$?

Yes, they can (with high probability) determine whether $a = b$; if $v_2 = 0$, then either $r_1 = 0$ or $a = b$; given that $r_1 = 0$ occurs with probability $1/p$, the attacker can conclude that $a = b$.

Now, that's the only thing the attacker can learn; for any observed $v_1, v_2$, then for any $a, b$ pair with $a \ne b$, there is a unique $r_1, r_2$ pair that makes it work.  As $r_1, r_2$ are selected randomly and uniformly, the attacker gets no information on what the actual $a, b$ pair is.


The difficult part about understanding the Paillier cryptosystem is to understand what the $L$ function in the cryption actually does and why it works. The good news is: To understand the homomorphism, that detail can be put on hold.

The best way to understand homomorphism is to have a close look at the encryption function. Here it is:
$$ E(m) = r^n g^m \mod n^2$$

If we take this apart, we can see:

The modulus is $n^2$. That means we operate on a multiplicative group with order $n \cdot \lambda$ (with $\lambda=lcm(p-1,q-1)$).
This means, there exist subgroups of order $p,q,n,pa, qa,$ and $na$, where $a$ is any proper divisor of $\lambda$.
The random number $r$ has an order equal to one of those subgroup orders. It could be divisible by $p,q$ (actually, it's overwhelmingly likely to be the order $n\lambda$). However, if we take that to the $n$-th potency, then the order of $r^n$ is not divisible by either $p$ or $q$, it can only be a divisor of $\lambda$. That is a property that can be used.

Now for the decryption, it is enough that somehow the decryption function can:

Remove any masking factor which is such an $r^n$, without knowing which $r$ it is.
Get $m$ back from the remaining number $g^m$, which is basically a discrete logarithm in this special kind of group.

Now for the homorphism, just encrypt two messages, build their product and do some very basic transoformations:

$$ E(m_1) = c_1 = g^{m_1}{r_1}^n$$
$$ E(m_2) = c_2 = g^{m_2}{r_2}^n$$
$$ c_1 c_2 = g^{m_1}{r_1}^n g^{m_2}{r_2}^n = g^{m_1+m_2} (r_1r_2)^n$$

Clearly, this is just the same as using the encryption method with the message $m_1+m_2$ and the random number $(r_1r_2)$. And for that the decryption works just like for a single ciphertext.


Authenticating a message with HMAC vs AES-CBC

Given some string s I want to [integrity protect], are following methods are equivalent to produce message with signature, assuming it does not matter whether s is visible in message or not?

Absolutely not; with AES_CBC, if the attacker modifies one particular block of the ciphertext, then the decryption of the modified ciphertext will have two blocks modified (the one corresponding to the modified block, and one block after that).

Hence, if s is (at least) two blocks long, an attacker can freely modify the first block of the ciphertext; the decryption will still have the string of zeros still in place (as that wasn't modified), and so the attacker has succeeded in undetectably modifying the string.

If you need a MAC, use a MAC (alternatively, authenticated encryption).  And, make sure that a MAC is appropriate (that is, both the sender and the receiver share a secret key, and you don't mind if the receiver were able to generate valid-looking messages of his own).


Large file validation on an embedded system through hash and encryption

You can make incremental changes that only touch small pieces of the file faster, at a cost in complexity.

Multiple hashes can help with that.  Rather than a single hash value, you can amortise the cost of computation by storing multiple hashes.  If you hash the large file in pieces, then you can create a single hash that covers the entire file by hashing all the resulting hashes, which should be quick.

Then you only have to calculate the hashes over the chunks that the patch touches, plus a final pass to combine them all.

This effectively splits the big file into many.  The main consequences is that if the patch alters the size of chunks, the chunk boundaries have to move too.  That means that you have to maintain the chunk boundaries too, so what you store is a list of offsets and hashes.  And you'll have to be careful about applying the patch across a boundary.  That makes cumulative patches tricky to get right.

As long as the hash reported with the patch (you'll want to authenticate this somehow) has the same understanding of the chunk boundaries, then you are ok.  You could include the boundaries with the patch itself.

Don't use md5 if you care about preventing tampering, its collision resistance is miserable.  SHA-2 is plenty fast if you don't have to run it over your entire data set all the time.


Elliptic curve with non-prime generator?

The question is a bit broad. Generating secure elliptic curves is highly non-trivial, see for example this question, which contains references to this and this paper.

Considering a black box group, the fact that it has order $6\cdot q$ does not break the DLP. What happens is that the DLP can easily be reduced to a group of order $q$ by eliminating the cofactor 6. So being a multiple of 6 does not break DLP, nor does it help.

However, an elliptic-curve group is of course not black box. In some particular cases we can use properties that reduce the ECDLP to simpler DLP's, for example in the case of supersingular or anomalous curves. These are criteria which have to be taken into consideration when choosing the curve, to make sure the corresponding ECDLP is hard.

However, cryptographic protocols rely on assumptions which are similar, but not exactly the same as the ECDLP. For example, the Diffie-Hellman assumption does not reduce to ECDLP. Therefore, we also have to choose curves in such a way that attacks on our particular protocol are avoided. There are many attacks which target an elliptic-curve-based protocols by using properties of the underlying curve. Important examples are small-subgroup attacks (very relevant here!) and twist attacks. There are many more examples.

In conclusion, having order $h\cdot q$ for a large prime $q$ and some integer $h$ is necessary to build secure elliptic-curve-based protocols. It is however not sufficient. Obtaining a secure elliptic curve of order $6\cdot q$ is possible, but you'll want to take many more properties into account before deciding to use it. This is very non-trivial, so generate your own curves with care.


This depends on the type of attack planned, and the information available. Given only the output string (or parts of it), any decent cryptographic PRNG is infeasible to try to predict (which is usually what you want, since future keys or other parameters are desired).

Additionally, if your symbol distribution is uneven, it is not a very good PRNG. (For the simple reason that it is easier to try to simply brute-force prediction guesses). Their main protection typically is limited number of brute-force trials possible for the attacker.

However, NIST has a standardized test suite to test bit-valued PRNGs (NIST SP 800-22. Simple googling will give you the document, source code and binaries).

The test suite will try to find a common set of weaknesses from a bit-valued PRNG output. Using the results from the test suite, it would be possible to try to estimate the PRNG behavior, statistically, in case it was badly designed.

In case the PRNG symbols are not binary, and/or they have an uneven distribution, most of the NIST-tests would fail, or refuse to start. It is a straightforward (but not necessarily trivial) transformation of number bases to move from N (evenly distributed) symbols to a binary base.

For the unevenly distributed case, it might be useful to try to find an evenly distributed set of symbols to try to arrive to applicable binary base. For example:

Given a distribution of A: 1/2, B: 1/4, C: 3/16, D: 1/16
Assign a set of 4-bit codes for each: 8 codes for A, 4 codes for B, 3 codes for C and 1 code for D
Replace the symbol string with this assigned bit-string such that for example for an occurence of A, assign randomly one of its 8 codes to that occurrence.

Because this transformation does not look like the original bit string, you will need more samples (probably at least as many times as is the size of the largest bit-set) to compensate.

In general, some of the NIST tests require in the order of billion-bit samples to complete, so they may be applicable only for automated systems, not for example physical world gaming devices. (Slot machines have sometimes been attacked via weak PRNGs inside them, see e.g. https://www.ethicalhacker.net/features/book-reviews/mitnick-the-art-of-intrusion-ch-1-hacking-the-casinos-for-a-million-bucks)


Does it make sense to block RSA keys under 1024 bits?

Those findings were based on a broken PRNG. A broken PRNG affects all keys generated on such a device, no matter the size or the algorithm.

Common primes were how the problem was detected, but the problem itself is unrelated to primes or RSA. If RSA keys of a specific size where affected, that's only incidental because that's what the broken devices generated.

Blocking keys smaller than 1024 bits can be a good idea, because their security margin against factoring attacks has grown pretty thin, even when they're correctly generated. But that threat isn't related to the paper you link.


Is it dangerous to encrypt lots of small files with the same key?

I'm assuming that the OP wants to access all files individually and updates or rollback to old versions, too.
The Cryptokit has only AES-GCM and ChaCha20-Poly1305.
Using the same key for all of the files is a dangerous path. Both AES-GCM and ChaCha20-Poly1305 are vulnerable in the case of (key,IV) reuse. For example,

if you encrypt the file $f$ with AES-GCM with the key $k$ and $IV_f$ to get $$(ciphertext,tag) = AES\text{-}GCM(k,IV_f,f)$$ and the file stored as $$IV_f \mathbin\|ciphertext\mathbin\|tag.$$ Where the IV's are unique for each file, otherwise you already in the pit of $(Key,IV)$ pair reuse.
Now, later you access the file and updated it. Used the same $k$ and $IV_f$. Now you gave an observer, not necessarily an active attacker, two files encrypted under the same $(key,IV)$ pair, the old version of the file and the updated). Now the confidentiality is lost or even more, an active attacker can make forgeries, too.

What are the options?

Continue to use the same key with a new IV.
You need to keep track of all of the used IVs and determine a new unique IV for every new file and whenever a file update. The better is;

Use a new key and new IV for each file and updates.
Generate a new random key and IV for a new file or update of a file to a fresh encrypt. How?
Get a master key $K_m$ and store it with a password manager like Keypass.

Using the file name and the update date and time of the file in the $$HKDF(K_{m}, fileName \|update)$$ can be a solution. However, there are traps here, too. The filename can be changed or you move the file into another location, the update information changed and you lost all!

The better one is using random information for each file like a 256-bit random bit as salt and use it together with HKDF. The HKDF can be used to derive multiple keys and even the IV. First, Extract a pseudorandom key (PRK) from the Initial Key Material (IKM) as $K_m$
$$PRK = \text{HKDF-Extract}(salt, IKM)$$
Then use the Expand with the additional info to arrive the Output Key Material (OKM) with the desired length $L$ and prefer AES-256.
$$OKM = \text{KDF-Expand}(PRK, info, L)$$
call it two times
$$File_{key} = \text{KDF-Expand}(PRK, \text{"KEY"}, 256)$$
$$File_{IV} = \text{KDF-Expand}(PRK, \text{"InitialValue"}, 96)$$ to derive the key and IV.
The IV size is 96 since GCM's recommended IV size is 96. During the update of the file, get a new random salt and use the HKDF again. The random salt can be generated /dev/urandom/ where available or in IOS SecRandomCopyBytes.
Store the file as;

$$Salt \mathbin\|IV \mathbin\|ciphertext\mathbin\|tag.$$

HKDF: HMAC-based Extract-and-Expand Key Derivation Function (HKDF) is defined in and proposed by H. Krawczyk and P. Eronen in May 2010 as RFC5969.

The age library
What we write above for developing a tool/library yourself. This has lots of pitfalls, too. Just consider the OpenSSL's evolution over time then it becomes almost unmanageable.
SAI-peregrinus made a comment about the age library. I've overlooked the library and saw that it is an active library and the developers are aware of the recent incoming attacks/problems and apply patches about them.
So instead of building your own library consider one that is well maintained and fit your needs.


How simple hash provide message authentication?

As indicated by Dave in the comments, hash-then-encrypt may not provide authentication, so the scheme in the picture you provided may not be secure at all.

Let's assume for this answer that the encryption scheme used is such that hash-then-encrypt is secure. It could for instance be mapped to AES-GCM which uses GHASH, or Poly1305 correctly paired with a block cipher.

The idea of authenticated encryption is not to provide security against leaking information about the key. If the key gets known to the adversary then all protection is lost.

Authenticated encryption provides message integrity - protection against changes of the ciphertext. These changes may be deliberate, i.e.  changes of the ciphertext during transport by an adversary or non-intentional such as data loss by lower levels in the transmission.

If you don't provide message integrity then an adversary may change the ciphertext and thereby alter the decrypted plaintext message without this being detected. It could also trigger the availability of a plaintext oracle that may even compromise confidentiality of the message. Note that hash-then-encrypt may not provide protection against padding oracles if CBC mode encryption is used, as the padding is (commonly) removed before the hash is verified.

Besides that, it provides message authenticity: proof that the plaintext as encrypted by an entity holding the secret key. Nobody else would be able to encrypt a valid hash after all.

In short, the hash is there to protect the message, it doesn't protect the key.


Does an encryption algorithm exist where encrypted data can be decrypted by multiple private keys?

Yes, quite easily, with key encapsulation and the appending the symmetric key twice (encrypted for each company):

Encrypt the data with a random symmetric key, for instance an AES key;
For each recipient, encrypt the symmetric key with the respective public keys of the recipients.

The ciphertext is the combination of the encrypted message and wrapped key for each recipient.

More theoretically, you could use identity-based encryption, which is close to what you describe. That does require a common setup, though, and possibly someone having a master key.


You have to specify a particular cryptosystem for a particular answer.  Generally, in an elliptic-curve-based cryptosystem, a secret key involves a scalar, which is an integer within the range of the number of points in a group on the curve, possibly subject to some constraints, and chosen uniformly at random from all possibilities.  It's OK if you get that by hashing a secret of sufficient entropy, and shoehorning it into the right range.

In the Diffie–Hellman function X25519, a secret key is traditionally an arbitrary string of 256 bits, with some bits masked so that the Curve25519 scalar is a uniform random choice of a multiple of 8 between $2^{254}$ and $2^{255}$ for a couple of reasons: [1], [2].

In the signature scheme Ed25519, there are a few different forms of secret key for different applications and performance constraints.  For compatibility reasons, the same masking is often done on the bits that get interpreted as an edwards25519 scalar, though there are other issues too in more exotic applications.

In ECDH and ECDSA over prime-order curve groups such as NIST P-256 or secp256k1, a secret key is usually the canonical encoding of any positive integer below the order of the group which is necessarily also the order of the standard base point.  Mostly ECDSA is done over curve groups with prime order and no concern for twist security (e.g., the largest prime factor of the order of the quadratic twist in NIST P-224 has only 118 bits, well within the realm of ECDLP feasibility), unlike X25519 and Ed25519 which work in a curve group of cofactor 8 whose quadratic twist has cofactor 4.


Multiple sender single receiver Encryption

They do not share their private keys, but they do have to share b^R(i) for each sender i.

What they might do is, the first sender supplies mb^R(1), the second will supply mb^R(1)^R(2) and so on for the numerator round (two rounds). To do this they need to come together (in your paper there is, "Simultaneously, the senders compute for the value of c2 using the formula...").


Derivation of many (Key, IV) pairs from random 128 nonces and one secret 512 master key

Do we get to assume that the master key is uniformly selected?  The goal of a KDF, as the HKDF paper defines it, is this:

  Its goal is to take a source of initial keying material, usually containing some good amount of randomness, but not distributed uniformly or for which an attacker has some partial knowledge, and derive from it one or more cryptographically strong secret keys. We associate the notion of “cryptographically strong” keys with that of pseudorandom keys, namely, indistinguishable by feasible computation from a random uniform string of the same length.

If the master key is selected uniformly at random, then the full HKDF extract-and-expand paradigm is not needed; all we need is the expand phase, which can be realized by a PRF with an uniform key.

Given the PRF security of HMAC-SHA512 your use of it looks appropriate then, but possibly overkill because:

HMAC supports variable input lengths, but this application has fixed input and output sizes;
The application is already using AES, so bringing in HMAC requires an extra primitive.

So perhaps simpler would be to just:

Use a shorter, 256-bit master key directly as the AES key;
Given a file's random nonce, derive the file key as fk = fk[1] || fk[2] || fk[3] || fk[4], where:

fk[0] = random_nonce;
fk[i] = AESENC(master_key, fk[i-1]).

This is equivalent to encrypting all-zero plaintexts in OFB or CBC mode with random IVs, so attacks against this approach should reduce to attacks against those modes.  So for example if some file keys are leaked as you suggest, that's a known-plaintext attack scenario.

As a real-life example, the current AES-GCM-SIV draft (draft-irtf-cfrg-gcmsiv-02) uses a variant of this to derive its encryption and authentication subkeys (section 4):

if len(key-generating-key) == 16 {
  record-authentication-key = AES128(key = key-generating-key, input = nonce)
  record-encryption-key = AES128(key = key-generating-key,
                                 input = record-authentication-key)
} else if len(key-generating-key) == 32 {
  record-authentication-key = AES256(key = key-generating-key, input = nonce)
  second-half = AES256(key = key-generating-key, input = record-authentication-key)
  first-half = AES256(key = key-generating-key, input = second-half)
  record-encryption-key = concatenate(first-half, second-half)
}


ECIES/ ECDHE/ EC-ElGamal encryption comparison

Fix a group $G$ of order $q$ in which discrete logs are hard, and fix a standard base point $g \in G$.  Fix an authenticated cipher $E_k$ of bit strings.

In (EC)IES, roughly:  A public key is a point $h \in G$.

To encrypt a message $m$, the sender:

picks an exponent $y \in \mathbb Z/q\mathbb Z$ uniformly at random,
computes an ephemeral public key $t = g^y$,
computes an ephemeral shared secret $s = h^y$, and
sends $t$ alongside $c = E_k(m)$ where $k = H(s)$ is a hash of the shared secret.

Note: The total computational cost is two exponentiations; the total ciphertext overhead is one group element.  Effectively, we are generating an ephemeral Diffie–Hellman key pair $(y, t)$ and doing a Diffie–Hellman key agreement with it.
The receiver, who knows the secret exponent $x \in \mathbb Z/q\mathbb Z$ such that $h = g^x$, computes $k = H(t^x)$ and decrypts $c$ with $k$.

Note: The total computational cost is one exponentiation.

In (EC-)Elgamal:  A public key is a point $h \in G$.

To encrypt a message $m$, the sender:

picks an exponent $y \in \mathbb Z/q\mathbb Z$ uniformly at random,
computes an ephemeral public key $t = g^y$,
computes an ephemeral shared secret $s = h^y$,
picks $k$ uniformly at random from some subset of $G$,
computes the product $z = k \cdot s$, and
sends $t$, and $z$, alongside $c = E_k(m)$.

Note: The total cost is two exponentiations and one multiplication; the total ciphertext overhead is two group elements.
The receiver, who knows the secret exponent $x \in \mathbb Z/q\mathbb Z$ such that $h = g^x$, computes $k = z\cdot t^{-x}$ and decrypts $c$ with $k$.

Note: The total cost is one exponentiation and one multiplication.

As you read, you may see a resemblance here!  Elgamal does essentially everything IES does, plus some extra work that adds no security, which I have written in bold.

In the elliptic curve case, Elgamal is even trickier.  Why?

In the finite field case where $G = \mathbb Z/p\mathbb Z$, the integers modulo a prime $p$ (or where $G = \operatorname{GF}(2^n)$), $k$ can be (say) a 256-bit string that serves a dual purpose as an AES key and, interpreted as an integer in little-endian, as an element of $G$.
In the elliptic curve case, there's no natural map between bit strings and elements of $G$, so you need to choose some correspondence between random elements of $G$ and (say) AES keys—like a hash function $H(k)$.  But if you were going to hash an element of $G$ into a key anyway, you might as well have just used ECIES!

Even worse, Elgamal requires computing multiplication in $G$, not just exponentiation $G$, which means that you can't take advantage of DH functions like X25519 which support only the equivalent of exponentiation (‘$x$-restricted scalar multiplication on Curve25519’, using the fast constant-time Montgomery ladder) but not the equivalent of multiplication (‘point addition on Curve25519’).

The only reason to use Elgamal is exotic applications that require expert guidance like voting systems, where the message $m$ is concealed directly, rather than some key $k$ used for an authenticated cipher; this happens only if you are exploiting the homomorphic properties of Elgamal, and doesn't work with arbitrary bit string messages but rather requires you to be very judicious about what messages are and how they are chosen.

If you want public-key anonymous encryption, you should use libsodium crypto_box_seal, which is conceptually the same idea as ECIES (with all the details I go into done differently).  Note, of course, that public-key anonymous encryption is a kind of weird thing to do that most applications, outside journalists accepting leaks, don't need.  More likely, you want public-key authenticated encryption, for which you should use NaCl/libsodium crypto_box_curve25519xsalsa20poly1305, if you have a definite notion of a sender and receiver who know one another's public keys and want to exchange unforgeable secret messages.


Your assumption is correct, that is called the Discrete Logarithm Problem.

The complexity of the problem is linear to the number of elements of the group but exponential to the number of bits of the group's size (These days you usually use a 2048 bit prime for a DH exchange, meaning that there are ~ 2^2048 elements in the group)


Why are PRNG in programming languages not cryptographically secure by default?

First, insecure PRNGs are typically faster than CSPRNGs. CSPRNGs based on /dev/urandom (if you're familiar with Linux), for example, have to call the crypto kernel module driver every time. For reference:

the BearSSL implementation of ChaCha20, which can be used as a CSPRNG, on an Intel Xeon CPU at 3.10 GHz, reaches 270.72 MB/s;

an implementation of a Mersenne Twister, which is a typical PRNG, on an Intel Xeon 5160 at 3 GHz, reaches 113.4*32/8=453.6 MB/s;

there are even faster algorithms/implementations. For example, the rand() function in the GNU Scientific Library, according to the same paper, reaches 227.8*32/8=911.2 MB/s. Xorwow, which belongs to the Xorshift PRNG family, reaches 1388.4 MB/s.

Second, writing cryptographic software, including CSPRNGs, is much more complex than writing general-purpose software.

There are also historical reasons. At least until the 1990s, developers, including some developers working on standardizing new programming languages, were afraid to deal with cryptographic algorithms, because the export restrictions on cryptography were severe and not entirely understood by them. Quoting one such developer:

  I would not have even considered putting crypto strength randomness into anything that shipped with the browser without getting a huge amount of legal advice from the MSLegal team. I didn't want to touch crypto with a ten foot pole in a world where shipping code was considered exporting munitions to enemies of the state. This sounds crazy from today's perspective, but that was the world that was.

What about more recent programming languages, such as Python?

Some people argue that baking CSPRNGs into programming languages by default would lead to a false sense of security, especially as new flaws arise and when dealing with older software. Say that now, in 2018, random is cryptographically secure. Do developers remember to check, when dealing with older versions, that the old random was actually insecure?

An interesting quote on this matter:

  Anyone writing crypto code without reading the docs and understanding what they are doing are surely making more mistakes than just using the wrong PRNG. There may be a good argument for adding arc4random support to the stdlib, but making it the default (with the disadvantages discussed, breaking backwards compatibility, surprising non-crypto users, etc.) won't fix the broken crypto code. It will just give people a false sense of security and encourage them to ignore the docs and write broken crypto code.

See this for more insight on how the Python community was reasoning about implementing a CSPRNG by default.

TL;DR. They are faster and easier to implement. In the past, people were afraid of crypto, because of heavy restrictions. Now, people are afraid of giving a false sense of security.


Offline anonymous electronic money systems and their cryptographical base

http://faircash.org/technology/teleportation.html

  Due to the Digital Coin concept, a value transfer between payer and payee is realized by transferring ownership of the eCoin. An essential part is the way how this transfer is conducted: Following the cash paradigm, it needs to be done peer-to-peer and offline in a repeatable way. Such a transfer is called teleportation.


Reordering non-block-aligned parts with DES in ECB mode

If the plaintext format is indeed as you describe, then you're out of luck: the insertion of the newlines and the consequent shifting of the plaintext records is enough to disrupt any structure in the ciphertext.  If the plaintext were longer, say, 8 records, then it could work, but with just 7 records there's no way to switch the first and last record simply by shuffling ciphertext blocks.

However, I suspect you're mistaken about the presence of newlines in the plaintext.  Specifically, since the encryption command you were given does not include the -nopad option, the openssl enc command applies PKCS #5/7 padding to the plaintext before encrypting it.  In order to be unambiguously reversible, this padding scheme always increases the length of the plaintext by at least one byte — in particular, it causes any plaintext length between 280 and 287 bytes inclusive to produce a ciphertext of 288 bytes.

Thus, I suspect that your data actually has no newlines, and simply consists of seven 40-byte fixed length records, plus 8 bytes of padding.  Keeping the last 8 bytes of the ciphertext in place, and switching the first and last 40-byte chunk of the ciphertext preceding it, should do the trick.


What makes the Discrete Logarithm Problem hard?

It is true that you have in the worst case $\operatorname{ord}(Z^*_p)$ values to test. However, the complexity of a problem is actually measured according to the size of the input of the problem in computer representation which is binary.
Here the inputs to our problem are h and p. These two are integers both of size $log_2(p)$ at most in computer binary representation. And the algorithm would take $\operatorname{ord}(Z^*_p) = p$ iterations. However, $p = 2^{log_2(p)}$, so we can clearly see that the number of iterations required is actually exponential to the size of our input of the problem. Which is why the discret logarithm problem is hard.
When you usually see complexities of the form $O(n)$ or $O(log(n))$, we actually assume that the size of our problem is $n$ in computer representation, without explicitely saying it.


What should I think about these unique certificate serial numbers

I would think these numbers would have been put on the google search engine, and yield (probably) many hits.

This assumption is wrong. Certificate serial numbers are not indexed by common search engines, nor are they typically posted to any HTML site. Frankly, I'm not sure why you would assume they'd be indexed.

The Wordpress certificate is used for all Wordpress domains; it is for *.wordpress.com (matching all subdomains of wordpress.com), and has wordpress.com as an alternate name (so it also works there). The Google certificate you list is only used for www.google.com; it is again something that commonly shows up (Chrome reports a different certificate for some reason).

The reason you don't find any posts about them on Google is that no one really cares.