How do I tack on "additional data" to libsodium's public-key authenticated encryption?

Internally, libsodium public key encryption uses the same primitives as the (nonAEAD) secret key authenticated encryption, namely XSalsa20 and Poly1305. NaCl, which libsodium is based on, does not have an AEAD interface at all. Instead, libsodium added it from a TLS draft. There is no similar reference for public key AEAD use of these primitives, since in TLS they are expected to be used with the negotiated secret key. That is my guess as to the main reason it does not exist in libsodium.

As an aside, the use case for public key AEAD seems a bit thin overall. Usually the additional data in AEAD is used for protocol information that is not secret but must be tied to a particular message. E.g. in TLS it includes the sequence number and compression details. However, if you have a protocol where multiple messages are sent, you do not really want to use public key encryption for each message, but rather a session key and symmetric encryption.

There are many ways you could go about constructing your own:

Simplest would be to just include the additional data in the message to be encrypted. That is wasteful if you also need to send it in the clear, of course, and you can only verify it after decryption. You can avoid duplicating long data by including only a hash of the data in the message.
Alternatively, you could sign the encrypted message + additional data. That requires a signing key-pair, the public key of which is known to the receiver. It also adds quite a bit of overhead. However, it does allow verification of the additional data before decryption.
Finally, you could negotiate a symmetric key and use the AEAD cipher already in libsodium. Simply generating a random symmetric key and encrypting it with public key authenticated encryption would work, but there are more complex ideas too, depending on what kind of security you need.

Note: the currently included AEAD cipher based on the draft only uses an eight byte nonce, which is too short to be safely generated randomly. A later version of libsodium will include the updated version with a longer nonce.


There is a lot to this question, and I believe some concepts of multiparty computation can be useful in relation with this problem. There's one catch: lying is a very abstract concept, even with a simple and well defined concept as age.

So, for the sake of the argument, let's define some conditions:

Each participant introduces a valid age value (i.e. within a given range -maybe 0-99, as Maarten proposed).
Each participant provides only one input to the protocol.
The counting entity is reliable.

For certain encryption algorithms (e.g. Lifted ElGamal) it is possible to prove that an encrypted value falls within a range without disclosing the value. Then, each participant $p$ has to generate a set $(p, E(a_p), proof_{a_p})$. When the counting entity has all the sets, it can verify each value of $p$ is unique. Since Lifted ElGamal is also additively homomorphic, the sum of all the ages can be computed without decrypting the values.

DISCLAIMER 1: if the counting entity cannot be trusted, the scheme gets harder, but the general spirit of the communication is similar.

DISCLAIMER 2: this is strongly based on protocols for voting. The verification of identity, adding and the decryption processes can be performed by different entities within the counting authority to keep a higher level of privacy around the encrypted values.

As Maarten suggested, here are some links to the relevant content:

Homomorphic encryption : a property of cryptosystems that enable some operations on the ciphertexts without decrypting the values.
Sigma protocols : a generic approach to Zero Knowledge Honest Verifier Proofs (ZKHVP).
Zero Knowledge : a long lecture on zero knowledge techniques. Set Membership is covered around the slide 144.
Estonian voting process : an example of a critical application based on the principle of division of responsibility within the counting (voting) authority).


How can I extract randomness from a JPEG file?

All original JPEGs are sources of true entropy due to:

Noise on the image sensor.  However small it might be, it is unavoidable due to the very nature of the stochastic photoelectric effect on the silicon detectors, be they CCD or CMOS. There are also other noise sources such as reset noise, thermal noise etc. This means that what ever you take a photo of, it will contain truly random noise across the image sensor.
Compression.  Once the image is captured by the sensor, the JPEG algorithm kicks in.  Various processes occur that have the effect of reducing the intensity of high frequency noise both level and colour wise.  So the randomness /entropy of the image drops significantly, perhaps to only 10% of that originally captured.  This remaining noise is then losslessly compressed into a final jpg file.  You could look up the JPEG algorithm.  The consequence of the lossless compression is that tiny changes to the input image result in huge changes to the compressed jpg file.  This is akin to changing a word in a zip file which then results in a totally different zip.  It’s also akin to the avalanche effect.

Since every original JPEG file ever taken throughout the known universe is unique, this forms a perfect source of entropy.

Since the format of a jpg file is highly structured, it cannot be used directly as a source of uniformly distributed random numbers.  It has huge correlations between bytes as you would expect of a standardised file format.  This is why you have to treat the file as one sequence of unique bytes, some of which are hugely correlated whilst others are totally fixed such as the golden byte.  Never ever open up the file and work on the image.  You have to extract the entropy out of the jpg file itself, after measuring it with something like a minimum entropy calculation.  I have a JPEG based true random number generator called a Photonic Instrument which you can see.  Ignore the dumb ass  humour and focus on the science, especially the Kullback–Leibler divergence graph.  It produces JPEGs with a  min. entropy of approx. 100 kbits /frame, which is about 5 bits /byte, and can do 4 frames /s.

You will have a true random number generator if you extract less than 100 Kbits from each frame / file.  This is the golden rule of true random number generation.  A common way to extract entropy is by hashing.  It can be any kind of hash function, and not necessarily cryptographic at all.  In fact, cryptographic hash functions can lead to the Cryptographic Hash Function Extraction Fallacy, which means if you use one you risk producing random looking output from any kind of rubbish input like a simple counter.  I avoid them like the plague and am suspicious of any generator using them.  Since you know that JPEGs are a source of true entropy in this case you  are okay using one for this example, but you could do better.

You have to ignore the bleating of the theoreticians who say there are no extractors that work on all sources.  You just have to ensure that [entropy out] < [entropy in].  Otherwise there wouldn’t be a thriving commercial market selling true random number generators would there?  Hash it and there you go.  You can use any of them (like MD5) but they don’t go over 1024 bits.  You could write your own as I did which is a simple substitution permutation network with a block size of up to 512 kbits.  That can hash my 20 Kbyte frame in one go.  Alternatively, use SHA-1 several times over the jpg, making sure you add a counter to change the initial state, or use a kinda of block chaining hash mode.

This is all a lot of talk so try this…  Take 10 pictures with your phone of anything at all.  Hash each picture with SHA-1.  The resulting 200 bytes will be truly random.  Go from there and prove the naysayers wrong…


XTS has been designed for disk encryption, where an attacker typically has access to the disk only a single time (when they steal/confiscate the device).

When an attacker sees several ciphertexts encrypted using the same key, they can tell which blocks differ between the versions, but not the content of the blocks. Compare this with CTR mode, which leaks which bits differ, which is far worse.

XTS should be used when an attacker typically sees only one version, but it doesn't fail completely when they see several.

As an alternative, you could either increase the effective block size. Since blocks being identical becomes rarer with longer blocks, this reduces the leak, but it doesn't eliminate it. BEAR, LION, LIONESS, "wide blockcipher" EME and AEZ might be worth reading about (I'm not familiar with the details of these).

Or you could store an IV alongside each sector of ciphertext, replacing it by a new IV when overwriting. If you use a 16 byte IV and 4096 byte sectors, this is an overhead of 0.4%. The bigger downside is that you won't have a direct mapping between equal sized plaintext and ciphertext blocks, which may impact performance and prevents write-through.

You can't avoid information leaks completely, if you can't afford per-sector IVs and need random write access.


Proof that a function constructed from a PRP is, or is not a PRF?

Here are two different ways to break $G$.

Attack 1. $G$ is unlikely to be a secure PRF, at least against non-uniform adversaries.  In particular: there is likely to exist a fast attack (though it might take $2^b$ steps of computation to find the attack).

The idea of the attack: With high probability, there exists $x,x'$ such that $E_A(x)\wedge 1 = E_A(x') \wedge 1$ and $E_B(x)\vee \overline{1} = E_B(x') \vee \overline{1}$.  This immediately yields a distinguishing attack on $G$, since (regardless of $K$) we are guaranteed that $G_K(x)= G_K(x')$, something that should happen with just $1/2^b$ probability (not with probability 1).

I don't know how to efficiently find $x,x'$.  I can see how to find such a pair in about $2^b$ steps of computation.  Basically, pick a random $b$-bit value $y$, then compute $E_A^{-1}(y)$ and $E_A^{-1}(y) \oplus 1$; this gives a candidate pair $x,x'$, and you can then check whether $E_B(x)\vee \overline{1} = E_B(x') \vee \overline{1}$ holds.  The latter holds with probability $1/2^{b-1}$, so you'll probably have to try about $2^{b-1}$ different values of $y$ before success.  Nonetheless, even though the attack is hard to find, once you know the attack, the attack requires only 2 oracle queries and minimal computation.  This suffices to demonstrate that $G$ is not a secure PRF, at least under standard definitions of security.

Attack 2. I'll show an attack on $G$ that has about the same complexity as the best attack I can find on $F$.  In both cases, the attack requires about $2^b$ steps of precomputation just to find the attack, but then once the attack is known, it takes a lot less than $2^b$ steps to distinguish $G$ (or $F$) from a random function.

My attack on $G$ is an adaptation of my attack on $F$, so let me start by spelling out the attack on $F$ that I have in mind.  Define the permutation $\pi$ by $\pi(y)=E_B(E_A^{-1}(y))$.  The precomputation is as follows: find a short cycle of $\pi$, say $y_0,y_1,y_2,\dots,y_k$ (where $y_k=y_0$ and $y_{i+1}=\pi(y_i)$ for each $i$).  Define $x_i=E_A^{-1}(y_i)$.  Then we are guaranteed that $F_K(x_1)\oplus F_K(x_2) \oplus \dots \oplus F_K(x_k) = 0$.  This gives a distinguishing attack on $F$ that requires $k$ oracle queries and trivial work.  Since $\pi$ is effectively a random permutation, we should be able to find a short cycle in $\pi$: it is very likely that a short cycle will exist.

How long does it take to find the attack on $F$?  I can't see how to do it much faster than $2^b$ steps of computation.

Now here's the attack on $G$.  First, we're going to construct a new function $H$, as follows: $H_K(x) = G_K(x) \oplus G_K(x')$, where $x' = E_A^{-1}(E_A(x) \oplus 1)$.  Notice that, if you have an oracle for $G$, you can extract an oracle for $H$.  Also, expanding the definition of $H$ yields $H_K(x) = E_K(E_B(x) \wedge \overline{1}) \oplus E_K(E_B(E_A^{-1}(E_A(x) \oplus 1)) \wedge \overline{1})$.  By analogy to the attack on $F$, let's define a permutation $\sigma$ by $\sigma(y) = E_B(x') \wedge \overline{1}$ where $x=E_B^{-1}(y)$, i.e., $\sigma(y) = E_B(E_A^{-1}(E_A(E_B^{-1}(y)) \oplus 1)) \wedge \overline{1}$.  During precomputation, find a short cycle of $\sigma$, say $y_0,y_1,y_2,\dots,y_k$, and define $x_i=E_B^{-1}(y_i)$.  Then we are guaranteed that $H_K(x_1)\oplus \dots \oplus H_K(x_k)=0$.  This in turn implies a relation on $G$, where the xor of $2k$ $G$-outputs is guaranteed to be zero (regardless of $K$).  Thus, any short cycle in $\sigma$ yields a distinguishing attack on $G$.  The distinguishing attack itself is very fast (assuming $k$ is small).

