Coefficients in Shamir's Secret Sharing Scheme

In Shamir's scheme is a secret sharing scheme, that is, someone that has fewer shares than is required get no information about the secret.  For example, if we have a system where we require 3 shares to reveal the shared secret, then someone with 2 shares cannot be able to reconstruct it.

This is true if we make the shared secret the zero-th coefficient; with $N-1$ shares, every possible value for the zero-th coefficient is equally possible.

This turns out to be also true for the (N-1)th coefficient; however it turns out not to be true for any intermediate coefficient.

Here's a simple example to illustrate this; suppose we pick the field $GF(5)$, and we select $N=3$ (and is, 3 shares are required to reveal the secret); hence we pick a quadratic with the secret as one of the coefficients.

Then, we distribute the shares; in this example, two of the shares we distribute are $(1, 1)$ and $(4, 0)$; that is, the holder of those two shares know that, for the secret polynomial $P$, we have $P(1) = 1$ and $P(4) = 0$.

Now, the holder of two shares should not be able to reconstruct the secret; however what they can do is list all the quadratics that are consistent with the values he does know.  There are five possible polynomials with degree at most 2 that meet the criteria:

$$0x^2 + 3x + 3$$

$$1x^2 + 3x + 2$$

$$2x^2 + 3x + 1$$

$$3x^2 + 3x + 0$$

$$4x^2 + 3x + 4$$

It is easy to confirm that plugging in $x=1$ and $x=4$ into the above polynomials will result in the known values 1 and 0.

Now, our attacker knows that one of these five equations are the secret one, but he has no information on which it can be.  If the shared secret were the 0th or the (N-1)th coefficient, we can see that he learns nothing; all values are equiprobable.   However, if the shared secret were the middle coefficient, well, all these polynomials have a middle coefficient of 3, and so the attacker would have learned the secret, even though he shouldn't have been able to.

This sort of thing can happen to any of the middle coefficients; the only safe coefficients are the first and the last.

---- UPDATE ----

Ok, I found a case where a middle coefficient is also safe; that is the case where the field has characteristic 2 (i.e. is $GF(2^n)$ for some $n$), and $N=3$.  In that specific case, it turns out that the behavior I listed above cannot happen; all $2^n$ possible equations (when $N-1$ shares are known) will have different values for the $x$ coefficient.  I believe that this specific case is the only example of a situation where an intermediate coordinate is safe; that in all other cases, you can find $N-1$ shares so that an intermediate coordinate is determinable with $N-1$ shares.


Why is it recommended to hash passwords with a secret salt?

NIST document section 5.1.1.2 Memorized Secret Verifiers.

That section is a "SHOULD" not a "SHALL".

It is standard practice not to keep the salt secret but to save it with the password hashed verifier.

If the salt is not secret a brute force search is possible if the password is weak such as being on a list of frequent passwords. One example source of such frequent passwords is SecLists.

If the salt is secret such a brute force search will not succeed. Note: stored separately from the hashed memorized secrets (e.g., in a specialized device like a hardware security module) and such a device is generally not available.


Primes are important because the security of many encryption algorithms are based on the fact that it is very fast to multiply two large prime numbers and get the result, while it is extremely computer-intensive to do the reverse. When you have a number which you know is the product of two primes, finding these two prime numbers is very hard. This problem is called prime factorization and finding an algorithm which does it fast is one of the unsolved problems of computer science.


OK, there seems to be some confusion with regards to terminology, so let's try to clean that up. I'll try and define things myself, but also provide the more formal Wikipedia definitions.

Encryption. Encryption usually is the process of concealing information solely based on the secrecy of some smaller value, which is called "a key" most of the time. Modern schemes allow for advanced functionality, such as operation on unknown data and guaranteeing the data integrity. Algorithms are not secret with encryption *.
*Except if you experience snake-oil crypto from which you should run. fast.

Wikipedia's definition:

  In cryptography, encryption is the process of encoding messages or
  information in such a way that only authorized parties can read it.

Compression. Compression algorithms are techniques that exploit redundancy in data to reduce the size of the data representation. This redundancy may be of strict mathematical nature or also of psychological nature (e.g. humans don't hear beyond 20-30kHz so you can strip that out as part of the compression). Compression algorithms aren't meant to conceal data, but may do so, if the compression algorithm is secret - until somebody reverse-engineered the algorithm.

Wikipedia's definition:

  In signal processing, data compression, source coding, or bit-rate
  reduction involves encoding information using fewer bits than the
  original representation. Compression can be either lossy or lossless.

Encoding. Encoding is the process of changing data representation. The same data may be represented in different encodings (such as binary, hex, decimal, base64, DER, BER, ...) which aren't (usually) meant to change the data's meaning. Size expansion / reduction may of course be a result of a different encoding. Encodings aren't meant to conceal data, but may do so, if the encoding / decoding alorithm is secret - until somebody reverse-engineers the algorithm.

Wikipedia's definition:

  An encoder is a device, circuit, transducer, software program,
  algorithm or person that converts information from one format or code
  to another, for the purposes of standardization, speed or
  compressions.

Codec. Most of the time a codec is a special compression format, usually paired with a defined encoding.
Wikipedia's definition:

  A codec is a device or computer program for encoding or decoding a
  digital data stream or signal. [...] A codec encodes a data stream
  or signal for transmission, storage or encryption, or decodes it for
  playback or editing.


Choosing asymmetric pairing for Elliptic Curves

Not all elliptic curves are suitable for use with pairings - you need to choose a pairing-friendly curve. There are several families of pairing-friendly curves; one of these is the set of Barreto-Naehrig curves. They are a good place to start.

For pairings that require that $G_1$ be distinct from $G_2$ (type 3 pairings, including the optimal Ate pairing), $G_2$ can be computed as the trace zero subgroup of the $r$-torsion; that is, it is the set of points which lie in the kernel of the trace map.

If $E$ is a Barreto-Naehrig curve, we know that the $r$-torsion embeds in the degree-12 extension $E(\mathbb{F}_{q^{12}})$. We also know that there is a related curve $E'$ (often called the twisted curve) over the degree-two extension $E(\mathbb{F}_{q^2})$ for which an efficiently computable group isomorphism $\psi : E'(\mathbb{F}_{q^2}) \to E(\mathbb{F}_{q^{12}})$ exists.

In our work, we generated elements of $G_2$ by first choosing arbitrary points on $E'(\mathbb{F}_{q^2})$, then converting them to $r$th roots. This is done using the fact that the order of $E'$ is $r * (2q - r)$, so if we multiply a point $p$ by $2q - r$, we get a point of order $r$. Once we have the $r$th root, we map it into the trace zero subgroup $G_2$ using the anti-trace map, defined as

$aTr(P) = 12 \cdot P - Tr(P)$

where the trace of a point $P = (x, y)$ on $E'$ is defined as

$Tr(P) = \sum_{i=0}^{11}(x^{q^i}, y^{q^i})$

where addition is elliptic curve point addition on $E'$.

I know this is pretty hand-wavy. There is a lot more detailed description in the online book "Pairings for Beginners" by Craig Costello.


Lattice-based cryptosystems for blockchain/ledger?

Are there [...] blockchain solutions for a post quantum world?

Quantum Computing and related algorithms are no threat to the current protocol of Bitcoin (and most other blockchain systems I am familiar with) at all. Indeed, Shor's algorithm can solve the Discrete Logarithm Problem (DLP) efficiently, and a modified version exists for the elliptic curve analogue (ECDLP). Blockchain systems in their conventional form are based on

preimage and collision resistance of the employed hash functions for most functions, including transaction IDs, block IDs, and the Proof-of-Work (PoW) scheme in mining
hardness of DLP/ECDLP for security of transaction signatures and user addresses (so that private keys can not be found)

At the current state of research, most consider hash functions quantum resistant due to their lack of mathematical structure. As mentioned, (EC)DLP is not resistant.

However, if user addresses are never re-used then this is irrelevant, since an attacker will only learn a users clean (i.e. non-hashed) public key once a transaction is signed in the name of said user address/public key. As long as the hash function (e.g. SHA-256) is preimage-resistant, an attacker has nothing to apply Shor's algorithm on.
So there is no pressing need for alternatives yet.

Nonetheless, lattice-based crypto is a proposal that comes up once in a while - to my knowledge no actual blockchain implementation exists as of today. As for the Shortest Vector Problem (SVP): the most efficient known algorithms are mentioned in the Wikipedia article.


salting with password hash to improve security?

Security against attacks using rainbow tables requires using a salt. In your first step $A_1 = MD5(P || S)$, you're already mixing in a salt. Provided that the salt is indeed globally unique (and randomly generating the salt is a correct way of achieving that), you already have protection against rainbow tables.

In a nutshell, rainbow tables trade off a huge amount of pre-computation for the ability to crack many hashes quickly. As soon as you use a salt, a useful rainbow table would have to accommodate for all possible salt values, which very quickly becomes impractical.
For more information, read
What are rainbow tables and how are they used?

There is nothing to be gained by mixing the salt in again through another application of MD5. However, if you repeated the process many times, you would achieve another property that is necessary for a password hashing function, namely that it must be slow, because that hurts the attacker far more than the defender. On this topic, do read
How to securely hash passwords?

So if instead of using $A_2$ you used $A_{10000}$ (or however many iterations would be reasonable based on current CPU speeds), you would have what looks like a reasonable password hashing scheme, built along the same lines as PBKDF2, which is one of the recognized good password hashing functions. However, in cryptography, details matter. Maybe what you're doing is as good as PBKDF2, or maybe it has a fatal flaw that isn't immediately obvious to me. It would take a long time of analysis by multiple expert cryptographers to determine whether your password hashing function is acceptable.

Therefore, don't roll your own: use a generally-approved password hashing function. There are three big names: scrypt, bcrypt and PBKDF2. Scrypt is the new and improved thing, bcrypt is tried and tested, and PBKDF2 is showing signs of age, so bcrypt and scrypt are slightly preferable, but even PBKDF2 isn't fundamentally wrong. All three have PHP implementations available.


Which cipher to use with openssl for shortest output?

It could be better to use PGP, which has been designed to encrypt files.

Only OpenSSL v1.1 latest versions contain a command line switch to choose the number of iterations (the work factor) to configure the password hash when using password based encryption (PBE). This is something that is required, otherwise the password must be of about the same strength as your original password. That would of course not help you any further.

As you require just normal confidentiality you could just use AES-CTR mode for PBE. Then there is just 16 bytes of overhead for the salt and header (you could remove the first 8 bytes of magic and replace it back afterwards as optimization). So then the ciphertext would be only 8 bytes more than the password. Base 64 - you can forgo the base 64 padding characters - will just expand this by one third.

However, the password consists solely of lowercase characters. So each character only needs to take 5 bits (2^5 = 32 which is greater than the 26 values required). So that way you can save 3 bits per character.

So the minimum size of the maximum value would then be 24 * 5 / 8 = 15, 15 + 8 = 23 bytes, expanded to (24 / 3) * 4 = 32 base 64 characters.

But don't forget to write down or remember the iteration count and - of course - the algorithm itself.

It might be easier to use e.g. an IronKey to store your passwords on a USB stick (or two), which would cost you about 50 Euro per piece. Remember that flash may not last forever though, it can leak state over time.


It looks like the first paper you linked hints at an explanation.

From what I can tell the idea is the same as with "intermediate tags", that is you have an instance of your cipher and you process all the data up to some point, then create a MAC-tag, insert it into the data stream for later verification and continue with the very same instance to process more data. The paper says:

  With appropriate domain-separating padding the security proofs allow
  the sponge states to be used for any number of consecutive
  authenticated messages (“MAC-and-Continue”) without the need for
  sequence numbers, and re-keying.

So why should one want to do this?

TL;DR: It's a "nice feature" to the programmer and data structure designer.

Strictly speaking you cannot be sure of the security of a decrypted message until you have fully verified the integrity of the entire message. That means if your message is 1MB you have to authenticate and decrypt the entire 1MB message before your crypto implementation should pass it on to the application. And with usual modes the tag marks the end of the message meaning you have to potentially re-initialize instances and worry about what the new nonce shall be. "Mac-and-Continue" simplifies that in that you can just insert a tag pretty much anywhere in the 1MB chunk and then all the data up to that tag is authenticated, meaning it can be handed to the application much sooner than expected. This helps to reduce buffer sizes, reduce latency (as you have less to process before being able to pass it on) and it eliminates the worries you would have if you had to manually design a mode that has chunks (which means defining nonces, protecting against re-ordering attacks and re-initializing your mode object).


Here's a solution:

If we assume many pairs $(c_i,p_i)$, and all the $p_i$ are primes (because  often the letter $p$ is used when talking about primes, and you relate to the DLOG problem in your question where the modulus is also prime), then we can use this method:

We ignore all the $c_i$. For every $p_i$ we find one generator $g_i$ of the entire group. And then we use the Chinese Remainder Theorem to find $g$, which fullfills $g = g_i \mod p_i$ for every $p_i$. Now $g$ is a generator for every subgroup, and therefore for every $p_i$ there exists some $r_i$, s.t. $c_i = g^{r_i}$. This has nothing to do with the DLOG problem, it is just finding a generator for several groups.

But if we assume any random $p_i$, then we also need a closes look at the numbers, and we need to consider all the $c_i$ as well:

First, we need to check which $c_i$ are not coprime to their respective $p_i$. If $ggt(c_i,p_i) = a$, then we already know that $a$ is a prime factor of $g$, which is like the equation $g  = 0 \mod a$ in the CRT.
Then, instead of looking at the individual $p_i$, we look at all the prime factors of all $p_i$ instead, which are coprime to $g$. And we need to take the prime powers of those factors into account, but it's quite straight forward as well.


Embedded device needs PRNG, has AES & EEPROM

No it's not that simple because you'll be selling kit that has  predetermined secret information within it.  Why should I use Orthrus when you know the PRNG seed?  How can I trust you when your user name starts with the letters NSA?  Seriously though, I don't think that your Mega32 is a secure  chip (cryptographically) so someone might be able to read back the seed using their own software.  There might also be side channel attacks.  (It might be worth while posting another question specifically regarding use of a Mega32 for secure computation.  There are people here who are very knowledgeable about that).

That aside, you have huge computational power on that chip and a shed load of I/O ports including a comparator on port D. And you have AES functionality.  Include a hardware random entropy source.  They're fairly easy and there are circuits widely available. Try to avoid using a reverse biased transistor as they're unstable long term, but if you only switch them on at card initialisation, you'll be fine.

Build one or two transistor or diode circuits, feed them though your comparator and you'll get thousands of bits of entropy in a few seconds.  Worth the wait for the undoubted benefits.  Pass a secure hash function over it like SHA-1, and you have your perfect seed material.  (I personally prefer Pearson hashes in memory rich environments).  You can generate 16 bytes of pure entropy in no time.  Ask another question about the specifics of this later.

The important part of what I've said is marketing.  You can market a hardware entropy source on the grounds of "quantum security" , "no one knows the seed", "unique randomness" etc.  Sounds a lot better than "I hid something inside the chip that I hope no one finds. Ever". The value of security through obscurity is debatable, but either way cannot trump quantum physics.


How to handle entropy and CTR DRBG for TLS on embedded system?

Unless you have documentation about the RNG interface that states that it's using a cryptographic PRNG seeded by an entropy source, use it only as a seed to a PRNG. (Seed initially, and re-seed from time to time as directed by the PRNG algorithm and possibly by certification requirements. Since you're using an existing PRNG library, just pass it the seed function and let it manage when it seeds.)

