Is murmur3 (128) a good hash function to use as a proof (hash) of a document in a smart contract?

Actually, it's even worse than what Otus suggested; it's trivial to find a second-preimage; that is, given a message, it is easy to find a second message that hashes to the same value.  In fact, you can make the second preimage start with an arbitrary text, and so this is a practical (rather than just an academic) attack.

It's actually quite straight-forward; the state update function for MurMur3-128 is:

h1 ^= mixK1(k1)
h1 <<<= 27;
h1 += h2;
h1 = 5*h1 + constant_1;
h2 ^= mixK2(k2);
h2 <<<= 31;
h2 += h1;
h2 = 5*h2 + constant_2;

where h1, h2 are the hash state, k1, k2 are 128 bits from the current part of the message, and mixK1, mixK2 are invertible functions.

What we do is process the arbitrary preliminary text (which we're assume is a multiple of 16 bytes in length), this will result in some state h1, h2.

Now, what we do is find some 16 byte block k1, k2 that converts this state into a state that is obtained during the processing of the original message; once we have done that, we can append the rest of the original message, and that will result in the same hash as the original message.

Finding such a k1, k2 is quite straight-forward; we just work backwards through the above logic.  We start with the h1, h2 being the target values, and compute what the previous state is.  When we hit the h1 ^= mixK1(k1) and h2 ^= mixK2(k2) lines, those are (in the backwards direction) the last time we'll update h1 and h2, and so we just set mixK1(k1) and mixK2(k2) to be the values that'll give us the state after processing our chosen prefix.

Since mixK1 and mixK2 are invertible, that gives us K1 and K2, which are the 128 bit values we're looking for.

Note that this is somewhat different from the analysis by Jean-Phillip Aumasson, as he is actually tackling a harder problem.  He assumed a secret start state (and was able to find collisions); I'm assuming a known state state (and able to find second preimages)


High Power Computing for Crypto Research

Insofar as cryptanalysis is considered a part of crypto research, certainly.  More computing power is always helpful for breaking ciphers, and indeed, some of the more notable massive distributed computing efforts of recent decades have involved the brute force breaking of cipher challenges such as the RSA Factoring, DES and Secret-Key Challenges.  Even with more "analytical" attacks, such as the recent MD5 collision attacks, the final stage of the attack typically still requires testing a large number of candidate values by brute force, a task made considerably easier by the availability of high computing power.

In other parts of crypto research, not so much, although some recent crypto primitives have made use of computationally intensive (pseudo-) Monte Carlo methods for choosing constants or combinations of operations to maximize desired cryptographic properties.  For example, the rotation constants of the Threefish block cipher used in the SHA-3 finalist hash function Skein were selected using a genetic algorithm.


What are the implications of the new alleged key recovery attack preprint on SIMON?

TL;DR: this paper seems to be a joke, or delusional; the "zero-knowledge proof" proves nothing.

The report purports to have found an efficient cryptanalysis on SIMON-32/64, a small block cipher. The exact details are, on purpose, not disclosed. However, to convince the reader that the method actually exists, a so-called "zero-knowledge proof" (not really what is usually called zero-knowledge, by the way) is presented in section 4. What I will show here is that this proof shows nothing, and the same kind of feat could be relatively achieved with any block cipher with the same block size.

SIMON is a family of block cipher. Here, we talk about the "smallest" of these, SIMON-32/64, which has blocks of 32 bits and keys of 64 bits. The block size is important here: it means that when the article shows 64-bit plaintexts and ciphertexts, these really are pairs of plaintext blocks and pairs of ciphertext blocks, encrypted in ECB mode.

Let's see the first kind of "proof": the paper shows a few keys that encrypt the plaintext "YHWHYHWH" into the ciphertext "YHWHYHWH" (using ASCII encoding for both). As explained above, these really are keys that encrypt "YHWH" (32-bit plaintext block) into "YHWH" (32-bit ciphertext block); the repetition is a mere distraction. If you find a key that encrypts a given 32-bit block $P$ into a given 32-bit ciphertext block $C$, then of course the same key will encrypt $P\mathbin\|P$ into $C\mathbin\|C$, and $P\mathbin\|P\mathbin\|P$ into $C\mathbin\|C\mathbin\|C$, and so on. This is what ECB mode means.

Now, take a given plaintext block $P$, and a given ciphertext block $C$. How hard is it to find a matching key? If you take a random key $K$, the encryption of $P$ with key $K$ yields a ciphertext block $C'$, which has size 32 bits. Thus, the probability of having $C' = C$ is about $2^{-32}$. Which means that if you try random keys, you'll need on average to try about $2^{32}$ keys to find a match. Any decent-sized laptop should be able to try about $2^{25}$ keys per second (I am assuming here that encrypting a block takes 400 clock cycles, the CPU runs at 3.2 GHz, and there are four cores; we can probably do a lot better than that with AVX2 capers, but let's focus on stupid, basic software). Thus, $2^{32}$ keys will be tried in about two minutes. In other words, if you ask me to find keys that encrypt "YHWHYHWH" into "YHWHYHWH", then I should find one every two minutes. The six keys presented in the article represent less than 15 minutes of work of a single laptop! And all of that is using SIMON-32/64 as a black box, i.e. assuming that it is a perfect, ideal block cipher.

Now, let's investigate the second "proof": the authors take a large corpus of 64-bit messages (pairs of blocks), extracted from the King James Bible. In raw UTF-8 text (really, ASCII, it's all in English and does not contain the word café), this is a 4452069 bytes file. This means that there are 4452062 sequences of 8 bytes in there. Let's round that low to $2^{22}$ to make computations easier. The "proof" is that they show keys that map one of these blocks to another of these blocks; the table 6 shows 18 such plaintext/ciphertext/key triplets (the text of the article says "19" but there are only 18 in the table).

Take a perfect ideal cipher with 64-bit blocks (here we are not even going to use the fact that SIMON-32/64 uses 32-bit blocks and that 64-bit messages are really pairs of 32-bit blocks). Take a random key. Encrypt one of the $2^{22}$ plaintext blocks into a 64-bit block. What is the probability that the output 64-bit block is one of the $2^{22}$ in the list? It's $2^{-42}$ (because there are $2^{64}$ possible 64-bit blocks and $2^{22}$ targets). This means that if you try random keys, you'll get a match every $2^{42}$ random keys on average. At $2^{25}$ per second, we're talking about one key every two days; the 18 keys will then take a bit more than a month. The authors claim to have required 120 days, so they're a bit lagging here. Again, taking the block cipher as an ideal black box, a basic brutal attack does better than the cryptanalysis claims.

(With some details: some basic optimization here is that the "attack" will only encrypt one 32-bit block to start with, and encrypt the second one only if there was a match with the first one; moreover, the lookup in RAM for a match can be optimized by doing it only if the output block is ASCII, i.e. if the top bits of each byte are zero, so we end up with, for each key: one SIMON-32/64 encryption, a test on the top bits of the output bytes, a lookup into RAM only in 1/16th of cases, and a second block encryption only in 1/64th of the cases were a lookup in RAM is done; thus, we can easily approximate the cost as "1 SIMON-32/64 encryption per try".)

So whatever they are doing, it does not seem to be any better than brute force that has nothing to do with the internal structure of the block cipher.

An open question is whether this is a deliberate prank, a skewed attempt at damaging the reputation of the eprint maintainers, or a case of self-delusion. I don't attempt to answer that question.


Difference between when select x from $\mathbb{Z}_{p-1}$ and $\mathbb{Z}_p$ in discrete logarithm Problem?

$\mathbb{Z}_p=\mathbb{Z}/p\mathbb{Z}$ denotes a finite field that is just integers mod the prime $p$, i.e., $\{0,1,\ldots,p-1\}$. This field (by definition of a field) has two operations: addition and multiplication, where the multiplication group (denoted by $\mathbb{Z}_p^*$) is defined only on the non-zero elements $\{1,2,\ldots,p-1\}$. Then, since $g$ is a generator of the multiplicative group of size $p-1$, the exponent $x$ should be sampled from $\mathbb{Z}_{p-1}=\{0,1,\ldots,p-2\}$ (which by the way is not a finite field).


Cryptographical formalization of computational privacy

It depends on how strict you are. In the traditional cloud computing sense, where one party "sends their data to the cloud" for all the computations to be performed, no. There aren't any other methods other than homomorphic encryption.

The most common techniques for computation on encrypted data besides homomorphic encryption are garbled circuits and secret sharing based schemes. The problem with them is that they are much more interactive than the traditional cloud computation model, where the data is encrypted and sent off.

Recent research, however, has been looking at cloud-assisted multi-party computation. In this paradigm, the cloud is a party of the MPC, but without any input. See Outsourcing Multi-Party Computation and Cloud-Assisted Multiparty Computation from Fully Homomorphic Encryption. I'm not completely aware of all the details (had forgotten about these works until working on this answer), but maybe these are headed in the direction you were thinking of.


how Content Scramble System (CSS) works?

1. Where does this key come from?
2. Is it embedded within the Hardware DVD or within the software player?

The soft|hard players have to authenticate to access the key from the disk. From Wikipedia

The details of CSS are only given to licensees for a fee. The
license, which is bound to a non-disclosure agreement, wouldn't
permit the development of open-source software for DVD-Video playback.
The player has to execute an authentication handshake first The authentication handshake is also used to retrieve the disc-key-block and the title-keys.

So, non-disclosure has the force.

3. what's the principle in which this method prevent DVD copy?

It has three types of protection, from wiki page;

Playback protection is based on encryption: the player requires a secret key to decrypt the feature.
Read protection is based on the drive: access to significant disc data is only granted if the player authenticates successfully.
Regional restriction is based on the disc and the drive: the drive can deny access if the disc doesn't belong to the drive's region.

All three protection methods have been broken.

And the keys are in the lead area of the DVD2;

It prevents byte-for-byte copies of an MPEG stream from being playable since such copies will not include the keys that are hidden on the lead-in area of the protected DVD disk


Generating non-repeating N-bit IVs, which are indistinguishable from randomness

I suppose the easiest way to generate these initialization vectors is to use a 64-bit block cipher (like Blowfish or DES/3DES), and encrypt sequential values of a 64-bit counter.

Of course, the "indistinguishable from true randomness" property of good block ciphers is only valid if the attacker can't observe much more than $2^{32}$ such initialization vectors, as then a truly random sequence would start to show duplicate elements, while your one would not, by your requirement.

