Fastest algorithm for message authentication?

eventually is there any algorythm that use a statistical method for
  granting authentication (the most of the messages are granted valid) ?

This would be a non-cryptographic way of doing it and would likely allow malicious users / attackers to fake authentication.

  to use a classic cryptographic signature (RSA or AES) over a MD hash.
  i dint find benchmarks/times for veryfying a signature (but just for
  producing the signature) . Surelly to produce a signature is slow, but
  to verify?

RSA and Rabin-Williams signatures are highly asymmetric in speed. Signature generation is slow, but verification is comparatively fast. However, RSA, ECDSA, RW and thelike are still very slow compared to symmetric methods.

Note that AES is not an asymmetric algorithm and thus does not fall into this category.

  first solution I knows it to use HMAC. For veryfing the data i have to
  produce the signature and comparing it with the original. It seams not
  the best in my case because the time for verifying is equal pratically
  to the time for producing the signature.

HMAC is a way construct a Message Authentication Code from a hash function. There are other MACs as well, which usually are faster (because hash functions are slow), which include GMAC, VMAC and CMAC (/OMAC).

The standard recommendation would be to use HMAC with a decently fast hash function. If that doesn't cut it, and you need more speed, you probably want CMAC with AES (assuming you have hardware acceleration for AES). If even that doesn't cut it, you are probably in a hardware deployment scenario and won't use Java anyways.

Note that HMAC and CMAC don't require a nonce for proper security, which makes them a nice choice most of the time. Other algorithms like GMAC and VMAC do require a nonce and there usually will be severe security implications (like a leak of the key), if the nonce is ever re-used.

  if yes in question 1, it would be usefull to see a example how do
  write the code for generating/verifying a byte array in java(probably
  the most idoneus is bouncy castle library). I thank you if you can
  show a short example for using it.

You will have to ask this question on a more programming focused site such as StackOverflow. Maybe also have a look at this previous Q&A there.


How does Output Feedback mode use the initialization vector?

Will I encrypt the Initialization Vector like a block of plaintext? to generate keystream and I will XOR it to the plaintext to generate ciphertext?

Yes, for the first block of plaintext. For the subsequent blocks, you use the output of the previous encryption (before XOR) as the input to the cipher (along with the same key).


What is the difference between an encryption protocol and an encryption standard?

A protocol is a standard, in the sense that multiple parties agree to use it (as is required for a communication protocol). However a standard-standard is very widely used and has some kind of official backing. Examples of standard-standards would be Data Encryption Standard, Advanced Encryption Standard, and Internet Protocol.


Can the same random number be used in encryption and signing?

Generically speaking you can do this but you shouldn't. It may well be possible to perform specific calculations when a random number is used for both (I'll leave it to the more theoretically inclined to create a demo if this is possible for ElGamal / DSA). Another reason is that the single secret gets known then both keys/algorithms will be compromised. It's certainly harder to create a security analysis or proof if the one part of the protocol depends on the other.

You can however use your random number as input to a DRBG (deterministic random bit generator) and let that generate more random data. Then the separate values will not be dependent on each other (as long as the random bit generator is secure, of course).

When based on symmetric primitives (block ciphers/hash methods) DRBG's should perform favorably when compared against ElGamal or DSA, so the performance degradation should not be that much.


Diffusion in Shamir's secret sharing scheme

I took a brief look at the code, but I fail to see how this transformation could introduce any additional secrecy. If the randomness used to define the polynomial is good, then Shamir's secret sharing provides information theoretic secrecy (no matter how the secret actually looks like). What Ricky points out in his answer seems reasonable, i.e., to provide some means against the malleability of the secret sharing. Since Shamir's approach is linear, one can "update" the shares to "update" the secret and if you add an additional layer of diffusion to the secret before sharing such "updates" are no longer possible in a straightforward manner. Note, however, that this does not influence the secrecy of the secret but against active attacks on modifying the shares.

Another issue which I initially thought could be the case comes below.