A hardware RNG always has biases. Those biases may be negligible or not depending on conditions, for example it may perform poorly at certain temperatures or if the power supply is not optimal. A cryptographic PRNG removes observable correlations from the RNG. Even if the seed is not perfectly uniform, the PRNG hides the biases: either the attacker manages to guess the whole seed (i.e. the whole HRNG output), in which case all is lost anyway, or the attacker only manages a partial observation (e.g. after a 1 bit, there's a 50.1% chance that the next bit is also 1) and the PRNG makes that observation useless on its own.

An ideal system uses a HRNG that's unconditioned, i.e. that has no mechanism to eliminate biases, and runs some basic tests about its output based on the known failure modes (e.g. a particular sensor might return all-bits-0 if not properly initialized). The output is then used to seed a PRNG. When that process is hidden in a black box labeled “RNG”, it's hard to verify that the entropy source is operating correctly.


If a single bit was known through all states in AES, which would cause the most information to leak?

If you are an attacker and could watch one bit of AES-128 for 10 rounds, which bit would you choose to recover the most useful information? I feel it would be a bit in the key schedule.

Actually, I'd expect a leak of one of the internal state bits would give the attacker more information.

The key schedule is static, and so if you leak 10 bits, well, you still have (at best) 118 bits of uncertainty in the key; no where close to small enough to be useful for an attacker.

However, if you leak the internal state, you can look at (say) one of the internal state bits after each round.  The advantage there is that we can look at the bits for a number of known plaintexts/ciphertexts; this yields considerably more information.  After 1 round, an internal bit is a function of the plaintext and 33 key bits; by looking at a number of plaintexts, we can get enough information to deduce those 33 key bits.


Mathematical Proof for Key independence in Differential Cryptanalysis

The difference between the pair of inputs going into the s-box (consisting of two plaintexts xored with the first round key) is the same as the difference in the plaintexts alone.  i.e. $(P_0 \oplus K_0) \oplus (P_1 \oplus K_0) = P_0 \oplus P_1$, because the round key $K_0$ cancels out.  Hence, the input difference is independent of the value of the first round key.  No matter what value you pick for $K_0$, the difference of the two inputs going directly into the s-box will be the same as the difference between the two plaintexts, with probability 1.

On the contrary, the output difference (difference between the outputs of the two s-boxes) is not independent of the round key.  Or to be more precise, if you know $P_0$, $P_1$, and $K_0$ then the output difference just after the s-boxes -- $S(P_0 \oplus K_0) \oplus S(P_1 \oplus K_0)$ -- is fully determined and will vary depending on the precise value of $K_0$.

If, however, you assume that the pair of plaintexts is chosen uniformly at random from all pairs that satisfy some particular difference $\Delta P$, then the probability that the output difference will equal some particular value $\Delta C$ is independent of the precise value of $K_0$.  This is because any given value for $K_0$ will simply exchange one pair of plaintexts that xor together to equal $\Delta P$ for another pair that xor together to equal $\Delta P$ (because of the equality in the first paragraph above).  As such, the input pair going into the s-box after the roundkey is applied is still a uniformly random pair that xors together to equal $\Delta P$.

So under the assumption that the input difference is fixed but the input pair that xors together to equal that fixed difference is selected uniformly at random**, the probability that the output equals $\Delta C$ is purely a function of the (unkeyed) s-box, as summarized in the difference distribution table for the s-box.  Note that this is different for key-dependent s-boxes.

** This assumption is equivalent to the assumption that the input pair is fixed but the roundkey is selected uniformly at random.


An involution is a function $f$ from a set to itself, such that $f\circ f$ is identity (i.e. applying the function $f$ on the result of the function $f$ gets back to the original element, i.e. $f=f^{-1}\,$). Recall that $\circ$ is function composition.
A permutation is a function $f$ from a set to itself, such that there exists a function $g$ from that set to itself, such that $g\circ f$ is identity (i.e. applying the function $g$ on the result of the function $f$ gets back to the original element). Equivalently, it's a bijection from that set to itself.
It follows that every involution is a permutation. And a permutation $f$ is an involution if and only if $f\circ f$ is identity.
A random involution (resp. permutation) is one chosen (implicitly: uniformly) at random among these over a certain finite set.
There are $n!$ (OEIS A000142) permutations of a set of $n$ elements, but much less involutions (A000085) for $n>2$. Orange is the number of permutations and blue is the number of involutions.

Among differences of cryptographic significance: a permutation can be one-way, but an involution can't (since any algorithm implementing an involution implements its inverse).
Also: for all $k\in[1,n]$, iterating a random permutation starting from a fixed point cycles on or before $k$ step(s) with probability $k/n$, while for a random involution that's certain when $k\ge2$, and with probability above $1/n$ for $k=1$ and $n>2$.


Cryptographic random numbers for key generation

There are many "cryptographically strong pseudorandom generators" and we know how to construct them well. If you have a strong 128-bit (or more) key $k$, then you can just use AES-CTR to get as much randomness as you need: $AES_k(0)||AES_k(1)||AES_k(2)||\cdots$. You can also do a similar thing with SHA256. The real problem that arises is where to get the key from in the first place. Typically, there is a source of entropy. This is turned into (almost) uniform randomness (a.k.a. a key) using a randomness extractor. In cryptographic applications, this is often achieved by just applying a hash function like SHA256 to the source.

When OpenSSL is run in Linux, it takes its initial random source from /dev/urandom. This is already a problem since /dev/urandom (unlike /dev/random) is not blocking, which means that it provides randomness even if the Linux entropy pool is empty. What makes it worse is that OpenSSL does not reseed if the entropy pool was originally low.

I just heard an interesting talk at BlackHat 2015 about this. The above claim about OpenSSL is based on their analysis of the code. You can see more information in their PPT and white paper (I don't agree with everything they say but it's very informative and good work).

I suggest that you reseed the OpenSSL generator yourself (using rand_seed) either by calling /dev/random yourself (you can query to see if the entropy pool has enough randomness in order to prevent blocking; use the command: # cat /proc/sys/kernel/random/entropy_avail), or by using RDSEED, which is a hardware generator inside all Intel chips from Ivy Bridge. See (https://software.intel.com/en-us/blogs/2012/11/17/the-difference-between-rdrand-and-rdseed for more info.)

It seems that due to Snowden fears, Linux does not use RDSEED. My opinion is that it should certainly be used, at least to add randomness to the OpenSSL generator.

One final note: if you generate a new process to check the available entropy, then you will modify the pool. It seems that the Linux operating system using 256 bits of randomness from the pool every time a process is generated (for random memory allocation etc.). This is huge overkill and means that the entropy sorely needed for crypto applications may be exhausted for things that don't need real randomness. Anyway, that's life. So, if you want to constantly poll, then generate a single process that will periodically check entropy_avail, and don't generate a new process every time.


What cryptography is suitable to motivate High School students to learn math?

15-18 is an age where kids are looking for independence and question authority of adults.  Cryptography is often horribly implemented, and can serve as a teaching tool of where professionals have gone wrong.

So pick some real world blunders, and do some analysis on those blunders.   There's enough cryptographic blunders that are easy enough for HS students to understand to fill an entire course with.

A good recent example is the Adobe password leak.  A good writeup is available here  You could very easily find the leaked data, create a small, anonymized subset of it, and repeat the same analysis done in the article on that subset.

It's a great example because it uses something kids use every day that's highly mathematical (passwords on websites), but they're unaware of.  It also shows how adults screwed up, which every kid loves, but also how to do things right.  The mathematics is simple enough that you don't need advanced degrees in mathematics, and you don't really need to go into depth on how the crypto works.


What's the reason why CBC-MAC shouldn't use IV or random IV?

I understood that the reason for CBC-MAC not to have random IV is if CBC-MAC has a random IV, the attacker can change the P1 block, making the tag arbitrary, so the CBC-MAC scheme can be insecure. Am I right?

If you assume that the attacker can know the first block of the message and can control the IV then it is easy to see that you can create an identical authentication tag for multiple IV / initial message block pairs. If the input of the first block encrypt and the following blocks are identical, then the authentication tag will repeat.

This won't work for the other blocks as the cipher will change the bits of the next vector independently of the change. An attacker doesn't gain much by being able to change 50% of the of the input of the cipher randomly.

  1-1. Attacker can make the tag arbitrary not depending on the IV because of the property of encryption blocks. Then why we should not use IV or should use all-zero IV?

I don't think the statement in the first sentence of the question is correct. The attacker should not be able to create a valid authentication tag, because the attacker does not know/control the key.

It's however unclear what you mean with encryption block property.

  If we use random IV, then a sender and receiver must share a IV before the receiver receives the tag and it is inefficient, so we don't have to use random IV. Did I understand right?

No. For CBC encryption the IV needs to be unpredictable to the attacker. There are however schemes such as encrypting a counter to generate an unpredictable IV without actually including it with the ciphertext.

As indicated, we don't use a random IV for CBC-MAC. CBC-MAC relies on CBC mode of operation but it doesn't use it for providing confidentiality. So the security requirements of the IV being unpredictable are not applicable to CBC-MAC.

  Are there any other attacks that can made if we use random IV?

I don't directly seen any.

After completely loosing integrity / authentication of a full block of the message, I guess we don't need any others.

Notes:

CBC requires an IV, so lets call this an all-zero IV (any other constant IV would have the same result, a zero IV is just easier to implement);
beware that CBC-MAC should only be used for messages with known-length and preferably a 128 bit (or higher) block cipher, use CMAC, HMAC or an authenticated cipher instead.


Question of proving the opening of Pedersen Commitment

With this zero knowledge proof, the prover attempts to prove that he knows an opening of the commitment.

The obvious way to approach this is to show that, if the prover is able to complete the protocol for two different challenges, he is able to construct an opening of the commitment (and hence he actually knows what he is attempting to prove knowledge of).

How we show this is straight-forward:

Suppose the prover knows a value $y$ for which he can correctly answer two distinct challenge values $e, e'$.  That is, if given the challenge $e$, he can answer with $z_1, z_2$ such that $g^{z_1}h^{z_2} = yc^e$, and if given the challenge $e'$, he can answer with $z'_1, z'_2$ such that $g^{z'_1}h^{z'_2} = yc^{e'}$
Then, given these values, the prover then knows:

$$g^{(z_1-z'_1)(e - e')^{-1}}h^{(z_2-z'_2)(e - e')^{-1}} = c$$

That is, with valid answers to those two challenges, he can deduce an opening of the commitment.

Hence, someone who doesn't know a valid opening to the commitment can provide a valid answer at most one challenge to any $y$ value.


How to select corresponding ciphertext in anonymous Identity-based broadcast encryption?

User $i$ should decrypt using the corresponding $r_i$ value. How do the users know about that?

From my understanding, a sender $S$ computes a polynomial $f(x)=\sum_{i\in\{0,...,t\}}c_ix^i$ which evaluates to $k$ if the the value of $x$ corresponds to the "share" of any of the designated user $ID_1,...,ID_t$ --- a share of a user $i$ as computed by $S$ is $v_i:=H_1(e(rQ_i,d_S))$, where $r=H_2(M,k)$. A receiver $i$, once it sees the polynomial, evaluates it on his share $v_i'=H_1(e(V,d_i))$ and if $v_i=v_i'$ it gets the gets back the key $k=f(v_i')$ (i.e., correctness). So, there is no correspondence between the users and the values of $c_i$s.

  In real implementation, how to define such kind of function for unknown $x$ for $n$ receivers.

As done in the paper, one just sends the coefficients of the function $f(x)$.

P.S. I hope I am not missing something.


There is an excellent paper from Bellare and Namprempre that addresses the security properties of composite schemes in a rigorous and formal manner. Regarding IND-CPA security of Encrypt-And-MAC the paper has this to say:

  E&M does not provide IND-CPA. E&M does not preserve privacy because the MAC could reveal information about the plaintext. This is true regardless of whether the MAC is weakly or strongly unforgeable. We provide details assuming that the MAC is strongly unforgeable below.

  Let $\mathcal{MA = (K_m, T , V)}$ be a given MA scheme. We define an MA scheme $\mathcal{MA'}$ which is the same as the given one except that it prepends the first bit of the message to the tag. Formally $\mathcal{MA' = (K_m, T', V')}$ has the same key generation algorithm as the given MA scheme and the following tagging and verification algorithms:

  Algorithm $\mathcal{T'(K, M)}$
  Parse $M$ as $x||M'$ where $x$ is a bit
  Return $x||\mathcal{T}(K, M)$

  Algorithm $\mathcal{V'(K, M, \tau)}$
  Parse $M$ as $x||M'$ where $x$ is a bit
  Parse $\tau$ as $s||\tau'$ where $s$ is a bit
  If $x = s$ and $\mathcal{V}(K, M, \tau') = 1$ then return $1$
  Else return $0$

  It is easy to see that if $\mathcal{MA}$ is SUF-CMA secure then $\mathcal{MA'}$ is SUF-CMA secure. However, if $\mathcal{MA'}$ is used as the base message authentication scheme in the E&M composition method, the resulting symmetric encryption scheme will not achieve IND-CPA because the first bit of the message is provided to the adversary via the MAC. The adversary can use this to break the scheme in the IND-CPA sense as follows. It queries its $\mathrm{LR}$ oracle with two messages $M_0$, $M_1$ such that the first bit of $M_0$ is $0$ and the first bit of $M_1$ is $1$. It gets back ciphertext $C = C'||\tau$ . It lets $s$ be the first bit of $\tau$ . As per our construction above, $s$ is the first bit of $M_b$ and hence $s = b$, so the adversary returns $s$. The advantage of this adversary is one.

  In fact, we can make a stronger statement. Not only do there exist schemes for which the E&M method fails to provide IND-CPA, but it will fail to be so for most of the commonly defined MA schemes, including CBC-MAC and HMAC, because the latter are MACs. Indeed, an adversary can use the MAC present in the ciphertext of the composite scheme to see whether the same message has been encrypted twice, something which should not be possible if the scheme is to meet a strong notion of privacy like IND-CPA. This attack is successful regardless of whether the underlying MAC is weakly or strongly unforgeable.

  E&M does not provide IND-CCA and NM-CPA. Since both IND-CCA and NM-CPA imply IND-CPA, the above means that E&M provides neither IND-CCA nor NM-CPA secure.

So your line of reasoning that you provided in your question is correct. We can use the fact that a MAC can leak information about the plaintext to break such a schemes IND-CPA security. Then, it follows that, since IND-CCA implies IND-CPA, a scheme that is not IND-CPA is not IND-CCA.


Three-way key exchange with elliptic curves without pairing

Without pairings, there is no known single round tripartite key-exchange algorithm. However, it is possible to do it in two-rounds. For example, refer to the Burmester-Desmedt conference key protocol (http://www.cs.fsu.edu/~burmeste/eurocrypt_plus_proof.pdf) which in fact works for an arbitrary number of users.

This being said, would it be possible to find a protocol along the line you are suggesting? The key problem would be to define the product of two points $Q_1Q_2$ on an elliptic curve. Moreover, for your idea to produce a common key $d_1\cdot Q_2Q_3=d_2\cdot Q_1Q_3=d_3\cdot Q_1Q_2$, you would like this definition of the product to be both bilinear and non-degenerate. Thus, your definition of the product of two points would be some (possibly new) kind of pairing.

Moreover, if the product of two points $Q_1$ and $Q_2$ is again a point on the elliptic curve, you would have an (efficient) algorithm for the computational Diffie-Hellman in this group. From a security point of view, this is bad, because there are reductions that use such an algorithm to solve the discrete logarithm problem once the computational Diffie-Hellman becomes easy (For example see http://www.stanford.edu/class/cs259c/finalpapers/dlp-cdh.pdf).

As a consequence, the most likely answer to your question is: no, it can't be done without pairings.


Forge CBC-MAC given the MAC of two messages and of their concatenation

Yes, your understanding is correct.  With the CBC-MAC's of $(a), (b)$ and $(a||b)$ you can forge the following new messages:

$(a||b \oplus MAC(a)), \\
(b||a \oplus MAC(b)), \\
(b||b \oplus MAC(b)),\\
(a||a \oplus MAC(a)),\\
(a||b||a \oplus MAC(a||b)), \\
(a||b||b \oplus MAC(a||b)), \\
(a||b \oplus MAC(a)||a \oplus MAC(b))\\
(a||b \oplus MAC(a)||b \oplus MAC(b))\\$

...And so on and so forth until you get tired of pwning CBC-MAC with forgeries (assuming the recipient accepts messages longer than the one-to-two blocks we know from the question).


Can timestamping provide evidence of absence before a certain time?

One application for a randomness beacon is to get this assurance.  A randomness beacon (NIST runs a prototype one) generates a sequence of public, signed, timestamped random numbers on a fixed schedule.  (In NIST's case, it's once per minute.)

The beacon operator is promising that the number won't be known to anyone (outside the machine on which the beacon is running) until the time on the beacon pulse.  As long as the beacon operator keeps that promise, you can know that nobody could have known the value of the beacon pulse at 12:31 GMT June 20, 2017 before exactly 12:31 GMT on June 20, 2017.  The beacon service keeps a record of all these pulses, all digitally signed and hash-chained together.  Sometime soon, we're releasing a new beacon format, and a couple other organizations will be running beacons, so you can choose which beacon you want to trust, or even combine them.

If you don't want to trust anyone to generate those random numbers, you can use something else from the environment.  Some people have proposed using closing stock prices, winning lottery numbers, weather data, and hashes from proof-of-work blockchains.  All of those have some issues in terms of convenience, and potentially a small amount of influence that could be applied by specific trusted people[1], but nobody can exactly predict what they will be even a day in advance.

[1] For example, consider weather data: You're going to define some official source as the place you get your cannonical weather data.  Everyone will notice if this source tells you there was a high temperature in DC of 20 C on a day when it really got up to 30 C, but that source will have some wiggle room in reporting a high of 30 C or 31 C.


Decrypting the password from SHA-512 hash value

You cannot recover the password from the hash. That's not something that password hashes are designed for — quite the opposite: with a proper password hash, the only way to recover the password given the hash is to make a guess and verify it — and the better the hashing scheme, the more costly verifying guesses is.

Passwords are used for authentication: a client attempts to prove its authenticity to a verifier by proving that it knows the password. The client knows the password and does not need to recalculate it. The verifier knows the password's hash; the client tells the verifier what it claims the password is, and the verifier computes the hash of the candidate password and compares it with the reference hash. The verifier does not need to compute the password. This works because computing the hash of the password is deterministic (the calculation always gives the same result).

A password hash needs three ingredients:

Hash: a one-way function (or a good enough approximation — a function for which nobody knows how to compute inverses), so that the password cannot be recovered from the hash except with a lucky guess.
Salt: a unique value that makes the hash computation unique, so that adversaries wishing to break passwords cannot make computations that are useful to break many passwords at once.
Slowness: so that brute force attempts by an adversary who knows the hash (make a guess, compute its hash, compare it against the known hash) take an impractically long time even for practical, low-entropy passwords.

See How to securely hash passwords? for a more detailed explanation.

Your password hashing scheme has two of the three ingredients: hash and salt. Keep in mind that the salt must be saved with the hash value so that the same hash computation can be made when a client submits a candidate password. You're missing slowness, which can be achieved by making many iterations of the hash function. There are better ways of achieving slowness which also make it harder to design specialized hardware dedicated to fast password computations; again, see How to securely hash passwords? for more details.


Difference between hierarchical and multi level secret sharing

In a multilevel secret sharing scheme there is only one secret $S$ that all levels seek to find. In a compartemnted scheme we can have multiple secrets that correspond to each level that must be found before $S$ can be recovered. In a compartmented scheme a set of compartments must work together to recover the secret, where each compartment contains a number of participants. In a hierarchical scheme participants from different levels can work together to discover the secret, but they don't have to.

As far as I know hierarchical is interchangeable with multilevel. A disjunctive scheme is indeed simply a hierarchial scheme where participants from different levels can work together but can also find the secret by cooperating with participants on their own level. However a conjunctive scheme is what Tassa terms a hierarchial threshold scheme (see: http://www.openu.ac.il/personal_sites/tamirtassa/download/journals/htss.pdf).

To give an example of this type imagine we have a scenario where there is a safe at a bank that must be opened by employees, however they cannot do this without being in the presence of two senior employees or a manager. This type of scheme is not the same as a compartmental scheme as not all levels must cooperate together to find the secret.

Additionally I think Nojoumian and Stinson have done something similar to what you propose: http://isyou.info/jisis/vol5/no2/jisis-2015-vol5-no2-02.pdf

Hope this helps.


Cryptographically Secure Hash Algorithm with Very Specific Property

No such function with either property would meet the requirements of a secure hash function; either of those properties would make it easy to find preimages, that is, given a value $H(x)$, you can find a value $y$ with $H(y) = H(x)$.

First off, I assume that $n$ is a constant for the hash function; if we were to assume that the first property holds for any $n$, then it is easy to see that the only function that has that property is $H(x)=0$ for all $x$.

To find a preimage of a function with the first property, we would compute the hashes:

$$H(1 + n)$$
$$H(2 + n)$$
$$H(4 + n)$$
$$H(8 + n)$$
$$...$$
$$H(2^k + n)$$

Then, when given a value $H(x)$, we use Gaussian Elimination to find a subset of the above list ${a, b, c, ..., z}$ with $H(a + n) \oplus H(b + n) \oplus H(c + n) \oplus ... \oplus H(z+n) = H(x)$
Then, because of the property, we know that $H(a \oplus b \oplus c \oplus ... \oplus z + n) = H(x)$.

With a function with the second property, it is only slightly trickier.  In that case, we would compute the list:

$$H(1 + n) \oplus H(0 + n)$$
$$H(2 + n) \oplus H(0 + n)$$
$$H(4 + n) \oplus H(0 + n)$$
$$H(8 + n) \oplus H(0 + n)$$
$$...$$
$$H(2^k + n) \oplus H(0 + n)$$

and proceed as previously.


You can in principle encrypt using a hash function, in the manner you describe (although what you have described is not necessarily a secure construction).  What you are trying to do is generate a keystream from a hash function and a key.

You can use counter mode to turn any strong pseudorandom function (PRF) into a stream cipher.  CTR mode produces a keystream that is XORed onto the plaintext to produce the ciphertext (or vice versa).   Some Message Authentication Code (MAC) functions are PRFs; in particular HMAC has been proven (Bellare 2006) to be a PRF if the compression function of the underlying hash is a PRF (as is the case with SHA-2).  So HMAC-SHA256 in CTR mode would be a secure construction that supports encryption and decryption using a hash function.

While you can do this, you probably shouldn't.  The security of block ciphers for this purpose has received more attention, and block ciphers are substantially faster than hash functions.  NIST SP800-108 "Recommendation for Key Derivation Using Pseudorandom Functions" permits HMAC-SHA256 in CTR mode as a key derivation function, but cautions against using the output as a keystream for a stream cipher as "The level of security provided ... has not been investigated".

See also Is SHA-256 secure as a CTR block cipher?.


Recovering the key in an ElGamal Signature Scheme variant

Well, we can approach it this way: if we denote the hashes of the two consecutive messages $H_1, H_2$, the signer used the internal values $k, k+2$, resulting in signatures $(r_1, s_1), (r_2, s_2)$, then we have (and all this arithmetic is modulo $p-1$):

$s_1 = (H_1 - x r_1) k^{-1}$

$s_2 = (H_2 - x r_2) (k+2)^{-1}$

where $x$ is the secret key we're interested in.  Rearranging, we get:

$s_1k = H_1 - x r_1$

$s_2(k+2) = H_2 - x r_2$

where we know the values of $r_1, s_1, r_2, s_2, H_1, H_2$; there's only two unknowns ($k, x$) which both appear as linear terms; we just solve the two simultaneous linear equations, which immediately gives us $x$.

It is easy to see that this observation can be extended to the case where the difference between two different internal $k$ values is something the attacker can guess.


If TDP exist then CCA-secure PKES exist?

For the context of this answer I will assume that that the author meant to say doubly enhanced TDP, since that's the only path I can currently think of. (See Definition 7)

Constructing CCA secure encryption

The relevant construction is due to Dolev, Dwork, and Naor. It is based on a CPA secure public key encryption scheme, a one-time signature scheme and a non-interactive zero knowledge argument. We'll show how those are instantiated below.

The basic idea of the encryption scheme is that we have $2\ell$ public keys $(\mathsf{pk}_1^0,\dots,\mathsf{pk}_\ell^0)$ and $(\mathsf{pk}_1^1,\dots,\mathsf{pk}_\ell^1)$ of the CPA secure PKE, where $\ell$ is the length of the verification key of the one-time signature scheme. To encrypt a message, we then encrypt the message seperately under $\ell$ public keys, where at position $i$ whether $\mathsf{pk}_\ell^0$ or $\mathsf{pk}_\ell^1$ is used, is determined by the $i$th bit of a fresh verification key of the one-time signature scheme. We then prove using the NIZK that all ciphertexts are encryptions of the same message and finally sign everything with the one-time signature scheme.

The main ideas of the security proof are:

Since we have many encryptions of the same message (something enforced by the soundness of the NIZK), we can reduce to CPA security, while still being able to decrypt, because we can use one of the other keys.
Any new ciphertext queried to the decryption oracle either uses the same verification key, in which case the adversary would need to forge a signature. Or it uses a different verification key, in which case at least one ciphertext uses a different encryption key from the challenge ciphertext and we are able to use the corresponding decryption key for decryption.

It of course remains to instantiate all those building blocks.

The building blocks.

CPA secure PKE

If a family of trapdoor permutations $\mathcal{F}$ exists then, due to the Goldreich-Levin Theorem there also exists a family of trapdoor permutations with a hardcore predicate. Given a TDP with a hardcore predicate, a simple construction of CPA secure PKE for bits exists, where a a keypair consists of a description of an $f_i\in\mathcal{F}$ for the public key and the corresponding trapdoor for the secret key. A ciphertext is then simply $(f_i(r),\mathsf{hc}_i(r)\oplus m)$ where $r$ is a uniformly chosen element from $f_i$'s domain, $\mathsf{hc}_i$ denotes the hardcore predicate of $f_i$ and $m\in\{0,1\}$.

If necessary, this encryption scheme can be used to construct CPA secure encryption for longer messages by encrypting each bit seperately. The security follows via a standard hybrid argument.

One-Time Signatures

The construction of Lamport gives us an existentially unforgeable one-time signature scheme for fixed length messages from any one-way function. In particular the construction can be therefore be instantiated from a family of trapdoor permuations.

Noninteractive Zero-Knowledge Proofs

NIZK for $\mathsf{NP}$ can be constructed from doubly-enhanced trapdoor permuations. The construction essentially works by performing an $\mathsf{NP}$-reduction to the Hamiltonian Cycle problem and constructing an NIZK for Hamiltonian Cycle. In the original construction in Goldreich's Foundations of Cryptography: Volume 1, Basic Tools it is incorrectly claimed that the construction is instantiable from any TDP, this was corrected in the paper linked above.


The classical ElGamal cryptosystem satisfies your requirements. Indeed, let us consider a group $\mathbb{G}$ of prime order $p$ and a generator $g \in \mathbb{G}$. Let $(h_1,h_2) = (g^{s_1},g^{s_2})$ be two public keys for two random secret keys $(s_1,s_2)$. To encrypt a message $m \in \mathbb{G}$ with the public key $h_1$, pick a random coin $r_1 \in \mathbb{Z}_p$ and send $C_1 = (g^{r_1}, mh_1^{r_1}) = (c,c')$. To re-encrypt it, it is sufficient to encrypt the second component $c'$ of the ciphertext $C_1$. So, pick a random coin $r_2$ and compute $C_2 = (c, g^{r_2}, c'h_2^{r_2}) = (\alpha,\beta,\gamma)$, which is a re-encryption of $C_1$ with the second public key $h_2$. Now, you can decrypt in reverse order: decrypt $C_2$ by computing $\gamma / \alpha^{s_1} = \delta = mh_2^{r_2}$, and decrypt the resulting ciphertext $(\beta, \delta)$ with $s_2$: $\beta/ \delta^{s_2} = m$.

However, re-encryption of a ciphertext is not compact: encrypting $n$ times a plaintext results in a ciphertext of size $O(n)$.

There are probably many other examples of commutative cryptosystems, and there has been some work on constructing various interesting cryptosystems with this property, but unless what you want is more complicated than just "commutative public key cryptosystem", the above examples are sufficient.


I see three main reasons why PAKEs are not widely used yet:

The lack of IETF standards. SRP has limitations discussed in the link @fgrieu posted above. Many PAKE protocols have been designed, but they lack a convincing security proof, or properties some applications may expect. This is being solved as we speak. The CFRG is currently having a selection process, existing PAKEs are being carefully reviewed, and the outcome will be a small set of recommendations for each use case.
The lack of implementations. Possibly due to the above.
The lack of awareness. Most people have never heard of PAKEs.


RSA reconstructing private key knowing MSBs

I do not believe that there is any reasonably efficient way to reconstruct the lsbits; if there were, then a good fraction of the RSA keys out there could be efficiently factored (!).

Here's why: a lot of RSA keys have a modulus $n = pq$, where $p$ and $q$ are primes of equal size.  Then, let us assume a small $e$ (it needs to be relatively prime to $p-1$ and $q-1$; we could use the $e$ in the public key, or pick our own and hope we're lucky).  Then, the relationship between $d$ and $e$ is:

$$de \equiv 1 \pmod{lcm(p-1, q-1)}$$

which we can rearrange into

$$d = (k(n - p - q + 1)/\gcd(p-1, q-1) + 1) / e$$

where $k$ is some unknown integer that turns out to be within the range $(0, e)$.  If we're interested in only the msbits of $d$, we can simplify this to:

$$d \approx (k (n + \epsilon) / (e \cdot \gcd(p-1, q-1)$$

Where $\epsilon < 5\sqrt{n}$.  We can guess $k$ and the contibutions of $\epsilon$ on $n$, and $\gcd(p-1, q-1)$ is likely to be a small even value; going through the possibilities, that gives us reasonable guesses for the msbit's of $d$; if one is correct, then we could use the assumed method to reconstruct the lsbit's, and then immediately factor.


Should this be a 2 step process ...

Yes, you need to do it in 2 steps with common algorithms such as RSA, ECDSA, ECIES, etc. (because they're not signcrypt algorithms).

You should first encrypt, then sign, as this ensures with (slightly) better confidence that signature don't reveal information about the file/message.

  If so, can you please provide a sample of what the command would look like?

Programming questions are off-topic. But if you really don't know how to use the command line, there is a high chance you can hurt yourself doing it, so a GUI app is recommended.


I know SHAKE128 and 256 are part of the SHA-3 standard but is the SHA3 standard officially released yet? i can only find a draft of the publication, does this mean it's not official and therefor not proven to be secure?

No, SHA-3 has not been formally approved.  On the other hand, what do you mean "not proved to be secure"?  Do you really thing that NIST approves only things that are "proven"?  In practice, we have only a handful of things that are "proven" (OTP, secure sharing); while NIST certainly tries to vet what they place on the approved list, they have no proof.

In any case, from your questions, it appears that you are interested in speed.  Now, SHA-3 is actually slower in software than SHA-2 (what SHA-3 excells at is if you can implement it with hardware gates); hence it would appear to be the wrong direction for you.

  What is the best hash to use, obviously it needs to be relatively fast and by my standards sha-512 isn't fast

Well, before I get into that, I would like to point out that your HMAC implementation can likely be improved.

In HMAC, as you know, we use the key to generate an IPAD and an OPAD; we then compute $a = Hash(IPAD | Message)$, and then compute $b = Hash(OPAD | a)$, and $b$ is the result of the HMAC.

Now, IPAD and OPAD are sized to be precisely 1 Merkle-Damgaard block of the hash function; hence one thing you can do is you can compute the initial hash compression function evaluation $Compress(IV, IPAD)$ and store that intermediate state; similarly, you can compute the initial hash compression function evaluation $Compress(IV, OPAD)$ and store that.

Then, to compute $a = Hash(IPAD | Message)$, you can restore the initiate state for that, and just compute the hash over the message (just using the precomputed evaluation as the IV, and adjusting the final padding to account for the longer message); similarly, you can use the same trick when computing $Hash(OPAD | a)$.

This allows you to compute HMAC using two fewer hash compression operations over the naive method.  Now, if you are computing the HMAC only once for a key, or if you are computing HMAC over a huge message, this doesn't help much.  However, if you are computing HMACs over a number of tiny messages, this helps a lot.

I suspect you aren't using this optimization, because if you were, the time differential between 64 bytes messages and 128 byte messages would be considerably larger.

Implementing this may have the time taken to HMAC a 64 byte message on SHA256 by 40% (3 hash compression operations rather than 5).

Now, as for the "best hash"; well, if you want to stick with NIST approved operations, the fastest alternative is HMAC-SHA1 (which is FIPS approved still); if you don't care for that, well, the best you have is HMAC-SHA256.


Problem with a reduction using Hybrid Argument

If there is a collision in the $r$ in the first game, then the attacker can learn the XOR of two plaintext messages by XORing the second elements. In the second game, the XOR of the two second elements if there is a collision will just be random. Thus, the attacker can distinguish these two games if there is a collision.


How to generate a non periodical, theoretically infinite, sequence of numbers from a secret alphanumeric key

There are quite a few options here as you can basically use any algorithm with a single key input and configurable amount of output:

a DRBG (or CSPRNG) such as Hash_DRBG or CTR_DRBG;
a stream cipher or block cipher in streaming mode such as Salsa20 or AES in counter mode;
a KBKDF such as HKDF;
a XOF such as SHAKE256 (SHA-3).

In principle a DRBG - deterministic random bit generator - may seem to be the best option. A DRBG basically turns a seed into a stream of random bytes. It may however request reseeding, which may be a problem. To resolve this, just keep feeding it the same value or zero bytes at the same point in the stream and you should be OK. Furthermore, the DRBG needs to be well defined; some programming API's make changes in the algorithm without notification. This may mean that there are few implementations available - if any, as most of them are simply designed to return unpredictable random numbers. Note that a DRBG is also known as a CSPRNG - a Cryptographically Secure Pseudo Random Number Generator or sometimes just as a PRNG.

A stream cipher takes a symmetric key (and possibly an IV) and turns it into a pseudo random key stream consisting of a virtually unlimited amount bytes. This is completely deterministic and doesn't require reseeding. Note that this key stream was created for encryption rather than randomness. One of the weird properties of counter (CTR or SIC) mode encryption is that it never repeats a block, which distinguishes it from a random stream of bytes. The chance of randomly creating e.g. two identical 128 bit blocks is however infinitely small, so that should not pose a problem.

A KBKDF - Key Based Key Derivation Function - such as HKDF generally can be seen to have an extract and expand phase. First during extraction the entropy in your initial key is put into the state. This state is then used to generate a virtually unlimited amount of bytes. This is called the expansion phase. Problem with this approach is that most of the KDF's expect the output size to be defined in advance.

A XOF - eXtendable-Output Function - can be used by using the key as input for the XOF and defining the random stream as output of the XOF. This is probably the easiest function to use. The input doesn't have to be a particular size and the function was defined to stream out information. The main known XOF's, SHAKE128 and SHAKE256 are however part of the SHA-3 specification and may not be available for all runtimes.

To use your alphanumeric key you first need to convert it into a key that is acceptable to the function that you decide to use. First of all, you'd convert it to binary using character encoding such as ASCII (or UTF-8, which amounts to the same thing).

You may need to use a KDF or hash to generate a key of the right size, in case your DRBG or cipher expects a key of a specific size. In general the leftmost bytes of a hash would also suffice.

In general all of the above are one-way functions so you cannot convert them back to your alphanumeric key apart from brute forcing the alphanumeric key. They all use deterministic (and therefore repeatable) algorithms to generate streams of bytes.

The XOF functions seems to be the main contenders as they are designed for streaming and accepts any size of input data.

AES in counter mode + hash as KDF to create the key - is a very good contender if simply for the reason that it is almost universally available, it's definitely impossible to retrieve the secret key and the output is likely good enough.


Should I authenticate memory data which was loaded from authenticated disk file?

[D]oes adding HMAC to each encrypted field and validating it before decryption makes sense?

No. Since you authenticate the data once, you can trust that it is the same as was originally encrypted and authenticated. That is, authenticating the ciphertext also authenticates the plaintext.

  The goal is to make make the app as secure as possible and minimize possibilities of tampering.

This may sound like a good goal, but it is really not. A good goal would be to have specific security objectives and types of attacks you want to prevent. For example, you should consider what kind of security you would expect in the case that an attacker 1) was able to read the disk image or 2) was able to write arbitrary data on disk.


Cryptographic functions are designed to survive some adversarial setting; their designs assume that there will be very clever people trying as hard as they can to "fool" them.  Non-cryptographic functions on the other hand are "optimistic"—they're designed to perform well with the sort of data that their designers expect will be given to them.

In fact, non-cryptographic functions are often observed to synergize with data sets that exhibit the expected patterns—for example, note how the functions tested in this Programmer's Stack Exchange answer have lower-than-chance collisions for the consecutive numbers data set.  This behavior is often by design.

  But non-cryptographic appear to be just curiosities made independently. And Google's CityHash is apparently made specifically for strings.  If Hash tables are solely the purpose of non-cryptographic hashes (and strings, as CityHash advertises), then are they not appropriate for error-detection in large binary data files that SHA1 and CRC32 are often employed for?

The answer to this is that there's no general answer other than whatever the designers of the functions set themselves as their goals.  With cryptographic hash functions, the adversarial setting dictates the standard that functions must meet, but once you take that away authors can just do whatever they think is most appropriate.

It's worth noting however than many of the modern non-crypto hash functions are tested using the SMHasher test suite, so lately you tend to see lots of hash functions that score well at it.  Here's a brief description of its tests.


Why does Signal repeatedly hash the secure passphrase?

Cryptographic hashes are designed to be fast and collision resistant. It turns out that when hashing passwords, it is more secure to have a slow hash function. One way to make a fast hash function slow is to iterate it. Like is done here.

Think about it this way. If an attacker is able to compute a million hash calculations in a second, if you only ran your password through the hash function once, they would be able to attempt a million guesses each second. On the other hand, if you iterate the hash function 250,000 times, now the attacker can only make 4 guesses a second. That is a pretty substantial reduction and increases the amount of work the attacker has to do. If users were really good at choosing passwords, this might not matter, but the fact of the matter is that users are not good at choosing good passwords. Making the hash function slow helps in that regard.

In the case of Signal, it looks like encrypted backups is a beta-feature. Looking at one screenshot, it appears that the backup key is not user chosen. It is likely (haven't dug through the code) a 30 digit random number. That means it has about 100 bits of entropy at best. My guess is that the designers still wanted a slow hash function for the reasons listed above, even though the passphrase was not user chosen. Making it slow is a good trade-off for having less entropy. They could have made the random number longer to get more entropy (256 bits maybe), but that would have made the backup key that the user has to store much longer.


Am I not understanding padding correctly?

You're not understanding the padding attack correctly.

Yes, only the last block is (typically) padded in CBC mode, however that doesn't mean that we can only attack the last block; what that means is that we can only use the last block.

In CBC-mode, the decryption of the block $i$ is computed as $P_i = D_k( C_i ) \oplus C_{i-1}$, where $D_k$ is the decryption using the unknown (to the attacker) key $k$.  Now, the attacker can see $C_i, C_{i-1}$, and so if he can deduce the value $D_k( C_i )$, he then has found the value of the plaintext block $P_i$.

So, what the attacker does is construct ciphertexts where the $C_i$ appears as the last ciphertext block $C'_n$, and he tries various values for the next-to-last block [1] $C'_{n-1}$; he submits those ciphertexts, and sees if, after decryption, the had valid padding.

Whether they do (mostly) depends on the last decrypted plaintext block, which is $P'_n = D_k( C'_n ) \oplus C'_{n-1}$; by trying various values of $C'_{n-1}$, he can deduce the value $D_k( C'_n )$.

Hence, this padding oracle attack can be used to decrypt any block, not only the last.

[1] The penultimate block, if you (like me) prefer to use the term 'penultimate' correctly...


XTS mode with the tweak key as the sole secret

Actually, you can't remove the $E_{k_2}$ as you did. You had:

$$C_{j} = E_{K_2}(P_{j} \oplus (K^\prime \otimes \alpha^j)) \oplus (K^\prime \otimes \alpha^j)$$

Let me replace the term $(K^\prime \otimes \alpha^j)$ with $K^{\prime\prime}$ and eliminate the $j$ to makes things easier to read. The result is:

$$C = E_{K_2}(P \oplus K^{\prime\prime}) \oplus K^{\prime\prime}$$

This form is that of a type of Even-Mansour cipher. It is a block cipher formed with a public (pseudo-random) permutation $\pi$ and one or more keys with a length equal to the block length. It looks like:

$$C = \pi(P \oplus K_a) \oplus K_b$$

XEX mode uses the same construction to make a tweakable block cipher. In XEX the permutation used is not public. (It is  a block cipher with a secret key.) For an EM block cipher the permutation does not need to be secret. (Therefore you can use a block cipher with a non-secret key.) Its security claims just depend on the block size, the assumption that $\pi$ is a pseudo-random permutation, and that the keys are unpredictable and from a uniform distribution.

You cannot eliminate the $\pi$ as you did.

$$\pi(P \oplus K_a) \oplus K_b \neq (P \oplus {K_a}^\prime) \oplus {K_b}^\prime$$

Given plaintext ciphertext pairs:

If you omit $K_a$ then you can trivially recover $K_b$.
$$C = \pi(P) \oplus K_b$$
$$C \oplus \pi(P) = K_b$$

If you omit $K_b$ then you can trivially recover $K_a$.
$$C = \pi(P \oplus K_a)$$
$$\pi^{-1}(C) = P \oplus K_a$$
$$\pi^{-1}(C) \oplus P = K_a$$

If both keys are present, then the best attacks on a generic single round*EM cipher require about $D$ plaintext/ciphertext pairs (D for data) and $T$ evaluations of $\pi$ (T for time) such that $DT \geq 2^n$ where $n$ is the block size.

As for the question "So in essence, the output of $\pi$ will necessarily not be known because of the [correction: $K_a$] added to the input?"

Yes, basically. The exact behavior is a bit subtle and I don't want to cause confusion. So actually either $K_a$ or $K_b$ being unknown is sufficient to make the ciphertext impossible for the adversary to predict IF no plaintext/ciphertext pairs are known.

I actually mean $K_a$ added to the input of $\pi$ makes the new output of $\pi$, that is $\pi(x \oplus K_a)$, impossible for the adversary to calculate because the "real" input, that is $x \oplus K_a$, is not known by him.

If you skip the second XOR ($K_b$) then from one pair you can recover $K_a$ as described above using the inverse of $\pi$.

Similarly if have secret $K_b$ the adversary can compute $\pi^{-1}(x)$ but not $\pi^{-1}(x \oplus K_b)$. The adversary needs to know the difference between $E^{-1}(C) = K_a \oplus \pi^{-1}(C \oplus K_b)$ and $\pi^{-1}(C \oplus K_b)$ to recover $K_a$.

So you can't recover the pre-key ($K_a$) efficiently without knowing the post-key ($K_b$). You can't recover the post-key easily without knowing the pre-key. Both are essential. One protects the other from being recovered.

I hope that makes sense. I struggled to phrase it in a way that made sense without resorting to formal arguments. I will look for references later.

The claim that an EM cipher is secure may not pass the smell test, though. And that's because I forgot to emphasize that you can't actually make a claim to that their security level is equal to their key-size. $|K_a| + |K_b| = 2n$ but the worst case security level is $O(n / 2$) if measured in terms of $min(D + T)$. And you don't limit $D$.

It's better to use larger block ciphers or permutations for that reason. I recall reading using more rounds brings the security level closer to $n$ bits.

(If for some reason we lost the ability to use typical block ciphers we would be perfectly fine using only one round EM ciphers with a "standard" block size of 256 bits instead of 128. We also wouldn't need double the key bulk if we did this. The different subkeys can be generated by KDF. For the single round version there is no loss in security on the generic construct if the pre- and post-keys are equal.)

Also the symmetry of the construct makes informal reasoning a bit easier. Whatever logic applies to encryption or the forward public permutation function also applies to decryption and the inverse permutation function. ie.

$$E_1(P, K_a, K_b) \text{ corresponds to:}\\
\begin{align}
 X &= P \oplus K_a; \\
 Y &= \pi(X); \\
 C &= Y \oplus K_b
\end{align}$$

$$E_2(P, K_b, K_a) \text{ corresponds to:}\\
\begin{align}
 X &= P \oplus K_b; \\
 Y &= \pi^{-1}(X); \\
 C &= Y \oplus K_a
\end{align}$$

* Rounds in the context of EM ciphers refers to the number of times $\pi$ is used. One round is XOR → permute → XOR. Two is XOR → permute → XOR → permute → XOR. And so on.


Dan Boneh's explanation of why Davies-Meyer requires the final step of XOR with the previous Hash

Dan Boneh's explanation is about finding a collision for the compression function $h$ defined by $h:\ (H,m)\mapsto h(H,m)\underset{\text{def}}=E(m,H)$ where $E$ is a block cipher with first parameter as key. Notice that the input of function $h$ is neither $H$ nor $m$; it's the pair $(H,m)$, or equivalently the bitstring $H\mathbin\|m$.
Finding a collision for $h$ is finding two distinct inputs to the function $h$ such that the output is the same. That is finding an $(H,m)$ and a different $(H',m')$ such that $h(H,m)=h(H',m')$.
The method Dan Boneh uses is to choose arbitrarily $H$, $m$, and $m'\ne m$; then compute $H'=D(m',E(m,H))$, where $D$ us the decryption function for the block cipher $E$. We'll use that $D$ is such that $\forall k,\ \forall c$, $E(k,D(k,c))=c$. This can be readily proven from the more usual $\forall k,\ \forall p$, $D(k,E(k,p))=p$.
From $H'=D(m',E(m,H))$, it follows $E(m',H')=E(m',D(m',E(m,H)))$. And then applying the above property of $D$ with $k=m'$ and $c=E(m,H)$, it comes $E(m',H')=E(m,H)$. And since we have chosen $m'\ne m$, it holds $(m',H')\ne(m,H)$. Dan Boneh's method thus always exhibits a collision for $h$.
Dan Boneh is allowed to chose $H'$ because he aims at exhibiting a collision for $h$. He would not be allowed that if he was trying to exhibit a collision for the different functions $h_H:\ m\mapsto h_H(m)\underset{\text{def}}=E(m,H)$, where $H$ is a fixed parameter rather than part of the input. Neither would he for a collision of a hash function built per the Merkle-Damgård construction using $h$ as the compression function.


What does a stream cipher provide that cannot be obtained with AES CTR mode operation?

AES-CTR is a stream cipher, of a particular kind where the keystream is obtained by encryption of a counter. So the question reduces to: what are drawbacks of AES-CTR compared to other stream ciphers?

The main ones compared to ChaCha20 are:

Without hardware support, AES can fail to cache-timing attacks.
Without hardware support, AES is slower.
Without hardware support, the fastest implementations of AES use significant memory.
Pre-computed AES subkeys (which speeds-up things) require not quite negligible memory (160 bytes for AES-128 in addition to the base key, compared to none for ChaCha20); this is an issue when many sessions each with a different key are active simultaneously.
There's a theoretical distinguisher for AES after about $2^{68}$ bytes (but it requires as much memory, and wouldn't be much a practical issue anyway).

Compared to other modern stream ciphers like Trivium, AES requires more hardware at comparable speed. On the other hand it allows random access to the keystream, and parallelization (as ChaCha20 does), when many other stream ciphers (including Trivium and RC4) do not.

Bare AES-CTR does not provide authenticated encryption (AES-GCM does, and uses AES-CTR for encryption), so comparison to ChaCha20-Poly1305 is unfair.


Security of tokenization of plain text conversations - cryptanalysis

Chinese "looks" encrypted. I believe it to be a marketing gimmick; they want to be able to show "encrypted text" that people will unconsciously associate with notions of unreadability and utter obscurity -- and nothing beats Chinese for that (except in China, of course; if they want to sell their product to China they will have to use Greek or Sumerian scripts).

There are more than 70000 Chinese characters in Unicode, but only 20000 or so in the "first plane" (the code points which fit on 16 bits), which are the most likely to be supported by existing software. This still allows for 14 bits worth of data in each glyph, which is not bad.

As your analysis shows, this appears to be a simple word-based substitution cipher, which will be broken by statistical analysis. People use perhaps 2000 common words, so I suppose that observing a corpus of, say, 30000 tokens ought to be enough to decrypt the whole thing, especially since there is an awful lot of context (on your screenshot we even have the pictures of the individuals involved !). Minoen "Linear B" script was unravelled with less data than that.

No, it is not secure, and hardly "serious".


Exchanging key material between HSMs of different manufacturers

No, there's no standardized way to exchange key material between HSM (and often not even between HSM of the same manufacturer, although manufacturers may provide a backup/restore or replication capability that works at least within the same model). As far as an HSM is concerned, the world is divided in two: inside and outside. What is outside is not trusted. From the point of view of HSM1, HSM2 is outside and therefore not trusted, so HSM1 won't give up its keys to HSM2.
Assuming that you keep a single copy of the wrapped application keys (plus their identical backups), both HSM need to have the same wrapping key. Either create that key outside the HSM and import it to both, or create that key inside one HSM, export it, and import it into the other HSM. After import, make sure to switch the key attributes to be non-exportable.
Even with a single HSM, you would need to have a copy of the wrapping key outside the HSM for backup purposes. This copy (or more precisely all the backup copies) must of course be stored securely. Depending on your security requirements, this could be a piece of paper stored in a safe, or key shares where several company officers are responsible for securing their own shares and K shares among N are necessary to reconstruct the key. As far as I know, there's no standard way to create these key shares, but one HSM may have this as a proprietary featue.


Apple CryptoKit - Understanding its portability

OpenSSL cli doesn't support authenticated encryption modes like CCM and GCM. The reason behind that is the lack of security if the IV/nonce is reused. Using OpenSSL cli, IV management totally rely on the user, who tend to make mistakes... In order to avoid catastrophic failures, they simply decided to not allow AEAD.

I guess the easiest way is to do a simple Python script. I would advice PyCryptodome, you can even find an example which suite your needs.


I could've sworn this was a duplicate question, but I can't find a good match for it here right now, so let me answer it instead.

What if size of encrypted input is always less or equal 16 bytes?
I suspect AES/ECB will be as good as AES/CBC in this case...

For plaintexts shorter than the cipher block size (i.e. 16 bytes for AES), CBC mode encryption is equivalent to:

padding the plaintext up to 16 bytes,
XORing the padded plaintext with a random 16-byte IV,
encrypting the resulting 16-byte block with raw AES (i.e. in "ECB mode"), and
concatenating the random IV and the AES output to form the encrypted message.

XORing the plaintext with a random IV does, in fact, provide a concrete security benefit: it ensures that even two identical plaintexts will (with overwhelming probability) encrypt to different ciphertexts, preventing an attacker from learning whether two encrypted messages conceal the same plaintext or not.  With ECB mode, which is purely deterministic, an attacker could simply compare the two ciphertexts to find out if the plaintexts are equal or not.
However, in this particular short-plaintext scenario, that's the only benefit of the IV.  In particular, it's of no help against any attacks that would involve breaking AES (or compromising the encryption key), since if an attacker can invert the AES encryption (step 3), they can then trivially undo the IV XOR (step 2).
On the other hand, the use of a random IV actually makes CBC mode vulnerable to some tampering attacks that EBC mode happens to be invulnerable to.  In particular, for short messages like in this scenario, an attacker capable of intercepting and tampering with the encrypted message can flip any bit(s) in the plaintext just by flipping the corresponding bit(s) in the IV!
Now, technically this does not compromise the claimed security of CBC mode, since CBC mode doesn't claim to protect message integrity against tampering attacks in the first place.  But a lot of people aren't aware of that, and in any case message integrity protection is still important and should be ensured somehow, either by using an encryption mode that provides it directly (such as GCM) or by using a message authentication code on top of the encryption layer.

The other question is: will AES/GCM be any better (secure) for <16 bytes input compared to AES/ECB &| AES/CBC?

Yes, GCM is better than either ECB or CBC for messages of any length, since it provides both message authentication (tampering resistance) and full semantic security (leaks no information about the plaintext other than its length).
(In some cases, specifically for messages sufficiently shorter than one cipher block, using ECB mode and verifying the padding after decryption can actually provide a form of message authentication.  But this doesn't work for longer messages.  CBC mode doesn't provide any authentication for messages of any length.)
The same holds for any other secure authenticated encryption mode as well, not just GCM.  There's not that much difference between them (in terms of security; speed, code complexity and library support can of course vary), and they're all secure against nearly all passive and active attacks if used correctly.  In practice, the main ways in which the security of such an encryption mode can be compromised are:

key compromise (obviously, no encryption scheme is secure if the key is leaked),
user / implementation error (bugs in the code, not using the mode according to its specifications),
information leakage via message length (e.g. if the plaintext is compressed before encryption; see e.g. the CRIME and BREACH attacks on SSL), and
bad IV generation (the security of many encryption modes, including GCM, can fail catastrophically if the same IV is used for two different messages).

Thus, whenever possible, my recommendation would be to use an authenticated encryption mode that provides IV misuse resistance (such as AES-SIV or AES-GCM-SIV) and a reputable open-source implementation of it, such as Miscreant, that provides a simple "black box" API with the least possible room for user mistakes.  And if you're encrypting variable-length data, be very careful about possible leaks via its length, since no general-purpose encryption scheme can fully conceal that (and most don't even try).


Is Identity-based encryption used in the wild?

SM9 (GM/T 0044.5‐2016) is an IBE scheme widely used in China. Unfortunately most of the documents are in Chinese with no English translations available. But a description of basic SM9 scheme is available on eprint and an open source implementation is in the OpenSSL fork GmSSL


Sage Vs C++(with NTL) for implementing cryptosystems

Sage can actually use NTL under the hood, so if you are more comfortable with sage (or that style of coding) and can implement things using the ntl wrapper, then there is likely no advantage to using NTL directly in C++.


Efficient way to combine collection of hashes into a single hash?

With the system as described, the last participant to submit its hash can trivially choose "the random number", knowing the initial value of rootHash and what hashes earlier participant submitted, by choosing the values of the hash s/he submits (s/he computes the XOR of these and $d+10^{10}r$ truncated to the hash width, where $d$ is the desired 10-digit value and $r$ is random; this insures "the random number" is $d$ ).

Even if what s/he submits has to be the hash of something (that's untold), finding a suitable something is feasible (that's expected to require a mere 5 thousand million hashes; or few hundred thousands if the last two submitters collude).

Replacing the XOR with a hash of the concatenation of the submissions do not help much (for example, it remains very easy for the last submitter to force "the random number" to be even).

A method truly solving this issue could be:

each participants draws a random $x_i$ (say, 128-bit)
each participant submits the hash of $h_i=H(x_i)$ to the server and/or each participant; that's called a commitment of $x_i$
after the above is complete each participant reveals its $x_i$
the server and/or each participant checks that $H(x_i)=h_i$ for all participants
the $x_i$ are processed just as the hashes in the question (there's no reason to initialize rootHash to an haphazard value, zero will do just as well).

This way each submitter can be convinced that whatever collusion there might exist among other participants, "the random number" is at least as unpredictable as the $x_i$ s/he submitted, if the hash is collision-resistant (implying it is wide, e.g. 256-bit). Note: if the hash was not collision-resistant, the last submitter of $x_i$ could have selected $x_i$ and $x_i'$ with equal hashes $h_i$, then knowing the $x_i$ of all other participants could decide to submit either $x_i$ or $x_i'$ so as to influence "the random number" in some controlled way.


How does the DH algorithm deal with enormous powers?

It doesn't. The mod operation does not have to be performed after exponentiation. Modular exponentiation can be implemented using modular multiplication (and modular addition). Modular multiplication in turn can be implemented relatively efficiently, for instance using a Montgomery multiplier.

Here's an example using decimals instead of binary; you know that $323 \times 323$ ends with a $9$ even without doing the full computation. This is a $\bmod 10$ operation. In the same way, you know that $323^3$ ends with a $7$ because $323 \times 323 \times 323$ ends with a $7$.


The perfect security of OTP hinges on the fact, that keys must be chosen truly at random and uniformly from the domain of all possible keys, i.e. all bitstrings of a certain length.
The problem with your approach is that you use a pseudorandom number generator to generate the key.

It does not matter how good the generator is, because the entropy that can be used to generate the key is limited by the seed you use.

Let's, assume that the 50 numbers you use are really random and distributed uniformly -- and that is at least debatable for mouse movement.
If you use 50 number in some range, lets say between $0$ and $x-1$, then for files of any size, you only ever produce at most $x^{50}$ different keys.

Obviously, for large enough files, this is much smaller than the total number of all possible keys and therefore, your perfect security does no longer hold.

An attack would for example consist of deciding which of two messages $m_1,m_2$ is encrypted in a ciphertext (your basic indistinguishability game). Keep in mind that for perfect security the runtime of the adversary is unbounded. That means that $\mathcal{A}$ could enumerate all $x^{50}$ possible keys and check if any of those decrypts the ciphertext to one of the two messages.
This works basically, because the number of possible keys is much smaller than it should be and the chance that the ciphertext could also be decrypted to the other message is very small (for large enough messages).


It just defines a function that expands the input size with the output size four times, where the output depends on configuration value $t$ as well. The hash function compresses the input to an output that is half the size (which is not common, usually a hash function outputs a constant size hash).

Here ^ is not a power function. It simply shows how many elements there are sequentially taken from the input set $\{0, 1\}$ - properly formatted it reads $\{0, 1\}^{4 \cdot n}$. So the $x$ in $\{0, 1\}^x$ simply defines an input or output consisting of $x$ bits - with value $0$ or $1$ of course.


Calculate number of chips to solve bit commitment using hash function

$M = H(R_1 || R_2 || b) || R_1$

You already know $R_1$ and you need to find $R_2$ and $b$.

$R_2$ is 40 bits long and $b$ is 1 bit, so you need on average $2^{41}$ guesses to find $R_2$ and $b$ which will give the hash you want.

You know that each chip can do 10,000 hashes per second, so you need to find out how many chips you'll need to do $2^{41}$ hashes in 5 minutes.

$\dfrac{2^{41}}{300seconds} = 7,330,077,518.51 hashes/second$

Since each chip can peform 10,000 hashes per second, we need

$\dfrac{7,330,077,518.51}{10000} = 733,008$ chips (rounded up)

At \$1000 per chip, that is \$733,008,000


There are no known dangers or attacks from this construction.  I agree with the quote from the TAHOE-LFS paper.  I would find it quite surprising if this use of the key material introduced some special weakness.  I can't prove it, but based upon my professional judgement, this is probably far from the biggest risk to your security -- it is very unlikely that this is the weakest link in the system.  It is far more likely that the weakest link is something else (e.g., endpoint security, the human processes, social engineering).  So, personally I wouldn't worry about this.


Understanding how SHA-512 achieves its design goals

SHA-2, like SHA-1, is an ARX hash function: that is, it uses Addition, Rotation, and eXclusive-or for bit diffusion.  The purpose of each one is explained very simply and clearly by Khovratovich & Nikolić in their paper Rotational Cryptanalysis of ARX, so I will simply quote them here:

  Addition provides diffusion and nonlinearity, while XOR does not.  Although the diffusion is relatively slow, it is compensated by a low price of addition in both software and hardware, so primitives with a relatively high number of additions (tens per byte) are still fast.  The intraword rotation removes disbalance between left and right bits (introduced by addition) and speeds up the diffusion.

So there is no "chaotic behavior interacting", but there is bit-diffusion, and that is what you want in a hash.  Sufficient bit-diffusion is called an "avalanche effect".  The message expansion mixes the bits between words, and the actual compression function is where the nonlinearity comes in, using these pre-mixed bits.

As to the second part of your question, $\operatorname{ch}(a,b,c)$ is the "choice" function: when $a$ is $\text{true}$, the result is equivalent to $b$, and when $a$ is $\text{false}$, the result is equivalent to $c$.  So $a$ acts as a selector between either $b$ or $c$.  $\operatorname{maj}(a,b,c)$ is the "majority" function, which takes the majority value as the final result.  So if two or three of the variables are $1$, then the result is $1$; otherwise, the result is $0$.  And usually there is also the $\operatorname{par}$ function, which is "parity" and uses XOR between the operands.

The truth density of each of these functions is 50%.  In other words, given completely random values for $a$, $b$, and $c$, you have a 50% chance of getting a $1$ or $0$ result.


Why was WEP apparently not reviewed by many cryptographers?

It is my understanding that the design flaws of WEP were well known from its beginning.

WEP on Wikipedia states, was introduced in IEEE 802.11 in 1997, and it was based on the stream cipher RC4.

There has been quite a lot of research to break WEP and its stream cipher RC4, but that's spread out over the last 20 years. Most notably for breaking WEP was the attack from Fluhrer, Mantin and Shamir in 2001. And earlier in 2001, this work was presented at a workshop and a conference (thanks @poncho for this reference).

For RC4, it was public knowledge that it is distinguishable from random, as pointed out by @SqueamishOssifrage in this source. Today that would surely disqualify the streamcipher to be considered secure, but mindsets change over time and I don't know if that was acceptable or not. E.g. the linked source states: "If your application can't stand a bias of 1 part per million, then
don't use RC4." Also, we do not know whether the people in charge of WEP were aware of this or not.

So no, your statement is wrong. Just because the flaws are well known today does not mean they were back then. If you're questioning decisions, you need to adapt the point of view from the time of that decision.

  In WEP’s design process, why were no people with sufficient “expertise in cryptographic protocol design” involved in the creation of a cryptographic protocol intended for broad adoption?

This can't be answered properly, unless you ask someone who actually was involved in that process. The only suggestion I have would be to contact the  IEEE 802.11 working group and ask them.


Make AES more secure by randomising the blocks in an encrypted file

TL,DR: No, don't do it. Use a standard protocol and don't write your own implementation. If you're thinking at the level of AES, CBC and RSA, you're doing it wrong. I recommend crypto_box.

  I am developing a software with hybrid encryption (RSA-4096

RSA-4096 is ok if done right. Done right means OAEP or RSA-KEM. PKCS#1v1.5 is theoretically possible to get right, but very difficult because it is prone to oracle attacks. A lack of padding or homegrown padding is plain broken. ECIES gives you as much or better security at much better performance, and typically fewer risks of getting it wrong due to insecure parameters.

  and AES-256-CBC).

Unauthenticated modes are dangerous because they are prone to oracle attacks. Even PGP got it wrong. Don't use unauthenticated modes. And especially don't use CBC, which has padding, which allows even more oracle attacks.

You might think you don't care about authentication, but you're probably wrong. If someone can send fake messages, that does help them obtain the content of confidential messages. The efail attack on PGP works by piecing parts of legitimate messages into fake messages and having the fake messages (attempt to be) decrypted. Use GCM or CCM instead (or use ChaCha20_Poly1305 instead of AES-GCM or AES-CCM). (But as I said earlier, what you should really be using is something like crypto_box.)

Also note that using authenticated encryption prevents oracle attacks at the level of the symmetric cryptography, but it doesn't prevent similar attacks at a higher level, since an attacker can make up their own symmetric key and send whatever they want by encrypting their own symmetric key with the public key. You should sign messages (sign (a hash of) the plaintext) with a separate set of asymmetric keys, where the sender holds the private key and the recipient knows the sender's public key (or can get it from a reliable source).

  The iv and key of an AES encrypted file will be RSA encrypted end exchanged through a different way than the encrypted file.

You can, and typically should send the IV with the file. The IV doesn't need to be confidential. The AES key is encrypted with RSA (that's how hybrid encryption works) and the encrypted AES key is typically sent with the file. The RSA private key is typically never transmitted at all: that's the point of asymmetric cryptography.

You do need to take care of transmitting the public RSA key separately, but that's a whole different issue which I won't go into here.

  I am thinking about where it is most easy to break the encryption of my own files and always come to the point where a key and iv guessing would take ages but is theoretically easy. It just takes time with the computing power we have today.

No, guessing the key is the hardest way to break the encryption. Nobody can break AES by guessing the key. It's theoretically easy, but practically impossible because it takes far, far more time than you have. If you took all the existing computing power on Earth now (yes, including NSA's) and ran it for the current age of the universe, you would still not stand a good chance of guessing an AES-128 key.

The way cryptography gets broken in the real world is not because the building blocks are weak, but because people take strong building blocks and assemble them badly.

  Version 1: Since CBC is always based on the the pre block, why do I not just change the order of the blocks in the file and write a map together with the key and iv into the RSA part? Is this a stupid idea?

You can only send a limited amount of extra data in the RSA part, so that would limit the size of the message. For a very short message (up to about 15–20 blocks — $\log_2(15!) \approx 40$, $\log_2(20!) \approx 61$), all possible permutations can easily be enumerated, so you have no security gain. For longer messages, what do you gain? The attacker has undecipherable blocks in some unspecified order. They're undecipherable anyway. The attacker can't even distinguish between the blocks.

So maybe you have extra security in case something else is broken? Think again. If the permutation gives extra security, it can only be because the attacker cannot distinguish between the blocks: otherwise that means the attacker can reconstruct the permutation. And if something else is broken, broken means that the attacker does have extra knowledge about the blocks. This extra knowledge isn't absolutely guaranteed to let the attacker know which order to put them in, but it's likely to help.

So the offshoot is that no, you're very unlikely to gain anything. What do you have to lose? Well, once again, where cryptography gets broken is because the building blocks are misused. Every extra complexity that you add increases the attack surface of both your protocol, and your implementation. Doing extra stuff makes your protocol less secure, not more.

  Version 2: Why do I not just replace a random character in each AES block with its "value" + 1 or so and write into my RSA a map of the chawed characters?

For pretty much the same reasons as version 1, this has a cost and no advantage. You'd just be increasing the attack surface to make indistinguishable blocks indistinguishable.

  Who knows about the computing power we will have in a few years.

To be resistant to quantum computers in case they actually become useful to break cryptography, use AES-256. Quantum computers basically halve the effective key size of symmetric algorithms. AES-128 is good against classical computing but fails to a quantum computer that's able to perform about $2^{64}$ (a few billion billions) operations.

The asymmetric part is more problematic. We don't have a widely accepted asymmetric encryption algorithm that would resist quantum computers.

But by far, the biggest risk in what you want to do is design and implementation mistakes. The worst thing you can do is to devise your own protocol. What you should do is:

Use an existing, vetted implementation of an existing, vetted protocol. To encrypt some data with an asymmetric key scheme, crypto_box has a good reputation.
Be agile: prepare to upgrade your protocol if it gets broken.


They are somewhat similar. A nonce is a more general concept which might occur in modes of operations or protocols whereas a tweak almost always refers to a tweakable blockcipher.

A nonce is a number that must be used only once. Of course there are now nonce-misuse resistant constructions which decrease the impact of accidental nonce reuse but in general you lose security if you reuse a nonce.
A tweak on the other hand can quite naturally be reused. One of the original uses for a tweak was for disk encryption where the tweak would depend on the position on disk. This will make the same plaintext encrypted with the same key give different ciphertexts.

In a way a tweakable blockcipher allows using more simple modes of operation without nonces. You don't have to chain blocks in complicated modes anymore to make sure that blocks cannot be compared or replaced you simply use "ECB mode" with a different tweak for each position.

So they somehow accomplish the same goal but nonces do so on the mode-of-operation level and tweaks directly on the blockcipher level.


Stream cipher -- Are all random bit generators suitable for stream cipher?

The requirements for cryptographically secure pseudo random number generator and those for a stream cipher are essentially the same.
Obvious not all PRNG are secure, LFSR and mersenne-twister to name a few aren't suitable for any cryptographic task.

In some cases a PRNG will be not practical for use as a cipher. If you look at it in the pure form of a seed generating a stream of random bits than we are OK, random bits are random and knowing some won't help me know the others. But if you look at the full system, PRNGs require some entropy collection and this can make it unpractical when you want to make it a keyed cipher, some PRNGs may for instance have a huge seed which you will not want to use as a key.