Actually, if the only requirement is a nonce, and your protocol messages arrive in sending order (like over a TCP connection), you don't have to send it with the actual stream data, as long as the other side has the necessary information to generate it. Then a simple counter, counted up at both sides (and never transmitted), will do nicely (and you don't have to think about another key which needs to be managed).


How exactly are PRNG's used to encrypt material, and what makes one any more secure than the other?

Well, first of, a linear congruential generator is not a secure pseudo random number generator at all, but if it's just about the basic understanding, we can ignore how you get that stream of random numbers for now.

So, but can you actually use this? The easiest approach is using the stream of random numbers in a stream cipher and just XOR each bit of the message with the according bit in the stream. For the actual implementation your RNG will provide a fixed number of bits and you need to keep track of how many bits you actually used. And then you transmit the result instead of the message itself.

On the other side you do the same.

An alternative would be to work on 8-bit symbols, and you just add the values together (modulo 256). Pseudo code:

Input: message as char array m[]
rng(): call to the RNG, returns an 8-bit integer array of length r.

j = 0
temp = rng()

for i from 0 to m.length:
  m[i] = (int(m[]) + temp[j]) % 256
  i++
  j++
  if (j > 255)
    j=0
    temp = rng()

Maybe this can be made more compact, but it should work for a toy project.


Why rogued certificate from hash collision is harmful

Very basically, the hash collision it can be used to fool CA's to sign a certificate that stores one set of information in the certificate's attributes, while there the requester uses it to create one or more certificates with different attributes.

The attributes in the certificate are as important as the public key that is being signed. They contain, for instance, the information of the holder. For web certificates the most important holder attribute is the domain name of the server. It is of course of vital importance that the name cannot be changed. Another part of the attributes is the key usage, which defines how the key should be used. One very important bit is the bit that defines if the certificate can be used as CA certificate. If it can be set then the user may simply start acting as an intermediate CA, issuing certificates himself, for any domain.

The public key stored in the certificate is only one part of information that is signed. That you can also sign another public key is not so much of a problem as the private key still needs to be controlled by the party sending the certificate request. This would only be a problem if the location of the private key is somehow part of the security properties covered by the certificate.

All in all, you seem to be focusing too much on the Public Key part and too little on the Infrastructure part of PKI. The attack isn't really a problem during the handshake of TLS, the attack is on the trusting of the certificate. The PKI method of establishing trust is used by TLS, it is not defined by it.


Pseudo random generator vs block encryption, which is faster?

