Efficient protocol to give out N known items randomly to k>=3 parties without independent bodies

Consider the following protocol to find the sum of secret integers among $k$ parties:

Pairs of parties use RSA or any other communication protocol to set up a secure channel of information. In the exchange, they declare a number $x$ such that the first party subtracts $x$ from their secret integer, and the second party adds $x$ to their secret integer.

When the following is satisfied:

Each party has communicated with at least 2 parties.
The graph formed by vertices being parties and edges being communications is biconnected. It is sufficient to make a cycle graph.

If every pair of parties communicated, then any communication between any pair of parties would not get any more information than them sharing which cards they have.

The parties announce their modified numbers, and the sum can be calculated by summing the modified numbers. This step takes $O(k)$ (or $O(k^2)$ for the other version) time.

Consider the following protocol to generate random numbers:

Each party generates a random bitstring of a certain and commits to it (by salting and hashing). All parties reveal their bitstring and the xor of all the bitstring is taken to be used for random numbers. This takes $O(k|bitstring|)$ time.

The main protocol is:

Each party $i$ chooses $N_i$ random integers in the range $(0, N^2)$ and commits to them. The parties would try to find the order of their random integers (number of other random integers chosen by all the parties which are less than it). We also have to detect when two parties choose the same integer.
For each integer $x$ from $0$ to $N^2$, each party is supposed to find the number of integers they have less than $x$, summing all the secret integers would give the order of $x$. If the order of $x$ and $x+1$ differs by more than $1$, rinse and repeat. As there are $O(N^2)$ numbers, this step takes finitely many steps with probability 1. This takes $O(N^2k)$ time.
Now, each party knows the order of their random integers, and the set of orders of the random integers is from $[0, N)$. We map the orders to the $N$ items by selecting an order and using the random number protocol to to generate enough bits to select a random item from the remaining items. This step takes finitely many steps with probability 1, and is expected to take $O(N \log N)$ bits, hence taking $O(kN \log N)$ time.
To prove that a party owns the item, the party has to reveal the random integer used for that item, and since it was committed in advance, other parties can check it.

Example: With $N=k=3$, the $N$ items being $A, B, C$, $N_0=N_1=N_2=1$, parties $0, 1, 2$ select the numbers $5, 2, 7$ respectively among $(0, 9)$.

Using the secret summing method, they get the orders (which we denote as $\text{ord}$) of the integers:

$\text{ord}(0) = 0$

$\text{ord}(1) = 0$

$\text{ord}(2) = 0$

$\text{ord}(3) = 1$

$\text{ord}(4) = 1$

$\text{ord}(5) = 1$

$\text{ord}(6) = 2$

$\text{ord}(7) = 2$

$\text{ord}(8) = 3$

$\text{ord}(9) = 3$

It is easy to check that there are no two randomly selected numbers that are the same.

Using the random number generator, the parties decide that the order of $0$ maps to $C$, $1$ maps to $A$ and $2$ maps to $B$.

Hence, party $0$ gets $A$ as $1=\text{ord}(5)$ maps to it.

Party $1$ gets $C$ as $0=\text{ord}(2)$ maps to it.

Party $2$ gets $B$ as $2=\text{ord}(7)$ maps to it.


How are the IVs of SHA-512/256 and SHA-512/224 calculated?

Those are calculated using the "SHA-512/t IV Generation Function", as described in FIPS-180 (pdf, see 5.3.6), the Secure Hash Standard.

The procedure is to first modify the normal SHA-512 IV, then calculate the hash of a string describing the truncation mode used, and use that as the IV. Those IVs are essentially just predefined hash outputs and so not any particularly nice numbers.

The reason it is done like this is to allow arbitrary truncation lengths below 512 (except 384, which has its own hash which was defined earlier).


Example of a cut-and-paste attack on CBC

Attacking CBC is much harder than ECB. In many cases there is no viable attack. Properly implemented CBC with a secure underlying block cipher is secure.
There have been successful attacks against padding in CBC, though non were anywhere as simple as attacking ECB.
Look at: https://en.wikipedia.org/wiki/Padding_oracle_attack
https://en.wikipedia.org/wiki/POODLE

There are also attacks on implementations of CBC with predicatble IVs e.g:
https://www.netsparker.com/blog/web-security/how-the-beast-attack-works/

CBC has lost favor not because it is insecure in itself but because it is easy to implement poorly and there have been many attacks. If you expect anything remotely as simple as attacks on ECB I am happy to inform you these do not exist nor are expected.

Edit: I seem to have missed the point of the question, it was about manipulating cipher text.
CBC is probably the least malleable of the common block cipher modes(harder than ECB or CTR) and yet without a authentication of some sort a MAC, or GCM or such CBC can still be manipulated, specifically if you have wiggle room and are willing to create a junk plain text block at your cut and paste boundary. If you know the plain text of a given block, you can replace it with a plain text of your choice by manipulating the previous cipher text blcok. calculate the xor diff between current plain text and desired plain text and apply it to previous cipher text block.
This will cause the previous block to decipher into gibberish and the target blcok to be deciphered into whatever you want.


I would suggest using a classical cipher like Vigenère, for example:

Plaintext:  Hello, How are you?
Key:        topsecret
Ciphertext: Asads, Jfa tks ngy?

But bear in mind that classical encryption techniques are very insecure by modern standards.


What functions allow for practical indistinguishability obfuscation?

Canetti ("Towards realizing random oracles," Crypto 1997) gave a reasonably efficient (very efficient, by the standards of most obfuscation work) "virtual black-box" obfuscator for "point functions," i.e., functions of the form $I_x(y) = 1$ if $x=y$, $0$ otherwise.  Such functions can be used, e.g., for password checking.

Virtual black-box obfuscation implies indistinguishability obfuscation, and is impossible for general circuits, but seemingly possible for specialized functions (like point functions).

In Canetti's construction, evaluating an obfuscated point function requires only one call to a collision-resistant hash function, and one exponentiation.  Its security relies on some strong, nonstandard, DDH-like assumption.

There are follow-up works by Wee and Canetti-Dakdouk, among others, on obfuscating point functions, hyperplanes, large-output functions, etc. etc. with VBB security.

Also, Lynn-Prabhakaran-Sahai ("Positive Results and Techniques for Obfuscation," Eurocrypt 2004) gave VBB obfuscators for certain classes of access-control functions, which I believe are not exceedingly inefficient.  They work in the random oracle model, however.

These are just a few representative works from prior to the iO revolution, when people were mainly working on VBB obfuscation for specific classes of functions.


The question is about an attempt to augment an encryption scheme with an integrity-protection measure, by additionally transferring the hash $H=\mathtt{Hash}(P)$ of the plaintext $P$ together with the ciphertext $C=\mathtt{ENC}(P)$ of the original encryption scheme; and having the recipient of an alleged $(C,H)$ obtain the alleged $P=\mathtt{DEC}(C)$, and accept that $P$ as genuine if $\mathtt{Hash}(P)=H$.

This attempt fails disastrously:

The original encryption scheme is greatly weakened, for $\mathtt{Hash}(P)$ reveals information about the plaintext $P$. An attacker Eve can test with high confidence if a guess of $P$ is correct! If $P$ legitimately sent by Alice is the result of a yes-or-no vote, or otherwise is one in a moderate list of possibilities (e.g. a password), Eve can now recover $P$ without attacking the original encryption scheme at all.
The change provides no integrity protection when used with a public-key encryption scheme, where Alice enciphers a message to Bob using Bob's public key. Eve can choose any message she desires, hash it, and encipher it using Bob's public key, just like Alice.
Even considering symmetric encryption schemes, in many important use cases, the change fails to provide integrity protection against an Eve able to guess/obtain/choose the plaintext, or part of it; these are standard hypothesis, and we have seen with 1 that guesses have been made verifiable by the attempted strengthening. Examples, among many:

a. Many schemes, including the One Time Pad, all Stream Ciphers, and all Block Ciphers employed in the OFB or CTR mode of operation, have the property that $\mathtt{ENC}(P\oplus X)=\mathtt{ENC}(P)\oplus X$ (where $\oplus$ is bitwise Exclusive-OR). In these cases, Eve is able to change the message $P$ to $P'$ of the same length: Eve uses $\mathtt{Hash}(P)$ to confirm her guess of $P$, chooses $P'$ she want to substitute, computes $\mathtt{Hash}(P')$, and computes $C'=\mathtt{ENC}(P')$ as $C'=\mathtt{ENC}(P)\oplus P\oplus P'$.

b. Most schemes have the property that truncating the ciphertext correspondingly truncates the plaintext (often, with restriction to truncation at block boundaries). An adversary unable to guess the end of a message, but knowing the start (because that is conventional, or transmitted in clear alongside) can truncate the ciphertext, and compute the corresponding plaintext's hash. Thus Eve can make a forgery that deciphers to the truncated original plaintext, and passes the hash check.

c. Many symmetric encryption schemes, including all Block Ciphers employed in the ECB, CBC or CFB mode of operation, have the property that decryption of a segment of the ciphertext leads to the corresponding fragment of the plaintext (often, with restriction to segmenting at block boundaries, and need to adjust the IV). If Eve can persuade Alice to encipher some message $P||P'$ of Eve's choice (a standard assumption; say, $P$ is a nice image that a viewing program will show when fed with the file $P||P'$), Eve now has $C'=\mathtt{ENC}(P')$ for $P'$ of her choice, and can compute the matching $\mathtt{Hash}(P')$.
Many common hashes (including MD5, SHA-1, and all SHA-2 hashes) have the length-extension property, which is that from knowledge of the length of $P$ and $\mathtt{Hash}(P)$, it is easy to determine a short $F$ such that for any $X$, it is easy to compute $\mathtt{Hash}(P||F||X)$. For some symmetric encryption schemes and plausible assumptions (similar to 3c), it might be possible to extend an unknown $P$ with some $F||X$, deduce $\mathtt{ENC}(P||F||X)$ from intercepts, and compute $\mathtt{Hash}(P||F||X)$ from the length-extension property.
The scheme is not protected at all against replay of earlier messages.

A Message Authentication Code (or keyed hash, which includes HMAC) can be used instead of the hash to fix 1/2/3/4 (but something extra is needed for 5). The key used for the MAC should be different from the key used for the encryption scheme, in particular if the MAC has building blocks in common with the encryption scheme.


How to derive formulas for addition and multiplication in Jacobian coordinates

I haven't worked through all the (boring) details but it should be fairly easy. Just start with the normal affine addition and doubling formulae but when it comes to the stage where you do any division, don't bother and just keep track of the numerator/denominator separately. The whole point of Jacobian and other projective representations is that you don't do any division until you HAVE to. The disadvantage is that one point has many different projective representations.

The $Z^2$ or $Z^3$ aspect is just shuffling multiplications around to make doubling slightly faster versus addition or vice-versa or to do with being able to add an affine point to a projective point more quickly. It tends not to matter too much. If you want faster calculations you should be choosing perhaps an Edwards curve representation and/or maths over an appropriately fast extension field.


Homomorphic encryption of logical OR/AND

One practical (if not theoretically satisfying) way would be to use Pallier, with the mapping "any encrypted nonzero value is an encrypted TRUE; any encrypted zero value is an encrypted FALSE".  To encrypt a TRUE value, you pick a random value and encrypt that, and the logical OR operation is the standard Pallier homomorphic addition.

Now, obviously, the OR of two TRUE values has a tiny probability of becoming FALSE; however it is far more likely that your computer is hit by a meteor...


How does ECDHE_RSA key exchange mechanism work?

Curve secp256r1 is not a type of curve; it is a curve, and is standardized under that name by SECG, under the name P-256 by NIST, and under the name prime256v1 by ANSI. It also happens to be the by far the most common elliptic curve used in cryptography. The field size, curve equation, and generator point are all part of the curve spec; the point of having a standardized curve is that it takes time to generate elliptic curve parameters, and there's no need for different people to use different curves.

Incidentally, based on your not mentioning the generator point you might be a bit mistaken on how the "random point" in ECDH is created. An ECDH key doesn't just have a randomly selected point for a public key; rather, you randomly pick an integer $k$ as your private key, and then compute the public key as $kG$ for a known point $G$. Like the curve parameters, both parties must know $G$; like the curve parameters, there's no reason why everyone in the world can't use the same $G$. So, this generator point is also part of the curve spec.

You also missed a crucial step in ECDHE: the ServerKeyExchange message. This is a mandatory part of ECDHE exchanges, and comes after the Certificate message and before ServerHelloDone. This has the server's ephemeral ECDH public key; the ClientKeyExchange has the client's ephemeral key.


Is Shoup's Practical Threshold Signatures considered secure?

Shoup proved security of his scheme in the random oracle model, which means that it should be "as secure" as RSA itself assuming you use a sufficiently strong hash function, which today should be SHA-2.

More important than the scheme itself, any implementation should be considered with some suspicion given the substantial history of buggy cryptosystems in the world; RSA is at least a tiny bit more forgiving than DSA/ECDSA in this regard.

In any case, I would suspect that threshold schemes, given their relative complexity, have some potential for side channel attacks, e.g., on timing.

Unless you require actual threshold signature capability, in which case one really needs to understand the schemes and implementations in depth, I would suggest using alternative methods that accomplish the same goal.

For example, one can simulate $t$-of-$n$ threshold signatures by issuing $n$ certificates and requiring that any $t$ of them sign a message before accepting that message. This unfortunately sacrifices some properties of threshold signatures (e.g., privacy) but can be more easily implemented using standard libraries.


how to calculate surge of cpu cycles consumption of an ipsec tunnel with aes256/sha512/dhgroup21?

In the scenario of the question, the cryptography involved on the server side will be, for each client connection, and ignoring a number of details like random number generation

Diffie-Hellmann in some group for the generation of session keys
Few SHA-512 as part of that, of relatively negligible computational cost for competent implementation, assuming 1 is in software (or if 2 was in hardware)
Some AES-256 cryptography, as part of packet exchanges, also of relatively negligible computational cost for competent implementation, usual packet size, assuming 1 is in software or 3 is in hardware (including using AES-NI of modern x86 CPUs)
Some other untold assymetric crypto operation (like a few signature verifications), especially if the clients are authenticated by assymetric cryptography; I'll leave that alone, but it could be significant, even dominant.

The groups in the blog post quoted in the question seem to be that of RFC 5114 section 3.2. I thus believe that the blog post makes a serious error when it ranks group 24 as "Next Generation Encryption" and more secure than group 19 ranked "ACCEPTABLE". Group 24 seems to be a Schnorr group with $p$ of 2048 bits and $q$ of 256 bits, quoted as giving 112-bit symmetric security where groups 19, 20 and 21 would be 256-bit, 384-bit and 521-bit elliptic curves with 128, 192 and 256-bit security (taking 192 and 256-bit security with a grain of salt as anything above about 160-bit in that sense could be attackable, with humanly sizable odds of success, only if there was a totally disruptive breakthrough, like quantum computers usable for cryptanalysis; or, regardless of security level, if there's some goof or backdoor in the implementation).

On a nearby VM with openSSL 1.02g installed and lscpu reporting 2 cores at 4 GHz, the command openssl speed reported what could be a passable benchmark for groups 19, 20 and 21 as implemented by openSSL (the last colum is mine, and I have slightly edited the others for legibility)

 256 bit ecdh (nistp256)   18190 op/s   (group 19)
 384 bit ecdh (nistp384)    1980 op/s   (group 20)
 521 bit ecdh (nistp521)    2834 op/s   (group 21)

I'm surprised that nistp521 is shown faster than nistp384; think of it as an illustration that timing varies enormously with the quality of the software implemention (and perhaps, different parameters in benchmarks, which I have not cheked). But these numbers tell us that the 2500 clients reconnecting simultaneously are unlikely to take more than a few seconds of CPU time for the crytography in 1 (thus in 1/2/3), with a competent implementation in software on a powerful x86 CPU, for groups 20 and 21; with group 19 significantly faster (and, as far as we know, unlikely to be an exploitable weakness anytime soon; compromize of the server or its private key is a much more down-to-earth concern).

Beware that an "ipsec concentrator/gateway" typicaly will use something much lesser than a powerful x86 CPU; on the other hand, some have crypto accelerators. The most important thing is how good and trustable is the software; and that's impossible to tell from specs.


UMAC uses AES, so it will not lead to a faster algorithm than the rolling hash + AES solution suggested in the previous question. Universal hashing based MACs like UMAC and Poly1305 usually use a PRF (which you could just use directly) to hide the hash. There are universal hashing MACs that do not, but as far as I know they are even slower. (Further, I am not sure if a secure MAC would even be enough, or if you actually need a PRF.)

Without leaking any more information, there are not many options. Rolling hash + SipHash is probably faster anywhere that you lack AES hardware, but that may be the best you can do.

If you find the performance cost to be unacceptable, you might want to allow some information to leak. For example, if you define chunking using parity(w) = 0 and then PRF(k, f(w)) mod (n / 2) = 0, you halve the number of PRF calls while only leaking one extra bit of information on the window (and even less for those positions where you did not end a chunk).

You can of course reveal even more information to reduce the number of calls further, but in the end you back at something leaks as much as just using f(w) mod n = 0.


How to find key length of a Vigenere chiper?

First find repeating substrings, longer repeating substrings are better. Look at the differences between the index of repeating subsring pairs. Calculate GCD of the differences.  If it is a reasonable key length you probably have it. If it came out 1 try dropping some outlier spurious substring occurences. If it came out too large to be a reasonable key you may need to find more repeating substrings allow shorter substrings to be considered.

Motivation:
We expect many repeating substrings of common char-grams, in English for instance : th,the,ing and more if these appear in a difference which is a multiple of the key length the cipher text fragments will be identical as well. However such a repeating cipher text is unlikely to appear from encripting some other text in another column.


Additional Data in AEAD (Chacha20-poly1305 libsodium)

First of all the Additional Data (AD) is not a tag. It is data that is also authenticated by the authentication tag. This authentication tag is appended to the ciphertext by libsodium. The tag doesn't consist of separate portions for AD and the ciphertext (and IV), the AD is taken into account during calculation of the tag.

The AD can be any data, including data that can be generated or data that is known in advance. In that sense it does not have to be send. How it is handled or generated is out of scope for the definition of the authenticated cipher. You do need all the AD data on both sides or you won't be able to calculate the authentication tag. The AD cannot be extracted from the ciphertext nor from the tag.

To my knowledge all authenticated ciphers already include the IV in the tag calculation, so there is no need to treat the IV as AD. It's actually a requirement for the CEASAR competition, so no doubt this algorithm will comply with that. Don't confuse or mix nonce and AD, they are different inputs to the cipher.

If you want a standard way of handling nonce, AD etc. you should look for a suitable container format such as CMS.


If the hash of the multiplication is equal to the multiplication of the hash, how can this be used to leverage an attack?

Perform a birthday attack:

Given $y\in G$ we want to find $w\in \left\{ 0,1 \right\}^*$ such that $H\left(w\right)=y$.

Randomly choose $x\in \left\{ 0,1 \right\}^*$ and calculate $H\left(x\right)$ and $yH\left(x\right)^{-1}$. Wait until we find $a,b$ such that $H(a)$=$yH\left(b\right)^{-1}$.

Now $w=ab$: $H(w)=H(ab)=H(a)H(b)=yH\left(b\right)^{-1}H(b)=y$.


Guessing the Secret in RLWE Search-to-Decision

The "guesses" are part of the enumeration of all possible values of $s\bmod \mathfrak{q}_iR^\vee$. The reduction has two parts essentially:

A way of telling if the guess was correct (the $\mathsf{WDLWE}_{q, \Psi}^i$ oracle)
A small space of values to try (as values $s\bmod \mathfrak{q}_i R^\vee$ are within $R_q^\vee/\mathfrak{q}_iR_q^\vee$, which from context in the paper appears to have size $N(\mathfrak{q}_i) = q = \mathsf{poly}(n)$).

You then enumerate all possible guesses, and return the one which verifies to be correct.
This is a deterministic process (although you're free to choose the particular order to enumerate things in).


It is possible to turn a hash function into a stream cipher; there are several methods for that, and the simplest is to compute $h(K||IV||x)$ for hash function $h$, initialization vector $IV$, and successive values of a counter $x$. This yields an arbitrarily long sequence of pseudo-random blocks (32 bytes per invocation if $h$ is SHA-256). Then XOR that stream with the data to encrypt or decrypt.

We don't usually do that for two main reasons:

Security of the scheme is not that easy to characterize. A "secure" hash function (resistant to collisions and preimages) will not necessarily imply a secure stream cipher that way. (Very) roughly speaking, the stream cipher is secure if the hash function behaves like a random oracle.
Performance sucks. Hash function are efficient at processing a lot of input data, not at generating a lot of output data.

It is of course quite tempting to have a unique primitive diversified into multiple usages; it would save space in code. However, in embedded systems where ROM size is at a premium (in particular smart cards), CPU power and RAM are even more scarce, and AES performs better than SHA-256 along these metrics.

Sponge hash functions, like the upcoming SHA-3 (Keccak), have an internal structure which is kind-of "reversible", meaning that they are good at input and at output. A Keccak core should allow both secure hashing and efficient pseudo-random generation (i.e. encryption, with a XOR).

Conversely, authenticated encryption modes like GCM use a block cipher for both encryption and integrity, the latter replacing what would have been classically done with a hash function (with HMAC).


How can I store confident data with OpenID?

Let's have a look on how OpenID works.

Alice wants to log into Bob's website using Charles as her identity provider. (So, you are Bob in this scenario.)

Alice fills her OpenID alice.openid.example.org into Bob's web form.
Bob (or Bob's server, actually) transforms this into a canonical form https://alice.openid.example.org/, and fetches this resource to find out who is Alice's OpenID provider (https://charles.example.com/openID/)
Bob redirects Alice's browser to Charles' web site, Charles then somehow checks that it is really Alice who is currently logged in (maybe asking Alice for confirmation), and redirects Alice's browser again to Bob, sending also some information about Alice for Bob along the way.

The information which Bob gets is either signed using a MAC with some previously negotiated common secret (between Bob and Charles), or will be later checked by direct interaction between Bob and Charles.

There is nothing in here which can be used as a private/secret key for Alice's user data by Bob, so there is no way Bob can encrypt something in a way that can be only decrypted with Charles' help (i.e. Alice's OpenID).

(Also, as Alice can use OpenID delegation, Alice can change here OpenID provider without changing her OpenID, and you surely want to have her data being still decryptable.)


How is PKCS a syntax to digitally sign, digest, authenticate, or encrypt arbitrary message content

PKCS stands for Public Key Cryptography Standards. The name was part of RSA Laboratories that managed to create and publish a very long list of standards, including:

PKCS#1 : RSA with various schemes for encryption + signature generation and schemes
PKCS#5 : Password Based Encryption or PBE
PKCS#7 : The Cryptographic Message Syntax or CMS
PKCS#8 : A scheme for storing / describing and and encrypting private keys
PKCS#11 : Cryptoki, a C based API for HSM's
PKCS#12 : A key & trust store format

PKCS in itself is not a scheme though. Many of these schemes use a language called ASN.1 that is used to describe data structures. It originated in the telco industries. For cryptographic purposes those data structures can be encoded using BER / DER binary encoding.

As RSA Labs was acquired by blood sucking capitalists, most of these standards have been supplanted by RFCs by now, including CMS, although you still see many mentions of PKCS#7.

As the name implies, CMS is a structure of cryptographic messages, described in ASN.1. As such it doesn't describe a method of creating signatures, it just describes how to store signatures and the signed content. Or indeed, how to store encrypted messages, possibly after signing them. CMS is a so called container format that describes what's inside, a bit like an archive or zip file but for cryptographic use.

Furthermore, it also describes how you can store X.509 certificates with the message that can be used to verify it. Verifying parties may not have the leaf / user certificate that was used to sign the document, but they may have a trusted CA certificate that can be used to create a certificate chain. X.509 certificates use a different structure also defined using ASN.1. Since certificates are basically also signed documents there are of course many similarities with CMS.

So no, CMS is not an algorithm, it is a container format for cryptographic messages. Those messages may be encrypted or signed using RSA, in which case CMS will reference the RSA algorithm. You can use the command openssl asn1parse or openssl -cmsout -print to view what the structure is and what's stored inside. You may have to use -inform DER if the input is binary instead of a textual PEM file (header, base 64 and footer).


It could enable a key exchange based off of symmetric primitives alone. For example, suppose I can provide to you a program that will allow you to perform AES-256 encryption of a single plaintext block. I could send you this program, you could perform your encryption and send me the result, and due to the whitebox nature of the algorithm, only I can decrypt it (not even you can).

This basically creates a public key encryption scheme using only the white box symmetric primitive. This is valuable because the hardness assumptions that underlie traditional public key primitives versus that of symmetric primitives. There is no known way to scratch the surface of the security of a single AES encryption. This is contrary to ordinary public key crypto, which is based on problems that more or less have very clear solutions, and only work because there are no known algorithms that are efficient enough to handle the key sizes involved.

The key size for AES are significantly smaller then say an RSA keypair, and the operations are significantly more efficient. A white box implementation might be different then a traditional implementation in this respect, but we'll have to wait and see.

This is not possible with a traditional implementation of AES because anyone who knows the key can perform both the encryption and decryption operations. With a white box implementation, the key is embedded into the program in a manner that makes it (ideally) impossible to extract. Of course, this also implies the program is constructed to only posses the encryption capability, and not decryption.


Fixed-points in block ciphers; why don't they indicate a vulnerability?

Intuitively, the reason fixed points are not a problem is the same reason that zeros in a one time pad are not. Because the transform is supposed to be random, a ciphertext that looks like plaintext could be that plaintext... or it could be any other plaintext. With proper encryption they are all equally likely.

  If I find out that the block that I captured is a fixed-point, I know the pText as well as eText for this key.

Yes, but how would you find out that it is a fixed point? By knowing that the plaintext and ciphertext blocks are equal. I.e. this is not additional information.

  Additionally, I know that the number of keys that result in such a fixed-point are very few. So maybe there is a way for me to get the possible keys given the fixed-point.

The number of keys with that particular fixed point depends on the key and block sizes. E.g. with AES-256 you'd expect about $2^{128}$ keys with any fixed point you want. In the case of AES-128 it is true that a fixed point would likely be unique to one or two keys. However, there is no way to exploit that knowledge.

If you know $E_k(x)=x$, you can iterate all keys testing for that. But you can do the same if you know $E_k(x)=y$ for some other $y$. So the fact that it is a fixed point does not make key recovery any simpler, unless the internal structure of the cipher is somehow weak with regard to this fact.

So...

  My assumption was that it'd be easy for the attacker to find out that the captured block is a fixed-point because it retains all of the original message's pattern.

That assumption is wrong, because there are supposed to be many other blocks that produce patterns that aren't in the original message. The probability that $D(x)=x$ should not be higher if $x$ has patterns.

  Also I assumed that the relation from fixed-point to key is quite obvious.

It is not at all obvious. There could be a relation, but that should be considered a weakness in the cipher.


What's the reason for Monte Carlo tests for block ciphers?

As usual, government departments simply repeat their existing rules.  So they incorporated the Monte Carlo tests from earlier test documents, this time from 1980.   If you follow the dusty trail from Maarten's link, you eventually arrive at NBS Special Publication 500-20, Validating the Correctness of Hardware Implementations
of the NBS Data Encryption Standard.  These are the two relevant extracts.

  This publication describes the design and
  operation of the NBS testbed that is used for the
  validation of hardware implementations of the
  Federal Information Processing Data Encryption
  Standard (DES).

and

  Since the test set is known to all, an additional
  series of tests is performed using pseudo-random data to
  verify that the device has not been designed just to pass
  the test set. In addition a successful series of Monte Carlo
  tests give some assurance that an anomalous combination of
  inputs does not exist that would cause the device to hang or
  otherwise malfunction for reasons not directly due to the
  implementation of the algorithm. While the purpose of the
  DES test set is to insure that the commercial device performs the DES algorithm accurately, the Monte Carlo test is
  needed to provide assurance that the commercial device was
  not built expressly to satisfy the announced tests.

So it is there to test  future hardware implementations of AES.


Would it be possible to generate the original data from a SHA-512 checksum?

No, because a  hash behaves (simply put) like a lossy compression function.

Meaning: you can use a hash like a sort of checksum, which enables you to identify and compare data. Using hashes, you can see if data has been modified (which, if re-hashed, would show a different hash as a result), or if two or more data packages are the same (every data package you hash will produce the same hash if the data is the same too).

But: you can not recreate the original data that was hashed. For that, you would need a (loss-less) compression function like you might know it from ZIP files.

So, no, you can not recreate the original data from it's hash. The only thing a hash is good for is to compare it with other hashes to see if the hashed data is identical or not.

To give you a real-world perspective on hashing data and your question about "extracting" the original data from a hash: expecting someone to be able to reproduce the original data from a hash, would be like asking someone to create a nice dinner for all of us while only having a receipt available.

The only option to try to recreate data that results in a predefined hash, would be to "brute-force" it with a trail-and-error approach where you create random data sets, hash those, and hope that they produce the same hash you've got. While such a brute-force method works with small data packages, it won't work for big data-sets as you describe them since it would take too long until you "by chance" happen to produce exactly the same data-set that once existed and which produced the originalhash. Good luck with that... you can safely expect to waste a life-time trying to get that one lucky match that fits a specific, predefined hash.

While I'm at it: it might be interesting for you to know that older and mostly broken hashes (MD2 etc) are known to have certain weaknesses that result in so-called "hash collisions". Such hashes are broken because those hash collisions mean nothing else than  that two different data-sets produce the same hash, which should not happen as a hash is expected to produce a unique values for different data-sets. But that's just additional knowledge as hash collisions merely show the related hash fails it's job; they can not and will not help you recreate the data either. Why? Because a hash is something like an identification tag. It does not hold all the hashed data, and can therefore not reproduce it in any way.


simple algorithm to encrypt/decrypt a text file

My advice would be to use a stream cipher.

First of all, it is easy to implement, because you won't have to think about dividing into blocks, padding, etc..

Secondly, the idea of stream ciphers is very easy: you generate a  pseudorandom sequence of bits out of the private key. Then you XOR this sequence with a plaintext. You will only have to code the generation, the rest is elementary.

Finally, there are very easy stream ciphers, e.g.  RC4 http://en.wikipedia.org/wiki/RC4;  another example is Salsa20 http://en.wikipedia.org/wiki/Salsa20

And when I say "simple" I mean not only the amount of lines of code, but also the ease of debugging/ flaws search.


Pseudorandom generator and AE-secure encryption

Yes.  The existence of a secure pseudorandom generator (PRG) implies the existence of all sorts of other symmetric-key primitives, including a secure PRF, a secure block cipher,  a secure MAC, etc.  That is enough to build secure authenticated encryption.


Can a 1 byte difference in AES 128 bit keys make huge difference in output?

If we take some randomly generated key of AES-128 and we change any random 1 byte of that 16 byte key, will this make huge difference in the AES cipher text generated over same input string?

Yes. The outputs with different keys differ greatly. If you pick two random keys the outputs must look completely uncorrelated, or an attacker could gain an advantage just by generating his own key.

With some changes the picture is a bit more complicated, because there are related-key attacks on AES. There the attacker would have to get access to encryptions with keys derived from the original, but if they did they would have an advantage since the outputs aren't totally independent.

However, that's not a very realistic attack in practice, and anyway AFAIK they only exist on AES-192 and AES-256, not (the full 10 rounds of) AES-128.

  Does this 1 byte change makes output look like uniformly random? Does it have an effect on security?

In the absence of better attacks, yes. It would be good for security if it was always true, but it's not a huge problem if it isn't, as long as random keys still produce unrelated-looking ciphertext.


Why is Decisional Diffie–Hellman assumption harder than the Computational Diffie–Hellman assumption in cryptography?

There are groups that allow a 'pairing' operation; that is, an efficiently computable function $e$ with the property:

$$e(x, y^a) = e(x^a, y)$$

for all group members $x, y$ and integers $a$.  Actually, the pairing operation maps the pair into another group, with the additional property $e(x^a, y^b) = e(x, y)^{ab}$; that's not important here (but is important for other uses of the pairing function).  We also assume that $e$ is nontrivial, that $e(x, y)$ doesn't uniformly map to the identity group member.

In any case, if we were given four values $g, g^a, g^b, g^c$, this function would allow us to check whether:

$$e(g, g^c) \stackrel{?}= e(g^a, g^b)$$

If this equation doesn't hold, then we know that $g^{ab} \ne g^c$ (and if we make some assumptions on $e$, then we can actually get equivalence).

However, this $e$ function doesn't give us any obvious way to recover the value $g^{ab}$, given $g, g^a, g^b$


ECDH is included in the ciphersuites, so the only answer is: yes, this should be possible.

For your further research, it might help to know that Crypto.SE features a lot of Q&As related to “OpenSSL ECDH”.

Also see the related documentation at the OpenSSL wiki for practical code examples showing how to use ECDH in OpenSSL, how to use the low-level APIs to achieve the same, and infos about how to handle ECDH and Named Curves.


Where to store sensitive keys in a device?

If it can be stored, it can be recovered.

Consider the unsettling fact that even if you were able to select a hard-to-discover location, since you are using a consumer device, at any point in the supply chain (HDL design, whoever makes your microcontrollers, etc) someone could have compromised the device long before you get to designing the firmware. You are wise to observe the likely-negligible extra security obtained.

As others have mentioned, reactivating JTAG or UART ports is not that big of a deal, and I can just crack open your device and dump out the flash memory anyway. Understanding firmware is easier than ever. You should assume your adversary has access to IDA Pro, understands firmware emulation, and is willing to drop some cash on an EEPROM or flash reader. (This is what I do, anyway.) Being clever may slow an adversary down but it can provide no guarantees.

Even HSMs are not necessarily secure. It's turtles all the way down.


Part of the problem you're having is that there are multiple distinct vulnerabilities in WEP, and you're getting confused by the sheer number.  For example:

  I still don't have an understanding of how one might exploit [repeating IVs] to retrieve the key

Answer: those are two separate vulnerabilities.

The shortness of the IV space is an obvious vulnerability; the keystream used to encrypt the packet is a deterministic function of the IV and the key; if we see two different packets encrypted with the IV, we can immediately reconstruct the xor of the plaintexts (by xor'ing the ciphertexts); depending on the plaintexts, this can often allow us to deduce what the plaintext was.

However, this observation doesn't allow us to recover the key.  The key recovery attacks rely instead on the details of how WEP creates the RC4 key (by concatinating the 3 byte IV with the 5 or 13 byte key), and how RC4 processes that key into the initial permutation, and then how it uses that permutation to generate the initial key stream bytes.  It turns out that, depending on what the IV is (which the attacker can see), the first byte of the key stream may be correlated to one of the key bytes - by observing enough of these first bytes (which the attacker can deduce, as the first byte of the WEP plaintext is fixed), the attacker can deduce the key.

  How does one exploit [the weaknesses with the message checksum] to break the key?

That's a third vulnerability, and it can't directly be used to recover the key (unless a cleverly modified message can confuse the receiver into revealing it somehow).

This weakness is simply the observations that a) the message tag is a publicly computable linear function of the plaintext, and b) by flipping a bit of the ciphertext, we also flip the corresponding bit of the decrypted plaintext.  Hence, we can flip an arbitrary bit of the plaintext, and then compute which bits of the tag would be flipped and flip those as well; what this means is that if we know/guess one plaintext message, we can modify it into anything we feel like (possibly restricted to the same length; I'm not sure how we could modify that).

Since this works independent of what the key is, it doesn't help us to recover the key.


How can I find the order of the group that an elliptic curve is defined over?

The number of points on the curve $|E({\mathbb F}_p)|$ is defined as $|E({\mathbb F}_p)|=p+1-t$ where $t$ is the so called trace of Frobenius. Using Hasse's theorem one can bound $t$ as $|t| \leq 2\sqrt p$, which gives you an estimation for the number of points for $E({\mathbb F}_p)$.

Now you could use a naive algorithm and simply run through all elements of ${\mathbb F}_p$ and determine whether they satisfy the curve equation to count the points, which however requires exponential time.

Luckily, you can use polynomial time point counting algorithms, such as Schoof or SEA, which allows you to efficiently determine the number of points on the curve.

For cryptographic use you will typically require a prime order subgroup $G$ of $|E({\mathbb F}_p)|$ such that the value $h = \frac{|E({\mathbb F}_p)|}{ord(G)}$, the so called cofactor, is a small integer (typically $\leq 4$).


How to generate whitebox AES decryption algorithm and code, with existing WB-AES encryption code?

Encryption table & decryption table are generated separately, using one same key (e.g., 16 byte key for AES128)? Correct? which means there are two table generation algorithms (and hence two separate lookup tables) - one encryption, one for decryption.

yes, this is correct. you need two different sets of tables to implement the encryption and the decryption algorithm. Both set are generated using, of course, the same secret AES key.

  What are the important steps to modify an WB encryption project into a WB decryption project?

To implement the AES decryption, one should undo all operation one-by-one doing the inverse: you could, therefore, rewrite the table generator algorithm following this logic and then writing the corresponding decryption function where the round structure is inversed.
Otherwise one can notice that decryption can be implemented using the same round structure as encryption but with a slightly modified key schedule (and the operations replaced by their inverses).
I suggest using this second way to implement decryption, as you only need to change the key schedule function and the rest of the implementation stays the same.

EDIT: more details are available on the AES standard publication at Section 5.3.5 where the Equivalent Inverse Cipher is described.

  Is there any WB AES decryption implementation for me to read?

if I remember correctly, the following implementation contains both encryption and decryption direction.
You can also read the very good tutorial by James A. Muir (pdf)


AES - which cipher is the safest one out there and what are the best practices for creating and storing the key

First question is what is the best way to create a completely random and unique key?

Simply generate an appropriately sized array of cryptographically random bytes from something like /dev/urandom, CryptGenRandom, or apparently openssl_random_pseudo_bytes.

The rest of your derivation process appears to serve no function; Even if it did, the entropy content of time and three random bytes is very low, so low that it can be guessed in practice.

So

$length = 32;
$hash = hash('sha512', microtime(true) . random_bytes(2) . chr(rand(0, 255)) . openssl_random_pseudo_bytes($length));
if((strlen($hash) / 2) > $length){
    $x = rand($length / rand(1, $length), strlen($hash) - $length);
    $key = substr($hash, $x, $length);
} else{
    $key = substr($hash, 0, $length);

Would become:

$length = 32;
$key = openssl_random_pseudo_bytes($length);

And that really is all that you need, assuming that openssl_random_pseudo_bytes provides cryptographically secure random bytes.

  The cipher that I'm using is: aes-256-gcm. Is there a better cipher that I could use (a more secure one that has a longer key maybe)?

There is no benefit to using a key that is larger than 256 bits. One of the only reasonable alternatives to AES-256-gcm would be a Salsa/ChaCha-poly1305 based construction. If you're concerned about side channel attacks, then it might be wise to switch. However, if the library you're using doesn't happen to support Salsa/ChaCha-poly1305 out of the box, then don't worry about it.

  Also why does aes-256-gcm accept a longer than 32 bytes key but on decryption it just ignores anything above the first 32 bytes of that key?

The algorithm is only defined to use key sizes of 128, 192, and 256 bits; You cannot simply supply more and expect them to be used.

It is possible that the key length not being checked might lead to a bug somehow.

  Finally what is the best way to store the key for later usage

Here are some options:

Derive the key from a password on application startup
Split the key into $n$ secret shares and distribute them to a bunch of distinct servers

Retrieve the shares and recover the key on application startup

Store the key on a hardware device such as a flash drive
Make use of some kind of HSM (hardware security module) device.

The last option should easily be the most secure, but it will cost money.

If you go with any option other than the HSM, do your best to ensure the key only stays in memory in one location and isn't copied all over the place. With an HSM this isn't a concern, as the key never leaves the HSM.


What is the "compression function" in Merkle-Damgård?

A compression function takes two fixed size inputs: a chaining value and a message and returns a fixed size value. So it's essentially a hash function with fixed input size.

Merkle-Damgård is a domain extender, which turns that compression function into a hash which supports arbitrarily long messages.

MD uses the output of the compression of one block as the chaining value when hashing the next block. It also describes how to pad the message so it consists of complete blocks.


I'm assuming you mean a base 64 encoded key file, since removing the newlines from a binary file would obviously break things.

The RSA standards (e.g. RFC 2459) only define a binary representation for keys. In practice, like OpenPGP keys (RFC 4880), they are often encoded in base 64 using the otherwise obsolete PEM standards (RFC 1421).

The PEM printable encoding section says:

  To represent the encapsulated text of a PEM message, the encoding
     function's output is delimited into text lines (using local
     conventions), with each line except the last containing exactly 64
     printable characters and the final line containing 64 or fewer
     printable characters.

The OpenPGP radix 64 section says:

  The encoded output stream must be represented in lines of no more than 76 characters each.

For SSH, on the other hand, RFC 4716 Section 3:

  A key file is a text file, containing a sequence of lines.  Each line
     in the file MUST NOT be longer than 72 8-bit bytes excluding line
     termination characters.

Do implementations in practice accept longer lines? I would expect many to do so. However, while no information is lost, it's technically nonconforming to use such encodings.


Which properties of a group are used in the steps of Diffie Hellman?

I’m trying to understand which properties of a group are used in DHKE at each step.

Actually, you can implement a DH-style operation in any semigroup; you need closure, and you need associativity (so $A^3 = A\times A \times A = (A \times A) \times A = A \times (A \times A)$ is well defined), but other than that, you really don't need anything.  You don't need an identity, you don't need the semigroup to be abelian (although the sub-semigroup generated by a single element will always be abelian), it doesn't have to be finite (although infinite semigroups would cause practical problems during implementation) and you don't need inverses (which, if you don't have an identity, aren't well-defined anyways).

We typically don't talk about doing DH in a semigroup mostly because (AFAIK) no one has found a semigroup (that's not also a group) that has any particular advantage over a true group.

Now, what's a more interesting (and considerably harder) question is "what properties do you need for DHKE to be secure?"  We do have assumptions such as the CDH assumption ("given $g, g^a, g^b$, it's hard to compute $g^{ab}$), however we don't know what semigroup properties ensure that...


Why the $IV$ used in Merkle–Damgård has to be fixed to a specific value?

One reason is convenience: if the IV was variable, it would have to be transmitted to a party verifying the hash, and we'd have to deal with its integrity.

Another reason is that it avoids an attack in a Merkle–Damgård variant with padding reduced to appending a single 1 bit and as many zeros as necessary to end the block. With such scheme and common compression functions, like the ones in MD5, SHA-1, and the SHA-2 familly, ability to choose the IV implies ability to chose a secret prefix that does not change the hash.

Notice that the compression function $C$ used in these hashes is of the form
$$(X,K)\rightarrow C(X,K)=X\tilde+ E(X,K)$$
where $X$ is the current state (initially the IV), $K$ is the block to hash, $\tilde+$ is a variant of addition (with a few carries suppressed), and $X\rightarrow E(X,K)$ is a reversible block cipher with key $K$.

Who defined an $IV$ that's not a nothing-up-my-sleeves number could have chosen a secret one-block $K$, computed $IV = E^{-1}(0,K)$, which insures $IV=C(IV,K)$. That allows insertion of $K$ at the beginning of any message, without changing the hash.


SHA3-512 troubleshooting - is there a worked example for hashing the "zero-length string"?

Does anyone know of some document or tutorial that gives a worked example of each step in using SHA3-512 to generate a digest of the message "" (or some other short message), giving detailed step-by-step values for all variables in the algorithm?

What you are looking for is called a "test vector" (with intermediate values) and NIST offers them for all their standardised primitives.

The one for SHA3-512 for 0-bit input is this PDF. Because it's 38 pages full of data, I won't post it here but it has the state after intermediate function application for all rounds for an empty message.


CVE-2014-1295 (Apple's Secure Transport and Triple Handshake Attack)

The attacker acts as a man-in-the-middle and can forward the clients nonce to the server and the servers nonce to the client. As a result both parties establish a connection with the attacker using the same nonces.

Because of a weakness in the TLS protocol, the two connections can have the same key, and this key is known to the attacker.

After resumption TLS 'forgets' that the connections were established with the attacker, and did not prevent renegotiation, e.g. using client authentication, between two honest participants. This is corrected by the patch that requires a renegotiation to present the same server certificate as was presented in the original connection.


Order of target group in bilinear pairing

I find it. The output is $e(g_1^p,g_2^a)=(g_t)^{ap}$. https://eprint.iacr.org/2013/812.pdf


Turning data into seemingly random noise

What you described is to use a so-called "stram cipher".

Stream ciphers output a random sequence of bytes for the same Key/IV pair.

The usual usage of stream ciphers is to XOR the data with the stream to obtain the encrypted data. You may want to follow the same approach by replacing the LSBs by the bits that were output by the encryption procedure (Data XOR Stream). The data is confidential then and can not be deciphered.

If you use some well-known algorithm like ChaCha, Salsa20 or AES-CTR you don't even have to hide the algorithm, you can tell your adversaries that you use this algorithm and they still can't read the enciphered data. You only need to keep the Key and the IV secret. Note: Using stream ciphers will hide any patterns that might be in the plaintext.

But you're not done here.
An attacker can't read the information but he can still alter it. So he can tamper with the data you encrypted and using some nice bit-flips he can alter the transmitted data in a malicous way (like changing numbers). So you wan't to use some sort of authentication mechanism (Message-Authentication-Code = MAC).

The best approach is to use AES-GCM or ChaCha-Poly1305 to get both: Confidentiality and Integrity. These modes will generate tags (usually 128 bits) which you'd store at the end of the data and you'll be able to verify that the data hasn't been tampered.


Time gap between Diffie-Hellman Key Exchange and ElGamal encryption?

Actually, if you read Diffie and Hellman's paper closely, you'll see that they explicitly talk about taking another's party value from a public file. Thus, it really already does public-key encryption. However, they didn't call it that, and people didn't view it as public-key encryption, but rather as key distribution.

The reason for this is that at the time, the understanding was that public-key encryption required a "trapdoor function" that can be inverted using the secret key. In fact, this is how Diffie and Hellman defined it, and thus they couldn't achieve it.

Now, El Gamal explicitly stated that the technical construction is just Diffie-Hellman. However, his conceptual contribution is enormous; he recognized that public-key encryption does not need to be an invertible function. By the way, the majority of his paper is about the digital signatures and this is novel.

This discussion raises an interesting point which is that some important results are completely non-technical and are important because they make us look at things differently. This is exactly what the El Gamal paper did.


Securely "forwarding" a Large message in a hybrid encryption system without sending the actual message

One common way is securely sending the encryption key for each user with their public key and store the encrypted data on somewhere where each user can access.

You can do this with RSA-KEM with using RSAES-OAEP padding and any Authenticated Encryption like AES-GCM;

The Distributer;

First generate a random encrption key $k$ for AES-128,192,or 256
Encrypt the message with AES-GCM genenerate an $IV$ and $$(IV,ciphertext,tag) = \operatorname{AES-GCM-Enc}(IV,message, k)$$
Upload $(IV,ciphertext,tag)$
For each user send a message with $\operatorname{RSAES-OAEP}(pk_{user},k)$ using their public key.

The receivers;

To get $k$, They are using their private key ,$$k = \operatorname{RSAES-OAEP}(priv_{user},k)$$
Decrypts the message with AES-GCM $$message = \operatorname{AES-GCM-Dec}(IV,ciphertext,tag, k)$$

This Key Encapsulation Mechanism (KEM) together with Data Encapsulation Mechanism (DEM) provides the standard of IND-CCA2/NM-CCA2 — ciphertext indistinguishability and non-malleability under adaptive chosen-ciphertext attack.

Note 1: The above described modified the RSA-KEM since the original RSA-KEM for multiple users will fall into Håstad's broadcast attack. Instead, using RSAES-OAEP makes it safe for multiple recipients with the same $k$ encrypted for different recipients as PGP/GPG.


k(k-1)/2: Combinations and the Birthday bound

$k(k-1)/2$ is usually called a binomial coefficient and written $k \choose 2$. It corresponds to the number of unordered pairs of distinct elements out of $k$ elements. It does indeed correspond to the sum ${k \choose 2} = \sum_{i=1}^{k-1} i$. This is quite intuitive: fixing one element, you have $k-1$ pairs containing this element. Now remove it, consider a second element: you have $k-2$ pairs with this second element, and so on. At the end, you get $(k-1) + (k-2) + \cdots +2 + 1 = k(k-1)/2$ pairs.

your bottom right formula is the general formula for ${k \choose r}$.


Does Linear Cramer-Shoup have pseudo-random ciphertexts?

The security claim on page 5 of the Linear Cramer-Shoup paper is that their modified scheme is CCA secure, which is weaker than the IND-CCA2 security of the original DDH based Cramer-Shoup scheme. However, from the outline of the security proof, it seems the author actually means the LCS scheme is CCA2 secure.

Also note the first sentence on page 6:

"Clearly, if $A$ has a different advantage in guessing the bit $b$ when $B$ is run with a Linear tuple $(g_1,g_2,g_3,g_1^{r_1},g_2^{r_2},g_3^{r_1+r_2})$ and when $B$ is run with a random tuple $(g_1,g_2,g_3,g_1^{r_1},g_2^{r_2},\eta)$, we obtain a distinguisher for the Linear problem."

The cipher text $(u_1,u_2,u_3,e,v)$ consists of the last three elements of such a linear tuple, plus a blinded message $e$ and a verifier $v$.

Since $u_1 = g_1^{r_1}$ and $u_2 = g_2^{r_2}$ and $r_1, r_2$ are selected at random, these two values are trivially indistinguishable from uniform, because they are uniform. Since $u_3 = g_3^{r_1 + r_2}$, this value is indistinguishable from uniform by the Linear assumption.

The blinded value $e$ is proven to be "independent of the view of the adversary", which I interpret as being indistinguishable from uniform. The proof is interesting. Basically, it is based on the following derived problem:

Given $(g^s,g^t,g^{sa},g^{tb},g^{a+b},g^{ad+be+cf})$ and any number of points on the "plane" $P(x,y) = g^{xd+ye+(x+y)f}$ except $P(a,b)$, output yes if $c = a + b$, no otherwise.

The uniformity of $v$ might be derived using the same technique. Set $g = g_3, g^z = g_1, g^w = g_2$. We then have:

$v^\prime = g^{r_1z(x_1+\alpha{y_1}) + r_2w(x_2+\alpha{y_2}) + r_3(x_3+\alpha{y_3})}$, where $v^\prime = v \iff r_3 = r_1 + r_2$.

Clearly, if $r_3$ is selected uniformly at random, $v^\prime$ is also uniform, so if you are unable to tell if $r_3 = r_1 + r_2$, you are unable to distinguish $v$ from uniform.


How to verify CA certificate from Yubico with openssl?

Well, they say they use gpg to sign the file (yubico-utf-ca-certs.txt) and the signature is in the linked file. So

gpg --verify yubico-u2f-ca-certs.txt.sig yubico-u2f-ca-certs.txt

gpg: Signature made Tue Sep  2 11:18:24 2014 CEST using RSA key ID 32F8119D
gpg: requesting key 32F8119D from hkp server keys.gnupg.net
gpg: key 54265E8C: public key "Simon Josefsson <simon@josefsson.org>" imported
gpg: 3 marginal(s) needed, 1 complete(s) needed, PGP trust model
gpg: depth: 0  valid:   1  signed:   0  trust: 0-, 0q, 0n, 0m, 0f, 1u
gpg: next trustdb check due at 2019-08-28
gpg: Total number processed: 1
gpg:               imported: 1  (RSA: 1)
gpg: Good signature from "Simon Josefsson <simon@josefsson.org>"
gpg:                 aka "Simon Josefsson <simon@yubico.com>"
gpg: WARNING: This key is not certified with a trusted signature!
gpg:          There is no indication that the signature belongs to the owner.
Primary key fingerprint: 9AA9 BDB1 1BB1 B99A 2128  5A33 0664 A769 5426 5E8C
     Subkey fingerprint: 9941 5CE1 905D 0E55 A9F8  8026 860B 7FBB 32F8 119D

Ok. This shows that the file in question was signed (validly) by someone at Yubico, so it seems.

The cert itself (some_cert.pem) is self-signed so openssl has to be told to trust it: "verify" checks the chain of certificates but here the chain ends right away: the cert signs itself. In this case you want to check the signature (but this says nothing about the origin of the cert, anyone can make a self-signed cert with Yubico in the name!), so we can do

openssl verify -trusted some_cert.pem -check_ss_sig some_cert.pem

Which indeed says OK (it says to check the last (here only) link, the self-signed one, and to explicitly trust the signer; normally there is a directory of trusted certs that openssl knows about or needs to be told about in a command line argument.).

To inspect the cert (that you now trust the origin of, due to it being signed by gpg etc.) and checked the signature of, e.g. do

openssl x509 -in some_cert.pem -noout -text

which outputs all the fields including the serial, which was also in the signed text file. So now you see that all is consistent in itself. But you have to  believe the gpg key (from a key server) and the fact that the file is hosted on the site etc. The gpg key is untrusted according to my gpg install...

Hope this helps.


Security equivalence proofs for breaking RSA

The summary in the Rivest-Kaliski paper does indicate that two specific problems are equivalent to the RSA problem itself.

Due to the algebraic properties of the field $Z_n$, if there exists any small fraction of weak cipher texts (i.e. a particular subset of cipher texts $C$ for which finding the solution $M$ to $C = M^e \pmod N$ is easy), then the RSA Problem is at most as hard as the running time of the adversarial procedure for decrypting the weak cipher texts times a polynomial factor. IOW: The RSA Problem guarantees that all cipher texts are equally hard to invert.
A similar argument applies to each individual bit of a RSA cipher text. If an adversary has a non trivial advantage to determine any bit of a RSA plain text $M$ given a RSA cipher text $C$, then all bits of $M$ are equally easy to determine.


What does it mean the security parameter for a FHE scheme?

What does this parameter signify ?

It's a tweakable parameter that varies (typically) the sizes of various objects in the cipher, and while any non-silly value will work (e.g. encrypt and decrypt properly), it does have an influence on the security of the system (typically, how hard of a 'hard problem' the system relies on).

  Is something that applies only to FHE schemes and puts them on hierarchy of security ?

Actually, it's fairly common for public key systems to have such a parameter; it's not limited to FHE systems.

  How does this parameter compare to classical schemes, like RSA or AES ?

Actually, RSA does have a 'security parameter'; it's the modulus size.  When you generate an RSA keypair, you select the size of the modulus; that's your security parameter.  Now, we typically don't call that a security parameter, however I believe that's for mostly historic reasons; RSA predates much of modern nomenclature, and so uses its own terminology.

As for AES, no, it doesn't - AES comes in three flavors (128 bit keys, 192 bit keys, 256 bit keys), and those are the only variations you are allowed.

Symmetric ciphers, in generally, usually don't have security parameters; I suspect that's because they're not usually based on preexisting 'hard problems' (and so don't need to choose the size of hard problem to rely on).


Well, yes, it does matter; however the terminology 'CBC-MAC' does not specify which.

CBC-MAC is a generic construction that takes an arbitrary block cipher, and turns it into an object that acts like a MAC for fixed length messages (much like CBC mode is a generic construction that takes an arbitrary block cipher, and turns it into a object that encrypts variable length messages).  And, just like "CBC" isn't necessarily used with a specific block cipher, neither is CBC-MAC.

Note: CBC-MAC has issues if you try to use it with variable length messages; CMAC and XCBC are two modes similar to CBC-MAC that avoid this problem.


Does the exact distribution of padding bytes in PKCSv1.5 type 1 matter?

In practice this should be okay. The reason the padding needs to be random is that if the padding can be guessed then the attacker can start encrypting candidate plaintexts (correctly formatted with the padding) under the public key and observe if the output matches the target ciphertext. Of course if the attacker finds a match then they have recovered the plaintext.

If the padding is 11 bytes of purely random padding that can take any value in $[1, 255]$ this means the attacker will have to do $255^{11} \approx 2^{88}$ encryptions for every candidate plaintext they want to check, which is clearly computationally intractable.

By sampling in the range $[0, 255]$ and replacing $\tt{0x00}$ with $\tt{0x01}$ you still have $255^{11}$ possible paddings but there are now some bytes that are more likely to occur than others (e.g. the first byte is more likely to be $\tt{0x01}$ than $\tt{0x02}$) so the attacker could optimize the order in which they check encryptions of padding / plaintext combinations.

If you are deriving padding bytes via a LCRNG this can lead to much worse results since there are ways to predict the output of a LCRNG. This in turn would reveal the padding to the attacker and instead of $255^{11}$ guesses per candidate plaintext they would only need $1$. In a sense when the padding is known the scheme degenerates to textbook RSA, and as such carries with it the same issues.


Private set supporting adding elements and proving elements exist

If we put in the set $H(x||r)$ instead of x where $r$ is a large enough random value (w.l.o.g assume each x is in the same length). Then, each player can add values without revealing it and the same item can be inserted by different players without knowing it (a collision might happen with negligible probability).
Then with access of the third player, one can prove that the value is indeed in that group.


What is the importance of adding round key in AES

The round key is derived from the key and adding it is what makes the algorithm a block cipher (AKA: a keyed permutation) rather than just a permutation.

In the image below you can see a typical block cipher. If the round key were not added in any round then the block cipher output would not depend on the key at all and it would be an unkeyed permutation.

as far as adding the round key each round rather than just at the start and end that's a design choice which improves security. xor-encrypt-xor can be used to easily tweak a block cipher and the basic principle of xor-permute-xor can be used with a strong pseudo-random permutation to construct a block cipher. AES, if round keys were added only at the first and last round, would look something like that.

The key schedule and the round keys added each round are a design choice which positions a lot of messy and difficult operations in such a way that they only have to be computed once for every key. When encrypting a lot of data with a single key, key setup is done once. When brute forcing a key, key setup must be done for every key tried. This translates over to cryptanalysis too.

image credit:Permutation-based encryption, authentication and authenticated encryption


Is prime regeneration necessary for every new session using a Diffie-Hellman key exchange?

How long are parameters used for?

Usually $g$ and $p$ are kept static for a very long time indeed. In fact, the values to use are actually written in to standards. See here for an example. Those were values standardised ten years ago.

So the answer is basically decades.

The impossibility of brute force

Let's suppose that I as an attacker decide I'm going to compute $g^{x} \mod p$. I start at 1 and work up to $p-1$ and start logging them in a table.

There are two problems here. One is there is not enough matter in the universe to store the number of items in that table. The second is that there is not enough time between now and the heat death of the universe to generate it either.

This is a simple consequence of the size of the primes involved.

What about collisions?

Suppose you have access to PRISM and you can see every Diffe-Helman key exchange in the world. Suppose I log every exchanged value in the hope that one specific exchange is repeated.

You're going to need approximately the square root of $p$ invocations to get a probability of approximately 50% that the item already exits in the list. The square root of $p$ is still so big that there simply isn't enough time, energy or matter in the universe to make that attack work.

Even with that table, you still need both exchanged DH parameters to be in there, along with any ciphertext from both sessions, if you wish to have a shot at recovering the plain-text.

Worse, this doesn't even mention that a collision might not even help you. If the cipher used after the exchange uses an additional initialization vector or nonce input (and this one is not simply derived from the exchanged secret, i.e. likely different), then the fact that two sessions shared the same key doesn't help you.

It's important to note here that unlike the attack above where you knew each $x$ for every $g^{x}$, in this attack you still don't know the $x$. All you have is $g^x$. I sensed a bit of confusion on this point in your question.

How are these values actually attacked?

There are more efficient ways to solve the discrete logarithm problem. Wikipedia gives a nice overview of the problem and some algorithms that solve it.

The parameters we choose in cryptography are large enough so that solving the problem is infeasible in any reasonable amount of time.


What's a proper window size in RSA exponentiation?

Window Size (W) for many practical implementation of RSA Algorithm (like OpenSSL) is related to key length.for example in openSSL library for insecure 80 bits key, W is 4 or for insecure 320 bits key , W is 5 and for 1024 or 2048 bits key (length), W is 6.

note:Maximum of Window size in openSSL Library is "6"


Question about OpenSSL testing for FIPS 186-4 and using BN_generate_prime_ex

I believe I have answered my own question.  It appears that OpenSSL uses FIPS 186-4 Appendix B.3.3 to produce its primes instead of Appendix B.3.6.  The FIPS algorithms were using Appendix B.3.6 which is why I was out in left field.

Appendix B.3.3 does not use the Xp1, Xp2, Xp, Xq1, Xq2, and Xq values to produce the primes p and q.

I've started writing a test tool from scratch that isn't linked to the FIPS code instead of updating fips_rsagtest.c which just didn't want to work anyways (had issues getting the RBG to work in it).


How do I produce a stream of secure random numbers from AES-Counter mode?

You can get up to around $2^{64}$ random bits from counter mode (before you hit the birthday bound due to the lack of a collision), simply by running it as is. If you've got a full implementation of counter mode, the plaintext can be anything you like, because the stream (ie the output of the $E_k(ctr)$ calls), should appear uniformly sampled from $2^{128}$.


What is the risk of storing an MD5 (or similar) hash of a decrypted file alongside the encrypted version of the same file.

Note that MD5 is not considered secure anymore, especially with regards to hashing or signing files. Please consider SHA-2 or SHA-3 for your hashing needs.

Otherwise, you're answering yourself below.

  Obviously if someone were to attempt a brute force attack against the file having the hash would provide an end condition for the attack.

Indeed, and that's the main problem.

  Does providing the hash make reversing the encryption easier in some other way?

No, because the hash - even MD5 - is not reversible, so it doesn't leak any other information. Cryptographically secure hashes are one way functions. You can only brute force them.

Note that storing a hash in the same location only provides protection against errors. An attacker may e.g. brute force the plaintext, change a single bit in by e.g. changing the CTR-encrypted ciphertext and recalculate the hash.

Storing a signature over the plaintext data makes a whole lot more sense. Or, if you want to always store the files encrypted and do not want to leak information, store a signature over ciphertext.


Construction of a MAC with decryption mode of a block cipher

A block cipher is a (strong) pseudorandom permutation. As such, it makes no difference if you compute it in the forward or in the backward direction. Thus, you can use AES in decryption mode and it has exactly the same security as AES in encryption mode, as a block cipher. Therefore, you can do CBC-MAC with AES decryption and you are fine.

Two remarks:

Make sure you use an independent key for the CBC-MAC (and not the same as the encryption), and
You should use CMAC and not straight CBC-MAC.


Why use HKDF for key derivation even it's not time demanding?

HKDF is not used to generate a secret key from a public input or a low-entropy password. It's used to derive a key from some secret input (e.g., a DH result) with high entropy.


Do certificates need to be stored as encrypted?

What is not so obvious is if the certificates used to verify a TLS connection should be stored as encrypted to. It is likely that the root level certificates will be self signed and have no chain back to a verified root CA.

As DannyNiu stated, there is no issue if someone were able to read the certificates; those are public information, and allowing an adversary to read them is not an issue.
However, there is a potential concern - what if an adversary can overwrite them?  After all, an adversary who can do that could insert his own root certificate, and then establish a TLS connection (based on the root certificate he picked).  This may or may not be a concern for you (can the adversary modify the flash, and then perform a negotiation?); if it is, one approach to prevent this would be to integrity check the certificate.  That is, you would pick a random key, and put that into the internal flash memory; you would use that key to compute a MAC of your certificate; that generates a moderate sized (perhaps 32 byte) string, and write that string alongside the certificate in your external flash.  Then, when it comes time to use the certificate, you would again compute the MAC of that on-flash certificate using the key, and check to see if the 32 byte string you computed was the same as the string that's stored in memory.
An attacker who tries to replace the certificate with his own is unable to compute the 32 byte string (because that depends on the key you have in secure storage); hence any attempt at modification will be detected.


Why do key fobs/garage doors openers use rolling codes instead of PGP or SSL encryption?

I can think of several issues with using PGP or TLS:

Both PGP and TLS require certificate management (unless password based), it would be tricky to get a PKI going for this;
PGP and TLS are overkill for key fobs / garage doors and would put unnecessary strain on the choice of processor and battery;
PGP and TLS require access to a secure random number generator, which is also pretty expensive to put in a key fob.
The TLS handshake requires two way communication;
Both TLS and GPG require intricate implementation of the message protocol (stuff you can do without for a door opener).

Even from a technical standpoint TLS is overkill; you're really just interested in authenticating a command that cannot be replayed. This explains the choice of a rolling code I guess.

Those are the technical reasons. I guess most of the manufacturers aren't that IT savvy either. They might not even know about PGP or TLS. They're more likely to be interested in motor & hinge design and picking the right color for your door.

That said, there's likely some kind of home automation that can

open a door and
uses some kind of transport protocol or message authentication.

I doubt if these two "heavy weight" protocols are used towards the door though.


There are a couple of definitions in the literature that each aim to capture an aspect of the degree $d$ to which a system of polynomial equations must be expanded before linear algebra on its Macaulay matrix will yield a solution. Some of them are confusingly referred to as the degree of regularity, despite being different things. I will do my best to avoid this term and call them by something else.

Index of Regularity. The index of regularity is defined using the Hilbert polynomial and sequence of an ideal $\mathcal{I}$ [1]. Denote the set of polynomials in $\mathcal{I}$ of degree $s$ or lower as $\mathcal{I}_{\leq s}$ and the same for $\mathbb{F}_q[\mathbf{x}]_{\leq s}$. The Hilbert function $HF_\mathcal{I} : \mathbb{N} \rightarrow \mathbb{N}$ of an ideal $\mathcal{I}$ is defined as $HF_\mathcal{I}(s) = \mathsf{dim} \, \mathbb{F}_q[\mathbf{x}]_{\leq s} / \mathcal{I}_{\leq s}$ and it follows immediately that $HF_\mathcal{I}(s) = \mathsf{dim} \, \mathbb{F}_q[\mathbf{x}]_{\leq s} - \mathsf{dim} \, \mathcal{I}_{\leq s}$. For sufficiently large $s$, the Hilbert function of $\mathcal{I}$ is identical to a polynomial $HP_\mathcal{I}(s) = \sum_{i=0}^d b_i \binom{s}{d-i}$ for some $b_i \in \mathbb{Z}$ and $b_0 \in \mathbb{N} \backslash \{0\}$. This polynomial is called the Hilbert polynomial. The index of regularity is the smallest $s_0$ such that for all $s \geq s_0$, $HF_\mathcal{I}(s) = HP_\mathcal{I}(s)$; this value is also called the Hilbert regularity [2].

Degree of Semi-Regularity.
A sequence of polynomials $(p_1(\mathbf{x}), \ldots, p_m(\mathbf{x}))$ is regular if $g \cdot p_i \in \langle p_1, \ldots, p_{i-1}\rangle \implies g \in \langle p_1, \ldots, p_{i-1}\rangle$. Regular systems capture the worst case of polynomial systems.
The Hilbert series of an ideal $\mathcal{I}$ is defined as the formal power series $HS_\mathcal{I}(t) = \sum_{s=0}^\infty HF_\mathcal{I}(s) t^s$.The Hilbert series of the ideal $\mathcal{I} = \langle p_1, \ldots, p_m\rangle$ spanned by a regular sequence of homogeneous polynomials $(p_1, \ldots, p_m)$ is given by $HS_\mathcal{I}(t) = \frac{\prod_{j=1}^m (1-t^{\mathsf{deg} \, p_j})}{(1-t)^n}$. It is known [3] that the degree of the highest-degree elements in a degree reverse lexicographical Gröbner basis is bounded (up to a linear change of variables) by the Macaulay bound: $\sum_{i=1}^m (\mathsf{deg}(p_i) - 1) + 1$. This bound can be used to estimate the complexity of Gröbner basis algorithms for regular (i.e., worst-case) systems. If $m = n$, the sequence is regular if and only if $HS_\mathcal{I}$ is a polynomial [4]. This means that for some bound $s_0$ and all $s \geq s_0$, $HF_\mathcal{I}(s) = 0$ and so $HP_\mathcal{I}(s) = 0$. In this case, $s_0 = \mathsf{deg}(HS_\mathcal{I}) + 1$ is exactly the index of regularity.

Unfortunately, regular systems do not exist when $m$ is larger than $n$. In this case, one must assume the ideal has a zero-dimensional variety, and given that this is the case one can adapt the definition of regular sequences as follows. A sequence of polynomials $(p_1, \ldots, p_m)$ is $d$-regular if for all $g \in \mathbb{F}_q[\mathbf{x}]$ with $\mathsf{deg}(g) < d - \mathsf{deg}(p_i)$, $g \cdot p_i \in \langle p_1, \ldots, p_{i-1} \rangle \implies g \in \langle p_1, \ldots, p_{i-1} \rangle$. The sequence $(p_1, \ldots, p_m)$ is semi-regular if and only if it is $s_0$-regular, where $s_0$ is the index of regularity [3]. For a semi-regular system the Hilbert series $HS_\mathcal{I}(t)$ will not be a polynomial but it can be written as a formal power series (i.e. a polynomial with an unlimited number of terms). In this case $s_0$ is the degree of the first term in this formal power series whose coefficient is zero or negative. I like to call this the degree of semi-regularity but it is in fact identical to the degree of regularity assuming the system is semi-regular. Treating random systems of quadratic polynomial equations as semi-regular seems to be empirically justified, but there is no proof that random systems are indeed semi-regular.

First Fall Degree. The first fall degree was first introduced by Dubois and Gama [5] in an attempt to explain why HFE systems seem easier to solve than random systems of the same dimensions. It recycles the intuition that the ``degree of regularity'' should be the lowest degree at which the system starts behaving irregularly, which in interpreted in this case as exhibiting a non-trivial combination of polynomials resulting in a degree fall.

Specifically, let $R = \mathbb{F}[x_1, \ldots, x_n] / \langle x_1^q-x_1, \ldots, x_n^q - x_n\rangle$, i.e., the ring of functions from $\mathbb{F}_q^n$ to $\mathbb{F}_q$. (In fact, we might as well use $R = \mathbb{F}_q[x_1, \ldots, x_n] / \langle x_1^q, \ldots, x_n^q\rangle$ because we only care about the functions' polynomials' homogeneous highest-degree part.) Consider the algebraic combination map $\psi : R \rightarrow \mathbb{F}_q[x_1, \ldots, x_n]$ defined by $(c_1, \ldots, c_m) \mapsto \sum_{i=1}^m c_i \cdot p_i$. We are interested in non-trivial elements of $R$ that are sent to $0$ under $\psi$; these represent combinations (with polynomials as coefficients) of the polynomials $p_1, \ldots, p_m$ that disappear --- a special word for this type of cancellation is syzygy, although that term applies more generally to algebraic combinations that result in any kind of cancellation and not necessarily mapping to zero. In fact, the syzygies we are interested in do not have to map to zero per se; it is enough for the image of $\psi$ to have a lower degree than $\mathsf{max}_i \, \mathsf{deg}(p_i) + \mathsf{max}_i \, \mathsf{deg}(c_i)$. Moreover, we are interested in syzygies of as low degree as possible. For simplicity, let $\mathsf{deg}(p_1) = \cdots = \mathsf{deg}(p_m) = 2$. Let $R_k$ be the subset of $R$ of homogeneous polynomials of degree $k$ and define $\psi_k : R_k \rightarrow \mathbb{F}_q[x_1, \ldots, x_n]$ accordingly as sending $(c_1, \ldots, c_m) \mapsto \sum_{i=1}^m c_i \cdot p_i$ and in this case the kernel of $\psi_k$ consists of exactly the syzygies we are interested in. Define the space of trivial syzygies $T_k(p_1, \ldots, p_m) \subset R$ as spanned by all basis elements of the form

$c \cdot (0, \ldots, 0, p_j, 0, \ldots, 0, p_i, 0, \ldots, 0)$ where the $p_j$ is in the $i$th position and the $p_i$ is in the $j$th position, and where $c \in R_{k-2}$;
$c \cdot (0, \ldots, 0, p_i^{q-1} - 1, 0, \ldots, 0)$ where the $p_i$ is in the $i$th position and where $c \in R_{k-2(q-1)}$.

The reason why $T_k$ is identifiable with trivial syzygies is that its basis elements can be derived without looking at the contents of the $p_i$; they can be described as functions of $p_i$ without replacing the symbol $p_i$ by the polynomial it represents. This leaves the space of non-trivial syzygies which can be characterized as the quotient space $\mathsf{ker} \, \psi_k / T_k$. Phrased crudely, this is the space of syzygies that do not boil down to clever combinations of trivial syzygies.

The first fall degree of the list of polynomials $p_1, \ldots, p_m$ is defined as $\mathsf{min}_k \{ \mathsf{ker} \, \psi_{k-2}(p_1, \ldots, p_m) / T_{k-2}(p_1, \ldots, p_m) \neq \{0\} \}$. Phrased crudely, this is the lowest degree at which algebraic combinations of the polynomials results in non-trivial degree falls. The first fall degree is useful because it is more easily bounded. See Ding et al. [7][8][9] for a series of upper bounds on the first fall degree of multivariate quadratic systems derived from the HFE construction. However, these bounds are not tight, especially for large field order $q$. While the index of regularity is always at least as high as the first fall degree, it can be higher. So a low first fall degree does not necessarily imply an easy-to-solve system although it definitely indicates that something fishy is going on.

Solving Degree. The solving degree was introduced by Ding and Schmidt [6] as a contrasting notion to the first fall degree. It is defined as the degree of the polynomials in the largest extended Macaulay matrix involved in the algebraic system solver. Linear algebra on this matrix dominates the solver's complexity, and so this degree is a good characterizer of this complexity. However, it is much more difficult to bound. Ding and Schmidt show experimentally that the solving degree lies close to the first fall degree. Nevertheless, it is possible to construct artificial systems where the difference is large.

[1]: David Cox and John Little and Donald O'Shea. Ideals, Varieties, and Algorithms. 2nd edition. Ch.9 Sect.3.

[2]: Wikipedia. https://en.wikipedia.org/wiki/Hilbert_series_and_Hilbert_polynomial

[3]: Magali Bardet and Jean-Charles Faugère and Bruno Salvy. On the complexity of Gröbner basis computation of semi-r egular overdetermined algebraic equations. https://www-polsys.lip6.fr/~jcf/Papers/43BF.pdf

[4]: Magali Bardet and Jean-Charles Faugère and Bruno Salvy. On the Complexity of the F5 Gröbner basis Algorithm. https://arxiv.org/pdf/1312.1655.pdf

[5]. Vivien Dubois and Nicolas Gama. The Degree of Regularity of HFE Systems. https://link.springer.com/chapter/10.1007/978-3-642-17373-8_32

[6]: Jintai Ding and Dieter Schmidt. Solving Degree and Degree of Regularity for Polynomial Systems over a Finite Fields. https://link.springer.com/chapter/10.1007/978-3-642-42001-6_4

[7]: Jintai Ding and Timothy Hodges. Inverting HFE Systems Is Quasi-Polynomial for All Fields. https://link.springer.com/chapter/10.1007/978-3-642-22792-9_41

[8]: Jintai Ding and Thorsten Kleinjung. Degree of regularity for HFE-. https://eprint.iacr.org/2011/570

[9]: Jintai Ding and Bo-Yin Yang. Degree of Regularity for HFEv and HFEv-. https://link.springer.com/chapter/10.1007/978-3-642-38616-9_4


The entire premise of modern ciphers is that they're indistinguishable from random by a computationally-bound adversary. If you believe the assertion that a modern cipher is secure, then it follows that you believe you cannot reliably distinguish it from randomness.

If you share a secret key with your clients, what you can do is verify a MAC over the ciphertext to ensure that it was generated by a client who has the same secret key as you (which is a good idea regardless, and the basis behind AEAD modes like GCM).

Your second point doesn't make much sense in the context of modern ciphers. About the only thing you can do is subject ciphertexts to randomness tests, but those results aren't of much use without extremely large amounts of input (on the order of gigabytes).

It's unclear though what exactly you're hoping to gain with such tools.


How often to reseed the NIST CTR_DRBG with AES256_CTR

As usual, the answer is: it depends.

It mainly depends on two factors:

Do you have a source of entropy and how good is it?
What's your environment and your threat model?

The benefit of re-seeding your DRBG should be clear: If the state of your DRBG gets compromised at any point, an attacker can re-compute all the outputs of the DRBG following up until the last reseed which limits the damage in case of an successful attack.

Now for the question you may have: Can a re-seed hurt security? No, it can't because information from the last DRBG state is included, transferring initial entropy into the new state and adding new entropy.

So for the first point: Assume you have a good RNG, then re-seeding as often as possible is a good idea that highly limits the risk associated with a state-compromise. If you however have a bad RNG or none at all, you could still try to re-seed, but then it's also a question of the effort involved in doing the re-seed and whether this effort is worth the minimal gain.

Now for the second point: The threat model. This really is your answer to the question: "what access to my device(s) does the attacker have?". If you have secure hardware for the DRBG and an attacker can at most get software-level access or only have a remote view, chances are that a state-compromise won't happen. If the attacker however can get hands-on with the device and try all their best in extracting the state (as you'd be able to with a stolen smart card for example), then advanced attacks like DPA need consideration. If you're sure that such advanced attacks aren't realistic (because breaking the RNG wouldn't outweigh the cost of developing and deploying these attacks), then you can go without a re-seed. If an attacker has a motivation to try really hard to get into the device they'll probably try all those attacks and depending on how good the secured hardware is, chances are they'll succeed.


Could scrypt salts contribute to entropy if passwords & salts are only stored in human memory?

If you use a potentially guessable username as the salt, you should add a global salt that no other services or programs will be likely to use for scrypt. For example, a long random number. That ensures that attacking another user database does not simultaneously allow attacking your users' hashes.

However, if two users are allowed to choose the same username within your userbase, adding global salt is not enough. You need something unique per user to use as salt instead of or in addition to the username. If random numbers really are not possible, consider using email addresses, which should be unique. (Those naturally add no entropy.)


Mersenne Twister (as an example) is a fast random number generator, and has good properties (long period, good distribution) for most applications of random numbers (like statistics, simulations, modelling).

For cryptographic applications, we need more: We need a cryptographically secure random number generator. Such a function (implemented by an algorithm) has the property that an attacker has no means of to distinguishing the output from a pure random bit sequence, if he does not know the seed.

Such CSPRNGs (cryptographically secure random number generators) can be build from several other cryptographic primitives:

cryptographic hash functions
block ciphers
stream ciphers

All these primitives effectively need the properties of a "normal" PRNG, thus they are usable as such.

On the other hand, the algorithms implementing such primitives are normally a lot slower than "normal" PRNG - thus don't use iterated SHA-1 when Mersenne Twister is enough for your needs.


Why are polynomials chosen with coefficients in $GF(2^{8})$ in Section 4.3 of NIST FIPS 197 for implementing AES?

The irreducible polynomial you showed above will create a polynomial field. (0x11b=283=100011011).
-now last nearest degree of 2 is ${2^8=256}$ hence all the operation of a field within the range of ${0,1..,255}$,

It is a Byte operation because the range ${0,1,2,...,255}$ can be represented as a byte(8 bit) and the field operation are performed and reduced to modulo ${x^8+x^4+x^3+x+1}$
Here, The statement ${\{0,1\}^8}$ means it can be a binary number of 8 bits.
But in case of normal polynomial the coefficient can be from set N,Z,R,C. which is not the case in AES.


What does public-coin mean in interactive proof and zero-knowledge?

In this setting, can we regard the verifier as an honest verifier, since he always replies with a random message (rather than a message depends on previous messages)?

No. In a public coin protocol the honest verifier will always send random coins as their messages.
A malicious verifier is under no obligation to do so.
They can choose whichever message makes the simulator's life the hardest.

Imagine some public coin zero-knowledge proof protocol where the length of verifier messages is at least linear in the security parameter. We can modify this protocol so that the prover does something stupid (say send the witness) in response to a very small number (say just one) of possible verifier messages.

In the honest verifier case this is not an issue because the case only occurs with negligible probability. So the original simulator still works for this modified protocol. I.e., the protocol remains HVZK.
But a malicious verifier can just always choose that one bad message, making simulation impossible without being able to efficiently find witnesses.

So there's no contradiction. [GK'91] only applies to ZK proofs, whereas Schnorr is only an HVZK proof.

Additionally one might note, the language you call $\mathsf{DLOG}$ is not in general a hard language. For any cyclic group $(\mathbb{G},\cdot)$¹ of order $q$ generated by $g \in \mathbb{G}$, the language for which Schnorr is an HVZK proof can be defined as follows:

$$\mathsf{DLOG_{\mathbb{G}}}=\{A\in\mathbb{G}\mid \exists x \in \mathbb{Z}_q: g^x=A\}$$

However, since the group is generated by $g$, this is just a very convoluted way of saying $$\mathsf{DLOG_{\mathbb{G}}}=\mathbb{G}.$$

Thus, if group membership can be decided efficiently for $\mathbb{G}$, then this language is not actually a hard language and it would actually hold that $\mathsf{DLOG_{\mathbb{G}}} \in \mathsf{BPP}$.
In fact in many cases, it's actually true that $\mathsf{DLOG_{\mathbb{G}}} \in \mathsf{P}$. For example in the case of an elliptic curve over a finite field it is trivial to deterministically decide whether a given point $P$ is on the curve or not by just evaluating the curve equation. Similarly in the safe-prime setting it is easy to check group membership.

The interesting part of Schnorr is not usually that it proves the existence of a discrete log, it's that it's also a proof of knowledge.

¹ Written in multiplicative notation as any sane person would.


How to calculate the probability to get two random numbers equal from the same generator

Well, to start with, if you run two DRBGs with the same seed, the probability of getting the same values from both of them is obviously 100%.

Assuming different seeds, the probability of getting any specific n-bit string is $1/2^n$, so getting the same 10-byte value twice in a row would happen with probability $\frac{1}{2^{10*8}} \approx 1/(1.2089*10^{24})$, assuming a perfectly random (uniformly distributed) DRBG.

If you just want to run the DRBG a number of times until any two results collide, we get into the area of the birthday paradox. I don't have the result for 80 bits (10 byte) at hand, but for 64 bits, to have a collision with the chance of 50% you would have to try $5.1 * 10^9$ invocations. For 128 bit, that grows to $2.2*10^{19}$ (results from this table). This will get lower if your DRBG is not perfectly random, but biased towards certain values.

As for the time this would take, it depends on the performance of the DRBG and your machine, but I think "quite a while" would be a good first guess. If you assume 1 ms for each invocation (including comparison), 64 bit would take around 60 days, while 128 bit would already take around $697\,615\,423$ years (for a chance of 50% for a collision). Yours would be somewhere in between.

Edit: If you want to hit a specific value, you will have the same chance of $1/2^n$ on every invocation. That's a Bernoulli process, and it's a bit of a headache.

Say you want to know what your chance is to hit one matching result in n tries, and your probability of success for each try is $p$ (that would be the $1/(1.2089*10^{24})$ from above). You would calculate $1-((1-p)^{n})$. The inner $(1-p)^n$ basically gives you the probability that you will not hit it on any of your $n$ tries (i.e. you will fail every time). You invert that by taking 1 minus that result and you get the probability of finding at least one match. You can use that to estimate how many attempts it would take.

There probably is a way to estimate the number of attempts to get to a certain probability of success, but I can't find it right now. If anyone knows, feel free to edit this answer.


CBC is a block cipher mode of operation, not a cipher. It can work basically with any block cipher - the choice of the block cipher itself is independent (to a large extent) from the choice of the mode of operation.

Examples of well known block ciphers include AES, DES, TripleDES, Serpent, Blowfish etc.

The title of your question, however, asks about decrypting AES using CBC mode operation. In which case you should be using AES, $P_t = \operatorname{AES-128-DEC}_k(C_t) \operatorname{XOR} C_{t-1}$. AES decryption is available in many crypto libraries (for example libtomcrypt, Crypto++, openssl, Java Cryptography Extensions, Python Cryptography Toolkit), and you can even use online AES "calculators" such as this one.


Should I use the first or last bits from a SHA-256 hash?

If taking the first or last bits of a SHA-256 output made any difference, it would be viewed as a serious blow against the security of SHA-256. Right now, no such weakness is known in SHA-256. So, as far as we know, you can use whatever bits you want.

If you need a more "administrative" answer, have a look at SHA-224 (also specified in FIPS 180-3). This is a hash function with a 224-bit output, which NIST defined in order to "match" (administratively speaking) the proclaimed 112-bit security of 3DES. They defined SHA-224 by taking SHA-256, changing the conventional IV, and truncating the output. For the truncation, they took the first 224 bits. If it is good for NIST then it is good for you: take the first bits.