How long does it take to find the attack on $G$?  I can't see how to do it much faster than $2^b$ steps of computation---in other words, about the same complexity as finding the attack on $F$.

This provides an alternate way to break $G$.


is coin-tossing an instance of secure computation (MPC, 2PC, etc.)?

Yes it does.
Here is a brief summary from https://eprint.iacr.org/2009/214.pdf:
When a majority of the parties are honest, efficient and completely fair coin-flipping protocols are known as a special case of secure multiparty computation with an honest majority (assuming a broadcast channel) as in

M. Ben-Or, S. Goldwasser, and A. Wigderson Completeness theorems for non-cryptographic fault-tolerant distributed computation. STOC 1988.

When an honest majority is not available, and in particular when there
are only two parties, the situation is more complex. Blum’s two-party coin-flipping protocol from 1982

M. Blum. Coin flipping by telephone - A protocol for solving impossible problems. 25th IEEE Computer Society International Conference, 1982.

guarantees that the output of the honest party is unbiased only if the malicious party does not abort prematurely (note that the malicious party can decide to abort after learning the result of the coin
flip).
This satisfies a rather weak notion of fairness in which once the malicious party is labeled as a “cheater” the honest party is allowed to halt without outputting any value. Blum’s protocol relies on any one-way function and Impagliazzo and Luby (see linked paper) later on showed that one-way functions are in fact essential even for such a seemingly weak notion.


Confused with the role of AES round keys

You are correct: if the AddRoundKey step is skipped, no key material is ever used, so decryption is trivial.

In case of using a bitwise OR, information would be lost in the encryption process. XOR is reversible, but OR isn't, so no decryption would be possible.


Is triple-CRC-32 a bad (or not) idea for generating a uniform distribution hash?

The identity function is also a bijection. That doesn't make it a good hash in any way.
If a function reduces input size, how can it be a bijection?
If you are not intending anything secure maybe this is the wrong place to ask. ;)
Maybe a more useful answer is this.


Proving security for Secure Multiparty Computation with malicious adversaries

I would like to provide a short answer, please see Lindell's tutorial for a comprehensive explanation.

As with the semi-honest model, the simulator in the malicious model also needs to simulate the real-world protocol execution (where some parties are controlled by an adversary). The simulator has access to the ideal functionality and an adversary (which is assumed to exist when constructing the simulator). The simulator can treat the adversary as a black-box algorithm and control its inputs and randomness tape. So, the simulator can rewind the adversary back to a particular step (where it needs some input to continue) and then feed it with a different input. However, simulation in the malicious model is much harder than that in the semi-honest model, mainly because we do not know what inputs the adversary is actually using even if we know what inputs are given to them.


Downsides of not using deterministic ECDSA signatures for blockchain validation?

No, you'll be fine (most likely).

DSA (the base of ECDSA) has been around since at least 1993 (when FIPS 186 was released). Much like with ECDSA you also need a $k$-value for DSA for each signature. From what I know, RFC 6979 (August 2014, first draft in march 2011) was the first general standard and Ed25519 (special case of EdDSA now, september 2011 (PDF)) the first specific DSA variant to use deterministic $k$-generation. So essentially people used random $k$ values for nearly 20 years and issues came up only when people failed to ensure the randomness of the value (by re-using it or using a bad RNG). However this does not apply to you as your HSM will take care of that. So you'll be just as fine as all the people were before we had deterministic (EC)DSA.

The only drawbacks are essentially those that you listed in your question, the first two of which don't matter if you trust your HSM and the last one you can't do anything about.

Also note that a deterministic (EC)DSA signature is indistinguishable from a non-deterministic one except if you have two signatures of the same data.


Dividing a secret into multiple nodes in a blockchain kind of system with time-release?

I understand what you are thinking, but you are mixing concepts. Just try to put the public parts of your schema at the blockchain... For instance, if you want to implement a PKI scheme without central authority (CA), you could by placing the public certificate at the blockchain. That way by being at the blockchain it is "compliant" with the decentralized CA...


I heard that when it comes to Encrypt-then-MAC, if an attacker forges the ciphertext then he gets the wrong MAC value and can't decrypt the ciphertext to plaintext.

Indeed, a forged ciphertext would immediately imply a forge on the MAC used therefore if the MAC is secure, the system is unforgeable.

  If so, what is happening Encrypt-and-MAC and MAC-then-Encrypt?

They both also achieve authenticated encyption if done properly (that is if "tidiness" is achieved and you treat the nonce explicitly). However in the other cases there is a simple counter-example to these constructions' AE security: Namely pick a CPA-secure encryption scheme and append an unchecked random bit. Now for the attack, simply flip that bit and you get a "different" ciphertext which the decryption oracle will happily decrypt.

  Do I have to bind the associated data to the ciphertext?

No, you don't have to bind associated data to the ciphertext. However, if there's context that needs to be sent publicly (such as routing information) or that is known by both parties and important to the state of the protocol (such as the current packet index), using associated data is a neat mechanism to conveying the correctness of the current state.

  So, is the attacker attacking without knowing both key and nonce?

No, it's usually assumed that the adversary can see and change the nonce if they want to (which is why it must be MAC'ed as well). Also in common security definitions the adversary has access to a pre-keyed encryption / decryption function so they have some sort of "access to the key" though not directly.


Quadratic Sieve: what's the next step after it fails?

In the QS algorithm, every linear combination adding up to a zero vector modulo $2$ has a chance of $1/2$ to give you a nontrivial factor.

Your suggestion 2) is the way to go, because adding additional numbers provides you with a lot more different linear combinations to get that zero-vector ($\phi(b)+1$ is just the minimal number required to find at least one set of linear dependent vectors).


Yes the multiplexing generator due to Jennings, and more advanced versions have been broken. I am assuming regular synchronous clocking of all 3 LFSRs in this answer.

The attacks mentioned are either correlation attacks or linear consistency attacks or a combination of the two. A reference which also cites earlier work is

Optimal correlation attack on the multiplexer generator, Jovan Dj. Golic, Guglielmo Morgari, Information Processing Letters 109 (2009):838–841.


Are AES-256's related-key weaknesses exploitable if it is used to build a hash?

The most efficient related-key attacks on AES-256 and resulting weaknesses AES-256-based hash functions are summarized in my PhD thesis. Though collision and preimage attacks on hash functions are out of reach yet, the components of these functions still expose some properties that are not expected of good hash functions or random oracles.

Getting to the details, the key schedule of AES-256 allows for numerous related-key differential trails with the most probable one covering as few as 19 S-boxes (page 96) and probability $2^{-119}$. By playing with the first rounds of this trail, one can get various properties of the AES-256-based compression function
$$
F(IV,M) = AES_{M}(IV)\oplus IV
$$ holding with rather high probability.

For example, one can fix values $\Delta I$ and $\Delta M$ and produce a number of pseudo-collisions $\{(IV_i,M_i)\}$ such that  for all $i$:
$$
F(IV_i,M_i) = F(IV_i\oplus \Delta I, M_i\oplus \Delta M).
$$

It can be proved that constructing $q$ such pseudo-collisions with the same $(\Delta I,\Delta M)$ requires almost $2^{n}$ work when $q>2$, whereas for AES-256 in the Davies-Meyer mode the complexity is about  $q\cdot 2^{67}$.

Though this is not a direct threat to the full hash function, a malicious designer may select an IV to maximize the differential properties of the first round. Among nothing-up-my-sleeve values there must be some that allow for higher-probability differential trails.


Is it correct that when creating encryption keys you take one large prime number multiple it by another prime number to leave you with a even larger prime number?

Any number that is a multiple of two primes is by definition not prime. This creates a semiprime: a number that has only two prime factors.

This approach is only used in a few cryptosystems, the most common of which is RSA. Many other cryptosystems exist that do not rely on integer factorization. Some of these systems (e.g., AES, ChaCha20) are symmetric algorithms unlike RSA, and some (e.g., ECC) are asymmetric like RSA. RSA is gradually being phased out in favor of modern systems based on elliptic curves.

  If 1 is correct, then is it correct to say "the reason for the large prime number calculation is it is very difficult and time consuming to work out what the initial prime numbers were used in the original calculation"?

Yes. As far as we know, integer factorization is a hard problem.

  What constitutes as a large prime number?

2048-bit RSA is a typical current recommendation. In this case, the modulus (e.g., the semiprime) is the part that is 2048 bits, so each prime is roughly 1024 bits long. For scale, a 1024-bit prime will be over 150 decimal digits long, so they are quite large.


Key exchange if forward secrecy is not an issue

No, because Bob cannot know for sure who send the public key in the first place. So impersonation may still be an issue, even if man-in-the-middle attacks are not possible.

If the communication is over a channel that can only be eavesdropped by Eve (i.e. Even cannot send anything to Bob within Bob knowing it is not from Alice), then this is secure. But that's a rather strong requirement.

In general, this is solved by a Public Key Infrastructure (PKI). The most well known one is the PKI based on X509 certificates used by internet browsers, which uses certificate authorities and browser organizations as trusted third parties as well as DNS to establish trust.


How did the cryptographers of Bletchley Park figure out the chi stream of the Lorenz cipher?

The answer can be found here:

The initial function of Colossus was to help determine the starting
point of the wheels. Colossus read the cipher’s stream of characters
and counted the frequency of each character. Cryptographers then
compared the results to the frequency of letter distribution in the
German language and to a sample chi-wheel combination, continually
refining the chi-wheel settings until they found the optimal one.

The setting that gave the highest count of •s was found to be optimal (F. Carter, Codebreaking with the Colossus Computer, 2008, pp. 16-17).
They understood the settings of the wheels because of the extraordinary work of William Thomas Tutte, OC FRS FRSC. From Wikipedia:

At Bletchley Park, mark impulses were signified by x and space
impulses by •. For example, the letter "H" would be coded as
••x•x. Tutte's derivation of the chi and psi components was made
possible by the fact that dots were more likely than not to be
followed by dots, and crosses more likely than not to be followed by
crosses. This was a product of a weakness in the German key setting,
which they later eliminated. Once Tutte had made this breakthrough,
the rest of the Research Section joined in to study the other
impulses, and it was established that the five chi wheels all advanced
with each new character and that the five psi wheels all moved
together under the control of two mu or "motor" wheels. Over the
following two months, Tutte and other members of the Research Section
worked out the complete logical structure of the machine, with its set
of wheels bearing cams that could either be in a position (raised)
that added x to the stream of key characters, or in the alternative
position that added in •.