Dedicated stream ciphers typically are, or at least can be, somewhat faster than constructions based on block ciphers.  (If they weren't, there would be no point in using them, since a block cipher can do everything a dedicated stream cipher can.)  What you gain in speed (and possibly code size), however, you lose in versatility:

A block cipher (in CTR / OFB mode) can be used to build a stream cipher.  There is no simple way to construct a block cipher out of a stream cipher.
Block ciphers can also be used to construct many other useful cryptographic tools, such as MACs and hash functions.  Stream ciphers are typically only good for encrypting streams of data.
In particular, a single block cipher can be used to construct a fully IND-CCA2 secure authenticated encryption scheme.  Stream ciphers do not generally include authentication, and thus cannot protect data from tampering.
Several block cipher modes of operation (most notably CTR mode, but also CBC and CFB to a limited extent) have the useful properties of parallelizability and seekability — that is, the en/decryption of different parts of the data can be done in parallel, and it's possible to start decryption from any point in the data stream.

Because of their versatility, block ciphers like AES are also popular candidates for fast hardware implementation.  If you have a fast block cipher implemented in hardware, there's a good chance that it'll be faster than any dedicated stream cipher you could implement in software.

All that said, some of the fastest dedicated stream ciphers can be very fast, both in hardware and in software, and many are also designed to be very compact in terms of code/circuit size.  If you really only need stream encryption (or random number generation), a dedicated stream cipher may be more efficient than a block cipher.

See also: Difference between stream cipher and block cipher


Can 64-bit “PRINCEcore” practically be brute forced?

PRINCEcore is a 64-bit block cipher with a 64-bit key $k_1$. PRINCE is a 64-bit block cipher with a 128-bit key $k_0||k_1$ built from PRINCEcore as
$$\operatorname{PRINCE}((k_0||k_1),x)=\operatorname{PRINCEcore}(k_1,(x\oplus k_0))\oplus P(k_0)$$ where $P(k_0)$ is given as $(k_0\ggg1)\oplus(k_0\gg63)$ which I read as: rotate the 64-bit $k_0$ right by one bit, then replace the rightmost bit by its XOR with the second leftmost one; making $P$ a mapping.

That extension from PRINCEcore to PRINCE is reminescent of the extension from DES to DESX, analyzed by Joe Kilian and Phillip Rogaway in How to protect DES against exhaustive key search (an analysis of DESX). At least, that construction greatly improves the resistance to exhaustive key search, and I do not see that PRINCE could be practically brute-forced with work commensurate to brute-force of PRINCEcore (that is, near $2^{63}$ encryptions).

Note: The best motivation I can find for $P$ is that the rotation it contains avoids a cancellation of $k_0$ in some common operating modes, like OFB, CBC, CFB.. However, by rotating the output of PRINCE, we can cancel that rotation. And the single-bit XOR in $P$ does not seem to add much security.


Rijndael vs. Serpent vs. Twofish: General comparison

The final report is here http://csrc.nist.gov/archive/aes/index.html. All five finalists had at least adequate security on all accounts studied during the process, but Rijndael had better performance characteristics in both software and firmware on other hardware than 32 bit processors, compared to the other finalists.


Encrypt than MAC scheme for Home Security system

my data is about 16 bytes , maybe 4 of additional data, and there's
  12 bytes IV, and 16 bytes Tag. I want to avoid that IV / Nonce to
  reduce frame size.

  Encrypt plaintext (that contains a UNIQUE 32bits counter for frames)
  using AES.

So this means that you already have a 32-bit unique value per-message. If you can guarantee it to be unique across all messages under any specific key, then you can use these 32 unique bits, padded with 0s to 96 bits as your IV for AES-GCM. Or you can construct the IV as your 32-bit unique value + 64 bit of randomness per message, which is transferred explicitely.

If you want to optimize even further (at the cost of security, mind you!), you could use a mode that allows tag truncation (do not truncate AES-GCM tags!), such as AES-CCM. There you would use a similar IV setup as above and additionally you could truncate a few bytes of the authentication tag. The calculation is simple: Let $r$ be the maximal risk you are willing to take that a forged message slips through. Let $e$ be the maximal number of times you output "invalid" for a given key on invalid ciphertexts. Then your tag should have length $l$ at least $l\geq \log_2(e/r)$ (this does not apply to AES-GCM). For more information, have a look at appendix B of NIST SP800-38C (PDF).


Is inverse of a combination function negligible?

Hint:

$$1/{n\choose a}=\frac{a!(n-a)!}{n!}=\frac{p!(p^2-p)!}{(p^2)!}=\frac{p!(p^2)!}{(p^2)!\prod^{p-1}_{i=1}(p^2-i)}=\frac{p!}{\prod^{p-1}_{i=0}(p^2-i)}$$

Now write the nominator as a product series as well. Then adjust the indices and use multiplicative factors to shift indices. Then write it as one big product. Find an upper bound for the fraction inside the product. Replace the fraction, making the multiplied term independent of the variable. Conclude.


HMAC SHA256 - fixed vs dynamic key - security and collision impacts

No, it is not useful to change the key between invocations of HMAC.
That would not change the expected probability of collision, which remains about $n(n-1)/2^{257}$ for $n$ values under a model of HMAC-SHA-256 as a PRF. For $n=2^{40}$ (over a million million, the UK bilion), that's less than $2^{-177}$, the probability of 177 consecutive tails with a fair coin, that is negligible in practice.
That probability can be brought to zero using encryption of a counter with a block cipher.


Are there any attacks / weak points with HMAC-SHA3?

No. Any such attack is yet to be discovered and would constitute a publishable result.


Timestamps, sequence numbers, and nonces for replay attack

AEAD constructions encrypt messages and append an authentication tag. That authentication tag is computed using the following data:

The secret key
The nonce
The message, before or after encryption
Optionally, some additional data

During the decryption process, the authentication tag is computed using the same data, and compared with the one that was attached to the ciphertext.

In order to prevent replay attacks, one of these parameters has to be implicitly known by the recipient.

A simple way to ensure that is to set the initial nonce to a given value, and increment it after every message.

The originator only sends the initialization vector. Individual messages do not contain a copy of the nonce used to encrypt them. They don't have to, since the recipient can perform the same operation as the sender, namely increment the nonce after every received encrypted message, in order to decrypt the stream.

If the stream being decrypted doesn't match the original stream, because messages have been altered, removed, added, duplicated or reordered, the authentication tag will not match the one computed by the recipient using the expected nonce. This issue will be immediately detected by verifying the tag.

When using a transport protocol such as UDP, encrypted messages are not guaranteed to be received in order. Some datagrams may also be missing or duplicated. Applications must reorder them and handle retransmission.

In that situation, a copy of the nonce, or value representing the difference with the initial nonce, can be added to every encrypted message. Since a message is encrypted and authenticated using a unique nonce in addition to the key, the decryption process will immediately detect a an encrypted message whose attached nonce has been tampered with.

Now, if the server is "stateless", there are no ways to ensure that a message hasn't been received before. However, it is still possible to check that a received message is not too old (with the definition of "too old" being application-specific).

Attach a timestamp to the message or to the ciphertext. If it is attached to the ciphertext, include it is the additional data, so that it will be part of the computation of the tag.

The recipient can then check that the timestamp has not been tampered with, and that it is not older than expected.

This requires synchronized clocks, and once again, only provides partial protection against replay attacks.


Is there any theory to measures and determine the strength of an encryption protocol?

Is there any mathematical explanation in this topic, like a "theory of everything" that makes it possible for every encryption protocol.

Sure. It's called concrete security proofs.

With these, you define a model that seems reasonable for your attacker (usually someone already did this), then you go ahead and model your protocol as close as possible to reality as possible while staying compatible with the definitional framework.
Finally you show that the protocol satisfies the definition.
As this usually involves the kind of implication "if you can break the security of the protocol, you can break <insert assumption>" you get security results of the form

  For any efficient adversary $\mathcal A$ against AKE security of
  Example, there exists adversaries $\mathcal B_1,\mathcal B_2$ such
  that

  $$\mathbf{Adv}^{\text{AKE}}_{\text{Example}}(\mathcal A)\leq \mathbf{Adv}^{\text{CCA}}_{E}(\mathcal
 B_1)+3\mathbf{Adv}^{\text{EUF-CMA}}_{S}(\mathcal B_2)$$

for some made-up protocol "Example" that achieves "Authenticated Key Exchange" security if the used encryption scheme is CCA-secure and the used signature scheme is EUF-CMA secure.

You can then research the security bounds for the advantages of your favourite encryption scheme and your favourite signature scheme and insert the expressions to come up with a bound on the security of the protocol.


Why exactly is a root hash used in relation to hash lists?

Yes, the transfer of just the root hash can be a good reason for using a hash list. Then you can still hash the leaf hashes in a parallel fashion.

However, generally the root hash is simply needed so that the hashes aren't reordered / removed. Of course this won't protect against deliberate attack; you would have to use the root hash in a signature scheme for that.

Sending hashes together with data blocks only makes sense if you expect accidental damage. In that case you might want to use a non-secure hash or another error detecting / correcting code (such as PAR2). In general the transfer of hash lists or trees takes part separately.

In the end, a hash list is a very generic concept. How it is used depends a lot on the protocol and/or use case. Possibly that's why you don't find that much practical information on it.

Note that the Wikipedia page correctly specifies that often a root hash is used. What is probably more common is that the hashes are aggregated in a separate data structure, and that that particular data structure is signed. This data structure can include additional (meta-) information in the signature.

You can see this in e.g. XML digital signatures, the cryptographic message syntax (PKCS#7 or CMS) but also ePassports where the separate data groups containing the personal info / fingerprints are hashed separately and the result is put in a structure and signed. This way you can verify components separately, while using only a single signature.


Where does signing/decrypting take place on a YubiKey 4/5 PIV private key?

From the official specifications, published by NIST;
https://csrc.nist.gov/publications/detail/sp/800-73/4/final
NIST  Special  Publication  800-73-4 Interfaces  for  Personal  Identity Verification  –  Part  1:  PIV  Card Application Namespace,  Data Model  and  Representation

A.5 Key  Establishment  Schemes  with  the PIV  Key  Management  Key
FIPS  201  specifies a public key pair  and associated  X.509  Certificate for  Key Management. The  key management  key  (KMK)  is further  defined  in  SP  800-78, which  defines two  distinct  key establishment schemes for  the KMK:
A.5.1.1  RSA  Key  Transport  with the PIV  KMK
As specified  in  SP  800-78,  the on-card private KMK can  be an  RSA transport  key that complies  with [PKCS1].  In  the scenario  described  above,  a sender  encrypts a symmetric key  with  the KMK’s  public RSA transport key.  The  role  of  the  on-card  KMK private RSA transport  key  is to  decrypt  the sender’s symmetric  key on  behalf  of  the  cardholder  and provide  it  to the  client  application  cryptographic  module

The client application cryptographic module would typically mean the software on the computer that you connected the card to. It means that RSA operations happens on the card, but the computer will then decrypt the full message. It's designed this way to not make the card a bottleneck for large messages.
The Yubikey mostly follows the official spec for these protocols.


The general strategy in sequence of games or game-hopping proofs is the following:
Starting with the original security game, change small details in the game in every hop until you get to a game where it is easy to prove security.
You do want small changes in the game hops such that you can prove indistinguishably between the games by security assumptions.
To answer your questions concretely:

The aim of each individual game is a small change from the previous game that can be proven indistinguishable from it.
We link these games by bounding the advantage of an adversary noticing the difference. If no P.P.T. distinguisher is able to decide whether it plays the first or the second game, we can include this bound in the overall security bound and consider the second game instead.

The lemma you stated is a formalization of this idea.


You're talking about the KeyGen algorithm of Bethencourt's CP-ABE. The scheme is described in general and this KeyGen algorithm is supposed to be executed for each user secret key request in full which includes choosing new $r_x$ values.
So, your (actual?) concern that different users who have the same attributes could collude is unfounded.

However, a key authority can add single attributes to an existing user secret key, but for this it is necessary to know $r$ (by storing it in an internal database) or a trick shown by Denisow et al. in "Dynamic Location Information in Attribute-Based Encryption Schemes".


Choosing finite field size in Shamir's Secret Sharing Scheme

Actually, you can do Shamir Secret Sharing over any finite field $GF(p^k)$, for any prime $p$ and any integer $k$.  If $k=1$, you have the $GF(p)$ field you mentioned; however it works on extension fields as well. We often pick $p=2$ and $k$ a multiple of 8; this makes everything nice even number of bytes (at the cost of doing our calculations in $GF(2^k)$).  Of course, this is a choice of convenience, you can make your own choice.

As for the size of $p^k$, well, $p^k > n$ is a hard requirement; you can't give out more shares than nonzero indicies available.  As for $p^k > S$, well, that's not actually a hard requirement; you can split up $S$ into several pieces (each piece no larger than $p^k$), and share each piece separately.  For example, if the secret is a 128-bit AES key, and you're using $p = 257$, you'd split up the key into 16 pieces, each from 0-255, and generate 16 independent polynomials, and give each share holder a point on each of those 16 polynomials.  Just remember: when generating the polynomials, the polynomial you pick must be selected independently of all the other pieces; otherwise you lose the security of the system).

As for not picking $p$ (or $p^k$) too large, well, Wikipedia is wrong there; Secret Sharing is informationally secure (assuming a randomly chosen polynomial); if someone has fewer than the threshold number of shares, then they learn nothing about the secret, and that holds no matter how large we make $p^k$.  I suspect someone took the discussion about Shamir Secret Sharing over the integers (which doesn't work, in part because the integers don't form a field, as there are elements without multiplicative inverses, and in part because it's impossible to select a random polynomial with a uniform distribution over the integers), and extrapolated the problems there to finite fields (which doesn't have those issues).


How to encrypt a string using RSA public key only?

This is not a question about cryptography itself, but rather use of a program or library related to crypto (OpenSSL). It would fit better on security.SX or superuser, or stackoverflow if you want to do it in your own code.

Your key is base64-of-SPKI which is nearly OpenSSL's PEM format; just break it into lines of length 76 (can omit this step if using OpenSSL 1.1.0 given your key is not too long), add a line -----BEGIN PUBLIC KEY----- before and a line -----END PUBLIC KEY----- after. (Note 'line' must have a terminating LF or CRLF depending on OS.) Alternatively just convert it from base64 to binary and that's OpenSSL's DER format.

Much as Squeamish said you can then use this key to encrypt small data (such as a symmetric key) from commandline using

 openssl rsautl -encrypt -inkey file -pubin [-keyform der]

or (in 1.0.0 up)

 openssl pkeyutl -encrypt -inkey file -pubin [-keyform der]

as described in their respective man pages which should be present on your system or on the web; or from code in ways depending on the API(s) available or preferred which you didn't identify.

Both of these by default use the traditional padding of RSAES-PKCS1-v1_5 (commonly abbreviated pkcs) and optionally can do OAEP from PKCS1 v2 (see the man pages) or raw/none (which is usually a very bad idea). You need the recipient to tell you what padding (or possibly choice of paddings) they accept; if you have a choice OAEP is better (and the reasons why are ontopic here but already answered). If they require something other than the two PKCS1 schemes you'll almost certainly need to code it yourself.


What is the difference between a PRF and a PRF+?

IKEv2 uses the term PRF to refer to a negotiated keyed random-looking function (for example, possibly HMAC-SHA256).  IKEv2 uses the term PRF+ to refer to a specific construction based on that underlying negotiated function, as defined in section 2.13:

prf+ is defined as:

prf+ (K,S) = T1 | T2 | T3 | T4 | ...

where:
T1 = prf (K, S | 0x01)
T2 = prf (K, T1 | S | 0x02)
T3 = prf (K, T2 | S | 0x03)
T4 = prf (K, T3 | S | 0x04)
...

The term PRF+ has no generally accepted meaning outside of IKEv2.


How to apply two consecutive Paillier encryptions?

I do not know what would be the purpose of doing so, but there are two simple solutions:

The ciphertext $c\in\mathbb{Z}_{n^2}$ is $2\log_2(n)$-bit long, so you can simply interpret it as a pair $(c_0,c_1)$ of $\log_2(n)$-bit string, that can in turn be seen as elements of $\mathbb{Z}_n$. Then, you can encrypt each component $(c_0,c_1)$ using Paillier again.
There is a natural generalization of Paillier to longer plaintexts, the Damgård–Jurik cryptosystem. It allows to encrypt plaintexts from $\mathbb{Z}_{n^s}$, with a ciphertext in $\mathbb{Z}_{n^{s+1}}$, for any $s$ (Paillier is just the case $s=1$). Hence, you can directly encrypt $c\in\mathbb{Z}_{n^2}$ with the Damgård–Jurik scheme for $s=2$, and get a ciphertext in $\mathbb{Z}_{n^{3}}$. This approach gives a result more compact than the previous one ($3\log_2(n)$ bits in total, as opposed to $4\log_2(n)$ bits with the previous approach).


Is script execution time a decent source of pseudorandom number generation?

AFAIK, there are papers that show, for example, that process times are not so random as they may seem. This is in the context of operating systems gathering entropy for devices like /dev/random. I've read this in many places but I can't provide any reference (if someone could it would be great ;-)).

Having said that, if you have other sources of entropy, script time could be an additional input, of course. Some considerations that come to my mind are:

Take care with the resolution of your time source: if the maximum resolution is minutes, it will probably return always 0.
Run some tests to see what results you get and how they are distributed. A usual distribution could be that 1 is returned 20% of the time, 2 30%, 3 30%, 4 20%, for example.

Depending on how you plan to use these "random values" these considerations may alter the results one way or another.

My advice is that you use a decent entropy generation algorithm instead of trying to invent your own. You can start your quest, for instance, here:

https://en.wikipedia.org/wiki/Fortuna_(PRNG)

See the reference links for more algorithms.


Question about the Proof of "Pseudorandom generators imply one-way functions" in "Foundations of Cryptography"

Let $n\in \mathbb{N}$, and fix $x,y \in \{0,1\}^n$, $f(x,y)=G(x) \in \{0,1\}^{2n}$. By $f$'s definition, $$\forall x,y_1,y_2 \in \{0,1\}^n,\;f(x,y_1)=f(x,y_2).$$
Hence, if we define the function $f'\colon\{0,1\}^n\to \{0,1\}^{2n}$ by $f'(x)=f(x,0^n)$ we get that $\operatorname{Im}(f)=\operatorname{Im}(f')$ and $\lvert\operatorname{Im}(f')\rvert\le \lvert\{0,1\}^n\rvert=2^n$.


ElGamal signature scheme: Why is r included in s