If your secret is larger than what
can be represented as an element of the used field, then computational secret sharing (CSS) can be used, but it is not implemented in ssss (it's only linked as an alternative at the bottom of the page).

Basically,  with CSS it is possible to make shares in a secret sharing scheme shorter at the cost of losing the perfect
secrecy guarantees provided by Shamirs approach. One only achieves computational instead of information
theoretic security.

The idea is to use any IND-CPA secure symmetric encryption scheme in the following (obvious) way:
Choose a random secret key $k$ of a suitable symmetric encryption scheme and encrypt the secret $s$ using $k$.
Then one uses polynomial secret sharing to compute $n$ shares $s_1 ,\ldots , s_n$ of the key $k$.
Note that the field $\mathbb{F}$ used for secret sharing here can be much smaller as in Shamir’s original approach,
as you only need to represent the key $k$ as field element and not a potentially large secret $s$.

Note that if you use Shamir's secret sharing directly on $s$, then $s$ needs to be represented as a field element (as the constant coefficient of the polynomial) and also the shares will then be of that size. If your secret is large, then CSS is an efficient alternative.


Question about a proof in Junod's paper about the Blum-Blum-Shub generator

If $x_0$ is odd, then $-x_0 = n - x_0$ must be even (and versa-visa).


Why does HKDF use HMAC(salt, key) instead of HMAC(key, salt)?

To me it seems like HMAC(salt, IKM) would be weaker against a brute force search of IKMs, as the digest of the salt can in this case be precalculated by an attacker (assuming the salt is a non-secret value or zero).

Yes, it is slightly faster to brute force, but if the IKM does not have enough entropy to give brute force resistance, then a small factor will likely not be significant. In that case you would want to use a slow iterated function.

With a short IKM and a single block of output from the Expand step, you need eight calls to the compression function, two of which can be avoided if the salt is reused between calls. So the actual speedup is only 25%.

  What is the benefit of using it this way?

It has to do with the security proofs (see in particular Section 6 and Appendix C).

If you feed the IKM directly into a hash function, there are some possible distributions for the IKM that would be dependent on the hash function structure (Lemma 2). By using a random (secret or not) salt as the HMAC key. the function is randomized and the distribution is independent.

Additionally, that order means that if the HKDF salt is a secret key the Extract function becomes a PRF. That is discussed in e.g. Appendix D of the paper.

Also, note that HKDF-Expand uses the normal order, because there the PRK is already a cryptographic key.


A few relevant mailing lists:

cypherpunks@cpunks.org
cryptography@metzdowd.com (moderated)
cryptography@randombit.net
liberationtech@lists.stanford.edu

Other crypto mailing lists with a narrower technical focus:

messaging@moderncrypto.org
curves@moderncrypto.org
cfrg@irtf.org
tls@ietf.org


What's the safest way to encrypt a messenger application?

Writing a secure messenger application is difficult, and vulnerabilities have been found, and keep being found in all of them.

This requires far more than just a stream cipher such as Salsa20. An entire protocol has to be designed for user registration, key exchange, group invites and more.

The MLS working group is currently designing a reference protocol to do group messaging.

Meanwhile, Signal has opensourced their core library (https://github.com/signalapp/libsignal-protocol-c), and this is something you may want to look at.

Wire, another popular application with fairly decent security, has also opensourced most of its components: https://github.com/wireapp

But I wouldn't recommend starting from scratch, especially if you are new to cryptography.


In a signature scheme with appendix (such as RSASSA-PSS), the signature $s=\operatorname{Sign}(M,\text{PrivateKey})$ of the message $M$ is usually appended to the unmodified message $M$, forming $(M,s)$ or $M\mathbin\|s$. This is effectively sent, and verified; the signature is an appendix to the message.

Signature scheme with appendix opposes to signature scheme with message recovery (such as ISO/IEC 9796-2). In the later kind, all or some of the message is embedded in the signature. When all of the message is embedded, the verification procedure requires only $s=\operatorname{Sign}(M,\text{PrivateKey})$ as input, and recovers $M$ as a by-product (that's known as total message recovery). Only the signature is sent; it embeds the message.

In the case of RSA, signature schemes with message recovery provide significant bandwidth or space saving for signed messages about the size of the public key used, including public key certificates; that's why they are common in the field of Smart Cards.


Signing with "md5WithRSAEncryption" means CA calculates MD5 hash to get an integer first and apply his private RSA key next to produce the signature. A DER-encoded string is the input to the hash. Client (Subject in X.509 parlance) data, including public key, is described with ASN.1 language, "to be signed" part of specification. Certificate extensions (v3) are also included into "to be signed".

"Plain" public key, as received from client, is encoded according to X.509 specifications. See ASN.1 description at PKCS 10, "certificate request".

Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile
Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile


In SSH, it is also necessary that the server authenticates itself to the client.
Otherwise, a man-in-the-middle (or any other party capable of manipulating the connection, e.g., via DNS spoofing) could impersonate the server and trick the client into revealing its password or, in the case of public-key authentication, a valid response to a cryptographic challenge (which the attacker may then use to log in at the real server).

This authentication step is done via the server's host keys.
Section 8 of RFC 4253 states:

  The key exchange is combined with a signature with the host key to provide host authentication.

Typically, servers support more than one signature algorithm for interoperability reasons, hence they need to tell the client which key types they have available: The server_host_key_algorithms field contains this list.

That mechanism is the reason you see the following (probably familiar) warning when first connecting to some server:

The authenticity of host 'example.org (192.0.2.121)' can't be established.
ECDSA key fingerprint is SHA256:Lj0PQQnA9K2NupAxdjJSnxQhVWoVvjTLcUQQWDFS+9A.
Are you sure you want to continue connecting (yes/no)?

Here, the client essentially asks you to confirm that you have verified the server's host key. After the first connection, the client stores the server's host key in its known_hosts file and will only warn the user again if the host key changes (for instance, if the server has been reinstalled or there really is an attack taking place).


Cipher Block Chain continued Initialization Vector

Is it okay for Bob to use the last AES ciphertext block as initialization vector for his transmission, given that this is the way CBC works?

There is a known vulnerability with this; if the attacker can convince Bob (or Alice, on her next message) to start the reply message with an attacker-chosen block, then the attacker can use this to form an encryption oracle (and can then use that encryption oracle to decrypt low-entropy plaintext blocks).

This isn't a problem for CBC itself; it assumes that Alice (or Bob) selects the message up front, and then gives it to the CBC-mode encryption engine.  The plaintext block that the attacker needs to submit for this vulnerability to apply depends on the immediately previous ciphertext block; as the intermediate chaining values are unknown when the block is selected, this doesn't apply.  However, in your case, the attacker may be able to see the entire previous encrypted block, hence reusing the last ciphertext block as the next IV can cause this problem.

Depending on how Alice and Bob form their messages, this might not be applicable to your use case; however it would seem prudent to avoid this possibility anyways.

There are a couple ways to get around this problem:

Generate the next IV in a way that depends on a secret key that both Alice and Bob know (but not the attacker, obviously); for example, the IV for message $n$ might by $\text{AES}_k(n)$
Use the last ciphertext block, but process it somehow (in a key-dependent fashion); for example, set $IV = \text{AES}_k( \text{LastCiphertextBlock} )$

As for how other block cipher modes would work, well, that'd depend on the actual mode.


No.
This isn't secure by itself against chosen-plaintext attacks.

This mode is known as plaintext-feedback mode (PFB) and referenced for example in here.
The next point is this mode hasn't received much attention in the cryptographic literature, whereas other modes (CFB, OFB, CBC, CTR) have.

Two notes:

Don't roll your own crypto.
Never use such modes if anyhow possible. Use established authenticated encryption modes like GCM.

Beyond that even CFB would be a better choice as you need to store the plaintext to encrypt the next ciphertext in this case, whereas for CFB you only need to store the (safe?) ciphertext.

The first attack proceeds as follows:

Suppose your want to decipher $m_2$ and are allowed to view $C_2$ and to choose $m_1$ and to learn the corresponding $C_1$. Suppose further you know $r$, which is required for the valid recipient to know for decryption.

Now choose $m_1=r$. Observe that the following relation will hold $E(r)\oplus m_1 = C_1$. Now extract $E(r)$ by calculating $E(r)=m_1 \oplus C_1$ which is possible since you know $m_1$ and $C_1$.

Now observe further that $E(m_1)\oplus m_2 = C_2$ is equivalent to $E(r) \oplus m_2 = C_2$, as $m_1=r$ holds. As you already calculated $E(r)$ above you can now calculate $m_2$ via $m_2 = C_2 \oplus E(r) = C_2 \oplus m_1 \oplus C_1$.

There's a second attack that decrypt a given message $(r_X||C_X||C_Y)$.

Decrypting $C_X$ goes as follows. Choose your message to be encrypted to be $(m_1=r_X||m_2)$ for an arbitrary $m_2$.You'll get the ciphertext (from the oracle): $(r_1||C_1=m_1\oplus E(r_1)||C_2=m_2 \oplus E(m_1))$.Now oberve that the following holds: $E(m_1)=E(r_X)=m_2 \oplus C_2$.Therefore you can construct $m_X = C_X \oplus E(r_X) = C_X \oplus m_2 \oplus C_2$.Ask for encryption of $(m_X||m_3)$ now.You'll get $(r_2||C=m_X \oplus E(r_2)||C_3=m_3\oplus E(m_X))$.Use this to calculate $E(m_X)=m_3 \oplus C_3$ and finally $m_Y = C_Y \oplus E(m_X) = C_Y \oplus m_3 \oplus C_3$.

You now successfully retrieved the message $(m_X||m_Y)$ using a chosen-plaintext attack.

Hence this scheme is broken.


Here's the example I use sometimes.

Suppose I want to convince you that I am an excellent archer.
If I show you a target painted on a wall, and an arrow in the bullseye of the target, are you convinced? No, since for all you know I could have fired the arrow first and then painted the target around it. In fact, even you could have done that, and you not a skilled archer. If instead you yourself paint the target first and watch me fire the arrow at the bullseye later, that's much more convincing.

So the "byproducts" of this interaction (the target and arrow) by themselves are not convincing. You could have generated them yourself (i.e., simulated them) even if you are an unskilled archer. Only if these byproducts were generated in a particular interactive way do they become convincing.


No, that doesn't work. OTP is secure because knowledge of the plaintext doesn't give you any useful information about the key. This is because the bits of the key (e.g. $P_0$) are never used to encrypt anything else.

If you would somehow reuse the key then leakage of the plaintext would cause leakage of $P_0$. Leakage of $P_0$ directly leaks $P_1$. I.e. instead of perfect security the information encrypted by $P_1$ is now directly dependent on the security of the plaintext and $P_0$.

OTP is only perfectly secure as long as the bits in the key stream are independent of each other. OTP doesn't allow for shortcuts in that respect.


Are there any bijective one-way functions not based on number-theoretic hardness assumptions?

It is not entirely clear what you want, but suppose you need a trapdoor permutation - the function that is easy to invert only if you know a secret parameter - and which is not based on number-theoretic assumptions.

There are two well known families of such schemes: Multivariate Cryptography (MQ) and Code-based cryptosystems (for instance, McEliece cryptosystem).

An MQ scheme typically consists of a low-degree invertible polynomial transformation $S$ (public or secret) and two secret affine transformations $A_1,A_2$. The public key is exposed a polynomial(s) $A_2(S(A_1(x)))$. There are many insecure candidates for the nonlinear layer (see survey in this paper), but it is generally assumed that the HFE cryptosystem with sufficiently large parameters is secure.

The code-based cryptosystems hide the generator of some linear code in a similar manner by multiplying it by properly chosen matrices and expose the public key as a matrix.

Both families produce terribly large public keys up to several megabytes, and are of limited use because of that and the lack of systems that withstood a lot of cryptanalysis (except for the original McEliece proposal).

UPDATE:
You may also want to look at some bijective polynomials suggested in the recent algebraic papers. I do not know if there exist efficient inversion algorithms.

For example:
$\left(X^{2^k}+X+a\right)^{-l}+X$ over $\mathbb{F}_{2^n}$, where $n/\text{GCD}(n,k)$ is odd, $l(2^k+1)\equiv 2^{n/2-1}\pmod{2^n-1}$, Tr$(\delta)=1$ in this 2010 paper

For odd $p$: $\left(X^{p^k}-X+a\right)^{\frac{p^n+1}{2}}+X^{p^k}+X$ over $\mathbb{F}_{p^n}$ in this 2012 paper.


Ciphertext length in TLS 1.3 additional data

the length of the encrypted text (which is the length field in the record header) is not known until the encryption is done

The length of the ciphertext is known as soon as the length of the plaintext is known. This is true for any non-broken encryption mechanism. An adversary can easily observe the length of the ciphertext, and if that allows the adversary to deduce anything about the plaintext other than its length, it's a weakness in the encryption.
All the standard AEAD mechanisms for TLS 1.3 (CCM, GCM, ChaCha20+Poly1305) are constructed in such a way that the ciphertext is the application of a stream cipher to the plaintext, followed by a one-time MAC (the authentication tag). Thus the length of the ciphertext is the length of the plaintext plus the tag length of the mechanism (16 for GCM, CCM and ChaCha20+Poly1305; 8 for CCM_8). RFC 8846 is worded in a more general way that would allow AEAD mechanisms with a more complex construction. But whatever the mechanism is, there is a way to calculate the ciphertext length from the plaintext length, although it could be harder than adding a constant.


Your counting arguments seem correct but are somewhat moot.

Note that $10^{23}\approx 2^{76}.$ Not even the most optimistic analyses of typical password entropy yield more than $2^{30}$ or so.

Plus there is the issue of what the system does with the password input. All an attacker needs is to find some input into the passwording process that gives the same output as your password.


What is the key length of shared secret by Curve 25519 ECDH

In this paper you can find nearly everything about Curve25519. In the section "Specification" you find the answer:

  {Curve25519 secret keys} × {Curve25519 public keys} →
  {Curve25519 public keys}

this is the function, which is calculated for a key exchange. So the shared secret key has the same properties as the public keys:

  { $q: q \in ${ $0,1,...,2^{256 - 1}$}}

This matches, what Bernstein says in the introduction: The key length (for both public and private) are 32 byte long. And in that format they are stored. In other words every key is 256 bits long.

In this post you see an example for these keys.


You're using 2-key 3DES, right?

DES and 3DES has the property that the least significant bits of the key don't actually contribute to the encryption process; hence any two keys that differ only in the least significant bits will be equivalent (and hence have the same KCV value)

Your KeyA and KeyB has exactly this property.

Aso, is there a specific reason you're not using a more modern cipher, such as AES?

As a side note: normally, when we encrypt data, we typically stir in some uniqueness (such as an IV); hence encrypting the same data twice with the same key generally results in different ciphertexts.  We do this for several reasons: to hide when we do encrypt the same thing twice, in order to disguise when we encrypt different but related plaintexts, and to foil some potential chosen plaintext attacks.  You obviously don't do this; you use using 'ECB mode'?  If so, well, that's rarely the correct option...

BTW: I suspect that KeyA was done by software, and KeyB was done manually.  Here's why: every byte in KeyA has odd parity.  The original DES documents suggest that the lsbit of each byte be set so that the byte has odd parity (both to catch some simple typo's (it was anticipated that humans would manually enter the keys), and also to justify the otherwise unused lsbits).  I suspect that the software actually attempts to conform to this, and automatically adjusts the lsbits appropriately.


Alternatives to simple bit-measured security for ciphers

My assumption: It would seem logical that a cipher that cannot be run in parallel is (in some ways) more secure compared to one which can. Or two ciphers with equal security levels are not truly equal if one of them runs a billion times quicker on a supercomputer.

Is my assumption misguided?

A cipher with $n$-bit security means that there are $2^n$ keys to choose as an encryption key. If we can iterate the key, that is always possible, then we can start to brute-force in parallel. Therefore, this not a good premise.
A cipher can be faster than others like Rijndael was faster than MARS and that is one of the reasons for the choice of Rijndael as  AES. We still consider the $n$-bit security as the number of possible keys. When comparing the attacks on the cipher we consider how the attack faster than the brute-force. So we compare the brute-force time - the running time of the one encryption times the number of keys -  vs. the time of the attack. The first one is easy but still depends on the platform, the second one can be hard since the attack can depend on many parameters and the measure may not be easy.
For example, in the Improving the Biclique Cryptanalysis of AES article Tao et. al considered the actual computation of running a brute force in all details and compared their attack in the same detail level to compare the success of the attack.
On the other hand, the factoring attacks use Landau notation to express their complexity.
If there is a faster attack we consider this as the encryption algorithm is broken. This still doesn't mean that it is broken practically. Consider AES256 has attacks but they are not feasible. Also, the attack may require too much random memory access that can severe the computation time. Therefore, it is totally dependent on the attack.

Are there any alternative approaches to measuring cipher security that takes into account the computational expense of the algorithm? If not, why not?

We don't consider the computational expense of the algorithm as a weakness, indeed it is greatness. Who doesn't want a fast and secure algorithm instead of slow and secure? Time is Money, area cost is money. In the and we want the cipher to resist all attack to be secure $n$-bit ciphers.
If we consider the security against all possible attacks than this is a huge list of the attacks

Linear attack security
Differential attack security
Algebraic attack security
The number of required known-plaintext
The number of required chosen-plaintext
Multi-target security.
Possibility of running parallel
Quantum security
Memory requirements
...

Consider the linear and differential attacks on DES. They are faster on the computation requirements but required known-plaintext and chosen-plaintext
for the attacks are so huge that they were not practical. Even today, the fastest attacks implemented on the DES are based on brute-force.
Therefore, it is not an easy job to put a metric. The real metric is the implementation and comparison with the brute-force. If this is not possible, and it is not most of the time, either a complexity analysis is preferred or detailed as in AES attack.


How about hashes?

$P_i$ choose random numbers $R_i$ that they exchange through $S$.
They calculate $H_i = H(R_1|R_2|m_i)$ that they give $S$.
If $H_1 = H_2$, then $S$ can be reasonably sure $m_1=m_2$.

Assuming $H$ is a strong cryptographic hash function and $R_i$ are long enough to avoid collisions (e.g. 256 bits), the worst the server can do is a brute force attack to find $m_i$. Giving an incorrect $R_i$ will only cause the equality check to fail.


To begin with 4: Remember Kerckhoff's principle. You should always assume that the attacker knows which algorithm is used to encrypt your data. All the algorithms used in practice are designed to be secure under this assumption, so you should consider that hiding the algorithm from the attacker is superfluous. But as a hypothetical...

I can't think of any real-world cryptosystem where it would be possible to tell exactly which algorithm was used knowing only the ciphertext, but in a theoretical sense such an algorithm could exist, and would not be any less secure because the attacker is supposed to know that anyway.
Same as above, for mostly the same reasons.
In light of the above, it shouldn't make a significant difference. If it does, your algorithm relies on security by obscurity, and is generally worthless.

In your "double encryption" case, the attacker will just treat the composition of the two algorithms as one big algorithm, he will not try to decipher one and then the other.


Is perfectly secret key exchange provably impossible?

Lets start with a set of basic assumptions.

The communication channel transmits a sequence of symbols with each symbol taken from a finite set, there is no weird quantum stuff going on.
The attacker can obtain a complete record of the symbols that were transmitted.
The end systems are finite sized computers fed from a finite sized random number generator and run for a finite amount of time.
The purpose of the key exchange algorithm is to establish a shared secret.
No secrets were known by the end points prior to the start of the key exchange process.

I believe that in this case an attacker with unlimited computing power can always crack the key exchange.

The attacker can simply enumerate all the possible outputs of the random number generator. Feed each one into the key exchange algorithm and compare the data that the algorithm generates with the data that was observed on the wire.

If the data exchanged on the wire matches then the shared secret must match.


Attack on a Feistel Cipher given the key and half of the ciphertext

In a block cipher (SPN of Feistel), we want each of the plaintext bits affects the ciphertext bits. In other terms, if you write down the boolean function of the ciphertext bits $c_i$, we expect that the function contains all of the plaintext bits and the key bits;

$$C_i:\{p_0,\ldots,p_l\} \times \{k_0,\ldots,k_n\} \mapsto \{0,1\}$$ $$c_i=C_i(p_0,\ldots,p_l,k_0,\ldots,k_n)$$with $l$-bit block cipher, $n$-bit key size, and $C_i$ is a boolean funtion and $c_i$ is the i-th bit of the ciphertext.

Similarly, one can write boolean functions for the plaintext bits;

$$P_i:\{c_0,\ldots,c_l\} \times \{k_0,\ldots,k_n\} \mapsto \{0,1\}$$ $$p_i=P_i(c_0,\ldots,c_l,k_0,\ldots,k_n)$$

One-bit missing case

In this case, each of the boolean functions $P_i$ will have a free variable, the missing bit. By avalanche property, we expect that being 1 or zero will affect the half of the bits randomly. So you will have an almost completely different plaintext if you set this variable 1 or 0. If you have a pre-knowledge about the plaintext, like the language or structure, you may able to decide which one is correct.

More than one bit is missing

In this case, the missing variables will behave much more complicated. One, however,  can still try guessing the bits and check the plaintext properties to verify.

The complexity

As one can see, all is nothing but brute-force. So the complexities are $2^m$ where the $m$ is the number of missing bits. And remember, brute-force can only be successful if you have some information about the plaintext, as in RSA challenge.

** update: a simple test case for one-bit change in DES.**

key        : $\texttt{0e1f35bbaf37a86b}$

Ciphertext : $\texttt{0123456789ABCDEF}$

Plaintext  : $\texttt{0d738d5e43fbd5fe}$

Ciphertext : $\texttt{1123456789ABCDEF}$

Plaintext  : $\texttt{bd85b2e02bb056df}$

The difference between two plaintexts with one-bit change;

$\texttt{b0f63fbe684b8321}$, and in binary;

1011000011110110001111111011111001101000010010111000001100100001

which has 33 1's


Yes, you need a commitment. The commitment comes from anyone who is trusted by the verifier to commit to genuine data. So to prove age, the date of birth, say seconds from epoch could come from a government issued ID. In case of lat-long, a location provider trusted by the verifier should be used so if verifier trusts Google.

There is vast literature and implementations and they provide varying guarantees like if you provide a proof to the same verifier twice but use the same commitment, the verifier will know that he has interacted with you before or not. Depends if you care about this or not. Regarding how they work, there are several techniques, a recent and popular is Bulletproofs. Another is this paper.


Which MAC algorithm is faster - CBC based MAC's or HMAC - depends completely on which ciphers and hashes are used. Furthermore, it depends on the runtime environment that contains the hash and cipher implementations.

With regard to the leading CPU architecture for PC's, there are the Intel whitepapers. Both AES and SHA-2 performance can be enhanced using CPU constructions. See for AES the AES-NI page on Wikipedia. Likewise, the Intel SHA extensions for later CPU's can also be found there. Both are also available on later AMD processors because of the cross licensing agreements between those firms.

Obviously not all runtimes do get direct support for these constructions. At that point it is very much dependent on the implementation. If you can get away with using HMAC-SHA-1 then it is likely that SHA-1 outperforms any other MAC algorithm (besides MD5, which is also secure for smaller HMAC output sizes). In general you're best off to test which specific algorithms perform best on a platform.

OpenSSL CLI has a speed option that can be utilized, for instance use:

openssl speed sha512 aes-256-cbc

to see the speed of the CPU with regards to bytes processed per second (I'm always pretty stumped when I see them on my lowly mobile i7 CPU).


What is adversary's advantage in cryptography and why we use it?

We begin with the probability $p$ of an adversary answering correctly.

For many problems in cryptography, such as factoring or computing discrete logarithms, finding a secret key or decrypting a plaintext, this is useful measure of how good the adversary is. If we have an adversary that can compute discrete logarithms with significant probability, that is obviously a problem.

But sometimes, we want a stronger statement than simply "the adversary is unable to decrypt". Instead, we want to be able to say something stronger, e.g. that the adversary cannot determine even a single bit of information about the decryption.

Now, I can guess the value of a bit with probability $p = 1/2$, which is significantly larger than $0$. Which means that the probability $p$ of answering correctly is not a useful measure of my power.

We could say that I should be able to guess correctly more often than half the time, in which case $p-1/2$ might be a sensible measure. But if I somehow always end up guessing wrong, so that the probability $p$ of me answering correctly is $0$, then essentially I know what the bit of information is. Reliably answering wrong is essentially as good as always answering correctly.

So we take absolute value, and arrive at the usual definition of advantage being $|p-1/2|$.


Do Carter–Wegman MACs allow key reuse if the MAC tag is kept secret?

You can use methods for hiding the output of the polynomial hash that don't require nonces, such as encrypting with a block-cipher of matching block-size or hashing it with a keyed hash (PRF).

Not using a nonce reduces the security bounds (security decreases as the attacker sees more messages using the same key), makes it incompatible with stream ciphers and increases latency, but avoids the risk of total failure due to nonce reuse.

You can avoid the reduced security bounds while keeping nonce misuse resistance by hashing both the nonce and the polynomial hash output, but the other downsides remain.

The Poly1305 paper justifies the use of nonces as follows:

  There are several reasons that Poly1305-AES uses nonces.

  First, comparable protocols without nonces have security bounds that look like $C ( C + D ) L / 2^{106}$ rather than $D L / 2^{106}$ --
  here $C$ is the number of messages authenticated by the sender, $D$ is the number of forgery attempts, and $L$ is the maximum message length -- and thus cannot be used with confidence for large $C$.

  Second, nonces allow the invocation of AES to be carried out in parallel with most of the other operations in Poly1305-AES, reducing latency in many contexts.

  Third, most protocols have nonces anyway, for a variety of reasons:
  nonces are required for secure encryption, for example, and nonces allow trivial rejection of replayed messages.

In the popular XSalsa20Poly1305 combination, you already have a severe confidentiality failure if you reuse nonces, so a MAC failure on top of that doesn't seem to be a big deal. You could use Salsa20 as a hash instead of a stream cipher to hide the polynomial hash output, but that'd add a non-parallelizable Salsa20 computation (SIMD implementations of Salsa20 benefit from parallelism, even in software), making it expensive for small messages.


TLS encrypts a channel, and that channel is between your browser or app and the Facebook server. You do not have a TLS connection to the friend you are sending a message to. There are messaging protocols that do support end-to-end encryption, but Facebook's is not one of them and TLS doesn't really ccome into it.


Cipher Block Chaining Ciphertext Alteration

One way is simply to look at the usual illustration of CBC decryption and follow the arrows.
Here is the figure from Wikipedia:

Imagine you alter the first block of ciphertext. Follow the arrows to see what will be altered in the plaintext: only two blocks.

We can also do this with math formulas:
CBC mode encryption can be described as follow,
where $ P_n $  and $ C_n $ are the $n$th plaintext and ciphertext blocks, respectively:

$$ C_n = Enc(P_n \oplus C_{n-1}) $$

(With the IV playing the role of $ C_0 $)

Thus

$$ P_n = Dec(C_n) \oplus C_{n-1} $$

As a result, if you alter $ C_n $ it is clear that
$ P_n $ and $ P_{n+1} $ will be affected but not $ P_{n+2} $ and the next blocks.

If you want to see this in practice, you may want to do the cryptopals challenges up to challenge 17.


"Strict" software for playing and learning with private and public key

I'd suggest to get OpenSSL source, build it, and run it under debugger,
watching exactly what "-text" is doing to private key.
One could verify exponentiation operations with a calculator having big numbers capability.
ASN.1/DER parser could be handy to see private key file.


No, not unless the input for the key small enough to be brute forced or guessed. For any secure block cipher the key cannot be retrieved even if you have the input (block of plaintext) and output (block of ciphertext). And there are no known attacks on Blowfish that break the cipher significantly.

So it really doesn't matter how the block cipher is used. There may be attacks on the mode of operation, such as CBC/PKCS#5/7 padding oracle attacks. Those may leak information about the encrypted message, but not about the key.

The small block size of Blowfish makes it harder to use in a secure mode of operation, which is probably the main reason why Bruce Schneier doesn't recommend it anymore (besides that it is an old algorithm, and there are simply better ones available by now).


How in the world is this possible?

The easiest way this can happen is if $w$ is a Carmichael number (and relatively prime to $p$).

A Carmichael number is a composite number such that $x^{w-1} \equiv 1 \bmod w$ for all $x$ relatively prime to $w$.

If you take a Carmichael number, and just insert it into the RSA machinery; that is, compute $d = e^{-1} \bmod \text{lcm}(p-1, w-1)$ (or $(p-1)(z-1)$, both works in this case), you'll get an encryption/decryption pair that works.

To make things even more interesting, there are also numbers for which $x^{w-1} \equiv 1 \pmod m$ is often (but not always) true (I personally call them quasicarmichael numbers; that might not be standard terminology); then, depending on what $p$ is (actually, it's the factorization of $p-1$ which is critical), and possibly whether you use $\text{lcm}(p-1, w-1)$ or $(p-1)(z-1)$, can also work.

  (Of course we assume that M and pw have no common factors).

Actually, we don't need to make that assumption.

  How do we prove that there is no such w that is 512 bits in size??

Actually, I believe that there are Carmichael numbers of that size.


How does DH work when combined with ECC or RSA?

What's missing is the authentication of the entities. If you don't authenticate the entity then you don't know who you've established the master secret with. This means an attacker can pose as a man in the middle or the attacker can simply act as one of the entities.

You can use static DH key pairs, but in that case the DH public keys must be trusted and the scheme loses the forward secrecy property.

In TLS 1.3 only DHE and ECDHE will be used for key agreement, which means that the key pairs are fully ephemeral and the forward secrecy property is indeed in effect.


Does blinding protect again fault injection attack against RSA with CRT

In the original Bellcore attack, the attacker needs to obtain a valid signature and a signature where the computation of one of the coefficients is faulty. The exact nature of the fault does not matter, as long as it affects one of the exponentiations. Therefore it doesn't matter how the coefficients are calculated: blinding has no impact on this attack.
In any case, a cheap defense against single-fault Bellcore-style attacks against RSA is to perform the public-key operation after the private-key operation and compare against the input to the private-key operation.
Blinding may help with more advanced variants involving multiple faults. If the attack requires the faults to happen in a specific way, blinding might cause the result to be unusable for the attacker. I'm not familiar with the literature on those variants.


Prevent MITM attack while encrypting data by using ElGamal ECC?

DrLecter is right.

It all boils down to making sure to use the right public key. In fact this is the same for any public key cryptosystem be it RSA elGamal or ECC variants thereof.

A MAC or whatever other construction local to your system won't do the job. The MAC e.g. can only make sure the last "editor" of the message knew the symmetric key the message is enciphered with, which a man in the middle obviously always does.

You can only achieve some protection by

trusting a CA who signed the key or
trusting a PGP style "web of trust" or
by meeting your communication partner in person and exchange keys face to face.

A somewhat weaker protection independent of an external organization might be achieved by:

Using a second independent and well protected channel to transfer the public key. E.g. use the phone if you trust your mobile...
Posting a video where you read your public key aloud.
(This helps with people who know you well in person and is hard to fake - I do that with my Academic Signature ECC-key here: http://www.fh-wedel.de/~an/crypto/key_read_anders.ogv . It might be awkward with elGamal or RSA keys which need to be very long nowadays.
There are also cryptographic concepts of deterministically deriving a public key from an e-mail address or a name string. This concept is called "Identity Based Encryption" (IBE). You can find it explained in wikipedia. IBE, however, IMHO just transfers the problem and doesn't solve it.


ECDSA signature with Brainpool curves in TLS possible?

RFC 8734 defines how to use Brainpool curves within TLS 1.3, including how they can be used in ECDSA signatures (section 4)
.  Hence, yes, there is an official way to negotiate Brainpool curves for use in the SERVER KEY EXCHANGE.


It sounds like you're trying to improve the security of OTP schemes by adding extra "random-ish" data. My answer will address that, please update your question if that is a wrong interpretation.

These schemes don't literally have multiple inputs that you could feed this extra data into, but you don't need them to. For example, with HOTP the security of the function lies in the secret key. If it's strong, you have nothing to gain by incorporating outside data like IP addresses that are neither random nor private.

It sounds like the problem is that you don't trust the key to be secure and you want to augment the security by throwing in a variety of other factors. But instead, just focus on generating a good key. Instead of having your OTP scheme take input from a variety of sources, you should have your key generation take input from a variety of entropy sources. All of your entropy, which might include things like network addresses, is then mixed together in one step, used to generate a key in another step, and then the key is finally plugged into an existing OTP scheme. Then your OTPs will be dependent on some of the data that you mention here.


How to create a private key using $n,e,d,p,q$ where $n$ is prime

You already stated the answer yourself: You know $N$ (which is prime by your assumption) and from the public key $e$ you can compute $d = e^{-1} \bmod N-1$, e.g. using the EEA.

With this $d$ you can then decrypt any ciphertext $c$ into the corresponding $m = c^d \bmod N$.


Pseudo random permutation for arbitrary size domains

Ciphers with Arbitrary Finite Domains by Black and Rogaway have some options like Prefix Ciphers, Generalized Feistel networks , Cycle walking etc.

Also Format preserving encryption has traits that you are looking for , but NIST standardized ones are patented by Voltage Inc.

In general Feistel networks + Cycle walking would give a good option for any arbitrary length (even or odd) domains .

This question has much better answer
Is there a length-preserving encryption scheme?


Decrypting ciphertext that is missing a block

The details depend on the mode of operation, but for all the commonly used modes, most of the message will still be fully decryptable without any guesswork even if one block of ciphertext is missing.

For the (insecure!) ECB mode, and for the OFB and CTR modes, all you will lose is the plaintext for the missing block.  Everything else can still be decrypted in the normal manner.  This is because, in these modes, each block of ciphertext only affects the corresponding block of plaintext.  (Indeed, for the OFB and CTR modes, each bit of ciphertext only affects the corresponding bit of plaintext.)

For CBC and CFB modes, you will lose the missing block and the next one.  On the flip side, if you can guess the plaintext for either of these missing blocks, you can use that to reconstruct the other one.  If your guess is wrong, the reconstruction will be essentially random gibberish.  If the plaintext doesn't normally look completely random, that can provide a useful way to verify your guess.

(At least, this is true for CBC mode and for CFB with full-block feedback.  For the rarely used CFB-8 and CFB-1 modes, you should still be able to easily reconstruct the next block if you can guess the plaintext for the missing one, but going the other way is slightly trickier.  I believe it should be doable with a backtracking search, but it'll be a bit more complex than just the single XOR and AES decrypt operation needed for normal full-block CFB and CBC.)

The also rarely used PCBC ("propagating CBC") mode is the one notable exception here, since it was designed so that decrypting a block of ciphertext should require knowing the previous block of plaintext.  Thus, with that mode, you will only be able to directly decrypt the message up to the last block before the missing one.

However, if you can guess the plaintext for any of the later blocks, then you can still decrypt the entire message, since you can in fact run the PCBC decryption process both forwards and backwards from the guessed block.  In fact, even if you can't directly guess any of the later plaintext blocks, you can still obtain the bitwise XOR of every pair of plaintext blocks after the break in the ciphertext, which effectively reduces the PCBC mode encryption to something equivalent to a repeating key XOR cipher and allows you to apply all the well known techniques for breaking a many-time pad.

As for more modern authenticated encryption modes, those generally don't fare any better in this scenario.  Indeed, most of them are built by combining one of the classical modes (usually CTR) with a message authentication code, and thus are just as easy to decrypt in this case as CTR mode itself.  The authentication layer can even give the attacker a reliable way to verify their guess about the possible content of the missing block.

In any case, just like with the similar recent question about decrypting without the IV, the moral of the story is that modern encryption systems are designed with the assumption that the key is secret and everything else is public.  If you break that assumption by making the key available to the attacker, then the system will probably not be secure any more, not even if you try to hide some of the assumed-to-be-public information instead.


How to cipher bocks with RSA in ECB mode?

Securely enciphering text with RSA is typically done in one of three ways:

The most usual one is with the help of a symmetric cipher: RSA is used to establish a symmetric key, and the text itself is enciphered with the symmetric cipher. That's a hybrid cryptosystem. One way is that the sender generates a uniformly random $x$ in range $[0..N)$, enciphers it with the textbook RSA public-key function $x\to x^e\bmod N$ and sends the results (of 256 octets) which the receiver can decipher; then both extract the (say) 192 low-order bits of $x$ and use it as key for AES-CTR, which enciphers the text.
RSA-ECB with random padding: the text is broken into pieces significantly smaller than the public modulus (e.g. 190 octets pieces for 2048-bit RSA); each block associated with some randomness and redundancy (e.g. 32+34 octets) into a padded block, by some algorithm (e.g. RSA(ES)-OAEP) typically involving a hash (e.g. SHA-256); each result $x_i$ is enciphered with the textbook RSA public-key function $x_i\to{x_i}^e\bmod N$; the results are concatenated. Decryption undoes that and discards the randomness. This option has huge drawbacks when more than one block is involved: slow decryption, sizable ciphertext expansion (e.g. +15% for large text). In practice, it is thus used only for small amount of data (e.g. the secret PIN number of a credit card).
RSA is used (possibly multiple times) to establish a shared secret random keystream as long as the plaintext, then used to encipher the plaintext with XOR (or other equivalent information-thoretically perfect cipher). E.g the sender generates uniformly random $x_i$ in range $[0..2^{2040})$ (enough that the 255-octet $x_i$ concatenated are at least as long as the plaintext), enciphers them with the textbook RSA public-key function $x_i\to{x_i}^e\bmod N$; the results are concatenated and sent, as well as the plaintext XORed with the keystream. This is nearly as slow as 2 (there are almost as many RSA decryption to perform), has significantly worse ciphertext expansion (ciphertext is over twice as large as plaintext), but requires no keyed cipher (as 1 does) or padding function (as 2 does).

In 2, cutting corners on randomness would allow an adversary to check a guess of a plaintext (that's a disaster for a PIN number, or the name of someone on the public class roll). Cutting corners on the padding function leads to other, more subtle security issues. Some introductory material uses 2, cuts corners on both randomness and padding, and uses very small $p$ and $q$. That's justifiable only for teaching purposes and with ample warnings (sadly often skipped or/and forgotten).

For large $p$ and $q$, the only recommendable options are 1; 2 exclusively limited to short plaintext and with decent randomness and padding function; or 3 for something which for some reason (e.g. pedagogical, conceptual simplicity, code size..) must use neither a keyed cipher nor a hash.

Note: none of these options provide message integrity of any kind. Since the public key is known to attackers, they can generate messages with any deciphered content they will. Upgrading option 1 with authenticated symmetric encryption does not satisfactory solve that issue (it only ensures that an adversary can not alter part of a message while leaving some unknown portion unchanged).

  I know that in order to cipher I can do the following: C = M^e (mod n) if M is an integer.

That's textbook RSA, is cutting on both randomness and padding, and thus is unsafe. For a start, any guess of M can be checked, and that's an unwanted property in encryption.

As an aside, I read C = M^e (mod n) as $C\equiv M^e\pmod N$ which means that $N$ divides $M^e-C$, and that is not satisfactory (in particular it allows $C=M^e$ which allows recovery of $M$ from $C$ as $M=\sqrt[e]C$ ). The proper equation is $C=M^e\bmod N$ , additionally meaning that $0\le C<N$ ; notice there is no opening parenthesis before $\bmod$ , making it an operator similar to the % operator of C, Java, Go, rather than implying that the previous equality is modulo $N$ (which is the case with  an opening parenthesis before $\bmod$ ).

  If it's not I think I have to break my binary string into say 32bit length substrings, calculate it's integer value, apply C = M^e (mod n), get the new integer and last represent it back into binary.

The general idea of cutting in blocks is right if choosing option 2, but doing so in the manner stated is very unsafe due to the lack of added randomness, allowing to find each 32-bit integer by trial and error. Further, if $e<{2048/32}=64$, there is an attack without trial and error due to lack of padding (computing $\sqrt[e]C$ will always reveal $M$ ). Further, the ciphertext expansion is by a factor of ${2048/32}=64$, which is wasteful; and decryption will be dead slow. Larger blocks somewhat improve things, but what's really needed is randomness and proper padding; or better, getting rid of option 2 / RSA-ECB altogether.

  How should block size be picked?

If using RSA-ECB (which again is reasonable only for short messages, needing a single block), the choice is dictated by the padding algorithm used. In all such algorithms, that can be at most $\lfloor\log_2N\rfloor-r$ bits, where $r$ is the number of random bits added, which determines the security level against confirming a guess of $M$; $r\ge128$ is recommandable. For $N$ of $8b$ bits, a hash of $8h$ bits, RSAES-OAEP allows block size up to $b-2h-2$ octets. For $8b=2048$ and $8h=256$, that's $190$ octets. It is a tad wasteful, but RSAES-OAEP (also known as PKCS#1v2 encryption padding) is the only RSA encryption padding with both a security proof and good support in common crypto libraries.


Substitution cipher (e.g., Caesar) and polyalphabetic substitution cipher (e.g., Vigenere) are deterministic encryption schemes. The same plaintext will always result in the same ciphertext. So, they are not secure in the sense of indistinguishability under chosen plaintext attack (IND-CPA).

It may be possible that "all the letters of the alphabet are evenly distributed", but it is very unlikely that all the 2-grams, 3-grams, etc., are evenly distributed (because some of them may be meaningless in the language). In this case, the frequency analysis can still work.


Is it possible to determine or estimate the period for Blum-Micali PRG?

Under the question's hypothesis, $x\mapsto g^x\bmod p$ is a permutation of $\mathbb Z_p^*$, that has some characteristics of being random.

If we take a random permutation of a set of size $s$, the length of the cycle iterating that permutation from a random point has length $l$ with probability exactly $1/s$, independent of integer $l$ with $1\le l\le s$. It follows that the cycle has length $l$ or less with probability exactly $l/s$.

This forms an heuristic argument (obvious, as pointed by Thomas in comment) that perhaps it is $\epsilon$-rare that the cycle length of the question's generator is much less than $\epsilon\,p$.

This is however very far from a proof or even a convincing argument. In particular, because $x\mapsto g^x\bmod p$ belongs to a very small and special subset of the permutations of $\mathbb Z_p^*$, with that subset having $(p-1)/2$ elements out of $(p-1)!$ permutations.

By contrast, D.W.'s argument is a valid proof that the cycle length is too large to be found when $p$ is such that the discrete logarithm problem is hard. However that gives a considerably looser safe estimate of the cycle length; perhaps likely at least $2^{100}$ for $2048$-bit randomly-seeded $p$, when the above heuristic argument suggests likely at least $2^{2040}$.


Why is padding used for RSA encryption given that it is not a block cipher?

RSA without padding is also called Textbook RSA.
The question why RSA without padding is insecure has already been answered
in this question.

We can fix a few issues by introducing padding.

Malleability: If we have a strict format for messages, i.e. that the first or last bytes contain a specific value, simply multiplying both message and ciphertext will decrease the probability of creating a valid (in terms of padding) message.
Semantical Security: Add randomness such that RSA is not deterministic anymore (a deterministic encryption scheme yields always the same $x$  for each instance of  $x = enc_{pubkey}(m)$ for constant $m$ and $pubkey$). See OAEP as an example on how to achieve this.

Edit: To answer the second question, RSA plain text are (unlike AES plain texts) limited by an upper bound. Messages must not be longer than the $N$ of the public key. It is also noteworthy, that common cipher schemes don't handle or pad blocks of RSA ciphertexts at all. Usually, the message is encrypted using a symmetric cipher (like AES) and only the key to this seperate cipher text is encrypted using an asymmetric cipher (like RSA). This is also called hybrid encryption.


Analyzing/Breaking a strange One-Time-Pad

I didn't actually manage to download the ciphertext you linked to — I'm pretty sure I clicked the real download button, and not the fake one in the ad next to it, but all I got was a long delay followed by an error message, and the site itself looked shady enough that I didn't feel like investigating further.  However, since what you really seem to be asking is a general question about exploiting non-randomness in a one-time pad, and since anything else would be off-topic here anyway, let me just try to give a general answer.

A proper one-time pad, as the term is usually used in cryptography, requires each key letter (or byte, or whatever your cipher alphabet consists of) to be chosen independently and uniformly at random from the full cipher alphabet.  As a consequence, it follows that the ciphertext will also look like a perfectly random sequence of letters.

While such a random sequence can, just by chance, contain occasional substrings that look like English words, they shouldn't appear significantly more often than any other substrings of the same length.  (However, do note that the human brain tends to be good at picking apparent patterns out of randomness, so unless the non-randomness is really obvious, you really should check this with a proper statistical test rather than relying on just your intuition.)

If the ciphertext looks recognizably non-random, it's possible that either:

the key used to encrypt it isn't really random, but might instead e.g. be the contents of some non-random file; or
the encryption process itself might be somehow broken, e.g. some parts of the plaintext might not be encrypted at all for some reason.

In the first case, your situation is basically the same as if you were attacking a two-time pad (i.e. a proper one-time pad with a reused key).  Specifically, with a reused key, combining the messages lets you cancel out the key, after which you're left with the XOR (or modular sum or difference, depending on which kind of OTP is involved) of the two non-random plaintexts.

If you're lucky, you may be able to identify the source of one of the plaintexts (e.g. it might be available online), which will then let you directly decrypt the other.

If you're not so lucky, you may be faced with a painstaking letter-by-letter reconstruction process, using crib dragging, intuition and lucky guesses to construct two plausible messages that, when XORed, yield the known XOR of the ciphertexts (or, in your case, the ciphertext itself).  While this process can be automated to some extent, in my experience it tends to work poorly without close human guidance, at least unless you have a very good predictive statistical model available for at least one and preferably both of the messages.

Anyway, since this was given as an exercise, I assume it probably is solvable somehow using a reasonable amount of effort.  You'll just first have to figure out exactly what's gone wrong with the encryption, to produce such a non-random ciphertext.

Ps. See also:

How does one attack a two-time pad (i.e. one time pad with key reuse)? (already linked above)
Many time pad attack
Attacks on Biased OTP
What does it mean when two encrypted files, encrypted with the same method but with different keys, when xor'd together, produce a repeating pattern?

There are probably other relevant earlier questions on this site, too, but those happened to be ones that I'd answered myself before.


Is this RSA / SRA cipher modification secure?

If e1 is selected even, the algorithm strength remain unchanged?

Actually, as far as we know, this algorithm relies on a weaker security assumption (and hence is arguably stronger than RSA).

RSA is known to be breakable if you can factor the modulus; however it's possible that there is a way to break RSA without factoring.  We don't know of such a way, but it may exist.

In contrast, it is well known that you can efficiently factor $n$ if you are given a method that takes $x^e \bmod n$, for $e$ even, and recovers a possible $x$ value.  Hence there cannot be a (much) easier way to reconstruct $x$ than factoring $n$

On the other hand:

  what is a different way to public encryption key and ensure everybody that I do not posses decryption key?

What makes you think you can convince anyone that, given $x^e \bmod n$ for even $e$, you cannot find $x$?  If you know the factorization of $n$ (which, assuming that you are the guy that picked $n$, is a reasonable assumption), you can reconstruct a handful of possible $x$ values (no more than $\gcd(p-1, e) \times \gcd(q-1, e)$, which may be as small as 4), one of which is the correct value.

Now, what is the problem you're trying to solve?  If you want to make sure that there is no 'decryption key', why don't you just, say, do a hash of the plaintext.

If there needs to be a 'decryption key' (and just that no one knows it), well, one way is to use one of the larger RSA challenge numbers as a normal RSA modulus (and use a large prime public exponent).  However, we rarely need to do that; what are you trying to accomplish?


What is the difference between synchronous stream ciphers and asynchronous stream ciphers?

With synchronous stream ciphers, the bits of the key stream do not depend on the ciphertext bits. With asynchronous stream ciphers the key stream can be inferred (provided one knows the secret key) from previous bits of the cipher stream. If you're familiar with block cipher modes CTR would be an example of a synchronous streaming mode and CFB would be an example of an asynchronous mode.
Synchronous ciphers have the advantage that key stream can be pre-computed before plaintext or ciphertext is provided, often with parallelism. They have the disadvantage of ciphertext malleability (a known change in ciphertext produces a known change in plaintext) and so will need to be combined with some form of message authentication. If a transmission is only received in part, in can be difficult to recover the fragment as the exact position in the key stream needs to be identified (synchronisation). Synchronous ciphers are also deterministic constructions with a finite number of possible states and so will eventually cycle. Care must be taken in their construction/initialisation to make sure that short cycles are unlikely. For most stream ciphers (e.g. those combining key and plaintext by XOR) chosen ciphertext is equivalent to chosen plaintext in the information provided about the cipher which simplifies the security modelling. With no ciphertext dependency two different plaintexts encrypted with the same key are added to the same keystream which leads to significant weakness.
Asynchronous ciphers are largely serial in the encryption process (though not necessarily the decryption process) and the key stream can only be computed once the plaintext/ciphertext is provided. However, changing the ciphertext changes subsequent key stream and so there is considerably less malleability and a degree of message authentication. They also allow easy synchronisation at any point in transmission as the receiver can infer key stream after an initial run up of cipher bits (self-synchronisation). Asynchronous ciphers can always be provided with plaintext that prevents cycling and so no special cycle analysis is required. However chosen ciphertext has an effect on keystream and so CPA and CCA must be considered separately. Distinct plaintexts will lead to distinct keystreams, reducing the danger of repeated keys.


What does the term "asymptotic security" mean?

One of the key ideas of cryptography is to provide security by means of operations that are (relatively) affordable to honest parties but prohibitively costly to adversaries.  So one thing you see over and over in cryptographic literature is efforts to quantify the cost to adversaries to break some proposed cryptographic scheme.

Asymptotic security is one paradigm for so doing.  In such an analysis, one states the adversary's cost as a function of a designated security parameter (e.g., key length).  The scheme is then said to be secure if an only if the adversary's advantage is a negligible function of the security parameter.  Very informally, an asymptotically secure scheme is one that's been conditionally proven to be harder than any polynomial for the attacker to break.

What the author seems to be highlighting is that alternatives to their proposal don't enjoy this "harder than polynomial" property (pp. 2-3):

  Finally, in contrast to traditional cryptographic protocols, proof of work offers no asymptotic security. Given non-rational attackers—or ones with extrinsic incentives to sabotage consensus—small computational advantages can invalidate the security assumption, allowing history to be re-written in so-called “51% attacks.”

This seems to mean that the computational effort to an adversary who wishes to defeat the proof-of-work system is a linear function ("51%") of the total amount of computing power in the network.  That amount of computing power definitely exists, so it is theoretically possible for some combination of actors to collude and assemble that much.  Whereas an asymptotically secure scheme—like cryptographic ones are—can in principle be tuned so that the universe might not be big enough to crack them.


4 x E = D in Simplified AES how it's possible?


Rehashing PBKDF2 hashes - do iterations stack?

PBKDF2 consists of a chain of one way functions. The one way functions are dependent on each others output and this output is computationally unique. That means that there are no shortcuts of creating a specific outcome.

So yes, you can chain the PBKDF2 functions that way. However, it won't be binary compatible with just using PBKDF2(20, password) as the concatenation of the steps that make up PBKDF2 will be different for both, even if you re-use the same salt.

Reusing the salt won't lead to problems, as the output of the previous PBKDF2 is randomized, so it will be different from any other password / output of the first stage.

Notes:

PBKDF2 directly uses the number of iterations, i.e. the work factor will increase linearly. Unfortunately computer processing power doesn't, it seems to continue to increase faster than that.
It may be a good idea to store some kind of version number with the PBKDF-2 hash so it is possible to distinguish between different forms of hashing (such as single PBKDF2 or extended PBKDF2 use as described.
TL;DR, option 2 is correct - yes iterations do stack.


What is an example of a secure sigma proof?

Sigma protocols as-is are secure only for honest verifiers. However, they can be easily compiled into full-blown zero knowledge protocols. If you don't want interaction, then the Fiat-Shamir transform suffices, with security in the random oracle model. With interaction, you can do the transform at little cost using commitments based on DDH. For more information on this, you can see this video. If you have Springer Online access, then you can also see this chapter. If you don't have access, then send me an email and I'll send you the chapter.


I think only for $n=1$.
The map $x\mapsto x\oplus\mathrm{rot}(x)\oplus s_0$ is 2-to-1 since $x$ and $x\oplus 1111\ldots 1$ both map to the same value. It follows that half of the values of $\{0,1\}^n$ do not lie in the image of this map. We can capture at most one missing value with our start point $0$, but the remaining $2^{n-1}-1$ points will never occur in the image.


The answer is we cannot improve the security of the one-time pad in this manner. Intuitively the reason is that the double one-time pad is just a less efficient one time pad.

The security of the traditional xor-based one-time pad is requires that the key $K$ is chosen uniformly at random for each message and that the key is at least as large as the message.

Because the xor operation is associative, we could re-write the double one-time pad as $C = M \oplus(K_1 \oplus K_2)$ or $ C = M \oplus K$, where $K = K_1 \oplus K_2$. Now if $K_1$ and $K_2$ are uniform, it is easy to show that $K$ is also uniform. Assuming the key and the message have length $n$

$P_K[k] = \sum_{x \in \{0,1\}^n}P_{K_1,K_2}[k_1 = x, k_2 = k \oplus k_1] = \frac{1}{2^n}$

In other words $K_1 \oplus K_2$ could be simply replaced by a single uniform key, therefore $K_1$ is enough. Moreover the double one-time pad is inefficient because it requires two xor operations.

Regarding cascade encryption, Maurer and Massey showed that cascade encryption is as strong as the first cipher. Matthew Green's blog post is a nice (easy to read) summary of multi-encryption security.


Can the precompiles in Ethereum Byzantium for pairings be used for implementation of BLS verification?

Let $P_1$ be generator of $G_1$ and $P_2$ generator of $G_2$. Let $f:(G_1 \times G_2)^k\rightarrow\{0,1\}$ be Ethereum pairing check operation.

Given $\sigma,R \in G_1$ and $V\in G_2$ it is possible to check if $e(\sigma, P_2)=e(R,V)\vee e(\sigma,P_2)^{-1}=e(R,V)$ is true with Ethereum built-in operations, you just check check whether:

$f(\sigma, P_2, -R, V)$ is true or
$f(\sigma, P_2, R, V)$ is true

Why this works:

Let $\sigma=sP_1, R=rP_1, V=vP_2$. So $s=log_{P_1}(\sigma),r=log_{P_1}(R)$ and $v=log_{P_2}(V)$. Also please note that $\forall i\in\{1,2\}\forall a\in G_i:(-a)P_i=-(aP_i)$ and from that $-log_{P_i}(aP_i)=log_{P_i}(-aP_i)$
$e(\sigma, P_2)=e(sP_1, P_2)=e(P_1,P_2)^s$
$e(R,V)=e(rP_1, vP_2)=e(P_1, P_2)^{rv}$
$e(R,V)^{-1}=e(rP_1, vP_2)^{-1}=e(P_1, P_2)^{-rv}$
$e(\sigma, P_2)=e(R,V)\vee e(\sigma,P_2)^{-1}=e(R,V)\iff s=rv \vee s=-rv$
$s=rv \vee s=-rv \iff s-rv=0 \vee s+rv=0$
$s-rv=0 \iff log_{P_1}(\sigma)log_{P_2}(P_2)+log_{P_1}(-R)log_{P_2}(V) = f(\sigma, P_2, -R, V)$
$s+rv=0 \iff log_{P_1}(\sigma)log_{P_2}(P_2)+log_{P_1}(R)log_{P_2}(V)= f(\sigma, P_2, R, V)$
$s-rv=0 \vee s+rv=0 \iff f(\sigma, P_2, -R, V) \vee f(\sigma, P_2, R, V)$
$e(\sigma, P_2)=e(R,V)\vee e(\sigma,P_2)^{-1}=e(R,V)\iff f(\sigma, P_2, -R, V) \vee f(\sigma, P_2, R, V)$

Said that, the paper you're citing is based on symmetric (type-1) pairing. In ethereum BN curve is used in asymmetric (type-3) setting so you have to use version of BLS that is adapted to that. Fortunately, there is one proved secure: BLS-3b on page 11 of https://eprint.iacr.org/2009/060.pdf. You have:

private key $x\in F_q$
public key $(W=P_1^x, X=P_2^x)$
hash-to-point function: $H:\{0,1\}^*\rightarrow G_1$
signature $\sigma=H(m)^x\in G_1$
you verify using $e(\sigma, P_2)=e(H(m),X)$

Verification again can be done using Ethereum pairings:

$e(\sigma, P_2)=e(H(m),X) \iff log_{P_1}(\sigma)log_{P_2}(P_2)+log_{P_1}(-H(m))log_{P_2}(X)=0$
$e(\sigma, P_2)=e(H(m),X) \iff f(\sigma, P_1, -H(m), X)$

Please note that $W$ is used neither in signing nor verification but is required for security proof. There is version without it (BLS-3), where public key is just $X=P_2^x$, but you can't construct proof with it even though assumption here is weaker than in BLS-3b.


Does a practical collision attack on a cryptographic hash function also mean it fails “indistinguishable from random data”?

Does a practical collision attack on a cryptographic hash function also mean we can (or should) consider it to fail “indistinguishable from random data”? Or does a collision attack have no influence on that?

For a random oracle with output length $n$, it takes $2^{n/2}$ time to find a collision.  So if you have a hash function with output length $n$ as well but for which there's an attack that finds a collision in less than $2^{n/2}$ time, then the hash function doesn't behave like a random oracle, period.  The function has some property that a random oracle does not have.

Note that even before we ever found a collision, we already knew that Merkle-Damgård hash functions like MD5, SHA-1 and SHA-2 don't behave like random oracles, because they're vulnerable to length extension attacks: for any choice of message $m$, an adversary who knows the result of $\mathrm{hash}(m)$ and the message length $|m|$ can use this knowledge to "shortcut" the calculation of $\mathrm{hash}(m || \mathrm{pad}(|m|) || s)$ for any choice of $s$.  A random oracle doesn't have this property—knowing the hash for any message is of no help for predicting the hash of any extension of it.

This doesn't mean that it's impossible to find some construction that uses the hash function in a carefully restricted way such that its output is indistinguishable from random (and indeed, HMAC-SHA1 is claimed to be a pseudorandom function—a function such that if you pick a secret key at random, the adversary can't tell it apart from a random function).  It means that from the point of view of an adversary that has control over the input of the hash function, they can very easily tell that it doesn't behave like a random function would.

(Note that I have been careful to talk about random oracles and random functions instead of just the outputs of a function; the very stringent question we ask of a hash function is how it behaves from the point of view of an adversary who can choose what inputs to feed to it.  Again, this doesn't rule out the possibility that in a weaker attack model—one where the adversary has fewer powers—the adversary might not succeed.)


How feasible is word-level frequency analysis over English (or any language)?

The feasibility depends a lot on the length of the corpus. The more statistics, the better guesses an attacker would be able to make.

  He'll try to use statistical attacks to fit the frequency curve of the tokens to the frequency curve of English words. This will allow him to guess the preimages of more frequent words with high confidence, but will he be able to guess less frequently-used words? Are there more advanced attacks he could use?

Once you knew/guessed the most common words, like prepositions, you could try n-grams. For example, if a particular token frequently appeared immediately after those for "in the", you could make some reasonable guesses. Find other instances where that token appears and you may be able to cross reference.

In reality, you'd do it programmatically, optimizing a quality function where each word pair/triplet/etc. would add or subtract from the score depending on whether that is a common combination in English.

Knowing exact word lengths would reduce the search space significantly, but with AES block length you'd get almost no extra information, since very few words are longer than the 16 – or 15 with padding – bytes you'd fit in one block, and those will probably not appear often. At least if you use ASCII/UTF-8 for English. UTF-16 would help the attacker some, and e.g. UTF-8 German might (multi-byte characters and longer words).

Trying to apply grammar to the text would be the next step, but I'm not sure it would help. N-grams already tell you what kind of words can follow e.g. an adjective.


Koblitz encoding a message to a point, what is the "associated auxiliary base parameter"?

Based on a quick Google search, I assume you're reading the paper "Modified Koblitz Encoding Method for ECC" by Kodali and Sarma (Int.J.Rec.Tr.Eng.Tech., vol. 8, no. 1, Jan 2013).

The fact that the paper doesn't actually cite any source for the encoding scheme, or even cite anything by Koblitz, makes me a bit skeptical of the paper's quality.  For that matter, so does the fact that they seem to be using tiny curve sizes and encoding individual ASCII characters as curve points.  The security levels they seem to be claiming in their last figure also look absurdly low (9 bits, really??), which at least seems honest, if not particularly useful.

All in all, while I admit to only skimming the paper, and that I may have missed some crucial detail, at least at a glance it certainly trips my bullshit detector.  I suggest you, at the very least, read it with a highly critical eye.

In any case, I assume that, by "Koblitz's encoding method", they're referring to one of the three encoding schemes described in section 3 of Koblitz's original 1987 paper, "Elliptic Curve Cryptosystems" (Koblitz, N.; Mathematics of Computation 48(177), January 1987, pp. 203–209).  It's not 100% clear to me which one they're describing, but I suspect it's most likely the second one, where the plaintext $m$ is mapped to a curve point by multiplying it by some constant $k$ (1,000 in the example) and testing all $mk \le x < (m+1)k$ by brute force to (hopefully) find an $x$ that corresponds to a curve point.

Ps. You may also find these earlier related questions interesting:

Mapping of message onto elliptic curve and reverse it?
Fast hashing into elliptic curve

Pps. I took a closer look at the Kodali & Sarma paper to see which EC cryptosystem they're actually using, and I couldn't make any sense of it — it looks as if they're effectively just running a symmetric Caesar cipher over an elliptic curve (after first doing ECDH key agreement). If so, that still makes absolutely no sense to me; it's not semantically secure, and anyway they'd be much better off just feeding the ECDH secret (computed over a secure curve, not the tiny one they seem to be using) to a KDF and using it to key a standard symmetric cipher, like normal people do.


Key exchange and man in the middle issue. Secure solution

You are right that the session public keys can be replaced if they are not signed by long term private key known to all parties.

What you want to do is not have Trent do anything but be a relay, then you need a standard key exchange process between the two parties using new random key pairs. Then once all parties have both public keys, they can generate an authentication hash of the key pairs as well as the prime/exponent and any other common data. After the key exchange completes and the session key is generated, you would need some way to compare them, even if it is an insecure channel, as long as that comparison cannot be modified.

Several programs use this method or one like it. I use one over IRC, with the IRC server taking the place of Trent. The obvious alternative is known long term keys that are only used for signing the session public keys.


You are quite correct.  A PRP in counter mode is, in fact, distinguishable from a random sequence if you approach the "birthday bound".  We get around this by never generating that much output at once.  With a 128 bit block cipher, an output of $2^{40}$ bytes (which is a lot of output) gives us a distinguishing advantage of about $2^{-56}$ (the probability of a random sequence of blocks of that length would have a repeat) -- this is small enough that we don't worry about it.


Is the decompression of compressed and encrypted data without decryption also theoretically impossible?

The decompression of compressed-then-encrypted data is not possible without the decryption key, at least for compression and encryption schemes independent of each other. We can make a theoretical argument for that: compression schemes compress only a small portion of possible plaintexts (that happen to be the ones where compression is used in practice), and slightly expand the others (e.g. random data). Encryption makes it impossible to distinguish if two ciphertexts of equal size correspond to plaintext that compression compressed, or not; thus prevents any meaningful decompression.

In the question's situation, the classical solution (described as "Another option" in the question) is to compress at A, then encrypt, then transfer the compressed+encrypted data to B. On retrieval, that same compressed+encrypted data is forwarded from B to A (or A'), decrypted, then decompressed. This reduce bandwidth for backup and retrieval, and storage requirements at B.

B does not need to decompress or decrypt the data at any point: the question's "but then B should be able to decrypt the data to decompress it" is true, but a non-issue. B does not need the key, and (thus) can't decrypt.

What is an issue is direct access to a portion of a huge data set: for many common compression algorithms, that requires transfer of all the data before the point being accessed (sometime, all the data). This is solved by a split-then-compress-then-encrypt strategy, where the plaintext is split in segments that are compressed independently, then enciphered independently (or mostly so). But the splitting tends to reduces compression, especially for short segments.

Another issue is that the compression ratio leaks to an eavesdropper, and that reveals something about the data. This can be a serious issue: for voice, it has been shown to be enough to understand what's being said!


choices for k in binary finite field modular reduction algorithm

$W$ is the size of the words we are operating on, and hence $u_k(z)$ is a precomputed polynomial for each bit of a word (note $0 \le k \le W-1$), defined as $z^kr(z)$. So if we have 32 bit words we have 32 precomputed polynomials, indexed by $k$.

Then, in the actual algorithm, at each step we compute $k$ as $(i - m) - Wj$, and use that value $k$ to select one of our precomputed polynomials, which we add to $C\{j\}$. So $k$ is not randomly selected, it is deterministically computed at each step of the algorithm and then used to select a precomputed polynomial.

As an example, if we are at a step where $i = 128, j = 2, m = 64, W = 32$ we would compute $k = (128 - 64) - 32  * 2 = 0$. So we would add $u_0(z) = z^0r(z) = r(z)$ to $C\{j\}$.


Can chaining hash functions reduce security?

Yes, there are concrete cases where chaining cryptographic hash functions reduces security; and you gave one. SHA-256(SHA-1(x)) is in particular less collision-resistant than SHA-256(x). We now know collisions for SHA-1(x), and these give collisions for SHA-256(SHA-1(x)), but not  SHA-256(x).

More generally, a chain of hashes is neither more collision-resistant, nor second-preimage-resitant, than the first hash performed is. Thus inserting a weak hash as the first/inner is a recipe for weakening an otherwise fine hash.

On the other hand, SHA-256(SHA-1(x)) resists length-extension attack when neither SHA-256(x) nor SHA-1(x) do; and SHA-256(SHA-1(x)) can be more resistant than SHA-256(SHA-256(x)) is to some attacks in some Proof-of-Work protocol; thus chaining hashes, including different hashes, can have some benefit.


Which PRNG security requirements do I need for key generation

Your idea is not bad, but not a magic bullet. Any serious vulnerability at the root CSPRNG as you describe is fatal for the system facing any serious attacker.

A serious vulnerability being that the attacker can at will force values or predict (partially) values generated in a particular timeframe.

A serious attacker is an attacker knowing your protocols and schemes - if you're worried about things like this and follow Kerckhoff's principle then you should assume you are indeed facing a serious attacker.

However, I doubt that things like CryptGenRandom face a serious vulnerability as described above. This does however not mean it's immune to things like related key attacks and biases. This is where your idea could potentially help.

If you're slightly distrustful of the underlying RNG and need high volumes, hash it and most potential biases/attacks should disappear.

If you don't require large volumes of seeding data, get a lot of output from the RNG and use a KDF to limit key space attacks.

If you want any kind of security that's worth it's salt get a hardware random number generator.


Of what use is my code for finding prime numbers of a certain size?

I'm sorry to say that your code is likely to have essentially zero use.

Primes used for cryptography (e.g., RSA), are on the order of 2,048 and 4,096 bits of length, or respectively roughly 616 and 1,233 digits long. Algorithms already exist to rapidly find (random) primes of this size, and unless you've broken new ground in number theory, your approach is slower.

Additionally, the general trend lately is moving away from systems like RSA towards elliptic-curve based cryptosystems which have no need for the generation of primes.


Could a 2nd EC private key be derived from a public key?

Given a EC public key, can a different, but plausible and functional private key be derived to match the public key?

No, a public key will correspond to only one private key (with one minor exception, which I will explain below).  With Elliptic Curve systems, the private key is an integer $d$ between 1 and $q$ (the order the generator point $G$), and the public key is most commonly the point $dG$, which defined to be $\underbrace{G + G + ... + G}_\text{d copies}$.

Now, the order of the generator has this property: all multiples less than the order will be distinct.  That is, if we consider the sequence of points $G, 2G, 3G, 4G, ..., (q-1)G, qG$, there will be no duplicates in that sequence.  What this means is that, since a public key occurs somewhere in the sequence, that is the only occurance; there won't be another private key (less than $q$) that will also yield that public key.

Now, the minor exception I mentioned: some elliptic curve systems don't use the full point $dG$ as the public key, sometimes they use only the x-coordinate as the public key.

It turns out, in that case, there is a second private key value that would yield the same public key; the value $q-d$.  There are no others, and that second key turns out to be of no use to an attacker; recovering that value is no easier than recovering the original value of $d$.


Sequential delayed release of chained HMAC keys for use as asymmetric signature

That sounds like Tesla, which also uses a chain of MACs (where each key can be computed from values later in the chain), revealing the previous MAC key with each packet.  Going through the paper, I don't see how they authenticate the last value; my recollection was that they used a conventional signature scheme.


I have a 256bit fully random entropy source from dices, which is probably not cryptographically secure.

If you roll enough dice, the rolls are fair, and no adversary can monitor them, it is cryptographically secure.  The reason is simple: an adversary who can't snoop on the dice rolls can't guess the results in any reasonable amount of time either.

You should concatenate (not add!) the results in the exact order you get them.  Each roll of a fair six-sided die has $log_2(6) = 2.58$ bits of entropy, so you need 100 rolls from six-sided dice to get to the 256-bit mark.

The more complex case comes when the dice rolls aren't fair:

The dice are unbalanced, so that one side is heavier than the others, and thus the side opposite to that one is disproportionately likely.  (Casinos use special dice designed to be more balanced than ordinary dice.)
The dice are rolled in a way that doesn't really randomize the results.  (Shaking the dice vigorously in a dice cup is said to improve the fairness of rolls.)

In the case of an unbalanced dice, imagine for the sake of argument that a six is the most likely outcome, and the probability of rolling it is not 1/6 ($16.\overline{6}\%$), but rather 17/100 ($17\%$).  Then each roll has a min-entropy of $-log_2(17/100) = 2.556$ bits, so 100 rolls give you $255.6$ bits of entropy—just short of 256 bits.

In such cases you might need more than 100 dice rolls to get to a full 256 bits of entropy.  Or alternatively and much more practically, you could just convince yourself that the 100 dice rolls, even if somewhat unfair, are actually way more than enough to provide adequate security.  You almost certainly don't need 256 bits of entropy anyway. Why not just settle for about 128 bits?  Won't you get bored rolling 100 dice?  Be practical!

  I have read that it's customary to take the hash of the entropy source in order to generate a safe key.

What you need to do is encode the outcome of the rolls into a 256-bit string so that none of the possible 256-bit strings is significantly likelier than the others.  Hashing a string with the results is a convenient way of achieving that.

  Somebody suggested to me to take the SHA-256 of the entropy source, but wouldn't that cut the entropy in half,as the SHA-256 actually has only 128 bit entropy?

Hash functions don't have "entropy"—the result is determined by the input, so the result of the hash function can never be more unpredictable than the input.  An attacker who has a technique for guessing the input to the hash can use the same technique to guess the output.

That 128-bit security number you allude to is the collision resistance—how much effort it takes an attacker to find two inputs of the attacker's choice that produce the same output.  That is not relevant here because your scenario is different: you're choosing the input to the hash function, and you're showing neither the input nor the output to the attacker.

Intuitively, what the output size of the hash function does here is put an upper limit on the difficulty of guessing the result (and thus the entropy of your hashed output):

If your dice roll input has fewer than 256 bits of entropy, the quickest path for the attacker is to try and guess your dice roll results and calculate the SHA-256 result for each guess.  So in this case the output has exactly as much entropy as the dice rolls.
If the dice rolls have more than 256 bits of entropy, the quickest path for the attacker is to try and test all the possible SHA-256 outputs, without bothering to consider which dice roll inputs produce which outputs. This means that in this case the output can't have more than 256 bits of entropy.

This also answers your questions of "What happens if I cram more entropy into the hash function, say 270 bits" and "What happens if the hash function's output is of more bits than the entropy source (hash 256 bits, but entropy source only 250 bits), what happens then to the security of the key?"

  Shouldn't I use the SHA3 variant instead of SHA2 as it's newer and more recommended?

It is extremely unlikely to matter in practice.


What exactly is addition modulo $2^{32}$ in cryptography?

In cryptography, addition modulo $n$ (where $n$ is a positive integer, maybe $n=32$ as in the original question, or $n=2^{32}$ as in the revised question) is usually understood as the application from $\mathbb Z\times \mathbb Z$ to $\mathbb Z$, $(a,b)\mapsto c$ with $c$ such that $0\le c<n$ and $(a+b-c)$ is a multiple of $n$. That's also a common sense in math, although there the result could rather be in $\mathbb Z/n\mathbb Z$ (recall $\mathbb Z$ is the set of signed integers, whereas $\mathbb Z/n\mathbb Z$ is the set of equivalence classes of the relation: equal modulo $n$).

We may write $(a+b)\bmod n=c$ using \bmod in $\TeX$. This implie $a+b\equiv c\pmod n$ using \pmod in $\TeX$, but only the former restrict $c$ to be in range $[0\dots n-1]$.

When the modulus $n$ is the $k$-th power of $2$ ($n=2^k$), addition modulo $n$ is also called $k$-bit addition. Thus, addition modulo $32$ is the same as $5$-bit addition, and addition modulo $2^{32}$ is the same as $32$-bit addition.

Often, in cryptography, we assimilate numbers to bitstrings, and the output $c$ of the operator is not a number, but rather a bitstring representing $c$ in base $2$ (over exactly $\lceil \log_2n\rceil$ bits and most significant bit first unless otherwise stated).

Thus the result of addition modulo $32$ of $27$ and $8$ is the integer $3$, or the bitstring 00011, depending on context. And the result of addition modulo $2^{32}$ of $2000000000$ (0x77359400) and $3000000000$ (0xB2D05E00) is $705032704$ (0x2A05F200) or the bitsring 00101010000001011111001000000000, because $5000000000-705032704=2^{32}$.

Sometime the inputs $a$ or $b$ of the operator are restricted to be non-negative, or/and less than $n$, or/and bitstrings, perhaps of fixed or limited size. Sometime the output range for $c$ is $-n/2\le c<n/2$ rather than $0\le c<n$ (e.g. for implementation of 32-bit addition in contexts lacking unsigned 32-bit type, see below). YMMV.

There is a Wikipedia entry on modular arithmetic which is a better introduction to that subject, but lacks the specialization to crypto and discussion on bitstrings.

The following discussion is exclusively about Java (except for restrictions of the language in some Java Cards, which may not support type longor even int), and thus somewhat off-topic here, but well.

When working with variables of type long (also int, short, byte) (a+b)&0xffffffffL is the sum of a and b modulo $2^{32}$ in the cryptographic sense, and of type long. That &0xffffffffL technique works for operators + - * & | ^ ~ (but not % /). It can be extended to any modulus $n=2^k$ with $0\le k\le63$ by adjusting the constant, which is $n-1$. Further, when $0\le k\le31$ we can remove the L, and if both a and b are of type int, shortor byte, the result will be of type int.

The definition of operators + - * & | ^ ~ (but not % /) operating on int variables is such that you can get along with assuming these operators work modulo $2^{32}$ as defined in cryptography, except that numbers in range $[2^{31}\dots 2^{32}-1]$ are represented as a negative int in Java. This makes code clearer, simpler, faster, and (for arrays) conserves memory. That technique is used because, before Java 7, there was no unsigned type in Java.

For n of type int in range $[1\dots2^{31}-1]$ and operands a and b of type int in range $[0\dots2^{30}-1]$, (a+b)%n is the sum of a and b modulo n in the cryptographic sense, and of type int. This does not hold for the full range of input operands for two independent reasons:

when the left operand of operator % is negative and not a multiple of the right operand, the result is negative;
(a+b) is defined to be the integer $c$ with $-2^{31}\le c<2^{31}$ and $c\equiv a+b\pmod{2^{32}}$, from which it follows that sometime $(\mathtt{(a+b)\%n})\not\equiv (a+b)\pmod n$ (though that second issue can not occur when $n$ is a power of two, including for $n=32$).

Notice that, except for educative/testing purposes, it is seldom a good idea to implement a cryptographic primitive in Java: in production, one should use more efficient primitives called from Java.


Difference between mix networks and onion routing

A mix-net is a combination of proxy servers which bounce all the request into some sort of 'backpack' where anyone can see the whole thing going on but it would be really hard to tell which is which.
Example
We have Mike,Dom, Peter and Jean, they're using a mix-net and each one sends a request to the mix-net. what it'll do is that it'll take all the request, put them into a 'bag' and bounce them all and distributed each message to a new mix node, each of which also had a couple of messages in their bags already. Then those nodes distributed messages to 6 more mix nodes, and those mix nodes opened the messages and distributed them to recipients.

Difference Between a mix net and onion routing
using a mix-net someone could see your traffic but it might be impossible to determine where did it go due to the fact mix-net collects all the messages (http requests) and bounce them all.
another fact is that the mixing will just work if there's more than one message in the proxy server otherwise it will behave like onion-routing with a delay time.
mix-nets don't use encryption on layers as onion routing does.
Onion routing was developed to enable privacy not security thus someone could use a man in the middle between the first node and the last node of your circuit and using a traffic analysis it could find out. your location plus he'll know what you're looking for due to the last node will send the request to the destination without any encryption at all
Summary : if it wasn't because of all the messages,the bouncing and redirection a mix net would work as same as onion routing but without encryption.
For more info read: https://ritter.vg/blog-mix_and_onion_networks.html


Yes, they refer to the same curve. I'm not sure why the equations' different, but I believe that's just a transcription error. The 04 in basepoint is just standard way to encode a point in SECG #1.

EDIT: (Answer extracted from the comments)

In the SECG case:

a = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF 00000000 00000000 FFFFFFFC

and

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF 00000000 00000000 FFFFFFFF

so $a = (p-3) \bmod p$

the Nist version does $x^3 - 3x + b \mod p$, whereas the SECG version does $x^3 + (p-3)x + b \mod p$. Subtracting $3x$ or adding $(p-3)x$ is equal $\bmod p$


Ideas for non duplicate cryptographically secure numbers

I had to do the exact same thing for unique product identifier codes. In my case they needed to be random looking, not cryptographically secure, so I had more room to work with. I still went with a cryptographic method since that is what I was familiar with.

In your case, you are looking for just under $2^{36}$ values, for which all values are unique, and where guessing the next number in a sequence is infeasible (at least 50 billion possible choices), even when given all previous values.

For this the easiest option is a block cipher with a block size of at least 37-bits performing the encryption operation on an incrementing counter. DES, Blowfish, AES, and others all meet the criteria, the difference being key size, ciphertext size, and hardware support. Since 64-bit Go supports AES hardware acceleration, it is probably your best option.

Simply generate a cryptographically random key, start with an all 0 block, encrypt the block and save the output, increment the input block by treating it as 2 64-bit integers and incrementing the 2nd one (+1), repeat steps as needed until all values are generated. You can generate quadrillions of unique and cryptographically pseudorandom 128-bit values.