where does the prime number taken in DH algorithm in IPSEC

It's in the SA payload of the initial packets.

It's attribute type 4 within the SA payload; in Main Mode of IKE (which is what you're looking at) the initiator will propose a list of groups, and the responder will pick one and send it back its selection in packet 2.

Now, what they exchange is a short integer value; both sides are expected to know the translation between the short values (current standard values are between 1 and 30) and the actual DH (or ECDH) group.  See this page for pointers to the definitions of the current standard groups.


Is this transposition cipher information-theoretically secure for 1 message?

For a scheme to be information-theoretically secure, you need that $$\Pr[M=m\mid C=c]=\Pr[M=m\mid C=c^\prime]$$ for all $c,c^\prime$ (that is, any ciphertext has the same probability $M=m$, so the ciphertext doesn't change the probability $M=m$).

Let's suppose we have a $c$ and a $c^\prime$. Both of them have the same number of ones and zeroes, because both are half ones and half zeroes. That means there's a permutation that takes $c$ to $c^\prime$ (in fact, there are a lot of them, but pick one); call it $\sigma$. We want to show that the number of permutations taking $c$ to some $t_0$ is the same as the number taking $c^\prime$ to $t_0$.

We can convert a permutation $\pi$ taking $c$ to $t_0$ into a permutation $\pi\sigma^{-1}$ taking $c^\prime$ to $t_0$: $\pi\sigma^{-1}(c^\prime)=\pi(c)=t_0$. Likewise, if $\pi^\prime$ takes $c^\prime$ to $t_0$, then $\pi^\prime\sigma$ takes $c$ to $t_0$. Also, $\pi\sigma\sigma^{-1}=\pi\sigma^{-1}\sigma=\pi$, so the functions are inverses. So, there are exactly the same number of permutations taking $c$ to $t_0$ as taking $c^\prime$ to $t_0$, so $$\Pr[T=t_0\mid C=c]=\Pr[T=t_0\mid C=c^\prime]$$ for all $c,c^\prime,t_0$.

Lastly, we know that $\Pr[M=m]$ is the sum of the probability that $T=t$ for all $t$ which have $m$ as their first half. Since all these probabilities are independent of the ciphertext, so is $\Pr[M=m]$. This applies whether or not you consider that $\Pr[T=t]$ is zero if $t$'s first half and second half aren't bitwise inverses; no matter what, it doesn't depend on the ciphertext, and neither does $\Pr[M=m]$. So, this scheme is information-theoretically secure.


To quote the paper

  Two probability ensembles... are said to be computationally indistinguishable, denoted $X\stackrel{c}{\equiv}Y$, if...

This is found in section 2.


Questions about the double ratchet mechanism in Signal

An eavesdropper who briefly compromises one of the parties might learn the value of a current ratchet private key, but that private key will eventually be replaced with an uncompromised one. At that point, the Diffie-Hellman calculation between ratchet key pairs will define a DH output unknown to the attacker.

This brief compromise is a of the current ratchet private key, one of the keys which I believe are called 'medium-term' in the DH paper (or at least in this security analysis. This means that the compromised key is only able to decrypt the current message, or messages in the current session before the key is ratcheted forward.

This is part of how signal provides both forward and future secrecy - the medium-term key for this session cannot decrypt any past messages, and as soon as the key is refreshed it won't be able to decrypt any future messages.

  If the user is compromised at time T during a communication, isn't it true that the device is considered compromised for all time > T? If so why is the above assertion in the paper good?

This would be true if the long-term key was compromised as well as a medium term key, but in fact signal protocol also uses ephemeral public keys which are stored on the signal servers and also replaced every so often, meaning that theoretically even if a session's medium term and ephemeral private keys were compromised, future sessions would still be secure.

didn't go into too much detail but can dig into the paper and explain a bit more if you would like. Does this help?


How can a key pair be derived from an arbitrary hash?

Bitcoin doesn't use RSA, it uses ECDSA. Every 256-bit value is a valid private key. (Though a very small fraction of them have to be folded.)

But even if the numbers had to be special, it still wouldn't matter. You could use every 256-bit value as a seed to a pseudo-random number generator which you could use to deterministically generate numbers that had whatever properties you need.

You can also trivially create schemes to generate numbers that do have needed properties from passphrases. For example, Ripple uses a scheme like the following:

Set a counter to zero.
Hash the passphrase together with the counter.
Does the hash have the needed properties? If so, stop. We're done.
Increment the counter.
Go to step 2.


what motivated the design decisions of RFC 8291 ("Message Encryption for Web Push")?

Although it is not forward secure against client-side compromise (i.e. disclosure of the user agent's long term private key), it is forward secure against server-side compromise (i.e. disclosure of all information available to the server).
Thus, for example, if ownership of the application server is transferred from one company to another and the user's trust relationship with the new company is not as strong as the old company, the user still has assurance that their old messages are not compromised.
Bidirectional forward security would seem to be preferable, but the the offline encryption implications of push messaging make this a constraint that is hard to achieve.


Is using the same IV in AES similar to not using an IV in the first place?

Lets see if I can clarify things for you.

For one, the IV is not specifically related to AES at all.  AES is a keyed invertible transform from a 128 bit value to a 128 bit value; that's all it can do.  Now, if you just happen to have a 128 bit value that you want 'encrypted' into a 128 bit ciphertext, well, you can just use AES as is.

However, we typically want to other things than that; we may have plaintexts which aren't exactly 128 bits long; we might want nondeterministic encryption (so that if we encrypt the same value twice, it's not obvious that we did so); we might want integrity checking on our ciphertext as well.

To allow us to do those things, we use a Mode of Operation; that's a construction that uses AES (or some other block cipher) to perform these more generally useful operations.  It is these modes of operation which may (not all do) take an IV.

At the moment, the most popular modes of operation are CBC and GCM; they also have very different requirements to their IVs.

So, in that context, I'll answer your questions:

  I'm supposed to generate a different IV for every msg because using only a key I will get the same encryption if the message was encrypted twice

That's not the complete story; yes, if you use the same IV, same message and same key (and same AAD for GCM), you'll get the same ciphertext, but that's not the full reason.

For CBC, if you use the same IV, there are two potential problems; one is that you'll leak how the two plaintexts are related.  For example, if the two plaintexts have the same first 16 bytes, and differ in the second 16 bytes, that'll be obvious to the attacker.  The other is that if the attacker can predict the IV (which he can if you use the same one repeatedly), and if he can introduce his own plaintext (which can happen in some scenarios), then he can use the encryption operation as an oracle (and thus deduce the value of low entropy plaintext blocks encrypted by the same key).

For GCM, if you use the same IV, there are two different potential problems (both of which are far more serious); for one, he can deduce the bit-wise xor of the two plaintexts (which is often enough for him to deduce those plaintexts).  Worse, it allows the attacker to deduce the internal authentication value, and thus allow him to modify ciphertexts (and thus the resulting plaintexts) without being detected.

  Now my question, is using the same IV for all of my messages is the same of not using IV at all? Or is it slightly better?

Well, for neither mode, you don't have an option of 'not using an IV'; when you perform a CBC or GCM operation, an IV must be there (for GCM, you can have a zero length IV; that's not quite the same as 'not having an IV').

And, you didn't ask, but I'll state the general wisdom anyways:

For CBC mode, the IV really ought to be unpredictable to the adversary.  Now, you can pick it randomly each time, or you can use (say) an AES encryption operation with the same key to generate it (which the attacker can't predict, as he doesn't have the key); both works.
For GCM mode, it doesn't matter in the least whether the IV is predictable to the adversary.  What's critical is that you use a different one each time.  If you can manage a counter (e.g. if you restart the program, you'll pick a fresh key), then using IV=0 for your first message, IV=1 for your second, etc, is the obvious approach.


State recovery of Micalli-Schnorr random number generator modulo a prime

EDIT: The answer below answers the RSA modulus case…

There is some related discussion in the answers to the Crypto.SE question “Why is the following RSA PRNG cryptographically secure?”.

Edit: As pointed out in comments, this answer is about the zRSA
The consensus among the answers seems to be that the required security assumption is too strong (strong RSA assumption) and the generator is too slow for practical use.

Here is a paper "On the Provable Security of an Efficient RSA-Based Pseudorandom Generator" by Steinfeld et. al. on this generator.

Let $N$ be the RSA modulus involved, $e$ the RSA public exponent, and $k$ the number of MSB bits taken from the generator at each iteration.

Basically  the authors suggest that under the strong RSA assumption it is possible to extract $$k= ((1/2)-(1/e))\log N$$  bits per iteration, without affecting the security.

And there is more recent work, behind a Springer paywall (see preprint here) "Time/Memory/Data Tradeoffs for Variants of the RSA Problem" by Fouque et. al. LNCS vol. 7936,
proposing Time/Memory/Data attacks on the generator, which for practical choices of the parameters is of course not a feasible attack. This latter paper also cites a paper by Hermann and May from ASIACRYPT 2009 in the introduction, where it has apparently been shown that if $$k\geq (1-(1/e))\log N$$ bits are extracted per iteration, the generator can be broken.


Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$

Okay, I came up with this, it's not a complete answer and the attack presented is pretty weak without a follow-up algorithm for breaking a somewhat unbalanced modulus but let me know if you spot any flaws or have any ideas to improve it...

If $n = pq$ with $p, q$ prime and $\gcd(pq, (p - 1)(q - 1)) = r > 1$ then clearly $r = p$ or $r = q$. Now obviously $q - 1$ cannot divide $p$ and so we must have $p$ divides $q - 1$, without loss of generality. Thus:
$$q - 1 = kp ~ ~ ~ \text{for some} ~ k > 1$$
Now suppose that $k$ is $B$-powersmooth for small $B$, then we have $M = \alpha k$ for $M$ a suitable product of prime powers up to $B$, some $\alpha$ and so for any $a$ we have:
$$a^{Mn} \equiv a^{Mpq} \equiv a^{(\alpha k p)q} \equiv a^{\alpha(q - 1)q} \equiv 1 \pmod{q}$$
And so in general we find that:
$$\gcd(a^{Mn} - 1, n) = q$$
Therefore in order for $n$ to be usable in the context of RSA, $k$ should not be smooth. Realistically we will be able to try $B$ up to $2^{80}$ or so (you won't be factoring the 2048-bit modulus through general purpose algorithms anyway) which means $k \approx 2^{81}$ and a special key generation technique needs to be used, probably involving letting $2rp = q - 1$ for large prime $r$ with $k = 2r$.

And since $k$ is large, that means $q/p \approx 2^{81}$ so the modulus is unbalanced. Perhaps this enables polynomial-time factorization of the 2048-bit modulus via existing methods which rely on particularly poor selection of $p$ and $q$, or perhaps the scheme is secure with careful selection of $k$. Further work is needed to determine which conclusion is the right one (but I am less and less confident in this scheme).


Hints:

For (a), suppose you had a collision with $\hat{H}$; how could you use that to demonstrate a collision with $H$?  What does that imply?

For (b), could you construct a collision with $\hat{H}$, that is, find two different messages $x_1||x_2$ and $x'_1||x'_2$ with $\hat{H}(x_1||x_2) = \hat{H}(x'_1||x'_2)$?


Why to try get key out of white box crypto? How can one protect WBC itself?

This is an excellent question.  Unfortunately, I'm afraid I don't know of any really convincing answer.

In principle, one possible application of white-box cryptography would be to build a public-key cipher out of a symmetric-key cipher.  If you could build a white-box cryptographic implementation of AES encryption (say) where no one can recover the key nor figure out how to perform the decryption process, you'd have a public-key cipher.

However in practice I don't think that's actually the motivation for most work on white-box cryptography.  For instance, most published white-box crypto schemes can be easily inverted: given a white-box implementation of encryption, you can easily derive a white-box implementation of decryption.  Most published schemes focus on preventing you from recovering the key, instead of preventing you from figuring out how to perform the decryption process.  So, building a public-key cipher does not appear to be their motivation.

I don't know any really good answer to your question.  I know of two not-very-good answers:

One possible answer is that the code of the white-box cipher might be a lot larger than the key, and if a cracker wants to share it with others, they'll have to spend a lot more bandwidth sharing it than they would sharing the key.  However, this seems very weak and unconvincing.
Another possible answer is that white-box encodings are usually randomized: you can give a million people a randomized white-box implementation of AES decryption under key $K$ (the same key for everyone, but they each get a separately randomized white-box implementation).  Thus, if someone shares the code of their white-box decryptor, it uniquely identifies them.  However, in practice, this doesn't seem like a very effective defense against copyright infringement (prosecution is usually too expensive, and false identity too easy to forge).

So, I'm afraid I don't know of a strong practical motivation for white-box crypto.  Maybe someone else will have a better answer for you.


ECCDSA-keys can be merged such that the sum of two private keys $S=S_1+S_2$ yields a public key which is the sum of the respective public keys $P=P_1+P_2$.

This is true, however it doesn't mean what you think it means; the $+$ operators in the two equations are two different operations.
The first one is simple addition (modulo the order of the elliptic curve group).  However, the second is elliptic curve addition, which is not at all addition modulo some number.

Thus, given a key pair it is trivial to construct all public keys that are integer multiples of that public key $P_n \equiv n\cdot P \pmod N$.

Nope; one can certainly compute $P_n = n \cdot P$, where $\cdot$ is elliptic curve multiplication, that is, short hand for $n$ copies of the point $P$ added together, however the actual values of $P_n$ are 'unpredictable' in the sense that, if you have a target point $Q$, it is a hard problem to find an $n$ such that $Q = P_n = n \cdot P$ (or rather, we hope that's a hard problem; if it isn't, all elliptic curve cryptography falls apart).

Does this mean there is a skeleton key with public key $1$ that could derive all keys?

No, or at least, we hope not.  If there is an elliptic curve point $1$ for which solving $Q = n \cdot 1$ was an easy problem, at least solvable a nontrivial part of the time (and not easy in the sense that "it hardly ever exists"), then again, all elliptic curve cryptography falls apart (and we don't need to know the private key corresponding to $1$).

Of course since it is infeasible to obtain the secret key to any given public key that's probably pure theory, but one worth much more to invest in than a single specific target...

Actually, it can be proven that the problem "given this large number $k$ of public keys, find one public key (and we don't care which one)" is not anymore difficult (that is, no more than an addition $O(k)$ work effort) then the problem "given this public key, find the private key".


In ECC, how do I prove that point addition is commutative?


Find hash and signature algorithms used in an X.509 certificate signed with RSASSA-PSS

The ASN.1 module

The OID of RSASSA-PSS is specified as below, however, it should only be used as part of an AlgorithmIdentifier, which is a SEQUENCE of the OID, followed by the parameters. These parameters are NULL for PKCS#1 v1.5 signatures, but for PSS they must be present

Here is the OID:

   --
   -- When id-RSASSA-PSS is used in an AlgorithmIdentifier, the
   -- parameters MUST be present and MUST be RSASSA-PSS-params.
   --
   id-RSASSA-PSS    OBJECT IDENTIFIER ::= { pkcs-1 10 }

and here are the configuration parameters of the algorithm:

   -- AlgorithmIdentifier.parameters for id-RSASSA-PSS.
   -- Note that the tags in this Sequence are explicit.
   --
   RSASSA-PSS-params ::= SEQUENCE {
       hashAlgorithm      [0] HashAlgorithm      DEFAULT sha1,
       maskGenAlgorithm   [1] MaskGenAlgorithm   DEFAULT mgf1SHA1,
       saltLength         [2] INTEGER            DEFAULT 20,
       trailerField       [3] TrailerField       DEFAULT trailerFieldBC
   }

where the hashAlgorithm defines the hash over the data, just like for PKCS#1 v1.5 signatures specify a hash over the data within the message.

However, we still have an undefined maskGenAlgorithm of the type with the same name:

   MaskGenAlgorithm ::= AlgorithmIdentifier { {PKCS1MGFAlgorithms} }

... that's not very helpful, so lets dive deeper:

   --
   -- Allowed mask generation function algorithms.
   -- If the identifier is id-mgf1, the parameters are a HashAlgorithm.
   --
   PKCS1MGFAlgorithms    ALGORITHM-IDENTIFIER ::= {
       { OID id-mgf1 PARAMETERS HashAlgorithm },
       ...  -- Allows for future expansion --
   }

ah, another hash function is defined here for use with the only defined Mask Generation Function, MGF1.

This - possibly different - hash function is used within MGF1 and therefore within PSS to provide the security required for MGF1.

Finally, a boring little constant for trailerField, so that we're complete:

   TrailerField ::= INTEGER { trailerFieldBC(1) }

Conclusion

OK, let's recapitulate: the signing algorithm is of course PSS, which depends on a mask generation function MGF1 as only option and a hash over the message. The MGF1 however also has a hash function algorithm assigned to it. Furthermore, you also can indicate a salt length - defaulting to 20 bytes - and a trailer field which currently just has one option.

Library design options

This message hash defaults to SHA-1, which is not secure for signing data. It also depends on a separate hash function used for MGF1, which also defaults to SHA-1. However, for MGF1 the hash function is actually secure. This unfortunately leads to different options for library designers:

specify one hash, and let this be the hash for both the message and the MGF1;
specify one hash, and let this be the message hash for just the message and keep MGF1 to use SHA-1;
always let the user specify both hashes, ignoring the fact that there is a default hash.

Commonly unfortunately either option 1 or option 2 is taken, leaving the developer guessing what hash is used for MGF1.

Encodings

OK, that was harder than it should be; let instead look at some options for encodings, using the online Lapo ASN.1 parser to decode the manually generated bytes.

First the one specified in the comments of the ASN.1 module within the standard:

   30 0D
      06 09 2A 86 48 86 F7 0D 01 01 0A
      30 00

which parses to:

   SEQUENCE (2 elem)
      OBJECT IDENTIFIER 1.2.840.113549.1.1.10 rsaPSS (PKCS #1)
      SEQUENCE (0 elem)

that's shorter then you'd expect. That's because the PSS parameters consist of a zero element sequence. This may sound weird, but it simply means that the default values are used, i.e. sha1, mgf1SHA1, a saltLength of 20 bytes and of course the only possible trailerField identifier, set to 1.

You can also specify the exact same structure without default values:

  30 3E
     06 09 2A 86 48  86 F7 0D 01 01 0A
     30 31
        A0 0B
           30 09
              06 05 2B 0E 03 02 1A
              05 00
        A1 18
           30 16
              06 09 2A 86 48 86 F7 0D 01 01 08
              30 09
                 06 05 2B 0E 03 02 1A
                 05 00
        A2 03
           02 01 14
        A3 03
           02 01 01

so this explicit encoding shows the actual structure. In above structure it is easy to replace the default parameters by different ones.

  SEQUENCE (2 elem)
    OBJECT IDENTIFIER 1.2.840.113549.1.1.10 rsaPSS (PKCS #1)
    SEQUENCE (4 elem)
      [0] (1 elem)
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 1.3.14.3.2.26 sha1 (OIW)
          NULL
      [1] (1 elem)
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 1.2.840.113549.1.1.8 pkcs1-MGF (PKCS #1)
          SEQUENCE (2 elem)
            OBJECT IDENTIFIER 1.3.14.3.2.26 sha1 (OIW)
            NULL
      [2] (1 elem)
        INTEGER 20
      [3] (1 elem)
        INTEGER 1

WARNING: beware that if a value has a default, and if the default value is being used then DER encoding specifies that it MUST NOT be encoded. So above is valid BER but not valid DER.

X.509 specifies that the signature field (of type AlgorithmIdentifier is in the TBSCertificate data (TBS means "to be signed", the data that is used in the signature calculation). The TBSCertificate data MUST be DER encoded. So above is not valid in a certificate.

Of course, as the numbering of SEQUENCE with defaults is explicit, generally it would be more logical to just specify the [0] and [1] parameters (tag encoding A0 and A1and leave the rest to the default).

So I would expect API's to generate e.g.:

  30 1E
     06 09 2A 86 48  86 F7 0D 01 01 0A
     30 11
        A0 0F
           30 0D
              06 09 60 86 48 01 65 03 04 02 01
              05 00

which parses as:

  SEQUENCE (2 elem)
    OBJECT IDENTIFIER 1.2.840.113549.1.1.10 rsaPSS (PKCS #1)
    SEQUENCE (1 elem)
      [0] (1 elem)
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 2.16.840.1.101.3.4.2.1 sha-256 (NIST Algorithm)
          NULL

for SHA-256 as message hash and the default SHA-1 as MGF1 hash; the rest is set to the default values as well.

And, for the ones that uses the same SHA-256 hash for the message and MGF1:

  30 3C
     06 09 2A 86 48  86 F7 0D 01 01 0A
     30 2F
        A0 0F
           30 0D
              06 09 60 86 48 01 65 03 04 02 01
              05 00
        A1 1C
           30 1A
              06 09 2A 86 48 86 F7 0D 01 01 08
              30 0D
                 06 09 60 86 48 01 65 03 04 02 01
                 05 00

which parses as:

SEQUENCE (2 elem)
  OBJECT IDENTIFIER 1.2.840.113549.1.1.10 rsaPSS (PKCS #1)
  SEQUENCE (2 elem)
    [0] (1 elem)
      SEQUENCE (2 elem)
        OBJECT IDENTIFIER 2.16.840.1.101.3.4.2.1 sha-256 (NIST Algorithm)
        NULL
    [1] (1 elem)
      SEQUENCE (2 elem)
        OBJECT IDENTIFIER 1.2.840.113549.1.1.8 pkcs1-MGF (PKCS #1)
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 2.16.840.1.101.3.4.2.1 sha-256 (NIST Algorithm)
          NULL

this just leaves the salt and trailer field to the default.

Lamentation on default values

It might not come as a surprise that I'm not a fan of default values. They complicate the hell out of structures like this, and once you've chosen a default, such as SHA-1, it is pretty likely that you'll get into trouble as well, as SHA-1 should be considered broken by now. So we now have a provable secure padding mechanism that defaults to an insecure hash.

A slightly larger algorithm identifier that can be canonically encoded (i.e. has just one representation in bytes) and explicitly specifies the algorithms should have been preferred over the ASN.1 hell it is now. As stated above, the DER encoding requires to leave out values if they are identical to the default one.


You could check, if $e\cdot d\equiv 1 (\bmod z)$. [1] Since your $z=\phi(n)$ and you want to do something like $(m^e)^d \bmod n= m^{ed} \bmod n \overset{!}{\equiv} m$. Therefore, $ed\equiv 1 (\bmod z)$

For decryption check cryptool. [2]

[1] https://en.wikipedia.org/wiki/Fermat%27s_little_theorem#Generalizations
[2] https://www.cryptool.org/


Public key cryptography lets the ransomware encrypt files so that only the malware author (who has the private key) can decrypt them or supply the needed per infection key.
Payment in Bitcoins is traceable, since all Bitcoin transactions are public. If the attacker transferred their Bitcoins to an exchange directly and converted them to a conventional currency, law enforcement could demand the records and find their identity. Mixing services allow the attacker to mix their coins together with lots of other legitimate coins, hiding where they end up. Mixing services exist and are only getting better.
The decryption for Bitcoins service can be hosted as a TOR hidden service. The attacker can set up a server that watches the bitcoin blockchain for bitcoin payments and provides one decryption key per payment. There is no link between the attacker and the servers except for the initial setup (which can be done through tor) and hosting fees (which can be paid in bitcoins).

All of these technologies are proven. It's just a matter of setting everything up and infecting victims. Until the general public learns to do better backups ransomware is here to stay.


McEliece parameter tuple (n, k, t) through BouncyCastles (m, t, poly)

The parameters are specified in the parameters object. You give them normally in the constructor: new McElieceCCA2Parameters(m, t, poly). I am however not sure how they map to the canonical parameters of the crypto system.

Javadoc: http://bouncycastle.org/docs/docs1.5on/org/bouncycastle/pqc/crypto/mceliece/McElieceCCA2Parameters.html


How can companies authenticate messages sent between different security components in the company?

Usually point-to-point transport security is used for this. The most well known protocol is of course TLS, but there is also SSH, IPsec etc. etc. TLS works directly between two computers (although intermediate machines may of course route the IP packets from one to the other, without decrypting).

For communication between computer systems you would generally need client and server authentication. A public key infrastructure based on certificates (PKIX) makes most sense for the entity authentication part.

In addition end-to-end application level security may be used. This is simply wrapping up each message in a container such as a CMS container or XML signing and encryption. This way the message may be protected from the intended sender to the intended receiver, regardless of the protocols and hubs in between. It also has the advantage that a message can be protected before being send or being received.

There are too many protocols to name here otherwise. You'll have to look them up yourself. There is - to my knowledge - no generally accepted protocol for communicating between a SIEM and IDS.


Modular Addition in RC5 is linear or not?

Consider $f: x\mapsto f(x)=\underbrace{x+x\ldots x}_{a\text{ times}}+b\bmod 2^{32}$ in the the ring $(\mathbb Z_{2^{32}},+,\times)$, where $a$ and $b$ are constants.
Per one meaning, $f$ is linear, that is of the form $x\mapsto a\times x+b$, for constants $a$ and $b$. Per another meaning, $f$ is not (in general) a linear boolean function. $f$ is also not linear in the field $(\mathbb F_{2^{32}},\oplus,\otimes)$, where $\otimes$ is polynomial multiplication modulo an irreducible polynomial of degree $32$.
To make «the rotations are the only non-linear operator in RC5» true, we can craft a meaning of «linear» that allows any of the above definitions.
Without rotations, RC5 would be trivially breakable no matter the number of rounds, for lack of propagation from high-order to low-order bits of the four 32-bit sub-blocks.
It's harder to prove the (true) assertion that with only fixed rotations, and baring much more rounds, RC5 would be breakable. That's because it would be too linear, in some sense that I fail to exactly define.


Are the taps placed correctly on the above figure?

No. That's acknowledged in the errata to the second edition, on the section for page 375 (AFAIK the 20th anniversary edition is essentially the second edition with a little extra at the beginning).
My preferred method to determine the hardware implementation for a Fibonacci LFSR from the polynomial:

Use a shift register with as many bits as the degree of the polynomial.
Number shift register state bits (the output of the internal D gates) from $0$ for the output, to $n-1$; with thus $n$ the input of the shift register.
XOR the bits $i$ from $0$ to $n-1$ of the shift register that has their term $x^i$ present in the polynomial¹ ($x^0$ is the term $1$ of the polynomial).
For an LFSR in scrambler configuration, additionally XOR the input of the scrambler.
Feed the result of the XORs to the input of the shift register.

Depending on convention, the taps shown are for polynomial $x^{32}+x^{31}+x^6+x^4+x^2+x+1$ or it's reflected polynomial $x^{32}+x^{31}+x^{30}+x^{28}+x^{26}+x+1$. These are not primitive², and accordingly, the sequence for the LFSR shown is not maximal-length.
LFSRs and CRCs are an area where there are many errors in literature and implementations, and several justifiable conventions around, especially for Fibonacci LFSRs:

There is no universal agreement that the low-order coefficient of the polynomial is on the output of the LFSR. Using the other convention¹ causes a reflection in time of the order of the bits in the generated sequence, for the reflected initial state.
The most common convention for an isolated LFSR is that the output of the LFSR is the output of the shift register, so that the first bits to the output match the initial state of the shift register. But the common convention for LFSR-based scramblers is that the output is the input of the shift register, which reduces latency in telecom applications. That offsets the generated sequence.
There is no universal agreement on numbering bits of the shift register/initial state from output to input. This is best IMHO since it matches the order in which output bits appear, and people agree on numbering these incrementally with time.
There is no agreement on numbering shift register bits starting from 0 (as in the above method) or from 1 (as in the question's figure). The same issue for output bits in the generated sequence, and I've seen the conventions differ.

Lots of theoretical work, high-speed hardware, and software use Galois LFSRs. There's relative agreement that if their $n$-bit polynomial is $P(x)$, then their state $S(x)$ is a polynomial of degree (at most) $n-1$ with state bits numbered from $0$ to $n-1$ according to rank in $S$. The state changes from $S(x)$ to $x^k\,S(x)\bmod P(x)$ after $k$ steps. Good luck for the rest.
Galois LFSRs are easily implemented in hardware and software:
s = (s<<1)^(p&-(s>>(n-1)));   // Galois LFSR, assuming s an unsigned exactly n-bit
s = (s>>1)^(q&-(s&1));        // Galois LFSR, reflected, assuming s at least n-bit

Note: p is the polynomial evaluated without it's high-order term in $\mathbb Z$ for $x=2$. q is the polynomial reflected, then evaluated without it's high-order term in $\mathbb Z$ for $x=2$.
The output sequence of a Fibonacci LFSR with term $1$ present in it's polynomial matches that of a Galois LFSR with the reflected polynomial (using the conventions above), and an appropriate adaptation of the initial state (which depends on conventions about where the output sequence is extracted from).

¹ Another possibility is to XOR the bits $i$ that have their term $x^{(n-i)}$ present. That works only if the term $1=x^0$ is present in the polynomial, which is true for all polynomials used in practice, all irreducible polynomials, and thus all primitive polynomials (which are those generating a maximal-length sequence when starting from a non-zero initial state, and input at $0$ if in scrambler configuration). The sequence generated is generally not the same.
² Proof: every primitive polynomial is irreducible, and $x^{32}+x^{31}+x^6+x^4+x^2+x+1$ is not, since it's divisible by $x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^4+x^3+1$. A polynomial and its reflection have the same status w.r.t. primitiveness and irreducibility.


Does XChaCha20 exist with similar properties to XSalsa20?

Unfortunately, there is no specification for XChaCha20. But several implementations provide a HChaCha20 function, built the same way as HSalsa20.

XChaCha20 can be built with HChaCha20 + ChaCha20, and the security proof is similar to the one for XSalsa20.

The Libsodium documentation has a section on HChaCha20, which includes a code snippet to build XChaCha20 out of it.


Why do cryptographic hashes need to be fixed length?

They don't, and in fact the sponge construction used in Keccak (SHA-3) allows for variable length output.

In other hashes the Merkle-Damgård construction was used which has a fixed output length due to the nature of its design. But there is no reason to not allow for variable output length other than ease of development or use.


Safety of a private key when knowing the full content of an encrypted message in case of fixed initialization vector

What you're describing is called a known-plaintext attack, and any secure encryption algorithm should prevent this. If we take an encryption function with no IV $C = ENC(M, K)$ we should get a system where knowing both $M$ and $C$ reveals nothing about $K$.
We can expand this principal to $C = ENC(M \oplus IV, K)$ and simplify it back to the example without an IV; $M \oplus IV$ simply becomes our new $M$ (you could say $M' = M \oplus K$). This principal applies also for $C = ENC(M \oplus IV) \oplus IV$.
Any encryption algorithm which fails to achieve this property cannot be considered secure, and as such in your scheme $K$ will not be leaked if the encryption algorithm used is secure.
However, using a fixed IV is bad practice since it allows statistical analysis attacks (read about it here). While $K$ may not be leaked $M$ might leak from statistical patterns.


Supersingular Isogeny Key Exchange Software

The inventors of the Supersingular Isogeny Key Exchange, Defeo, Jao and Plut have posted some code on GITHUB at:

https://github.com/defeo/ss-isogeny-software/

There is also a paper on implementation of this key exchange by some people from the University of Waterloo.  Their paper is "Efficient Implementations of A Quantum-Resistant Key-Exchange Protocol on Embedded systems" and can be found:

http://cacr.uwaterloo.ca/techreports/2014/cacr2014-20.pdf

I would also like to note that while Lattice Based Cryptography (as suggested by the other answer) is more efficient than the Isogeny based key exchange it has not received significantly more analysis than the Isogeny based scheme.  In particular the work of Galbraith and Delfs from 2013 is an independent assessment of the difficulty of solving the underlying hard problem in the case of the Isogeny problem.

Many of the lattice schemes are designed and analyzed by the same small group of researchers who base their research on each others previous research.  Of course research on the Isogeny key exchange is not immune from that.  A more recent paper by Biasse and Jao on the difficulty of finding isogenies includes one of the inventors (Jao) as an author.  Nevertheless, the Isogeny key exchange builds on almost two decades of intense research on elliptic curves.  Until recently the only lattice based scheme under active scrutiny was NTRU and there the findings were historically problematic.  Of course if efficiency is what you need, the lattice based schemes are indeed superior to the Isogeny based key exchange.  I hope this helps.

You might want to write to Fishein, Jao, and Azarderakhsh to see if they posted their software anywhere.  They claim to have software that is significantly more officient that the original code.


I don't recommend inventing your own hashing algorithm unless if you are knowledgeable and careful. The available hashing functions are good SHA 3 was chosen based on an open competition, you may just use it.

I don't see a point of coming up with a new hash function.


Is it feasible to get a hash collision for CRC32, MD-5 and SHA-1 on one file?

Finding a simultaneous collision for all three would take the effort of approximately $2^{72}$ SHA-1 compression function evaluations.

The overall idea would be to take the general $2^{67}$ idea found in the answer to How hard is it to generate a simultaneous MD5 and SHA1 collision? and perform the attack 33 successive times (generating 33 places in the hash image where we can take either $X_i$ or $Y_i$ without affecting either the MD5 or SHA-1 hash).

That'll give us a total of $2^{33}$ images with all the same MD5 and SHA-1 hash; there must be a pair of images with the same CRC-32 value as well, and so that solves the problem.

Whether $2^{72}$ operations is in the realm of feasibility is another question entirely...


What is the most efficient 1-out-of-N Oblivious Transfer construction described in current literature?

It depends if you want many instances (like 1 million) of OT, or just a few.
For a small number of OTs, I would recommend looking at our very recent paper:

McQuoid, Rosulek, Roy: Minimal Symmetric PAKE and 1-out-of-N OT from Programmable-Once Public Functions, CCS 2020.

We're not aware of other protocols whose communication is independent of $N$.
For a large number of OTs, you would use some kind of OT extension approach. The leading OT extension protocol for 1-out-of-N is:

Orrù, Orsini, Scholl: Actively Secure 1-out-of-N OT Extension with Application to Private Set Intersection, CT-RSA 2017.


Is it possible to recover the seed used by Python's pseudo-random number generator?

I have the first 40 numbers of the sequence. Is there a way to recover the seed or find the next 460 numbers in the sequence?

The first thing to know is that Python's random module uses Mersenne Twister as the PRNG. That is not a cryptographically secure RNG, in fact it is easy to recover the state as long as you have enough samples.

40 numbers of the sizes you use is not sufficient to recover the full MT state and find the next outputs that way.

It is more than enough to recover a time seed as Python uses when OS randomness is not available. You can just run a brute force of time values in the recent past. Latest versions of Python 2/3, however, initialize the full state from urandom or similar where available, and that cannot be inverted with this little output.

(Of course you can still call random.get_state() but presumably you were not asking that ;)


Private key not used in a signature scheme

Compute $v^e \equiv a^m b^s c \pmod n$. Output $(e,s,v)$.

This should perhaps read:

Solve $v^e \equiv a^m b^s c \pmod n$ for $v$.  Output $(e,s,v)$.

If you can solve $v^e \equiv u \pmod n$ for $v$ without using $p$ in general, you have found a major breakthrough in cryptanalysis!


How does the 'Flatten' function reduce the coefficients of a vector/matrix?

When all the entries of $a$ are binaries, then yes, $Flatten(a) = a$, because $BitDecomp^{-1}(a)$ will give a $k$-dimensional vector whose entries are decomposed back to $\ell$ consecutive entries of $a$ (by $BitDecomp$).

However, when $a$ has non-binaries entries, this is not the case.

For instance, for $\ell = 3$ and $k = 2$, we would have $N = 6$. Then, consider $a = (0, 3, 0, 0, 0, 1)$.

Then, $BitDecomp^{-1}(a) = (3\cdot 2, 1\cdot 4) = (6, 4)$, and $BitDecomp(6, 4) = (0, 1, 1, 0, 0, 1)$.

Notice that for the last block of $a$ (last $\ell$ entries), $Flatten$ worked as the identity, because this block was binary.


This is largely a reasonable strategy given the tools at hand.  The salt need only be 16 bytes to thwart multi-target attacks, though using a 32-byte salt doesn't hurt.  You will presumably want to store the secret and the salt separately, so that it requires both of them to confirm a guess about the password; otherwise there's no sense in having a separate secret.

Rather than use PBKDF2-HMAC-SHA512 with exactly 100 000 iterations, you should estimate how long you are willing to wait on the slowest device you care about, and use as many iterations as that device can compute in that time.  Even better, if you have a large memory available and access to scrypt or argon2, you should use one of those to exploit the memory available in order to raise the attacker's costs in a different dimension.

The more time you spend, the more joules of energy the attacker must spend to try each guess.  But the attacker can try guesses in parallel.  The more memory you spend, the more die area the attacker must spend on memory instead of parallelism.

N.B.: This is only about the cryptography.  I am not commenting on the quality of your JavaScript code; there is CodeReview.SE for code reviews.


In Elgamal, the generator g is always quadratic non-residue modulo p where p is a safe prime and inverse of g can be also generator?

Ok, I assume that you speak of ElGamal working in $Z_p^*$ and you mean that $g$ is a quadratic residue modulo $p$.

The problem with ElGamal, when taking some arbitrary prime $p$ is that you cannot achieve IND-CPA security.

Recall, in the IND-CPA security game, the adversary chooses two messages $m_0$ and $m_1$, obtains the ciphertext of $m_b$, where $b$ is the result of a coin flip, and has to guess with non negligible probability better than $1/2$ which message has been encrypted.

The problem is that you can use the Legendre symbol to efficiently decide quadratic residuosity modulo $p$. Now, if an attacker chooses one message to be a quadratic residue and one to be a non-residue, then the adversary with the knowledge of the quadratic residuosity of $g$ has non negligible advantage to guess the correct message (I guess this is homework so I do not discuss this in details).

If choosing $p$ to be a safe prime of the form $p=2q+1$ where $q$ is also prime, then the order $q$ subgroup of $Z_p^*$ represents the cyclic subgroup of quadratic residues (this is not hard to see). Then, if you choose $g$ to be a generator of this subgroup and restrict the message space to be quadratic residues, for obvious reasons, you achieve IND-CPA security.

Now, to your last point (inverse of $g$). Note that in a group of prime order ($q$ in our case) every element is a generator. This group of quadratic residues of order $q$ is a subgroup of $Z_p^*$. If you recall basic group theory then you may remember the definiton of a subgroup: Let $G$ be a group and let $H$ be a nonempty subset of $G$. If for all $a,b\in H$ it holds that $ab^{-1}\in H$, then $H$ is a subgroup of $G$. This means, that the inverse $g^{-1}$ of $g$ is in the subgroup and since every element in the subgroup is a generator you have what you want so show.


What are the properties of error vector used in symmetric McEliece cryptosystem?

The weight of the synthetic error vector is $n/2$ where $n$ is the block length, this corresponds to maximum entropy error patterns, with independent probability of error $1/2$ for each bit.

The error correcting capability of the code should be much lower for good security.

In the original proposal, $n=1024$ and $t=50$ so this should give you some idea. There is a very readable paper here about this cryptosystem. Look for papers by Sendrier, for updated information on parameters and attacks.


How to solve the system of linear equations to recover original file using "Erasure Coding"?

The original data are $X_1$ and $X_2$.  The shares are

\begin{align*}
  A_1 &= X_1, \\
  A_2 &= X_2, \\
  A_3 &= X_1 + X_2 \\
  A_4 &= X_1 + 2 X_2.
\end{align*}

You store the shares $A_1$, $A_2$, $A_3$, and $A_4$ on disk, or over the internet and through the hills on someone else's disk, or buried in a tree somewhere for safekeeping.  If a forest fire takes out the tree and someone else's house is washed away in a flood (or, if a malicious storage server tries to modify one of the shares and you detect it because you're using cryptography and throw that modified share away), but you still have two of the four shares, say $A_2$ and $A_4$, you can recover

\begin{align*}
  X_2 &= A_2, \\
  X_1 &= A_4 - 2 A_2,
\end{align*}

and get your original file $X_1 \mathbin\| X_2$ back.


Break AES-CFB mode having access to a AES-CTR black box

It is quite easy, try to imagine if you have only one block of plaintext and you encrypt it under CFB or CTR with the same IV...
(using the black box you can actually get the encryption of any IV of your choice)


When to prefer exchanging cryptographic certificates over exchanging only public keys?

There is another advantage that certs provide that has nothing to do with trust issues.  Certs are a pretty-much universally-recognised public-key bit-bagging format that's portable to pretty much everything, while there's no such equivalent for raw public keys. By placing your public key in a certificate, you're converting it into an interoperable form that almost anything (even some versions of PGP) can read.

This use of certs as public-key exchange formats is quite common, it's effectively what a self-signed cert is. In addition many crypto tools ignore the rest of the certificate (even when it's issued by a CA) and just use the public key, since that's all they care about, either because the cert/public key are communicated via authenticated channels and the use of a CA is just a distraction, or because all you need is the cert as a token to enable crypto without having to go through all the calisthentics of cert validation.

So I'd always use certs to exchange public keys, not because of any magic surround certs, but because they provide a useful interop format for keys.


Relying on a 4-bit S-box instead of an 8-bit one

While an ideal 4x4 s-box will have less ideal properties compared to an ideal 8x8 s-box, you can make up the difference with more applications of the smaller s-box.

As an example, the worst differential in the AES s-box is 4/256, or 1/64. If your s-box only has 16 entries, you clearly cannot obtain an entry nearly so low as 1/64 - the lowest possible entry is only 1/16 in the smaller s-box (neglecting the need for uniformity). But if you apply your smaller s-box repeatedly, you can see that the overall probability can be made to be equivalent.

Note that the design of 4x4 s-boxes is basically a solved problem - there are multiple papers out there that have already searched through all possible 4-bit mapping and found the s-boxes with optimal properties that can be implemented in a minimum number of instructions from among all 4x4 s-boxes.


Interpretation of advanced composition theorem of differential privacy

Consider the composition of $k$ algorithms each of which is $(\varepsilon,0)$-differentially private. We want to calculate parameters $\varepsilon'$ and $\delta'$ such that that the composition of these algorithms satisfies $(\varepsilon',\delta')$-differential privacy.

The comparison is between advanced composition
$$\varepsilon' = \sqrt{2k\log(1/\delta)}\varepsilon + k \varepsilon (e^\varepsilon-1)$$ and basic composition $$\varepsilon' = k \varepsilon$$.

There is no way to say that one of these expressions is universally better than the other, as it depends on the parameter settings. However, we can argue that for some realistic parameter settings the first is better than the second.

What do I mean by realistic parameter settings? Let's say that the number of queries is fairly large (e.g., $k = 10^5$) and the final privacy parameters are not too big (e.g., $\varepsilon' = 1$ and $\delta'=10^{-6}$).

Then for basic composition we need $\varepsilon = \varepsilon'/k = 10^{-5}$.
For advanced composition the calculation is a bit messier, but we can calculate that $\varepsilon=58 \times 10^{-5}$ suffices. In other words, advanced composition saves a factor of $58$ over basic composition. The improvement becomes more dramatic as $k$ increases.

Asymptotically, if we think of $\varepsilon'$ and $\delta'$ fixed but $k$ becoming larger, we see that basic composition requires $\varepsilon \approx 1/k$, while advanced composition requires $\varepsilon \approx 1/\sqrt{k}$. (I'm dropping all non-relevant terms and constants here.) This is the advantage of advanced composition.


Length of prime number used in Pedersen Commitment

If you mean a prime in the neighborhood of $2^{80}$, well, that is incorrect.  A prime that small will allow someone to commit to a value, and then reveal another one.

A Pederson commitment is a value $g^x h^r \bmod p$, where $g$, $h$ and $p$ are public values, $x$ is the value being committed to, and $r$ is a random value.  To reveal the commitment, you publish $x$ and $r$.

To reveal a second value $x'$, one way to do this is compute a value $r'$ with $g^x h^r \equiv g^{x'} h^{r'}$, this is equivalent to $h^{r'} \equiv c$, where the attacker can compute $c \equiv g^{x - x'}h^{r}$.  If the attacker can solve his discrete logarithm to the base $h$, we can recover $r'$ and reveal his second value $x'$.

Now, for primes of 80 bits in length, this discrete logarithm is easily solved.  To make it impractical, you need a prime at least 1024 bits in length, preferably at least 2048 bits.

On the other hand, if you mean a prime that's $2^{80}$ bits in length, that is, around $2^{2^{80}}$, well, you'll find that is an impractically large prime to work with; computing $g^xh^r$ would be infeasible.


Where to store the file extension to retrieve it correctly after decryption

If you are encrypting one file to one file, simply save the correct extension. Example: open test.pdf, encrypt the content, and save as test1.pdf, or test1.pdf.enc (so that you know that the file is encrypted and any pdf won't try to open it when you double click).

If you are encrypting more than one file together (and, in the end, you have one big chunk of data that contains more than one file inside), you're already having to deal with "which byte belongs to which file", and then storing the original filename is just part of this file manipulation.


Do Partially Homomorphic Encryption schemes also suffer from noise overflow?

If by PHE you mean systems such as Paillier, then the answer is no. They don't have noise as in FHE and SWHE.


Average case problem and worst case problem in lattice

According to my understanding, in cryptographic constructions based on worst-case hardness we based the cryptography scheme on hard subsets in which the problem is hard, so we should also avoid we based the cryptography scheme on subsets in which the problem is easy.

I think the idea of the statement is more along the following line:

"For most cryptographic schemes we have no proof that the distribution we use in practice is actually as hard to solve as the hardest ones we could come up with. With lattices however we have a proof that the sampling strategy we use generates problems that are just as hard to solve as the hardest instances we could come up with."

So the statement is about the average case for lattices being provably as difficult as the worst-case.


A zero-knowledge proof for a language in BPP is trivial: a statement in BPP can be verified in probabilistic polynomial time (by definition). So, for any language $L$ in BPP, and any $x \in L$, here is a trivial proof that $x\in L$: the prover sends nothing, and the verifier checks whether $x\in L$ (this takes polynomial time) and output yes iff this holds. Correctness is trivial, soundness too (the prover cannot cheat as he does not send anything at all), and zero-knowledge as well (it requires simulating an empty transcript...).

Here is an example: consider the language of prime numbers. Given a number $n$, the prover wants to convince the verifier that $n$ (which they both know) is prime. To do so, he comfortably stays at home and watches a movie, while the verifier checks by herself that $n$ is prime, using any polytime primality test of her choice. When she's done, she can just tell the prover "ok, you convinced me".


$$x<\!\!<\!\!<k$$ normally means cyclic rotation of a bit string $x$ to the left by $k$ bits.


About the best you can do is have a master public/private key pair where the public key is stored on your server and the private key is stored offline. When you generate a new private key, encrypt it with the master public key and store that in the database. That way, if a password is ever lost, you can recover the user's private key by using the master private key to decrypt their encrypted private key.


Multi-Linear Secret Sharing vs. Shamir Secret Sharing

I'm not an expert but I will try to answer from my understanding.

LSS allows you to divide the secret to many shares and it does not limit you to give only one share to a person. In the example you have given, the secret is divided into 5 shares and gave to 4 people. In this case, P_2 receives 2 shares.

Having r_2 in two different rows doesn't help much in this case because there are other terms to help hiding the secret. You can treat both row as a different share of secret. In this case, it is hold by the same person P_2.

The above example is Linear Secret Sharing, where the reconstruction of the secret come from the linear algebra operation from the matrix used. Multi-Linear Secret Sharing is like an extension to LSS by hiding more than one secret at the same time and use the similar algorithm to reconstruct the secret.

Shamir Secret Sharing, on the other hand, rely on polynomial interpolation to reconstruct the hidden secret. Using the fact that d+1 points can interpolate degree d polynomial with Lagrange's Coefficient, we can assure that for d+1 shares can reconstruct the hidden secret. This is a good explanation video on SSS.


Transparent, publicly updatable accumulator with constant-sized witnesses

Later edit: Actually, some new Stanford work shows how to obtain transparent RSA accumulators using class groups. This was also discussed in Secure Accumulators from Euclidean Rings without Trusted Setup, by Helger Lipmaa.

The Stanford work also shows how to publicly add and remove elements in the accumulator. And the proofs are constant-sized.

Original answer: If you're willing to generate RSA keys in a distributed fashion, then you might as well go for bilinear accumulators, since you can also generate $q$-SDH parameters for them in a distributed fashion and they will be faster for non-membership proofs and also support subset proofs.

Depending on how you squint your eyes, yes, bilinear accumulators have all of those properties.

No trusted setup: just use MPC to generate $q$-SDH public parameters.
Publicly updatable: given old set $X$ and updates $U$ s.t. new set $X' = X \cup U$, anybody can simply recompute $acc(X')$.
Constant-sized witnesses: bilinear accumulator witnesses are 1 group element for membership and 1 group element plus 1 field element for non-membership.
Witnesses should be publicly-verifiable: in bilinear accumulator they are
Accumulator updates (additions and/or deletions) should be public(ly made): anybody can recompute an updated bilinear accumulator
Witnesses should be updatable from publicly-broadcasted auxiliary information: I know membership witnesses can be easily updated in $O(1)$ time after 1 addition to the accumulator. Not sure about non-membership witnesses. However, given the new set $X'$, anybody can compute a new witness in $O(n)$ time.

Hope this helps!


You want to find a point $(X,Y)$ on an elliptic curve $y^2 = x^3 + ax + b$ knowing only $X$ and a single bit indicating whether $Y$ is even or odd. To find $Y$, you use the relation defining the curve: you know that $Y^2 = X^3 + aX + b$ since the point is on the curve. So you compute $X^3 + aX + b$ using your value of $X$ and the public parameters $a, b$, and you want to find values of $Y$ such that $Y^2$ is equal to that value.

If the modulus $p$ is congruent to $3$ mod $4$, that's very easy to do: for any $z$, the square roots of $z$, if they exist, are $\pm z^{(p+1)/4} \bmod{p}$. Indeed, suppose $z$ has a square root, say $a$. Let $g$ be a primitive root mod $p$, and let $a = g^x$. Then $z = (g^x)^2 = g^{2x}$. In turn,

$$(z^{(p+1)/4})^2 = z^{(p+1)/2} = (g^{2x})^{(p+1)/2} = (g^x)^{p+1} = (g^x)^{p-1}g^{2x} = g^{2x} = z$$

which shows that $z^{(p+1)/4}$ is indeed a square root of $z$.


Is there a library that output LFSR images given parameters?

Yes, there is a python library LFSR-Automatic-Draw  that can output $\LaTeX$ Tikz code and that can be converted to PNG images by
pdflatex -shell-escape lfsr.tex
The library has many parameters to draw;

One can print the feedback polynomial on the bottom
One can enable/disable printing the name of the boxes
One can  enable/disable printing the initial values
Font size, box sizes, colors, arrow sizes, etc.

Sample outputs are

And, the library now can output multiple images per clock that can be converted to loop-animation


Elliptic curve point addition with $Z_1 = Z_2 = 1$

This question was answered in the comments:

If you add two points with $Z_1=Z_2=1$, the resulting point will (in general) have $Z_3\neq1$. Given that we typically do a full addition chain, and not just add two points together, what is your stategy when it comes time to do the second addition? – poncho
In other words, the drawback is that it only works when $Z_1=Z_2=1$. :) And of course you must normalize the resulting $(X_3,Y_3,Z_3)$ if you want the $(x_3,y_3)$ coordinates that point. – Chris


Property that prevents determining key from ciphertext and plaintext

As mentioned in the comments, it appears that you are seeking to understand what provides a cipher with resistance to known plaintext attack. "Diffusion" and "Confusion" I think are the answer here.

Diffusion

"Diffusion" means that the terms/bits of the algebraic expression of the cipher are inter-dependent. Without diffusion, different subsections of the state will act independently, and so can be attacked independently. With diffusion, different subsections of the state will be dependent on the values of other subsections of the state. More diffusion leads to a greater number of terms in the expressions that represent the cipher.

Confusion

"Confusion" means that the algebraic expressions of the cipher are non-linear, which makes them difficult to work with. Non-linearity increases the degree of the ciphers equations. Ideally, the non-linear expressions are not even approximately similar to any linear expressions.

A linear cipher can often times be easily broken with negligible time/space complexity, regardless of how many rounds or how much key material is applied. The linearity means that we can view the ciphertext as a simple equation of key + message bits, which can be easily solved if you know the message bits.


How were the constants chosen in round 2 and 3 in MD4?

I've got the solution myself in here

It says

  SHA-1 was designed by NSA and uses the constants 5a827999, 6ed9eba1, 8f1bbcdc, and ca62c1d6. In case you haven't already noticed, these are hex representations of $2^{30}$ times the square roots of 2, 3, 5 and 10.


Is there an anonymous non-interactive authorisation scheme with peer-side auth. signature generation?

I could solve my question using the fundamental work of Eric Verheul: Self-Blindable Credential Certificates from the Weil Pairing.

What I didn't know was the basic principle of self-blinding. In its simplest form, a peer (sk: $x\in Z$, pk: $X=g_1^x\in G_1$) communicates with an authority (sk: $a\in Z$, pk: $A=g_2^a\in G_2$) to get a certificate for his pk. cert: $C=X^a \in G_1$.
Now the peer is able to self blind his public key and the certificate using a random $k \in_R Z$:  $X_b=X^f\in G_1$; $C_b=C^k \in G_1$. This can be verified using $e(X_b,g_2)=e(C_b,A)$ which is $e(g_1^{axf},g_2)=e(g_1^{xf},g_2^a)$.

To add authorisation, a hash of the authorisation information $c=hash(Authorisation Information)$ can be included: $C=X^{a+c}$. Now the verifier needs to recalculate $c=hash(..)$ to verify the authorisation: $e(X_b,g_2)=e(C_b,A \cdot g_2^c)$.

(Just for the record: this example is not secure, since the peer could remove its key from the certificate and then sign any other PK too.)


is there cryptography algorithm space /input invariant?

This isn't the most direct answer to your question, but you could segment your input into blocks, and just encrypt the blocks. However, performing this could possibly introduce vulnerabilities caused by being able to exploit how you're segmenting the data (if that method can't be stored in your brain).

Part of how a lot of encryption methods work is they can take a variable length input and create an output that varies size. The only encryption method I can think of that is input invariant the way you describe is a Caesar cipher.


To prove that a scheme is not secure under such a definition you usually would propose an algorithm such that the experiment described in your question outputs $1$ with probability non-negligibly larger than $1/2$.
As this looks very much like a homework problem I will not give you a solution. However constructing the algorithm is actually very simple in this case. You only need to think about how you would choose the messages $m^{(0)},m^{(1)}$ in such a way that you would be able to distinguish their ciphertexts.
As a hint: The deterministic nature of the encryption-process could be a problem here, and you can actually distinguish with probability $1$.


I am familiar with the RC4 related key attacks; I can say that if you publish the nonce, and use any of the first 256 bytes of the RC4 keystream, that you are vulnerable to those attacks.

These attacks exploit a correlation between specific bytes of the RC4 key, and the initial output values; with your approach, the attackers can guess what (say) byte 2 of the master key was (by computing what the corresponding RC4 key is for each message, and checking to see if the RC4 byte statistics is what he'd expect); this would allow him to recover the entire master key with enough messages.

I would strongly urge you that, if you can't follow D.W. advice, and you have to live with this scheme, that you always discard the initial (at least) 512 bytes of the RC4 keystream immediately after you rekey RC4.  Why 512 and not 256?  Well, some statistical analysis shows that byte 258 of the generated keystream has a measurable bias towards the value 03; it is unknown why it is, or if it has any correlation with the initial key; but it is a bad sign.


Unlike KDC or public key authority, CA does not have to be online to provide keys to users

What they mean by that is that the CA doesn't have to be on-line at the time of negotiation.  That is, when you use TLS to take to Amazon, the CA doesn't have to be a part of the negotiation.  Instead, Amazon can send its certificate and you can verify it (and then use the embedded public key) without the CA being involved direction.  The CA can be (and generally is) shut off from the network during that time.

This contrasts with (say) a Key Distribution Center; when Alice and Bob need to negotiate a shared secret, the KDC is a necessary party within that negotiation.

This implies two things:

Because the KDC must be on-line, that means that it must present an interface to the users; such an interface is a potential attack surface.  As the CA is usually off-line, it is rather more difficult to attack.
Scalability; because the KDC participates in every negotiation, that means that it gets a lot of traffic.  Of course, there are ways to address this, such as redundant KDC servers; however that just increases the attack surface.

Of course, the CA does have to be available at the time of enrollment.  What Amazon gets its certificate, the CA has to generate it and send it to Amazon.  However, this is a comparatively rare event (compared to how often negotiation happens), and so less of an issue.

  I think KDC and public key authority are same as CA.

No, they are not.  A KDC is a central authority that distributes keys.  How it generally works is that the KDC would share a symmetric key with each of its uses; when Alice wants to talk to Bob, it would send a request (using Alice's symmetric key) to the KDC; the KDC would generate a key, and send it to Alice (using Alice's symmetric key) and to Bob (often via Alice) using Bob's symmetric key.


What is meant by a "short" vector in cryptography?

Short just means small (in terms of some metric, usually Euclidean).

You can see that if $e$ is the zero vector, $s$ becomes trivial to recover, using Gaussian elimination. If $e$ is uniformly random, then you can imagine that it is impossible to recover any information on $s$, since it is hidden against a uniformly random backdrop.

If you're familiar with lattices, it might be helpful to picture the following instead. Consider the LWE lattice

$ \mathcal{L} := \{ \mathbf{A} \mathbf{s} : \mathbf{s} \in \mathbb{Z}^n_q \} + q \mathbb{Z}^m .$

If the vector $e$ is small enough, $b$ is close to only one of the points in this lattice. In other words, the LWE problem becomes a bounded-distance decoding problem on this lattice. If $e$ is too large, $b$ might be closer to another vector in this lattice.

Since we are typically interested in recovering $s$ and not a set of possible secrets, we must be given a guarantee that $e$ is sufficiently short (hence bounded distance decoding).

So "short" just means that $s$ is recoverable. Usually, $e$ is sampled from a discrete distribution approximating a Gaussian centered around 0, with width small relative to $q$. This allows one to ensure that $s$ is recoverable with an arbitrarily high probability, while still making the problem as difficult as possible.


What is the value of the fpad used in the NMAC?

If you look at the original publication of NMAC & HMAC you will notice that there is no such padding in NMAC and in HMAC the constants are XORed with the key.

I don't know where this fpad comes from. It's not mentioned in the HMAC RFC either.

Found it! It is mentioned in the paper with the update security proofs. But there it is stated that it doesn't need to fulfill any requirements (p. 7). I assume that it is not defined in practice because the practical implementation of NMAC is HMAC and, as also stated in the above paper, leaving it out entirely is fine.


Has any alternative to RSA and Discrete Logarithm been standardized for deployment?

Since you say

  to rescue the internet

I presume you are specifically referring to TLS. With a quick look at the supported Key Agreement Schemes in TLS 1.3, the ongoing draft of TLS, it is clear that all the Key Agreement Schemes are based upon the generalized Discrete Logarithm problem or Integer Factorization. Both of these are broken by Shor's algorithm on Quantum Computers, in the event that the physical constraints limiting the construction of such high bit quantum computers are solved.

However, there are numerous asymmetric cryptosystems that exist with no known efficient quantum algorithm. As you noted, there are multiple based upon the Shortest Vector Problem. In addition there are other systems, such as the Anshel-Anshel Goldfeld Key Exchange, which is based on the difficulty of the conjugation problem on braid groups. There is no known efficient algorithm to solve this.

There are standardizations for several post quantum systems, though they are not slated for inclusion in TLS. The lattice based ones have standardizations, but new variants are continually being proposed with different properties. There are standardizations for the code based schemes.


Yes, it's the same XOR. It gets used inside most of the algorithms, or just to merge a stream cipher and the plaintext.

Everything is just bits, even text. The word "hello" is in ASCII 01101000 01100101 01101100 01101100 01101111. Just normal bits, grouped in 5 bytes. Now you can encrypt this string with a random string of 5 bytes, like an One-time pad. Let's say we got the randomly generated string 10001001 10000010 00001011 01001101 11101101 (generated with www.random.org). Now we XOR both strings, getting 11100001 11100111 01100111 00100001 10000010. If you never reuse or reveal the key, nobody can crack this cipher. (Well, I did reveal the key, so it's not secure anymore.)

Many block ciphers use XOR. Let's take AES: The Advanced Encryption Standard uses xor on single bytes (some other algorithms use blocks of 16 or 32 bits; there's no problem with sizes other than 8 bits). The round key will be XORed with the intermediate result and after that permuted and substituted. XOR also gets used in the key shedule.

IDEA also uses XOR as one of its three main functions: XOR, addition and multiplication.

XOR has (inter alia) these advantages when used for cryptography:

Very fast computable, especially in hardware.
Not making a difference between the right and left site. (Being commutative.)
It doesn't matter how many and in which order you XOR values. (Being associative.)
Easy to understand and analyse.

Of course, some of this "advantages" can be disadvantages, depending on the context. The fast speed makes it possible to use XOR often without huge performance drops. The security of Threefish, another block cipher, relies on the non-linearity of alternately using modulo addition and XOR. Despite of the use of 72 rounds (as the base of the hash function Skein) it's still quite fast.

XOR alone is not enough to create a secure block or stream cipher. You need other elements like additions, S-boxes or a random, equally long bit stream. This is because of the linearity of the XOR operation itself. Without non-linear elements, a cipher can easily be broken. See Why do block ciphers need a non-linear component (like an S-box)? for more details on why non-linearity is important.


To a cryptographer, "signing a document is to encrypt its hash using signer's private key" is wrong, because:

It is specific to RSA and cousin cryptosystems including Rabin, and not even remotely descriptive of other common signature schemes;
It misses an important step, padding, which is different for RSA signature and RSA encryption. If we use no padding, some attacks apply (in particular, that allow computing signature of a document from a moderate number of signatures of other chosen documents).

PHP's openssl_private_encrypt used in the software linked in the question is thus horribly named (it should be openssl_RSA_sign), but when used with OPENSSL_PKCS1_PADDING (which seems to be the default), I believe it uses RSASSA-PKCS1-V1_5, an RSA signature padding; it's a tad obsolete and lacking a strong security argument (contrary to RSASSA-PSS), but stands currently unbroken.

Note: the linked software uses SHA-1, and that's obsolete, and broken by the definition we use in cryptography. It was practically and publicly broken in 2017.

Note: the linked application is at best as worth of trust as the weakest of the web server running it, the web client used to access the website for signature and that used for signature verification, the cryptography between server and clients, the source of the public key, the generator of the private key and anything that was ever used to handle it.