With your proposed modification of the ElGamal signature scheme you can produce forgeries for arbitrary (hashed) messages $m$.

By looking at the verification equation $$g^m = yr^s$$ you just have to set $r$ to $r=(g^my^{-1})^{s^{-1}}$ (just by rearranging the verification equation) which you can do for any $s$ from $\mathbb{Z}_{p-1}^*$, i.e., every $s$ that has a multiplicative inverse in $\mathbb{Z}_{p-1}$.


Passwords are not keys. Keys consist of a specific number of randomized bits. So to encrypt a file using a password (password based encryption or PBE) you first need to create a key from a password.

Password hashes or Password Based Key Derivation Functions are the schemes that consume a password, a salt, a work factor (or iteration count) and possibly other parameters (parallelism, memory usage) and then produce a key. Known PBKDFs are PBKDF2, bcrypt, scrypt and Argon2.

The salt is mainly used for two reasons: making sure that duplicate passwords do not derive the same key and avoiding rainbow table attacks. Producing the same key is not a big issue during encryption; you can use an IV to create a different ciphertext. Rainbow table attacks are more problematic: you can create a table with keys derived from passwords and try and decrypt: this would allow an attacker to test keys without minding the work factor.

As you can also derive an IV with a PBKDF you might as well use a salt. This would make PBE indeed more secure for the reasons stated above. So yes, you should use an up to date PBKDF such as Argon2, a strong password, a large work factor and - indeed - a salt during encryption.


What does this notation means $\mathbb{F}_{2^{-}}$?

You've been confused by the placement of the "-".

It's not $\mathbb F_{2^-}$ (Latex: $\mathbb F_{2^-}$), this does not exist. What was actually meant is $\mathbb F_2$-adjective (Latex: $\mathbb F_2$-adjective), where the hyphen binds the field and the adjective (eg "linear" or "affine") to bring more specific meaning to the adjective.

Example:

  [...]with an $\mathbb F_2$-affine permutation[...]

You would have read "with a permutation that is affine in $\mathbb F_{2^-}$" as opposed to the intended meaning of "with a permutation that is affine in $\mathbb F_2$".


You're right. In general if a $g$ is not a primitive element of $\operatorname{GF}(p)$ it generates a smaller subgroup of $\operatorname{GF}(p)^{\ast}.$ Since $|\operatorname{GF}(p)^{\ast}|=p-1$ is divisible by 2, this subgroup can be as small as 2 in size, and its size can take on any value $w,$ where $w \mid (p-1).$


What's a relatively fast way of checking if a string is decrypted English?

Searching purley for substrings in a string would be a programming question but since Stackoverflow already sent you here I will give it a try:

Java:

public class MyClass
{
    public static void main(String[] args)
    {
        String myString = "XPAWWALLTPJZYYZWBGSHGARECPVHDAAPLJLBGAPVTFVCWAS";

        int intIndex = myString.indexOf("ARE");

        if(intIndex == - 1)
        {
            System.out.println("ARE was not found");
        }
        else
        {
            System.out.println("Found ARE at index "+ intIndex);
        }
    }
}

C#:

using System;

public class MyClass
{
   public static void Main()
   {
      string myString = "XPAWWALLTPJZYYZWBGSHGARECPVHDAAPLJLBGAPVTFVCWAS";

      if (myString.Contains("ARE") == true)
      {
         Console.WriteLine("Found ARE");
      }
      else
      {
         Console.WriteLine("Word ARE was not found!");
      }
   }
}

These should both work.

You can then create a loop that searches the string for common words.


ElGamal: Why is reusing the same $k$ not secure?

In ElGamal encryption like you said for unknown $m_1$ and known $m_2$ we have:

$m_1: C_1=g^k\ mod\ p,\  D_1=m_1.g^{a.k}$

$m_2: C_2=g^k\ mod\ p,\  D_2=m_2.g^{a.k}$

$k$ is the same in both encryptions, by dividing $D_1$ and $D_2$ we have:

${D_1\over D_2}={m_1\over m_2} => D_1.m_2 = D_2.m_1$

$m_2$ , $D_1$ and $D_2$ and are known so now we can calculate $m_1$. This is how can attacker proceed and find unknown $m_1$.


How to prevent Public Key from being replaced entirely?

Also Can it be prevented If I store the Public key in a certificate store?

Well, an adversary could probably just overwrite that entry and mount the same attack as before.

  Now I have a problem, what if someone's signs the license file content with entirely new set of private\public key pair.

What you have stumbled across is the "trust problem" of public key infrastructures (PKIs). Namely that you need a binding between a public key and an entity.

In this case you want a binding between your public key and your identity as the software vendor. The simplest solution would be "pin" the public key (eg the SHA256 hash of it) in the verifying program so that it only accepts the public key / signature pair if the hash matches.  Of course this could be patched out of the software by an adversary wanting to elide the license check, but so could be the check altogether (DRM is hard)...

  It would be really get if you could add a few more lines on "pin" the
  public key part.

The idea of pinning is the same as is used for trusted root CAs in browser. You keep a copy of the public key you trust in your software package. Then when verifying the signature, you check whether the received public key matches (any of) the stored, "pinned" public key. If it does you proceed with verification otherwise you immediately return with an invalid signature error. If binary size is a concern you can also hash the incoming public key and compare the hash against a hard-coded hash.

In theory you could also pin a public key of your own "CA" and force all signatures to present a certificate signed by that CA, but it seems like the simple pinning of the data-signing public key should suffice and the additional scalability in number of keys is not needed.


Is it possible to test implementation for side-channel attacks?

At least for compiled languages it should also be possible to have
  tools that perform static analysis on machine code, shouldn't it?

Indeed, such tools exist. There are companies specialized in this domain which provide this kind of tools (see this datasheet for example). But you should note that an only software tool will not be able to detect all weaknesses against certain types of attacks (e.g. some fault injections).

  it should be possible for timing and maybe even cache based attacks

There is also CacheAudit which is a tool for the static analysis of cache side channels (plus, it's free). It can be configured to test your implementation against several architectures (e.g. separate or shared cache for data and instructions) and several attack models. Here is the description of the framework and you can download it here. To put it in a nutshell:

  CacheAudit takes as input a program binary  and  a  cache
  configuration  and  delivers  formal  security  guarantees  that
  cover  all  possible  executions  of the corresponding system.


Is it safe to use Diffie-Hellman with Schnorr group primes, or DSA with safe primes?

Safe, yes; efficient, no.

For DSA, that signature algorithm includes a clever trick that reduces the size of the signature to twice the size of the subgroup (the size of $q$).  Because of this, we want to reduce the size of the subgroup as much as possible (without cutting into security).  You could use a safe prime, but that means that the signature would end up being much larger than required.

For DH, there is no corresponding clever trick; the key share is the size of $p$.  However, there are two things which allow a performance difference:

We use use a small $g$ (often $g=2$); such a $g$ has order $q$, and so works perfectly well.  Such a small $g$ makes the initial modular exponentiation cheaper.  In contrast, with a Schnorr group, you have to use the $g$ which came with the group (which will be larger)
We can safely reuse private exponents.  With a safe-prime, if someone gave us a bogus key share, they could deduce the lsbit of our private exponent, but nothing else; hence, the leakage is minimal.  In contrast, with a Schnorr group, they can deduce our private exponent modulo $s$ for every small $s$ which is a factor of $r$ (where $p = rq+1$ is the Schnorr group); you could defend against this by either selecting $r$ is 2 times a prime (I haven't heard of someone doing that, but they could), or by raising the key share to the power of $q$ (which would eliminate any potential performance gain by reusing the private exponent).

You state that Schnorr groups are more efficient because $q$ is smaller; that is not true, because with a safe prime, there is no reason to select your private exponent randomly from the entire range $[1, q-1]$; you can select from a smaller range (for example, the range you would use if you used a Schnorr group); there's no known discrete log method that could use the additional information.


How does openssl signature verification work?

It depends on the type of key, and (thus) signature.

If it is an RSA key, by default OpenSSL uses the original PKCS1 'block type 1' signature scheme, now retronymed RSASSA-PKCS1-v1_5 and currently defined in PKCS1v2.2. OpenSSL commandline also supports the RSASSA-PSS scheme (commonly just PSS) defined in the preceding section of PKCS1v2.2, with the dgst -sigopt option (online copy of man page) whose relevant values are actually documented in the pkeyutl man page.

If it is a DSA key, OpenSSL implements the algorithm as specified by the standard, FIPS186 currently at revision -4 and available at https://csrc.nist.gov/publications/fips (edited: usually, but download currently hangs presumably due to the government shutdown even though the webpage does display which initially fooled me); a shorter, less bureaucratic and more reliably available description is in Wikipedia. One minor point not stated in FIPS186, or Wikipedia, is that the signature value, which is mathematically a pair of integers, is concretely represented using ASN.1 (as a SEQUENCE of two INTEGERs). (In contrast PKCS1 for RSA defines the representation of the signature, which is mathematically an integer in $[2,n-1]$, using the I2OSP and OS2IP primitives, as bigendian (unsigned) binary with size equal to that required to represent the modulus.)

If it is an EC key, OpenSSL implements ECDSA as specified by X9.62, which costs money, but is also available in document SEC1 at http://www.secg.org (which ironically can't easily be accessed by https because it has a mismatched certificate!), and again in Wikipedia. Again the signature is mathematically a pair of integers, represented in ASN.1.

All of the above sources cover signing, aka signature generation or creation, as well as verifying for a given algorithm.

If it is a GOST key, OpenSSL may or may not work depending on version and build or packaging; this support has fluctuated. And if it works I'm not familiar with what it does, except that it is somehow like ECDSA.

Note that the 'raw' format used by openssl dgst -sign/verify, and openssl pkeyutl -sign/verify which skips the (data) hashing step (and for RSASSA-PKCS1v1_5, optionally the ASN.1 encode/decode step), is not used by most other software. Most actual signatures (for things like emails and code files and XML or JSON data, and certificates and CRLs and OCSPs and timestamps, as well as the signatures used in protocols like SSL/TLS and SSH) are represented in a form that adds metadata about the signature algorithm and a way to find the publickey for verification, and often to validate that key, and sometimes contain or are attached to the data signed as well.


Decrypt digital signature using RSA public key with openssl

openssl rsautl expects a signature in binary format, not Base64-encoded. You should also check the signature scheme used. PKCS#1 v1.5 and PSS (PKCS#1 v2) are your best bets

The -verify switch is a bit misleading, the command only outputs the decrypted hash. You have to compare with the expected hash yourself.

Beware of the fact that the output will be the DER encoding of the SHA-256 hash.


Using cryptographic hash to match AES key size

Is this a sound way of doing things?

Depends. Where do the keys come from? If they come from a user's memory (e.g., a password) then no. The reason for this is that a simple hash if fairly fast to compute. Typically we recommend people use something like PBKDF2 or scrypt as they run through thousands of iterations. The effect of this is that computing this function once is still fairly fast and user won't notice the delay. Trying to brute force it, however, involves computing the function many, many times. This slows down a brute force attacker significantly. Also, scrypt in particular was designed to be slow on hardware. That means attackers can't throw a GPU or other hardware device at the problem to speed it up.

  Also since the output domain of sha256 is much larger than any key a "normal" person can remember, does this add security if an attacker gets hold of the password digest from for example a computer?

No. We often measure security in bits. In particular, bits of entropy. A deterministic function (like sha256) cannot create entropy.


trying to identify the key of a vigenere cipher via brute force

If you only think about Brute Force as an attack, then we first have to compute the number of possible keys: $77^{41} = log_2(77^{41}) \approx 2^{260}$. For Brute Force this would end up in 259-260 Bit security. Common sense is, that 128 - 256 Bit security is already save. Therefore your Cipher would be secure, if Brute Force is the only possible attack and the probability for someone guessing the correct key is negligible.
On the other hand there are better attacks for Vigenere. (It took several hundred years to find efficient attacks, but today it is said to be unsecure) The Kasiski attack may be best suited to attack your cipher, because the attacker knows the length of the key.
How you may make it more secure: A secondary layer of security is in many cases not useful (either is does not archive the wanted security, it does not make anything more secure or in some cases even make security worse). Creating a good secondary layer is often difficult.  One way to make your cipher more secure is using a bigger key. If you look at the Kasiski attack the attacker needs to know the length of the key. If you use different key length this may make that attack more difficult. You could also combine bigger key length with keys of different length.


Random Masking of Padded RSA Ciphertext through homomorphism

In the last bullet of the question, Bob computes $x^d\bmod N=m_p$. This the padded message $m$. Padding must be removed from $m_p$ by Bob to get back $m$. And serious problems can occur if Bob leaks at what step the padding check fails, just like in James Manger's A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0 (in proceedings of Crypto 2001).

If Bob leaks where the padding fails (e.g. by timing), and allows that to occur often enough (some thousands times) for different $x$ chosen by an adversary, then an active adversary can decipher a message, unbeknown to Bob, even though Alice would have refused to decipher the message should the adversary have asked Alice directly (because Alice authenticates who she accepts messages from).

There is no proof that having $(N,e)$ and the capability to raise to the power $d$ modulo $N$ (by querying Alice) does not allow Bob to factorize $N$ and get at $d$ (or an equivalent). That's only widely conjectured.

It should also be emphasized that Bob does not have $d$, but has access to something almost as good: the capability to raise to the power $d$ modulo $N$. And he can share that capability (by forwarding requests to Alice and her answers, or just revealing his credentials w.r.t. Alice).

Also: even with secure padding such as OAEP verified by Bob without leaking anything other than success/failure, Bob should still be careful that messages deciphered with the help of Alice that pass the padding check are in no way authenticated. For example, if a (genuine) message $x$ has deciphered to "the winner is Carol", and Bob later gets a message $x'$ that decipher to "repeat: winner is Malory", Bob should not leak that he is surprised, for that would reveal that the winner is not Malory to whoever (e.g. Malory) generated the bogus $x'$.

Aside of these, and standard implementation attacks on Alice and Bob (e.g. side-channel leakage), I see no other attack specific to the protocol.

Per comment: I do not see that the protocol is sensitive to minor imperfection in the generator for $r$, including w.r.t. Alice trying to get at $m$.


How fast is hashing and is it always regarded as an O(1) operation?

You are right. A hash function applied to $n$ bits of input will typically take $O(n)$ work to evaluate. It is important for a hash function to use every single bit of input as part of the calculation or collisions become very, very easy.
The "hashing takes time $O(1)$" is true for fixed/bounded length inputs, but as you say this is misleading.


Some literature said the running time of attack algorithm is measured by clock cycles.

I suspect that either you misunderstood what was written (sometimes we measure the speed of crypto algorithms in terms of clock cycles, because that is somewhat more platform independent than, say, time), or you have taken it out of context.
  I'll assume the literature was discussing the performance of a cryptographical algorithm, rather than an attack (which we generally do not feel the need to define the performance as tightly).

As for what a 'clock cycle' is, well, when we have a computer (CPU), then generally the CPU executes instructions based on a master clock (which runs, at least for periods of time, at a fixed rate); the various operations that the CPU performs to execute instructions are based on this master clock.  One 'beat' of this master clock is termed a 'clock cycle'; that is, if the instructions used to encrypt a byte of data in completed in 10 beats of this master clock, we say it runs in 10 clock cycles.

Of course, it turns out that real computers are rather complicated affairs, and so the above description is both vague and simplified.  They sometimes have multiple independent clock implementing different parts of the processor, and sometimes the rate of the clock will vary (because of a number of reasons).

What 'clock rate' can be used to compare the efficiency of two different algorithms on the same processor, as it (mostly) factors out the differences between absolute clock speed; for example, it can be used even if one processor is running at 2GHz and the other at 3GHz.  However, comparing 'clock rates' between different CPU types (for example, Intel and ARM) makes absolutely no sense; in fact, it makes little sense to compare clock rates of different Intel internal architectures.


Question about second preimage resistance of hash function combiner

The answer you are looking for is that a pre-image/2nd pre-image attack on two combined hash functions is at least as difficult as an attack on the stronger of the two hash functions.

Take a look at Joux's paper on multi-collisions. There is a section on pre-image attacks for concatenated outputs. (I suggest reading the entire thing. It's one of those rare short, to the point, easy to read papers.)

The attack described in the paper has complexity of:

$n_g2^{{n_f}/2} + 2^{n_f} + 2^{n_g}$

For two hash functions of length $n_f$ bits and $n_g$ bits where $n_f \leq n_g$


Which elliptic curves are quantum resistant?

Post-quantum crypto is a very young field and is still changing quite rapidly. If you just want a reading list to introduce you to the topics, I would recommend the March 2015 report released by the EU's PQCrypto Project, and the April 2016 report from NIST.

As of today, here's an (incomplete) list of candidate algorithms for post-quantum cryptography with a link to the best reading material I could find for each:

Hashes: everything we have now is fine, you just have to double the output size against a Grover search:

SHA-2 256 and up
SHA-3 256 and up (aka Keccak)

Hash-based Signatures:

XMSS
Sphincs

Symmetric Encryption: everything we have now is fine, you just have to double the key size against a Grover search:

AES 256

Asymmetric Encryption (some of which also include signature schemes, but why would you when hash-based sigs work so well?):

NTRU (lattice-based cryptography)
McEliece (code-based cryptography)
Ring Learning with Errors (R-LWE) (lattice-based cryptography)
Multivariate polynomials (no specific algorithm yet)
Isogenies on supersingular elliptic curves (no specific algorithm yet)

Since you specifically asked about elliptic curves, you'll notice that ECC in its current form is not on this list. That is because the discrete log problem of reversing elliptic curve point multiplication is easily solved by Shor's algorithm on a quantum computer.

That said, elliptic curves do appear on the list in the form of isogonies: transformations mapping a point on one curve to a point on a (potentially) different curve are conjectured to be hard to invert on both classical and quantum computers.

Personally this is my favourite algorithm from the list above for two reasons:

The keys are smaller and the runtime faster than the other approaches
The other approaches all have the flavour "do some linear algebra which is possible for Eve to invert, so sprinkle in some error that both Bob and Eve have to guess in order to widen the computational gab between them. This fundamental approach makes me kinda uneasy.

The more future-proof answer to this question is to watch NIST: they are gearing up to run a competition-like thing over the next 18 months to select the best post-quantum encryption primitives.


(It seems that the proof can be salvaged.)

Let $\text{RLWE}$ denote the standard ring-LWE problem where the secret $s$ is drawn uniformly at random from $R$. Thus, the $\text{RLWE}$ assumption is:
   $$(a,as+e)\approx(a,r):a,r,s\leftarrow R, e\leftarrow\chi,$$
where $\approx$ denotes computational indistinguishability.
$\text{RLWE}$ assumption implies the non-standard LWE assumption [Lemma 2, ACPS09], denoted $\text{RLWE'}$, where the secret is drawn from $\chi$:
  $$(a,as+e)\approx(a,r):a,r\leftarrow R, s,e\leftarrow\chi.$$
The hardness of the promise problem, denoted $\text{RLWE''}$, follows by a hybrid argument (see below) assuming $\text{RLWE'}$ holds. Thus, the chain of reduction is:
 $$\text{RLWE}<\text{RLWE'}<\text{RLWE''}.$$

The hybrid argument. We want to show that the two distributions
  $$D_L:=(a_0,a_1,a_0s+e) \text{ and } D_R:=(a_0,a_1,a_1s+e)$$
are computationally indistinguishable, for $a_0,a_1\leftarrow R$ and $s,e\leftarrow \chi$. Consider the hybrid distribution
  $$D_H:=(a_0,a_1,r)$$
where $a_0,a_1,r\leftarrow R$. We show that $D_L\approx D_H$ and $D_H\approx D_R$, and it follows by transitivity that $D_L\approx D_R$.

To see that $D_L\approx D_H$, suppose for contradiction that it is not: that is there exists an algorithm $\mathsf{A}$ that distinguishes $D_L$ from $D_H$. We show that $\mathsf{A}$ can be used to break $\text{RLWE'}$. The reduction $\mathsf{R}$ is straightforward: given a $\text{RLWE'}$ challenge $(a,b)$ (where $a\leftarrow R$ and $b$ is either $as+e$ or $r$), $\mathsf{R}$ samples $a'\leftarrow R$ and sends $(a,a',b)$ to $\mathsf{A}$ and outputs to its challenger whatever $\mathsf{A}$ outputs. If $b=as+e$ then $\mathsf{A}$ simulates $D_L$; otherwise it simulates $D_H$.

The argument showing $D_H\approx D_R$ is similar.

References.

[ACPS09] Applebaum, Cash, Peikert and Sahai. Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. CRYPTO 2009.


The easiest way would be to make use of a trusted third party. In this way, users can authenticate to the trusted party (maybe with the cellphone/IMEI number) which then issues them with a "ticket" or "group/blind signature" along with a pseudo-identity, similar to those used in e-voting schemes. The pseudo-identities can then be checked for duplicates.

Without a third party, I think it will be hard for you to proof that each user is unique even if you have access to all his sensors. e.g. user can always change his current location to change the gps, temperature, illumination, and humidity sensor readings.


You can just follow the instructions on HotBits, which is exactly what you're trying to build. It's been running for years and is the only radioactive TRNG on the internet. It goes into great depth regarding underlying nuclear physics, sample distributions and extractor mechanism.
Although not really within the realms of strict cryptography, there is also a good counting analysis here from Caltech. In a nutshell, at low count rates the click rate follows a Poisson distribution. But as the mean click rate $(\mu$) increases, it morphs into a nice symmetrical Gaussian shape which is typical behaviour of Poisson if $\mu > \approx 20$.
If you can get a good tube and a decent/safe source, it'll be pretty simple if you follow the instructions.  Don't worry about the tick distribution. Simply detect the ticks and follow the de-biasing procedure in the sections featuring this:-

It's a reversing von Neumann extractor. It's written up so I won't repeat the details. If tube dead times and saturation levels are met (so that there is no autocorrelation), you'll get uniformly distributed random bits popping out of the de-biasing algorithm. So that we can see HotBits' quality, I downloaded their 91 Mbit data set and ran ent over it:-
Entropy = 1.000000 bits per bit.

Optimum compression would reduce the size
of this 91750400 bit file by 0 percent.

Chi square distribution for 91750400 samples is 0.05, and randomly
would exceed this value 81.93 percent of the times.

Arithmetic mean value of data bits is 0.5000 (0.5 = random).
Monte Carlo value for Pi is 3.141486168 (error 0.00 percent).
Serial correlation coefficient is -0.000773 (totally uncorrelated = 0.0).

They have other more stringent testing on their site, but it's a clean pass at this level. Chi square also answers your "is it really necessary to have uniformly distributed random bits to have good generator?" mini question. Yes, they do have to be uniformly random for cryptographic use.
So do what HotBits does.

Please note this though:-

the increased sensitivity of the RM-80 and its immunity from saturation increased the rate of HotBits generation from about 30 bytes per second to more than 100.

It's not fast. And there's all that high voltage stuff.


Hill cipher cryptanalysis - known plaintext known key size

Let $k=\left(\begin{array}{cc}k_0 & k_1\\k_2 & k_3\end{array}\right)$ be the key. And I'll assume the transformation $a=0$, $b=1$, and so on.

So you know $k\left(\begin{array}{c}0\\1\end{array}\right)=\left(\begin{array}{c}c_0\\c_1\end{array}\right)$ where you know $c_0$ and $c_1$.

Thus $c_0=0k_0+1k_1$ and $c_1=0k_2+1k_3$. So that is two equations, 4 unknowns. Can't be solved yet. But you have more data which gives you $c_2=2k_0+3k_1$, $c_3=2k_2+3k_3$, $c_4=4k_0+5k_1$ and $c_5=4k_2+5k_3$. Now you have 6 equations and 4 unknowns. Setup a system of linear equations and solve. That will give you the $k_i$ values for your key. The decryption key is just the inverse.

Remember that the math is done modulo 26.

You won't always be able to solve the system of linear equations, but you likely have enough plaintext ciphertext pairs to get it done. Using the PT/CT pairs in the comments, for example, you would end up with the following equations for $k_0,k_1$.

$$
\begin{align*}
2k_0+17k_1&=11\\
24k_0+15k_1&=3\\
19k_0+14k_1&=3
\end{align*}
$$

From there, my preferred method is to take two of the equations, build an augmented matrix and put it in reduced row echelon form. So you'd first have

$$\left(\begin{array}{cc|c}19&14&3\\2&17&11\end{array}\right)$$

Instead of doing all the math, I'll just get you started. Start by multiplying the first row by $19^{-1}=11$. Then you would have

$$\left(\begin{array}{cc|c}1&24&7\\2&17&11\end{array}\right)$$

Then you want to get rid of the $2$ on the second row, so do $row_2=row_2-2row_1$. Eventually you'll be in the right form and have $k_0$ and $k_1$. Repeat this process for $k_2$ and $k_3$. For this one it will work out. If you had started with the $3=24k_0+15k_1$ row on top, you may have gotten stuck since $24$ has no inverse. So if you get stuck (needing to invert something that is non-invertible), try a different equation or a different set of elementary row operations.


How passwords are fed to key derivation functions?

You are correct: generally it is required to synchronize or otherwise synchronize information if you want to use a password based key derivation function (PBKDF) for sending messages.

That doesn't mean that using a password on the client side a derived key on the server side doesn't have advantages:

the password isn't stored on the server side, so an attacker may not be able learn the password if the backing database is stolen;
the password nor key needs to be stored client side (and a key is not so easy to remember) so stealing the device on the client side will likely not lead to any breach of the protocol.

That said, a PBKDF is commonly not used for sending messages in an online protocol. Instead a password based key agreement or PAKE could be used to authenticate the client and establish symmetric keys. However, a PAKE also requires a setup phase. In Augmented PAKE the server doesn't learn the password, only a derived value used for verification.

In the end, there is nothing asymmetric about password based encryption; the password is a secret; that secret or a derived value needs to be shared with the authenticating party.

Note that often the client application is often also from the same organization as the server. This means that the client will have to rely on the organization's security at some point - whichever cryptographic protocol is used. It's only possible to mitigate that problem as much as possible.


As $n$ is the product of primes $p$ and $q$, $\varphi(n) = (p - 1)(q - 1)$ and $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$. The former multiplies $p - 1$ and $q - 1$, whereas the latter finds the least common multiple of the two. Naturally, $\forall a,b:\operatorname{lcm}(a,b) \le a\cdot b$, so we can say that $\forall n:\lambda(n) \le \varphi(n)$. In the case that the LCM for $a,b$ is $a$ and $b$ themselves, then they will be equal. Otherwise, the LCM will always be smaller. As $p$ and $q$ are always primes and therefore odd, we have $2\mid\gcd(p - 1, q - 1)$, thus $\lambda(n) < \varphi(n)$.

So yes, it is true.


With a true random number generator at hand, how to implement one-time pad?

There are four concerns here:

Pad generation
Pad transmission
Message privacy
Message authenticity

Pad generation

The security of the one-time pad depends on the assumption that the pads are generated from a truly random source.

This is actually quite a big ask. Suppose for a moment that you want to exchange a 4 gigabyte pad. Let's say your RNG does that one byte at a time. What you're basically asking is for billions of iterations of the RNG without any kind of generation failure.

Worse, the RNG can fail in a way that is not immediately obvious or detectable. The Debian bug springs to mind here.

Or, more directly, a nation state could deliberately weaken your RNG.

Pad Transmission

The next problem is finding a secure way to transfer the pad. The pad will be longer than the message you wish to transmit, at least if you want to be able to detect alterations to your message. See below.

This immediately raises the question of what one hopes to gain by using the OTP. If you have a secure channel capable of transmitting a pad longer than the original message, why not just use this channel to transmit the message?

Given this logic, there is only really one use for the OTP, which is to time-shift a secure channel. For example, I might be able to meet my friend in the pub and give him a terabyte of pad but afterwards he might be abroad for two years.

Message Privacy

Assuming you've solved the problems of generation and transmission, next comes actually encrypting your message. This is the most straightforward piece of the whole exercise.

You just work through your message a word at a time and logically XOR that word with a corresponding one from the pad. No part of the pad may be re-used under any circumstances. It's best to have your program destroy the read section of the pad after completing the encryption operation.

Decryption on the other end is exactly the same process. Simply logically XOR the cipher-text with the pad to recover the plain-text. This works because XOR is its own inverse:

A XOR B XOR B = A

Message authenticity

One of the things that trips up amateurs is that encrypting your data doesn't means that nobody can undetectably alter the message in transit.

Suppose that an ATM used the OTP to encrypt its communications but no authentication. I have £0 in my bank account but I ask the ATM to give me £500. The bank replies with a single bit message which indicates whether the withdrawal is authorised or not: 1 for yes, 0 for no.

I know the bank is going to decline me so at precisely the right moment, I flip the bit before it gets to the machine. The machine spits out the £500.

You get around this problem by having a message authentication code (MAC). This is an authentication code you tack on the end of the message which acts as a secure checksum.

If I tried to flip the bit on a message with a MAC protecting it, the checksum would not longer verify and the system would know something funny is going on.

To authenticate OTP messages, you probably want to use a universal hash. This allows you to retain the security proof on both the hash and the cipher-text.

Universal hashes are a whole series of questions and answer in their own right so I'm just going to say that you should read around the subject.

Conclusion

The OTP is one of these ciphers that lot of amateurs gravitate towards because it's "perfectly" secure.

However, in reality we don't deal with perfection. We often don't have a secure channel with which to communicate a pad. We often don't have an RNG that has a failure rate of fractions of a billion or trillion. There are often cockups that result in pad being re-used.

For all of these reasons, competent cryptographers never recommend an OTP.


Proof of work for determining whether a number is prime?

First off: Divisibility testing is an atrociously bad way to check whether a number is prime or not.  It is horribly inefficient and ineffective.  You need to first read up on the literature on primality testing before you think about how to distribute it among untrusted clients.

Use any standard primality test.  Give each client a different iteration of the test, and have them send you the result.

For instance, you could use Miller-Rabin primality testing.  The idea of this primality test is that you choose a random value $a$, then do some computation based upon $a$ (e.g., you compute $a^d \bmod n$, and some other stuff that I'll ignore for simplicity); this might result in a proof that $n$ is not prime, or it might result in nothing.  If you do this 10 times with 10 different random values $a$, and none of them find a proof, then it's very likely that $n$ is prime.

Here's how you could distribute Miller-Rabin primality testing:

Choose a few dozen clients randomly.
For each client, pick the value $a$ randomly.  Give the client $a$.  Ask the client to compute $a^d \bmod n$ and send it back to you.
If any client claims to have found a proof that $n$ is not prime, send the same $a$ to 4 other randomly chosen clients.  If at least 3 out of those 5 clients give you the same value for $a^d \bmod n$, then probably all 3 of those were honest and probably $n$ is not actually prime.
If none of the clients found a proof of non-primality, then probably $n$ is prime.
If you ever want to confirm that a particular client did its work correctly, send the same value $a$ to a few other clients and see if they all return the same value for $a^d \bmod n$.

You can adjust the parameters (the number of clients selected, the number you require to agree before you accept the result is probably correct, the number of iterations of Miller-Rabin) based upon how much confidence you require and what fraction of your clients you think are honest.

I expect this framework ought to lead to an efficient way to test primality of even very large numbers.  If it doesn't suffice in your setting, then you should edit your question to provide more specifics of why it does not work and what you have tried.


A group if a set of elements and some operation that satisfy some requirements. This operation is usually called "addition" or "multiplication", depending on the group, even though it may not be actually the classic addition or multiplication. The integers $0 < x < p$ for some prime $p$ form a group under the modular multiplication operation (multiply the integers, then compute the remainder of the division by $p$). This group can be denoted by $\mathbb{Z}_p^*$.

A field is a set of elements with two operations that satisfy some requirements; you can think about it as consisting of two groups (one for each operation). The integers $0 <= x < p$ for some prime $p$ form a field under modular addition and multiplication. This field can be denoted by $\mathbb{F}_p$.

That is the field that is used by FFC DH. However, note that DH only requires a group, and not a field. FFC DH uses the multiplicative group of the finite field, i.e. $\mathbb{Z}_p^*$; the addition operation is never used.

An elliptic curve is a set of $(x, y)$ coordinates ("points") that satisfy some equation. In cryptography, these coordinates are elements of a finite field, e.g. $\mathbb{F}_p$. The curve also forms a group under the "point addition" operation, which takes two pair of points and return a third point also on the curve. Note that a curve forms a group, and uses an underlying field, but it's not a field itself.

(A curve has a "point multiplication" operation, but that's not a group operation between points, it's simply repeated addition, like exponentiation in $\mathbb{F}_p$ is just repeated multiplication).


Non-interactive proof that an element is in a subgroup

My guess would be that they have a proof that their scheme has the zero-knowledge property if the challenge comes from the set $\{0,1\}$, whereas the proof doesn't work if the challenge comes from the set $\{0,1,2,\dots,2^{160}-1\}$ -- and they don't know how to construct an alternate proof to show the latter.

If you want to understand why their proof doesn't work for larger challenges, you should start by reading through their proof for small challenges and see if each step remains valid for large challenges.

For instance, you might find there is a rewinding step that works if the challenge comes from the space $\{0,1\}$ but doesn't work if there is a large challenge space.  This is a common phenomenom in rewinding-based proofs.  If the challenge space is $\{0,1\}$, you can rewind the challenger and run the protocol forward, and with probability $1/2$ the resulting challenge will match what you want it to be.  Thus, on average, you only need to try twice, and that's fine.   In contrast, if you used a random 160-bit challenge, the probability of success on rewinding would be only $1/2^{160}$, so you'd need to try $2^{160}$ times, which is not feasible.  As result, many rewinding proofs work fine if you have a 1-bit challenge but fall apart if you have a 160-bit challenge.  This poses a barrier to proving the zero-knowledge property using large challenges, using this kind of proof technique.  If the only way they know to prove the zero-knowledge property is using this sort of rewinding proof technique, then that'd explain why they propose a 1-bit challenge.


NIST random test suite choosing bitstream length and count

Look for the document "NIST Randomness Testing SP800-22b.pdf" (or more recent updates if available) in the NIST website.

My guess is that your sequences are way too short (32 bits long) and no kind of statistical convergence can be expected to occur, which is necessary for the test to work. I presume this may be the reason why you get the error message.

The section "sequence length", p.102 in the NIST document states:

  The determination as to how long sequences should be taken for the
  purposes of statistical testing is difficult to address. If one
  examines the FIPS 140-1 statistical tests, it is evident that
  sequences should be about 20,000 bits long.

Coupled with this, you have 1 million such outputs. Depending on the conditions of how these outputs were obtained, you may want to concatenate them into longer outputs, in some principled manner.


What is an accurate definition for a 'Monoalphabetic substitution cipher' and why does it provide a poor level of security

A monoalphabetic substitution cipher uses a fixed permutation of an alphabet $A$ namely $$\pi:A\rightarrow A,$$ to encrypt a plaintext $P=(P_1,\ldots P_n)\in A^n$ of length $n$ into the ciphertext $C=(C_1,\ldots,C_n) \in A^n$ via $$C_i=\pi(P_i),\quad i=1,\ldots,n.$$

For a natural language, the letter frequencies are non-uniform. Thus, given a long  enough ciphertext, the original text can be easily recovered.

The length of plaintext required for unique recovery of the ciphertext is called the unicity distance, see here defined by Shannon, and is related to the redundancy in English, which is a result of the non uniform letter distribution. Most models of English give a unicity distance of around 30 letters.

Edit: To see how easy it is to attack monoalphabetic substitution, consider the letter frequencies of English, say as shown here. The four most common letters (E,T,A,O) have a total probability of around $0.38$. Thus if we have a 30 letter ciphertext (in a ciphertext only attack), the number of occurences of the letters in the set $$\mathrm{U}=\{\sigma(E),\sigma(T),\sigma(A),\sigma(O)\}$$ is highly likely to be the four most common ciphertext letters, and on average about $0.38 \times 30 \approx 11$ letters will belong to this set. There are only $4!=24$ permutations of this set and trying all will likely expose some English like fragments, helping in the cryptanalysis.

The probability that less than, say $t=8$, ciphertext letters belong to $\mathrm{U}$ can also easily be evaluated using the binomial distribution $\mathrm{Bin}(40,0.38).$

This attack can be further strengthened by considering common digrams (two consecutive letters), trigrams etc. and forming hypotheses on those, not only is the letter $\sf{T}$ very common, the digram $\sf{TH}$ is very common in English, etc.

One good countermeasure to protect this encryption to some extend is to use a Homophonic substitution, i.e., a new alphabet of larger cardinality and splitting the letters of English more or less uniformly, where each common letter is mapped to more than one new ciphertext symbol pseudorandomly.
Simon Singh's website describes this rather well here. However by no means does this countermeasure provide modern cryptographic strength against computer based attacks.


Why is "multiplying" $g^x$ and $g^y$ not possible?

$g^x \cdot g^y \;\;\; = \;\;\; (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x$ of them] $\ldots \cdot g\cdot g\cdot g) \: \cdot \: (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.03 in}y$ of them] $\ldots \cdot g\cdot g\cdot g)$

$= \;\;\; g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x\hspace{-0.05 in}+\hspace{-0.05 in}y$ of them] $\ldots \cdot g\cdot g\cdot g \;\;\; = \;\;\; g^{\hspace{.02 in}x+y}$


What do recent announcements about solving the DLP in $GF(2^{6120})$ mean for RSA

Göloğlu, Granger, McGuire, and Zumbrägel broke the DLP in the Galois finite field with $2^n$ elements for $n=6120$, and Antoine Joux did it for $n=6168$, with modest computing power. These recent announcements directly imply that cryptosystems (if any) based on the DLP in a field with $2^n$ elements are no longer secure, including for $n$ big enough that this finite field was previously thought to be of cryptographic interest (e.g. for pairing schemes), at least when $n$ is of the forms explained here enabling the new attacks.

One way to see the Galois finite field with $2^n$ elements, $GF(2^n)$ or $\mathbb{F}_{2^n}$, is as the set of $n$-bit vectors representing the coefficients of a binary polynomial of degree $n-1$, with as additive law the addition of binary polynomials, and as multiplicative law (of interest in the DLP) the multiplication of binary polynomial followed by reduction modulo some suitable binary polynomial of degree $n$.

RSA and DSA work on different algebraic structures:

RSA works on the finite unit ring of integers modulo $N$, with $N$ a public composite of secret factorization, which factors are huge primes. Notice that the number of elements in this ring is $N$, and thus not of the form $2^n$.
DSA works on the finite field of integers modulo $P$ for a public prime $P$ (such that $P-1$ is divisible by some suitably large prime, which is the order of a multiplicative subgroup; thanks to Samuel Neves for pointing my earlier serious mistake on that). Notice that the number of elements in this field is $P$, and thus not of the form $2^n$.

Because of these different algebraic structures, I can confidently tell that the algorithms used in these recent announcements are not directly usable against RSA and DSA. In my not so informed opinion, for the same reason, they are not directly usable against schemes based on the DLP on elliptic curve groups, including when the base field of the elliptic curve is some of the $GF(2^n)$ that are common practice for ECDSA. In fact I can not spot any cryptographic scheme in wide use that is directly impacted.

As of future advances against RSA, DSA, and Elliptic Curve cryptographic schemes, that may be enabled by these recent developments, my opinion is near worthless, for I'm not a competent number theorist. But I can still commit my feeling: I'm not too worried for the security of RSA, DSA, DH; and ECDSA or ECDH over elliptic curve groups with base field $GF(P)$, or even $GF(2^n)$.

Additions: The $n$ in the new attacks is large (compared to $2048$ or $4096$, previously thought safe and very safe levels) because the attackers can, and bigger values better demonstrate the power of their techniques.


Remark: in One Time Pad the pad is used once, thus this is not OTP, since here $k$ is reused.

Hint for part 1: Write the relations between $k$, the message blocks $m_i$, the ciphertext blocks $\small C_i$ with the convention $\small\text{IV}=\small C_0$. Then, find equations that allow computing the desired $m_3⊕m_4$ from known quantities.

Hint for part 2, textbook variant: What is the definition that a cipher is not IND-CPA secure? Exhibit whatever that asks.

Hint for part 2, shortcut variant: IND-CPA implies that, for random plaintext, nothing can be learned about the plaintext given the ciphertext.


Is it worth applying a MAC on data in a HSM?

Designing an HSM or other secure device is relatively easy; making it reliable even in the absence of adversary requires careful engineering; making it safe against adversaries with some level of physical access is hard; demonstrating that it is safe (for some definition of that) is even harder.

One thing to worry about is integrity of stored data (including keys) w.r.t. to both accidental events and deliberate attacks. One should consider problems often neglected in other embedded developments:

memory writes during power loss, which can leave a data block partially erased or written, in manners depending heavily on technology:

for RAM, it is easy to observe a data block left partially written, with e.g. low addresses holding new data, high address still holding old data;
sometime it can be observed that in between, a word is garbled apparently randomly;
for EEPROM and Flash, the physical erasure before write (typically, with alignment to some page boundary) is often apparent;
with EEPROM or Flash, it might be observable that some memory cells are left in an unstable state where the content read (until another erase or write) will vary randomly, or/and as a function of operating temperature (if you do not trust me on this one, ask the IC vendor to put in writing what it guarantees about what's read in memory that was being written or erased at time of power loss, with rationale at the physical level to support that);

non-deterministic CPU operation, which itself can occurs when operating conditions (e.g. power supply) are non-nominal, and there is no adequate (e.g. voltage) sensors to block operation in these conditions;
cosmic rays; incidence vary enormously with memory technology, capacity, altitude, solar activity, location on surface of earth, and (metaphorically) phase of the moon; search Single Event Upset RAM for references;
deliberate fault attacks trying to cause or simulate some of the above.

Carefully designed and tested measures (software and/or hardware) to deal with at least power loss is a must. Some kind of integrity protection on top of that is a good idea. One option is to substitute AES-128-CBC with AES-GCM; another is to use a separate MAC, e.g. HMAC-SHA1 (if we neglect side-channel leakage issues, it is fine to do this on the plaintext, and probably fine to use $k_r$ as the HMAC-SHA1 key, though $\operatorname{AES}(\operatorname{key}=k'_m,\operatorname{data}=k_s)$ would be more academic and work with any MAC). If that's tolerable from a functional standpoint, moving the HSM to a zeroized state in case of error is the safest from a security standpoint (but zeroization itself requires care; something like "on error detected erase $k_s$", where that erasure is performed in two halves, potentially leaves open to an attack halving the effective key size).


What are the disadvantages of XOR key derivation?

The two main concerns I'd have with the scheme you describe are 1) the risk of one of the subkeys being compromised, and 2) related-key attacks on the cipher.

The first concern is obvious: since the XOR operation is reversible, if an attacker finds out any one of the subkeys and knows the corresponding salt, then they can recover the master key.

Of course, if you can guarantee that all the subkeys are just as well protected as the master key, then this may be a non-issue.  But an extra layer of safety in case of subkey compromise can still be a nice thing to have, and using a non-reversible key derivation function instead of just XOR provides it at a very low cost.

The second concern is a bit harder to quantify.  There are known related-key attacks against AES, but so far none of them are efficient enough to be a real threat in practice.  Still, they do demonstrate that AES does not necessarily deliver its full advertised level of security in situations where an attacker may know the XOR of two or more keys.

As before, assuming that no new and significantly better related-key attacks against AES are found, you might be able to get away with this in practice.  (We do need to make some assumption like that anyway, given that nobody has proven AES to be secure, with or without related keys.)  But again, the safe and conservative choice would be to use a proper key derivation function that does not reveal any mathematical relationship between the subkeys.


Since your q is composite with factors 3,7,19 we get $\phi(q)=(3-1)*(7-1)*(19-1)=216$ and not 398 The rest of the calculation follow as in the question.

And since $p=2$ we get also $\phi(n) = 216$

As a result we also get $d=e^{-1}=7^{-1}=31 \bmod 216$

And we can verify that $669^{31} \bmod 798 =123$ as expected.


What weaknesses in Hash_DRBG did NIST find and fix?

Please bear in mind that this information is all secondhand. I have not looked closely at the original drafts of Hash DRBG (although you might find a draft that's early enough if you peruse the FOIA results in [1]).

However, during conversations with folks at NIST I was told that there were certain weaknesses in early drafts of Hash DRBG that were very similar to known issues in the FIPS 186 (DSA) DRBG. Kelsey, Schneier, Wagner and Hall have at least one paper on this [2]. In particular, if an attacker is able to control some of the entropy inputs to the DRBG, they could force that DRBG to repeat output. I gather from these discussions that the original draft of Hash DRBG had similar issues. The version published in NIST SP 800-90A was modified to deal with these.

It's important to note that I'm not saying these flaws were deliberate. Quite frankly they just look like bugs. And they appear to have been fixed long before to the publication of NIST SP 800-90A. I also can't state with certainty that Hash DRBG was an NSA design, though I believe the NSA was involved in its design.

One more note: it's my understanding that Hash DRBG was eliminated in the ANSI standard because it was deemed redundant, but it was kept in NIST SP 800-90 (though in repaired form) because the NSA asserted that some partners had already implemented it. Hash DRBG was also included in ISO 18031, some portions of which I can probably dig up and add to this link later. It's not clear whether the ISO version includes the repairs.

Welcome to our crazy world!

[1] https://github.com/matthewdgreen/nistfoia
[2] https://www.schneier.com/paper-prngs.pdf


What does DH(IPKa, IPKb) notation mean? Diffie-Hellman confusion

As X3DH uses elliptic curve Diffie-Hellman, I'll write things in elliptic curve notation thus if we have a curve $E$ with $q$ points and a base point $G$ we might see Alice choose a private key $a\pmod q$ and create a public key $A=aG$. It should be easy to convert to multiplicative notation if you need to.
Regular Diffie-Hellman
In the regular form of the Diffie-Hellman, Alice and Bob each choose a single private value $a$ and $b$ respectively, and generate public keys $A=aG$ and $B=bG$ which they then exchange. In the notation of the question
$$\mathrm{DH}(A,B)=aB=bA=abG$$
is the shared secret value. Although it is written as a function of $A$ and $B$ this is in a mathematical rather than a computational sense. It should be infeasible to compute $\mathrm{DH}(A,B)$ without knowledge of one of the private values. This notation can be frustrating.
People talk about static Diffie-Hellman and ephemeral Diffie-Hellman depending on whether the same values are used over multiple exchanges or whether new values are generated for each exchange. Static Diffie-Hellman gives some assurance that you are communicating with the same person in both exchanges. Ephemeral Diffie-Hellman prevents the same key being generated and provides forward security which is the assurance that if a private key becomes known, it only jeopardises a single message rather than any previous ones.
X3DH
X3DH tries to create keys with the benefit of both the static and ephemeral versions. It has Alice and Bob choose multiple secret values and public values, say $a_0$, $a_1$ etc. and perform multiple DH computations to combine the results. In particular, they both create long term identity keys $IK_A=ik_AG$, $IK_B=ik_bG$; they create medium term signed keys $SPK_A=spk_AG$ and $SPK_B=spk_bG$ which change from time-to-time but are digitally signed so that users can be assured that they are only used by the claimed user; they create several one-time-keys. In particular then
$$\mathrm{DH}(IK_A,SPK_B)=ik_ASPK_B=spk_BIK_A=ik_Aspk_BG$$
and
$$\mathrm{DH}(EK_A,IK_B)=ek_AIK_B=ik_BEK_A=ek_Aik_BG$$
Thus there is a measure of both identity assurance and separation of key values.
The X3DH protocol is designed so that Alice can initiate communications even when Bob is offline and so it makes sense for Alice to perform her half of the computation and send it even if Bob is not present. Bob can then complete his half of the transaction when he comes online and deals with Alice's message.


What is the inverse function of the finite field GF($2^3$) and GF($2^4$)?

Yes, the only sensible interpretation I can see is that they're talking about the multiplicative inverse.

In particular, the multiplicative group of a finite field is cyclic, and contains all the non-zero elements of the field.  This implies that its order is the size of the field minus one, i.e. $2^3 - 1 = 7$ for ${\rm GF}(2^3)$, and thus that $a^6 \cdot a = a^7 = 1$ for all $a \in {\rm GF}(2^3)$, which means that $a^6$ is the multiplicative inverse of $a$.

Similarly, the multiplicative group of ${\rm GF}(2^4)$ has $2^4 - 1 = 15$ elements, and thus the multiplicative inverse of any non-zero element $a \in {\rm GF}(2^4)$ can be calculated as $2^{14}$.  More generally, in any Galois field ${\rm GF}(p^n)$, the multiplicative inverse of $a$ equals $a^{p^n-2}$.

A point of notation perhaps worth making here is that by $a^6$ above I mean the field element $a$ raised to the sixth power using the field multiplication rule — which itself can be represented as polynomial multiplication followed by reduction modulo an irreducible monic polynomial, if the elements of ${\rm GF}(2^3)$ themselves are represented as polynomials over ${\rm GF}(2)$ of order less than 3.

The reason this can be confusing is that, in this representation, expressions like "$x$" and "$x^6$" could themselves represent specific field elements, written as polynomials of a single variable $x$.  (Of course, $x^6$ cannot be the canonical polynomial representation of any element of ${\rm GF}(2^3)$, since its order is too high.)  Where such notation is used, as in your question, it's usually a good idea to avoid using the symbol $x$ for any other purpose except as the formal variable in the polynomials representing the field elements.  In particular, it should not be used to designate an arbitrary field element (except, of course, for the specific field element canonically represented by the first order monomial $x$).


Computational Complexity - When is it really exponential time?

The names of complexities normally refer to $b$, not the bitlength $n$.

$\mathcal{O}(log\ n) = \mathcal{O}(b)$ is polynomial time, $\mathcal{O}(n) = \mathcal{O}(2^b)$ is exponential time.

Matrix multiplication of a matrix of length $n$ would involve more operations than multiplying all elements of your group with all others. It has complexity of $\mathcal{O}(n^3) = \mathcal{O}(2^{3b})$ which is exponential time - it is not considered effective.
In $\mathcal{O}(n^2)$, you could create the multiplication table of your group, which is basically a lookup table. If you have that, you're basically done with the DLP, so it should be obvious, that solving the DLP should be less complex than matrix multiplication.

Also, this does not seem to be consistent. In some cases (like crypto) it makes sense to say that $\mathcal{O}(n)$ is exponential time since the thing that grows is the bitsize, and thus $n$ grows by $2^b$. In other cases, when we're talking outside of crypto $\mathcal{O}(n)$ might be considered polynomial, since n is the thing that grows (like sorting algorithms).


Proof that lottery does not know outcome of draw

Protocols for selecting uninfluenced random numbers typically fall into two camps: random beacons and coin-tossing protocols.

A random beacon is a source of randomness that is agreed by everyone to be unpredictable. For example, you can funnel a large amount of financial data into a small random number. While you cannot prove you didn't know what the closing prices would be before they actually closed, can prove that someone who possesses such knowledge can make a lot of money. A coin-tossing protocol is a protocol where everyone chooses random numbers that are combined to form the master random number. This is what is mentioned in the other answer you found.

As you point out, both of these produce a number of predetermined length. But that is ok, once the lottery closes,

Calculate the number of bits you need to select $m$ out of $n$ tickets using a standard selection algorithm (for example, you can run the Fisher–Yates shuffle until you've pulled out $m$ items). Say it takes $N$ bits.
Use either a random beacon or coin-tossing protocol to generate a cryptographic seed for a pseudo-random generator (PRG).
Use the PRG to generate $N$ bits and run the selection algorithm.

Note selection algorithms may be non-deterministic in the number of bits they need, so you can skip step 1 and just run the PRG until the selection has completed.

You must publish beforehand the exact protocol (selection algorithm, beacon/coin-tossing, PRG) that will be used. The only variable will be the secret seed.