Does a Finite Field of 36 elements exist?

Finite fields only exist for an order $q$ if $q$ is prime or a power of a prime (http://mathworld.wolfram.com/FiniteField.html). Since 36 is neither a prime itself, nor it is a power of a prime ($36 = 2^3 * 3^2$), there is no finite field with 36 elements.


This technique is known as Ciphertext stealing. Ciphertext stealing avoids padding, but only works if the total message size is bigger than one block.

Ciphertext stealing secure in principle, but as @mikeazo already pointed out using ECB and using 64 bit block ciphers is generally a bad idea.
There are fancier length preserving encryption schemes. FFX mode is one example.
I strongly recommend adding a nonce/IV and a MAC. While these increase the size of the message, the security implications of not having them can be severe.

In particular the MAC prevents attacks that modify the ciphertext and watch the reaction of the decrypted and nonces/IVs ensure that encrypting the message twice doesn't leak that it's the same.


Unique assignment of X.509 certificate to each client

In a typical X.509 PKI implementation, the CA is somewhat heavyweight. Far more than just a special CA certification, running a CA typically implies running a web service to service certificate requests, perhaps an OCSP responder, publishing CRLs regularly, perhaps an SCEP server... This heavyweight notion works well for large enterprises, but somewhat less well for small deployments like your own. Suck it up, though, because there really isn't a good solution for lightweight deployments.

What I'm trying to say is that yes, the "correct" solution in this case is for the CA to check to make sure it hasn't issued a certificate to that user before issuing a new one. This is a fairly annoying extra requirement for a small deployment, but an utterly trivial task next to all the other crazy things a "standard" X.509 deployment is expected to do. I feel your pain, and I know it's not very elegant, but the easiest solution in this case is to just keep a list of all the ID codes served so far and fail if one is resubmitted.

In an ideal world, you'd be able to map the unique identifier you're talking about to a unique key, so re-issues wouldn't be a problem. However, that's not doable with X.509.

PS: I'm assuming here that you in fact want to do what the question title says: assign only a single certificate to each user. If, instead, you only need to prevent double-voting during the election, you could just record the subject unique ID of everyone who's voted already, which would make having more than one certificate for the same unique ID useless. Changing the logic of your voting application is probably easier than changing the logic of whatever CA service issues the certificates.


Why does NaCL have different keys for signing and encryption?

The encryption part of NaCl is older. I think NaCl itself still doesn't have official signature support.

NaCl's box uses montgomery form public keys together with the montgomery ladder. This ladder only returns the x-coordinate of the result and thus is not compatible with most signature algorithms.

Ed25519 on the other hand uses (twisted) edwards form, with keys in the same format.

But it is possible to convert the keys between these formats (the missing sign of the second coordinate can cause some complications when converting from montgomery). There are several encryption products which use these conversions to share a key.
Using the same key for multiple purposes requires the algorithms to be jointly secure. Some people are not comfortable with that. Tanja Lange voiced some vague doubts at 30c3.

See Using same keypair for Diffie-Hellman and signing


Yes this seems secure.

Note that for CTR we use a nonce not an IV but it has similar role. Depending on your operational requirements there may be simpler secure methods. The key question is how the shared secret is managed, of course.


Security Consideration on The Use of Random Number in Digital Signature

You should in general never use randomness from one cryptosystem in another cryptosystem. Bad things can happen.

Note that pseudo-randomness is good enough for cryptography, so generating new randomness is cheap.

Consider the specific example of using signed Diffie-Hellman with Schnorr signatures. Alice chooses a random number $r$, sends $g^r$, and later signs everything using by hashing $g^r$ and some other stuff to $e$ and then computing $z = r - ae$, where $a$ is her long-term secret signing key.

Now suppose the secret signing key is compromised at some point in the future. An adversary that paid attention recorded $g^r$ and the signature $(e,z)$. That adversary now knows $e$, $z$ and $a$, he recovers $r$ and can then recompute the shared Diffie-Hellman secret.

Just don't do it.


It is not impossible, only harder. This is because of RAM. In a GPU, you have a number of cores which can do 32-bit operations. They will run at one operation per cycle and per core, as long as they operate on their respective registers. RAM access, however, is more troublesome. Each group of cores has access to a small amount of shared RAM, and all cores can read and write the GPU main RAM, but there are access restrictions: not all cores can read from or write to RAM simultaneously (constraints are stricter for main RAM).

Now bcrypt is a variant of the Blowfish key scheduling, which is defined over a table (a few kilobytes) which is constantly accessed and modified throughout the algorithm. Due to the size of the table, each core will have to store it in the GPU main RAM, and they will compete for usage of the memory bus. So bcrypt will run -- but not with full parallelism. At any time, most cores will be stalled, waiting for the memory bus to become free. This comes from the type of elementary operation bcrypt consists in, not from the fact that bcrypt is derived from the key schedule of a block cipher.

For SHA-1 or SHA-256, computation entirely consists in 32-bit operations on a handful of registers, so a password cracker will run without doing any memory access at all, and full parallelism is easily achieved (I did it on my GeForce 9800 GTX+, and I got about 98% of the theoretical maximum speed with a straightforward unrolled SHA-1 implementation).

For details on the programming model in CUDA, have a look at the CUDA C Programming Guide. Also, the author of bcrypt now proposes scrypt (edit: actually that's not the same person; the author of scrypt is Colin Percival, while bcrypt has been designed by Niels Provos and David Mazières), which is even heavier on the memory accesses, exactly so that implementation is hard on GPU and FPGA.


Is It Safe to Reuse the Same Salt in Bcrypt Password Hash (Specifically for Chaining Hashes)

I am not aware of any research for this problem and it is difficult to declare anything as safe without a good reason.
Probably that's why everyone holds back with answers.

Suppose, however, the main attack against these BCrypt hashes is a dictionary attack, probably with custom hardware,
I can't see a weakness in any of the solutions. Reusing the salt for different passwords weakens a scheme. That is not the case here.
For other attacks (cache-timing...) this shouldn't matter.

But you sail in unknown waters.


Is this an acceptable way to increase the block size of a block cipher?

The purpose of a mode of operation for a block cipher is to get rid of the size limitation imposed by the block size, so what you're proposing is to use an insecure mode, tweak it to try to hopefully make it secure, and finally build a new block cipher with this... At the cost of 4 AES encryption to achieve diffusion (whereas the MixColumn and ShiftRow operations in AES try to achieve the same diffusion at a much lower cost.) So I'm not convinced by the performance of your block cipher and don't see why it is superior to, say, AES-CBC with a fixed 512 bits size.

Now, what flaw are you possibly missing?

Well, since you are using AES ECB, if your plaintext is for example a repeating block of 128 bits, it will get encrypted into the same AES block by AES ECB, which means that your Shift operation will do nothing, since all of its row will be filled with a repetition of the same byte:

111 <-- shift by 0            = 111
222 <-- shift by 1            = 222
333 <-- shift by 2            = 333
444 <-- shift by 3 (equiv. 0) = 444
555 <-- shift by 4 (equiv. 1) = 555
666 <-- shift by 5 (equiv. 2) = 666
777 <-- shift by 6 (equiv. 0) = 777
888 <-- shift by 7 (equiv. 1) = 888

which means that you'll end up with a block of multiple AES-ECB encryption of the exact same blocks, which will give you interesting patterns in your ciphertext, and leak information, so you do not achieve the ciphertext indistinguishablity one would expect from a secure block cipher.

Which basically means that "No, this is not an acceptable way".

Could you tweak it further to avoid this problem? Most likely, but if you want to build bigger block cipher, you can as well just build a bigger AES and have better performance than stacking multiple AES on top of each other.
Should you? IMHO, no. Stick with secure AES constructs such as CBC, CTR, GCM, etc., or use a secure stream cipher such as ChaCha.


Please help me understand this k-out-of-n oblivious transfer protocol

Recall the ElGamal encryption scheme: The secret key is some random $r \in \mathbb{Z}_q$, the public key is $h := g^r$ , together with the group order $q$ and the generator $g$ of the group $\mathcal{G}$. To encrypt a message $m \in \mathcal{G}$, one chooses a random $s \in \mathbb{Z}_q$ and computes the ciphertext $(c_1, c_2) := (g^s, m \cdot g^{rs})$. To decrypt the ciphertext, one computes $c_2 \cdot (c_1)^{-r} = c_2 \cdot (g^s)^{-r} = m$.
In case of your OT scheme, $g$ and $q$ are assumed to be known and are therefore not part of the public key. Now, instead of sending $g^{r_j}$, the receiver sends $\Gamma(s_j) \cdot g^{r_j}$. When the sender raises this to the power of $s$, this results in $\Gamma(s_j)^s \cdot g^{r_j s}$. Hence, the $d = g^s$ and $b_j = \Gamma(s_j)^s \cdot g^{r_j s}$ sent by the sender correspond to an encryption of $\Gamma(s_j)^{s}$. This is then used by the receiver to obtain $H_{\ell}(\Gamma(s_j)^s)$, which was in turn used to (one-time pad) encrypt the actual message. The trick here is to allow the sender to encrypt $\Gamma(s_j)^s$ without knowing $\Gamma(s_j)$.

Yes, the selection $s_j$ corresponds to the $j$th index the receiver wants to receive.


What practical uses can random hash collisions be put to?

If it is for completely random data you could still make a program that uses the random looking input to make different choices. For instance, you could sign two .jar files in Java, using the SHA-256 hash over the file in the META-INF folder. Then you can use the different files a property to make one choice or the other. Basically you're replacing one of the data blocks in a hash tree or list (which is in turn signed for Java).

Of course, most hash collisions don't work like that. For instance, the MD5 collisions need to be pre-calculated, but they work for normal data + a postfix. Even then, the amount of attacks that can be launched is limited. Faking a signature is such a big attack that the rest is more or less inconsequential.


Actually, those two algorithms are surprisingly close; I'll write both of them up to show how close they are.

They both can be written as a combination of three substeps:

A := Add( B, C )

This takes the two points B and C, and adds them together (I'll be writing things in additive notation; in RSA, with would be a modular multiplication)

A := Double( B )

This takes the point B, and adds it to itself (or, in RSA, a modular squaring)

If (cond) swap( A, B )

This tests a condition on the multiplier (exponent in RSA), and depending on that, either exchanges A and B, or leaves them alone.  Note that if it leaves them alone, it still performs the read and write operations; however when it writes A, it writes A's original value (and not B's value); this allows this operation not to leak any information via the cache.

Note that all these three can be done in constant time, and with constant memory accesses; hence we don't leak any information, even against an attacker who can listen to cache accesses.

Now, both algorithms use temp variables A and B, and I'll call the original point G.  The core of the DoubleAndAdd algorithm can be written as:

A := Double(A)
B := Add(A, G)
if (bit_i_of_multiplier_is_set) Swap(A, B)

(Actually, the swap operation here can be simplified; we don't care if it actually updates B)

The core of the Montgomery Ladder can be written as:

if (bit_i_xor_bit_i_1_is set) Swap(A, B)
A := Add(A, B)
B := Double(B)

There are also differences with how the two algorithms initialize A and B (Montgomery stirs in G by how it initializes A and B), and where they find the final result -- those are relatively minor.

So, given that both algorithms solve the problem of doing a point multiplication in constant time without leaking any information via the cache, how do they compare?

Well, for one, if you look at the Montgomery Ladder, the two operations it does can be done in parallel.  I would be skeptical if it would be a win to give them to two different cores (core synchronization is not cheap); however if you could have them done on a 2-way SIMD (if the add and double operations are sufficiently similar), that may be a win.

On the other hand, if you look at the DoubleAndAdd algorithm, we always add the point G.  Now, with Elliptic Curves and RSA, this doesn't buy us anything, but with Diffie-Hellman, we can pick G to make this operation cheap (say, G=2); that would speed up the first phase of the operation.  Also, in my humble opinion, DoubleAndAdd is a bit less complex than the Montgomery Ladder.

So, bottom line: there isn't actually that big of a difference; there might be some minor implementation differences.


The problem with talking about XMSS private key size is that there is a fairly large number of size/performance trade-offs, and so there's no one answer.

At the minimum, the private key needs to have the value used to generate the WOTS+ private keys ($n$ bits), the $n$ bit public seed, and current leaf index (20, 40 or 60 bits, depending on the parameter set).  In addition, if you follow the recommendations of the RFC, you also have an $n$ bit SK_PRF value (to do randomized hashing), as well as the $n$ bit root (although you could recompute that on the fly if you had to).

If you do this (including the recommendations), this translates to a private key (for $n=32$) of 136 bytes (assuming a parameter set with a hypertree of 60 levels).

On the other hand, if you just did this, this would imply that, with every signature you generated, you would need to reconstruct every XMSS tree involved; that's not cheap.

Now, the obvious thing to do is also include the internal contents of each XMSS tree; this makes things fast, but vastly increases the size of the private key.

As a compromise, you can save a handful of internal Merkle tree elements, and use a tree walking algorithm, such a BDS to generate the next authentication path incrementally (and don't forget, if you're doing XMSS^MT, to start work on building the next Merkle tree while you're traversing this one, if you want to avoid having to build the entire next XMSS tree when you exhaust this one.  There are a number of tree walking algorithms known, with various trade-offs (and tweakable parameters).

In addition, you may also want to include other things in your private key.  For example, if you are interested in detecting fault attacks (where a miscomputation of a lower level XMSS public key causes the next higher WOTS+ signature to sign two different messages over two different signature operations), you may want to store the signature (or public key) of the current lower level tree (or, alternatively, the hash of the signature); that way, either you never actually sign with the same WOTS+ private key twice (or, alternatively, you catch it if a miscompute causes you to generate two different signatures).

All this leads to the fact that there are a number of different trade-offs you can make, and hence, no simple answer to 'how big is the private key is'

You asked for an example using BDS; lets lay out some assumptions:

We'll assume that the private key contains the various central information I listed above, a BDS tree for each Merkle tree in the hierarchy, a place to construct the next Merkle tree (for all Merkle tree levels except the top), and nothing else
We'll use the BDS algorithm with the internal variable $k=2$ (note: the BDS paper stated that the algorithm works only if $H-B$ was even; a simple modification to the algorithm makes it work in all cases).

Then, the central information takes $4n+h$ bits.

And, if we denote $H=h/d$ as the height of each Merkle tree, each BSDS tree (both the current and the next one being constructed; total of $2d-1$) takes up no more than $n(\lfloor 3.5H \rfloor - 4)$ memory (actually, it uses a bit less, however a characterization of how much less is nontrivial).

In addition, each of the active BDS structures (total of $d$ of them) need some auxiliary information to track what's stored in their stacks (we don't need to store auxiliary information for Merkle trees we are in the process of building).  I don't feel up to examining precisely how much memory this takes up; I'll just estimate it as $8H$ bits.

This gives a total of $n(4+(2d+1)(\lfloor 3.5h/d \rfloor - 4)) + 9h$ bits

Different assumptions give different numbers (and could be higher, could be lower...)


Would this still be a valid and comparably secure protocol as Shamir's No-Key protocol?

No, it would not be secure at all.

In this revised protocol, Alice sends a message $M$ to Bob, to do that, she picks a random string $A$, and sends:

$$A \oplus M$$

Bob receives this, picks a random string $B$, and sends:

$$B \oplus (A \oplus M) = A \oplus B \oplus M$$

Alice then xors in her original string $A$, and sends

$$A \oplus (A \oplus B \oplus M) = B \oplus M$$

Now, someone in the middle hearing these three exchanges, if they exclusive or all three, they get:

$$(A \oplus M) \oplus (A \oplus B \oplus M) \oplus (B \oplus M) = M$$


How do you find the inverse degree of a hash function?

Trying to express the inverse of the non-linear Chi fonction of Keccak as a multivariate polynomial of the bits of the state will yield a degree 3 polynomial.

How to derive such inverse is explained in section 6.6.2 of Joan Daemen PhD thesis as stated page 15 of http://keccak.noekeon.org/Keccak-reference-3.0.pdf


How to know when decryption fails in Yao's Garbled Circuits

Your intuition is correct, the encryption is set up to indicate a failed decryption when an incorrect key is used with the ciphertext. A very simple way of doing so can be as follow: when encrypting the message $m$ with the key $K$, encrypt $m||0^{\lambda}$ ($\lambda$ is a security parameter, e.g. 80 or 128). When decrypting a ciphertext, check whether the last $\lambda$ bits are $0$; if this is not the case, decryption failed.

Note that the paper you are reading describes also the point and permute technique, which allows to find out which ciphertext we should decrypt, without having to try them all. This is an important optimization for garbled circuits.


Your core problem is the fact that you only have about 20 bits of entropy at most (assuming users pick fully random 6-digit PINs which most probably won't). 20 bits of entropy also means that it takes an attacker at most 1,000,000 times the amount of work that you invest for verification to find the password, but the attacker can greatly parallelize the password search and he can use stronger, higher-clocked architectures than you are usingb potentially. So just relying on the password hash is really not an option here.

Right now, I see three solutions to your problem:

HMAC the password or the hash, this has the advantage of being very straightforward and being guaranteed to be non-invertible.
Functionally equivalently one can also append a high-entropy secret to the PIN prior to bcrypt hashing (this is called "peppering" and has the drawback of blocking interoperability with the third approach).
Encrypt the password or the hash, this has the advantage that you could in theory with password hashes that allow it, upgrade the parameters without client-login, however if your encryption key gets leaked so gets the encrypted data
Outsource verification to a rate-limiting HSM, this has the advantage, that an attacker cannot possibly try passwords faster than the rate-limit

Your best option really would be to use a rate-limiting HSM which provides HMAC and then HMAC the bcrypt hashes or directly the passwords.

  They are now thinking of encrypting the hashes before storing them to
  add an extra layer of protection.

Yes, this will bring security up from an attacker just having to exfiltrate and break the hash to an attacker having to exfiltrate and break the hash after he exfiltrated the encryption key (which you can prevent, right!?).

  I can't see it hurting and adding the additional hurdle probably won't
  hurt but I've heard of odd interactions between different algorithms
  so don't want to say to do it without someone who knows their stuff
  looking at it.

While in theory there may be odd interaction, the probability of this happening in practice is negligible.


Trustless, Two-Party Random Number Generation

Why should user 1 disclose the resulting random number in addition to disclosing his own seed,

when user 2 can compute the resulting random number from the two seeds?

That might be safe enough, but it's far from secure.

For one thing, each user obtains user obtains proof that the "random number" is only pseudorandom.

For another thing, one would need to hope that the RNG still works well when one half of its

seed is chosen  in a way that adversarially depends on the hash of the other half of its seed.

A simple, somewhat good way is the following:
User 1 gives user 2 a commitment to a random string whose length is equal to the RNG's seed length.

User 2 gives user 1 a random string whose length is equal to the RNG's seed length.

User 1 sends User 2 the opening of the commitment, and both users

feed the xor of the two allegedly random strings into the RNG.

A secure way is the following:
User 1 gives user 2 a commitment to a random string whose length is equal to the output length,

and a zero-knowledge argument of knowledge of how to open the commitment.

User 2 gives user 1 a random string whose length is equal to the output length.

User 1 gives user 2 the value that was committed to (but not the opening information!),

and a zero-knowledge argument of knowledge of how to open the commitment to that value.

Both users output the xor of the two allegedly random strings.


Encrypting any text without key after padding oracle attack in CBC mode

CBC encryption requires the encryption operation of the cipher, which cannot be build from just the decryption operation of the cipher. Your solution space is empty.

Padding oracle attacks let you find the plaintext without attacking the cipher itself. That's not the same as creating an encryption oracle.


Is there a form of AES encryption where the cipher text matches the length of the clear text and does not show patterns?

What you want is length-preserving encryption, which is a special case of Format-preserving encryption.

A standard mode for achieving this FFX mode, which uses a blockcipher, like AES, in a Feistel network. This mode is relatively complex and slow.

But I strongly recommend using normal authenticated encryption over format preserving encryption whenever possible. Format-preserving encryption always leaks if two plaintexts are identical, whereas semantically secure encryption avoids this leak. It also lacks integrity protection, unlike authenticated encryption.


Predicting values from a Linear Congruential Generator

This answer relates to an earlier variant of the question, which at one point gave an example problem with a, c, m known, as follows:

  Consider the following in Java that prints 100 random numbers from 0 to 5:

  Random r = new Random(); // seeded by system time
  for (int i=0; i<100; i++) System.out.println(r.nextInt(6));

  where r.nextInt(6) is essentially the following:

  seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
  // i.e. seed = (seed * multiplier + addend) $\bmod 2 ^ {48}$

  int bits = (int)(seed >>> (48 - 31));
  return bits % 6;

Yes, it is possible to predict the output of that Linear Congruential Generator variant from its first outputs. For a start, the only unknown is the original value of seed, which is 48 bits. That could be brute-forced, given moderate resources (some CPU.days), and that we have plenty enough outputs (if the output was truly random, we'd have about $100\cdot {log}_2(6) \approx 258$ bits of information). However there are much better attacks possible, succeeding in seconds.

That problem itself has varied. Originally it used a small integer (the final modulus) of 8, instead of  6. We first study that, because it turns out to be easier, and a good intro for the version with 6.

Original problem, ending in return bits % 8

Here seed has 48 bits, bits is its leftmost 31 bits, and the result bits % 8 is the 3 lower bits of that. The top 28 bits of seed never have an opportunity to influence the output of the generator (in a LCG with modulus m a power of two, a bit change in seed never propagates to lower-order bits of seed). Thus for the purpose of predicting the output, seed behaves as a 20-bit (not 48-bit) state. Further, the 3 high bits of that reduced 20-bit state are directly known from the first output.

Now, since everything except the initial state of the RNG is known, brute forcing the remaining 17 bits is almost instant. There are smarter methods that avoid the guesswork.

This illustrates that when the output of a LCG using a power of two as its modulus m is taken modulus some power of two n, the output has a much smaller period than the original LCG (and other weaknesses that may be a disaster even for simulation purposes).

Update: It turns out that Java's nextInt(int n) method special-case what happens when n is a power of two, and then does something very different from what was shown in the original question. That's in order to avoid the effect described above.

Other problem, ending in return bits % 6

Here, all 48 bits of seed have an influence on the output sequence. But there is an easy way to break these 48 bits into two separately attacked segments.

Because the final modulus 6 is even, the low bit of bits is also the low bit of the output, and leaks directly. It is the high bit of the main LCG, reduced to the low 18 bits of seed. That allows recovering the low 18 bits of seed from the low bit of the first outputs (slightly more that 18, I guess). A simple approach is enumerating the $2^{18}$ values of the low 18 bits of seed and, for each, check which gives the correct parity of the first output values. That will recover the low 18 bits of seed well under a second, and is enough to predict the parity of further output. Again, there are smarter methods that avoid the guesswork.

Now we are left with the 30 high bits of seed unknown; that can be brute-forced in seconds. Likely there are smarter methods.

Update: It turns out that Java's nextInt(int n) method does not work exactly as was shown in the original question, even when n is not a power of two; that's in order to remove a bias in the output. However, the simplified description given is good enough that the cryptanalysis described has fair chance to work as is, and can be adapted to work reliably.

Update 2: The above works because m is a power of two, and the final modulus n is divisible by $2^k$ with $k>1$. This allows a separate attack of the $k+r$ lower bits, where $r$ is the number of right bits of seed not used to produce the output ($k=1$, $r=17$ in the above example). If a and/or c and/or $r$ was unknown, it would still be possible to make this separation, and find the $k+r$ lower bits of each of seed, aand c, and the value of $r$, from a number of consecutive outputs considered $\bmod 2^k$, irrespective of the other unknowns.

A more general approach, applicable also to odd n, and perhaps to unknown a and/or c, would be to encode the problem under the formalism of boolean satisfiability, and use one of the many automated solvers available. I can't predict the runtime, though. This flexible approach has broken some mildly serious ciphers, see e.g. this cryptanalysis of A5/1, or this one.

LCGs are seriously bad for cryptographic purposes. They are fine for continuous simulation purposes (where the output is turned into the mantissa of a floating-point number and used as such), but brittle for discrete simulation purposes. In particular, if the LCG uses a power of two as its modulus m, do not take its output modulus an even number and expect the result to behave as a dice with that number of faces: that assumption is incorrect, and many simple tests will show that.

For example, the imbalance between the number of odd and even results in consecutive (simulated) dice throws is exactly zero after $2^{1+r}$ throws. This could be detected with even less samples with a bidirectional Chi-squared test of nextInt(6)%2 or even just nextInt(6). The incredulous can run this test code; it almost always outputs 0 (exceptionally, another single-digit value), when true random would usually give a 3-digit value.

import java.util.Random;
public class diceparity {
    public static void main(String[] args) {
        final int m = 262144; // number of dice throws
        Random rand = new Random();
        int s = -m/2; for (int i = m; i != 0; --i)
            s += rand.nextInt(6)%2;
        System.out.println("Deviation from expected: "+s);
    }
}

Also, the parity of throws repeats after 262144 throws (or slightly less).


I wonder if it's possible to do it with indistinguishability obfuscation. Let's say that the two files have hashes H1 and H2, and that Bob knows those hashes. He can give Alice an obfuscated program that checks the two files against H1 and H2, aborts if the check fails, and if not returns one of the two files (say the one corresponding to H2) encrypted against his public key.

Alice can make sure that both files are not transferred by capping the response to 1 GB. Alternatively Alice can provide a zero-knowledge proof that the response of the obfuscated program is exactly one of the files.


Why Rejewski advanced three position for the right rotor in the second set of rotors in the Cyclometer he devised?

To understand why it was done so, it's necessary to understand what the cyclometer was. And to understand that, we need to get through a bit of encryption procedures for Enigma, as well as steps used to break that encryption.

The procedure for encrypting with Enigma was (simplified):

Set the machine to specific daily setting
Generate a random, 3 letter, key (say RFV)
Encrypt this key using the initial settings, twice
Set the machine to generated key and encrypt the rest
Prepend the encrypted key to the message

Because of this, the 1st letter of ciphertext and the 4th one were in fact the same cleartext letter, but encrypted with different settings (as the machine rotated rotors each letter). So were 2nd and 5th as well as 3rd and 6th.

The Rejewski's method worked by gathering a lot of messages from radio interception, and generating permutations from those. E.g. say you intercept 3 messages, with initial 6 letters of:

pkpjxi
jxixtm
xtmrcy

Than you have partial permutations of

p -> j -> x -> r -> ... (by taking 1st and 4th letter)
k -> x -> t -> c -> ... (by taking 2nd and 5th letter)
p -> i -> m -> y -> ... (by taking 3rd and 6th letter)

Those permutations were unique (or at least almost unique) for each possible initial setting of the machine. So, by recovering the permutations from the intercepted messages and looking them up in catalogue, one could recover (with some more tricks that are out of scope of this question) recover the daily keys, and thus all messages.

Now, after you recover the permutations from daily messages, you need the catalogue to look them up. This is where the cyclometer comes up. It wasn't a decryption tool, it was a tool to facilitate creating the catalogue. As you see, the permutations alternate between the same letter encrypted at first and fourth position (let's forget the other sets for brevity). One could encrypt with all possible settings and get the permutations from that, but cyclometer simplified that - it was two rotor sets, interconnected in a way that whatever you pressed was encrypted via first set, fed to the second set for encryption, than back to the first set and so on, until there was a cycle. As the Enigma advances the rotor after encrypting each letter, and the second rotor set in cyclometer mimics machine operation at 4th letter, the rotors in the second set had to be advanced by 3 characters.


How can an adversary use Mac(.) with a new key to compute a tag although this is not a query to Mac oracle?

In modern cryptography it is generally assumed that algorithms are public and only the key is kept private.
Thus, the adversary can compute $\operatorname{Mac}(k', m)$ for any key $k'$ and message $m$.

The oracle $\operatorname{Mac}_k(\cdot)$ in the experiment allows $A$ to additionally receive valid macs under the challenge-key $k$ for which it is supposed to forge a valid mac (for some message $m^\ast$ that it has not queried from said oracle).

The same goes for the second part of your question: the algorithm is public, so $A$ can run it on any input.


Single-pass authentication with a block cipher that accepts a counter

It is not secure if you use the $E(K, T, X)$ values as the exposed ciphertext; it is secure if you're using this scheme as a MAC (and use an independent scheme to encrypt).

If you send the $C_i = E(K, T_i, X_i)$ as the ciphertext (and send $E(K, 0, \bigoplus C_i)$ as the tag, then what the attacker could do is flip the same bit on two different $C_i$ values.  The resulting $\bigoplus C_i$ will remain the same, and so the tag would validate (and the decrypted plaintext would be incorrect).

On the other hand, if you keep all the $C_i$ values internal, then this system can be viewed as a Carter-Wegman MAC.  All you need to show is that $\bigoplus C_i$ is an almost universal hash function (which is fairly easy to do, assuming you get the message padding right), and the standard CW proofs apply.


ZK due to rewinds, why we need poly number of rewinds?

Well, I mixed up everything. The answers to this question helped me figure it out.

Short answer: A polynomial number of rewinds and reduced challenge space are needed when we deal with the malicious verifier and don't ask for commitments. Rewinds are handy, cause they allow us to prove honest verifier ZK for interactive protocols (ZK as well but either for protocols with commitments or small challenge space).

Long answer:  An interactive sigma protocol is an honest-verifier zero knowledge. This means there exists a simulator, that can falsify the transcript between Prover and Verifier without knowing a Prover's secret. The intuition behind simulation is the following: if verifier can't distinguish between a fake transcript that was generated by the simulator that knows nothing about Prover's secret at all and a real one produced by a Prover, no information about the Prover's secret is leaked. Ironically, in settings where Prover by default is not honest, zero-knowledge property aims to protect Prover's privacy.

Proving honest-verifier zero knowledge is a bit tricky. We know how to simulate the transcript but can't predict verifier's challenge. We can try to guess the challenge, but even for an honest verifier (who behaves and for sure selects it randomly), the probability of guessing is one over the challenge space. If challenge space is large, this probability is next to none.

So, challenge space is a problem. On the one hand, to make sure that a malicious prover's chance to win is exponentially small, challenge space should be reasonably large (soundness). On the other, if challenge space is large, our simulator has almost no chances to guess the challenge right.

The solution is to rewind Verifier - it's an equivalent of having a time machine. We guessed wrongly, went back in time and now we don't need to guess, we know an honest Verifier's challenge. The reason is simple: if Verifier is honest, he would use only his tape to chose the challenge, thus after rewinding, he will select the same challenge.

However, a classic interactive sigma protocol is an honest-verifier zero-knowledge and not just zero-knowledge for a reason. It's not secure against malicious verifier, because even with time-machine we can't guess a malicious verifier's challenge in the polynomial time.

The problem that even rewinds can't solve is a possible dependency on Prover's reply. No matter how many times the Simulator would rewind Verifier, he will not be able to guess the challenge right, cause (a) challenge space is big and (b) challenge depends on what Simulator sends.

There are several ways to solve this problem:

Forget about interactive proofs and switch to non-interactive.
Reduce challenge space (this is where a polynomial number of rewinds appear)
Make Verifier commit to the challenge first

Reduction of the challenge space is not very practical. DrLecter explained it in details here. To sum it up: after each rewind, Verifier computes a new challenge based on what Simulator sent, but since challenge space is small several Simulator's first messages correspond to one challenge, so he will guess it eventually. The book "Modern Cryptography: theory and practice" by Wenbo Mao did the math and conclude that for a simulator to run in poly time a challenge ideally should be from $[0, \log_2 p)$. The only drawback, it's not enough for soundness. To make sure that a malicious prover's chance to win is exponentially small, we have to run many protocols sequentially.

Using commitments as a guarantee is an option too. It adds interactions but requires just one rewind. There are two types of commitments we can use: perfectly hiding and computationally hiding. The former gives ZK, same soundness as before, but require 2 additional interactions: Prover sends $h$, Verifier replies with $g^r h^e$ (Pedersen commitment - perfectly hiding).  For the computationally hiding commitments, ZK and computational soundness can't be achieved. Both claims were proven by professor Yehuda Lindell. The first proof (Theorem 6.5.2)  can be found in "Efficient Secure Two-Party Protocols" by C. Hazay and Y. Lindell (The proof has an error that was later corrected in An Erratum). The second claim is stated here with a sketch of a proof.


Qubit / Qutrit - Is there a theoretical limit on how many orthogonal states a quantum bit has?

There is, in principle, no limit to the dimension of the state space of a quantum system. This includes infinite dimension (usually countable, i.e. a separable Hilbert space) and any large but finite dimension. In the context of quantum information, systems with a state space of dimension $d\geq 2$ are usually called qudits.

It's also important to mention that physical implementations of larger dimensions are harder to bolt down, and particularly it's harder to have a system of dimension $d>2$ that doesn't talk to more states of the system. This is because qubits are realized by restricting some larger system (usually infinite-dimensional) to only two states, by suitable physical considerations, and it is generally quite challenging to really cut out all the other states. Trying to restrict to three or more states while keeping the restriction clean is, generally speaking, harder.

In principle, though, there's nothing stopping you from having any large dimension you want on your system, but then you don't call it a 'bit' anymore.


Signing many small messages with minimal overhead

Then, in the next message, include that random value and a new hash of another random value.

What would prevent someone from taken that valid 'next message', replacing the contents with their own message, and keeping the random value in place?

You could define a hash chain by hashing the entire message to come up with the previous value, but this would imply that when you sent the initial message, you already knew all the other messages at that time; that's unlikely to be a workable assumption.

Alternatives that immediately come to mind:

Use ECDSA (or EdDSA) signatures; those are only 64 bytes (for 128 bit security)
Consider using the Tesla protocol to do the authentication; it works similar to yours, except the actual signature comes at the end, not the beginning (and the receiver isn't sure that the messages are authentic until it receives that final message).


Since you're calculating a scalar multiplication value, and the base point has order $q$, you should calculate $s$ in the field $\mathbb{Z}/q\mathbb{Z}$, not in $GF(2^m)$. In particular, this means that you can't use xor or polynomial division to implement addition and modular reduction, but should use regular addition and division instead.

For example, this should give you the value for $k^{-1}$ as:

$$k^{-1} \equiv 2315871241563531210130617073628712209517930583176 \pmod q$$

which is 1 95A7 4210 396D 0D19 E522 8C83 6815 E728 EFD7 9488 in hexadecimal notation.

Since $q$ is prime, the order of $\mathbb{Z}/q\mathbb{Z}$ is $q-1$, so you can easily calculate the inverse of $k$, and then calculate $s$. This gives the correct output:

>>> q = int('4000000000000000000020108A2E0CC0D99F8A5EF', 16)
>>> x = int('09A4D6792295A7F730FC3F2B49CBC0F62E862272F', 16)
>>> k = int('23AF4074C90A02B3FE61D286D5C87F425E6BDD81B', 16)
>>> m = int('5795edf0d54db760f156f0eb4a7a0fe38d418e813', 16)
>>> r = int('113A63990598A3828C407C0F4D2438D990DF99A7F', 16)
>>> k_inverse = pow(k, q-2, q)
>>> s = (k_inverse * (m + r * x)) % q
>>> '%X' % s
'1313A2E03F5412DDB296A22E2C455335545672D9F'


Does this block cipher mode allow for decryption?

Ok, I will assume that:

The block you have labeled as "Encryption" is some sort of block cipher
You run this mode to transform the IV and the plaintext into a ciphertext
You are asking whether someone with the IV, the ciphertext and the block cipher key can recover the original plaintext.

Well, the quick answer is that they can't.  This is true in two senses:

It is difficult to find a message that would encrypt to the given ciphertext.  To recover (say) the first plaintext block, they would need to find a $P_1$ that solves the equation:

$C_1 \oplus IV = E_K( P_1 ) \oplus P_1$

However, for conventional block ciphers, there's no easy way to solve for such a $P_1$.  Now, if the receiver knew the last plaintext block, he could decrypt all the rest.  However, that isn't a standard assumption.
There might be multiple plaintext messages that encrypt into the same value.  This is because, while $E_K( P_i )$ is a bijection (this is a standard assumption of block ciphers), there's no reason to suppose that $E_K( P_i ) \oplus P_i $ is (and, in fact, with high probability, it isn't).

To give a simple example of this last point, why don't see assume that we have a 1 byte block cipher with:

$E_k( 0x00 ) = 0x71$

$E_k( 0x17 ) = 0x66$

Then, if $IV = 0x19$, then:

The encryption of the single byte message $0x00$ will be the single byte $0x19 \oplus E_k( 0x00 ) \oplus 0x00 = 0x19 \oplus 0x71 \oplus 0x00 = 0x68$

The encryption of the single byte message $0x17$ will be the single byte $0x19 \oplus E_k( 0x17 ) \oplus 0x17 = 0x19 \oplus 0x66 \oplus 0x17 = 0x68$

Hence, in this case, if we get an encrypted message $0x68$, we have no idea if the original plaintext was $0x00$ or $0x17$


The tangent line at point $P(x_1,y_1)$ is:

$\frac{\partial f}{\partial x}(x-x_1)+\frac{\partial f}{\partial y}(y-y_1)$

Solving differentials, we obtain:

$\frac{\partial f}{\partial x}=3x^2+2x$

$\frac{\partial f}{\partial y}=-2y-1$

For $x_1=0$ and $y_1=0$ we have:

$\frac{\partial f}{\partial x}=3x^2+2x = 0$

$\frac{\partial f}{\partial y}=-2y-1 = -1$

So, by the first equation, the tangent line at $P(0,0)$ is $-y$.

Now, to calculate the intersection point with the curve we need to solve the next equations system:

$-y=0$

$y^2  + y = x^3 + x^2$

That have two solutions:
$x=-1, y=0$ and $x=0, y=0$

So, the tangent line intersect the curve at $(-1,0)$ and $(0,0)$.


How much does a successful Distinguishing Attack "break" the attacked stream cipher?

I would say a distinguishing attack should count as a break. Especially so if it is practical.

The reason for this is that if you can distinguish the key-stream from random, you invariably leak details about the plain-text.

For example, suppose somebody turned up a few terabyte disks encrypted with VMPC under the same key. It says in the paper that after approximately $2^{40}$ bytes the cipher can be distinguished from random. The bias in the underlying cipher might allow an attacker to work out whether the plain-text was written in Arabic or English.

That in itself is useful information to know about the plain-text and, to me at least, constitutes an unacceptable weakening of the cipher.


Is it safe to hash a packet with a shared secret to prove authenticity?

From what you I described I understand your scheme to be following:
Each message $M$ gets a tag $T$ which is $H(S \mathbin\| M)$ where $H$ can be MD5 or SHA2 and $S$ is a common secret. Both hash functions are vulnerable to a length-extension attack effectively allowing to compute $H(S\mathbin\|M\mathbin\|x)$ from $H(S\mathbin\|M)$ and the length of $M$ so your scheme should not be used for authentication.

A better alternative would be to use a message authentication code (short MAC), which is a group of algorithms specifically crafted for cases similar to yours, including the widespread HMAC which allows to turn even broken hash-algorithms like MD5 into relatively secure MAC's.


How to securely store and validate a 4-digit PIN used on a mobile device?

PIN check is bound to rely on trusted device or security by obscurity.

If a 4-digit Personal Identification Number is stored and validated in an device (possibly composite, like combination of server and mobile device) of known construction, and an adversary acquires/extracts all the data stored in the device, including the (possibly encrypted or hashed) PIN and try counter, then that adversary is able to find the PIN with at most 10000 times the effort/energy it takes to try a wrong value of the PIN. Argument: the adversary simulates what the device does to test a candidate PIN, and when wrong just fires another simulation. The multiple PINs can be tried in parallel, thus the time it takes can be down to a single PIN try.

All ways around move the PIN and counter into a trusted device: security IC (Smart Card, Subscriber Identity Module, Trusted Platform Module...) for offline solution, or online server. The appropriate logic for a PIN check in a trusted device is:

if the error counter is below a threshold (typically 3)

increase the error counter in non-volatile memory, and if that succeeds

compare the proposed PIN to the stored PIN, and if it matches

reset the error counter to 0
authorize access until some event, such as a reset or a timer elapsing.

Historical section: Implementers sometime got that wrong. My deceased friend and Smart Card inventor Roland Moreno can be seen (audio in French) demoing a device that finds the PIN code of a bank card as was used in France in the early 1990s or slightly earlier. That particular one:

Used PROM (implemented as UV-EPROM with protection against UV erase) for the PIN error counter, and relied on a separate VPP power contact to program that, allowing an adversary to inhibit the writing by supplying too low a voltage.
Used an array of bits for the counter, with a scheme maximizing the number of PIN presentations considering the physical impossibility to erase a bit: the position of the programmed bit told if the count was reset or incremented, with the counter determined by the pattern on the frontier at the left of the right zone of unprogrammed bits (* = programmed, . not programmed, x = any)

xxxxxx**................ 0
xxxxxx**.*.............. 1
xxxxxx**.*.*............ 2
xxxxxx**.*.*.*.......... 3

Towards the goal of choosing which bit to program, performed the PIN comparison before the increment.
Leaked the result of that comparison thru a side channel. It happened that a byte characteristic of the PIN comparison was in a RAM buffer also used for communication, and readable after a warm reset that did not clear that byte, using a standard command.

I was told that a different model of card using comparable technology, and immune to this exact attack, still allowed to recover the result of PIN comparison before counter update, thru some timing attack.

Practical section:

  Can I do something more ?

Two main cases (with the question about the second):

The PIN needs to be checked locally on the mobile device: crypto mostly does not help!

Offload the PIN check security functionality to the mobile device OS, which is in a better position than an application programmer to use the underlying hardware. If there's no such explicit service, it might still be possible to replace PIN authentication by the mere unlocking of the device, leaving it to the user to decide if that's with a PIN or otherwise.
OR use security by obscurity in the mobile app.
OR/AND, under the plausible assumption that (D)RAM is harder for an adversary to read than something more permanent, and if there is some form of more secure user login (even a password), and it is acceptable that the user makes use of that at each boot: hold the PIN hash encrypted/protected under that more secure user login credentials when on disk, and decipher it in RAM on boot. The makes the PIN as secure as the other login form when the user device is powered down to the point that (D)RAM content is lost.

The PIN only needs to be checked in an online scenario: crypto helps but is not a silver bullet!

Have the mobile device carefully validate the remote server in charge of PIN check and counter maintenance, e.g. thru a pinned TLS certificate, and send the PIN keyed-in by the user in a TLS tunnel with the server for checking. Additionally sending messages (e.g. PIN or a derivative) encrypted with another server public key devoted to PIN, along a server challenge preventing replay of the cryptogram, is theoretically redundant with TLS, but complicates attack. An alternative (with little if any benefit) is a PAKE such as SRP (tags: pake srp) to send and store the PIN on the server.
AND, use a long-term secret on the mobile side, if it is functionally possible that a user resetting the device or using a different one prevents login with PIN only. That can help protect from Denial of Service (where an attacker submits wrong PIN to prevent the rightful user to log-in), and make it impossible to find the actual PIN from server-side data (which is useful when a user reuses the same PIN on multiple servers).
A possibility is that the user device draws and stores a fresh ECC private key and a random secret integer $S\in[0\ldots9999]$ each time the PIN is changed, with public key and Randomized Identification Number $\text{RIN}=(S+\text{PIN})\bmod10000$ stored on the server side. At each login the server sends a random challenge $C$, the device asks the PIN and gets $\text{PIN}'$, the device computes $\text{RIN}'=(S+\text{PIN}')\bmod10000$ and sends $\operatorname{Sign}(C\mathbin\|\text{RIN}')\mathbin\|\text{RIN}'$ encrypted to the server (see 2.1 for how). The server extracts the signature and $\text{RIN}'$, increments the transaction counter only if the signature matches that of $C\mathbin\|\text{RIN}'$, then in the affirmative tests if $\text{RIN}'=\text{RIN}$ to decide if the counter should be reset and access granted.
Note: that provides functionality similar to that other answer with 35 bytes per user stored on the server side instead of several kilobytes.
AND take computer security precautions so that the server does not leak its storage, which (combined with long-term secret on the mobile side if any) is bound to allow finding the PIN with little effort for a competent attacker (the mere ability to roll back a backup of the PIN state counters unavoidably makes such attack possible). Precautions must include trustworthy server administrators with robust access control to administration, encrypted offline backups (preferably with a public-key), and can include making the PIN/RIN check and counter update in or with the help of a security device such as an HSM or security IC.
AND it can only help that the PIN or RIN of 2.1 is stored (on disk/NVM/(D)RAM/database..) on the server side as a password should be: hashed with a purposely-slow memory-hard entropy-stretching hash such as Argon2, together with random salt (stored along the hash) and semi-secret pepper, and ample security parameters (number of iterations, RAM). But again, that's not an even passable protection, for 10000 attempts is sure to allow to find the PIN (for who knows hash, salt and pepper, and long-term secret on the mobile side if any).


What would be the result if $r/2$ was -1?

I assume you meant "how does this work if $a^{r/2} \equiv -1$?
Yes, that does not give us a factorization; however there's an easy fix - use a different value of $a$.
I don't mean "go back to the Quantum Computer and rerun Shor's algorithm with a different base"; instead, select a different value $a'$ and check if $a'^{r} \equiv 1$.  It turns out (if the original value of $a$ was randomly selected) that a random selection of $a'$ has a good probability of making this work; once that works, you can then look at $a'{r/2} \pm 1$; those have a good probability of yielding a factorization.
The other possible complication is "what if the $r$ value that Shor's algorithm hands you happens to be odd?"; it turns out a similar approach works; select a random $a'$, and compute $a'^{2^{\lambda}r}$ for $\lambda$ small (0 until, say, $\log_2(n/r)$); if you find a $\lambda$ with $a'^{2^{\lambda}r} \not\equiv 1$ and $a'^{2^{\lambda+1}r} \equiv 1$, that has a good probability of yielding a factorization (and, yes, this looks a lot like how the Miller Rabin primality test works).
In addition, if you can't find a value $a'$ for which $a'^{2^{\lambda}r} \equiv 1$, you can also compute $\gcd(n, a'^{2^{\lambda}r}-1 \bmod n)$; that also yields a factor in some rare cases.
The bottom line is that, given an output of Shor's algorithm, we have good fast probabilistic methods for obtaining the factorization (which fail with low probability if $a$ was selected randomly [1]); the method isn't quite as simple as "plug in $r$ and $n$ into this simple deterministic algorithm, and out pops the factorization."

[1]: The failure case happens if the order of $a$ modulo $p-1$ happens to be significantly smaller than $p-1$ (and the same modulo $q-1$; that final test covers the case that only one of them is significantly smaller).


Definition and meaning of "semantic security"

What if it could? What does this definition mean in practice?

Consider $M_0=$ attack and $M_1=$ don't attack. If the adversary can distinguish which message you are sending to your troops, they can optimize their strategy to defeat you.

Another example. Say you are casting a yes ($1$) no ($0$) vote for a proposed piece of legislation. If the adversary can distinguish between yes and no votes, they might be able to throw the election (by discarding votes that don't go their way) or persecute you according to your vote.


Since $a_1 = e^{r_1(p-1)} \bmod N$ and since $p$ divides $N$, it follows that $a_1 \equiv e^{r_1(p-1)} \equiv 1 \pmod p$.  We so have $a_1 - 1 \equiv 0 \pmod p$ or, equivalently, $a_1-1$ is a multiple of $p$.  In turn, this implies (with overwhelming probability) that $\gcd(a_1-1,N) = p$ and thus $q =N/p$.

Since $d_1 \equiv {a_1}^{s_1} \equiv 1 \pmod p$ and similarly since $d_2 \equiv 1 \pmod q$, message $m$ can be recovered as $\operatorname{CRT}(c_1 \bmod p, c_2 \bmod q)$, using the values of $p$ and $q$ as obtained above.


If you are using a cryptographicly secure PRNG with a sufficiently large seed. Then it is expected to be infeasible to detect a relationship between the random stream output.
If you find two carefully crafted seeds where the output streams then have some clear relationship it would be considered a (mild) weakness in the PRNG, and much more so with random seeds.


Usage of parameter "b" of an elliptic curve over GF(p)

Adding two points $(x_1, y_1)$ and $(x_2, y_2)$ with $x_1 \neq x_2$ gives point $(x_3, y_3)$ with

$$x_3 = (\frac{y_2 - y_1}{x_2 -x_1})^2- x_1 - x_2$$

$$y_3 = (\frac{y_2 - y_1}{x_2 -x_1}) (x_1 - x_3) - y_1$$

The case $x_1 = x_2$ is either adding the inverse or point doubling.

Doubling point $(x_1, y_1)$ with $y_1 \neq 0$ gives point $(x_2, y_2)$ with

$$x_2 = (\frac{3 x_1 + a}{2 y_1})^2 - 2 x_1$$

$$y_2 = -(\frac{3 x_1 + a}{2 y_1}) (x_1 - x_2) - y_1$$

So addition does require neither $a$ nor $b$, whereas point doubling and exponentiation with a scalar number requires only $a$. Checking if both points belong to the same curve also only requires $a$.


Decrypting messages crypted with one time pad (used more than once)

First of all, there is nothing really special about spaces. It is a fact of how the ascii encoding is put together that e.g. chr(ord('a') ^ ord(' ')) = 'A' and vice versa. Your code should just xor things together and not try to do anything special if the key character is a space.

4 important properties of xor are:

1) a xor 0 = a
2) a xor b = b xor a
3) a xor a = 0
4) a xor (b xor c) = (a xor b) xor c

(i.e. xor gives rise to an Abelian group where every element is its own inverse).

This implies that if a and b are both encrypted by the same k, to get cipher texts a xor k and b xor k, then if you xor the two cipher texts together you get:

(a xor k ) xor (b xor k) = (a xor b) xor (k xor k)
                         = (a xor b) xor 0
                         = a xor b

k drops out leaving you with a encrypted by b.

Now -- if you have 23 ciphertexts, xor the last 22 with the first one. The result is now 22 new ciphertexts encrypted with the same key (where the first albeit unkown plaintext is the common key). At first this seems pointless -- but note now that the key is far from random whereas the original key was likely to be random. You are assuming something about the alphabet the first message is written in and are hoping that it should have a reasonably common frequency profile.

What you can do is the following -- and this can be automated in Python: For each character position in message 1, pick the character in 'a'-'z','A'-'Z',' ' which renders the statistical profile of the characters at that position in the remaining 22 cipher texts as close to English as possible. As a simple expedient, pick the character which maximizes the count of the 4 or 5 most common letters in the English language (or whatever natural language is being used). This gives you a tentative decryption of message 1. It is almost certainly wrong -- but there should be more than enough for you to guess most of the words in it -- and you have 22 ways to verify each guess. Further more, as more and more words in message 1 fall into place, you start getting trial decryptions of the remaining 22 messages, including words that you can guess and that shed light on any portions of the first message that are still known. Once the dominoes start falling, they should fall quite rapidly.

One possible use of the observation concerning spaces is that, since lower case letters are much more common that upper case letters, if after you get your 22 messages encrypted with the first one, if you see any position in which the overwhelming majority of the 22 characters in that position are upper case, it is somewhat likely that the corresponding position in the first message is a blank, which could help you guess where the word boundaries in the first message is. Also -- I have been assuming that all messages are the same length. Obviously things are slightly more complicated if the messages are of variable length, though these sorts of idea will still work (though the longest message would likely have a tail which in incapable of decryption).


Why is a random component needed for ECDH key pair generation in Mbed TLS?

It is used to implement countermeasures against side-channel attacks.
From the paper:

If f_rng is not NULL, it is used to implement countermeasures against side-channel attacks.

And

The RNG function, for blinding purposes. This may b(sic) NULL if blinding isn't needed.

See more in mbed API Documentation.

The modular inverse operation as implemented in Mbed TLS was previously vulnerable to a single-trace side channel attack. This allowed an attacker with access to precise enough timing and memory access information (typically an untrusted operating system attacking a secure enclave such as SGX or the TrustZone secure world) to fully recover an ECDSA private key after observing a number of signature operations.
To combat these sorts of attacks, we can employ blinding; we include random data in our computations, and while the end results is independent of the random value, the intermediate values are strongly dependent, and thus the correlations between the intermediate states and anything that the attacker wants (such as the private key) is much weaker.
For further information on blinding, see

Scalar Blinding on Elliptic Curves with Special
Structure by Scott Fluhrer. Section 2 specifically discusses and references various techniques.

The specific attack on Mbed TLS is detailed further in this paper,

From A to Z: Projective coordinates leakage in the wild by Aldaya et. al, in 2020.

as taken from the mbed security update

Side channel attack on ECDSA .

There is a somewhat related follow-up from the same authors

Side-channel attack on ECC key import and validation

Note PolarSSL was acquired by ARM Holdings in 2014 and As of the release of version 1.3.10, PolarSSL has been rebranded to Mbed TLS.


2DES and 3DES against a DES build with complimentary

Is the following build stronger than 2DES or 3DES with 2 different keys (or even normal DES)?
$DES(DES(x,k),\overline{k})$

It is only slightly stronger than DES; it is considerably easier to attack than 2DES or 3DES.
The most practical attack against DES is brute force; simply try the various possible keys until you stumble on the correct one.  With a known plaintext/ciphertext pair, this takes an expected $2^{55}$ DES evaluations.
Against your design, because the key is still only 56 bits, this brute force method is still practical.  In your case, this takes an expected $2^{56}$ DES evaluations.
We generally don't know the attacker's capability to that much precision, a factor of 2 increase in the work effort is well below our uncertainly (and hence are effectively the same).
In contrast, 2DES can be attacked with the same approximate work effort; however the algorithms that do that require a significant amount of memory, and are harder to parallelize (and hence are, in practice, more difficult to do).
Also, if you think that your design forces two DES key schedules for every DES key tested, that turns out not to be the case.  Because of the DES key complementation property, we have:
$$DES(DES(x,k),\overline{k}) = \overline{ DES( \overline{ DES(x, k) }, k)}$$
Hence, a key can be tested by performing two DES evaluations on the same key, and an intermediate complementation.


Yes, using Miller-Rabin with a random witness does give a practical factoring method.  When you run the Miller-Rabin algorithm, it can end in one of three ways:

The final value is not 1; this case causes Miller-Rabin to output "Composite"
An intermediate value was not 1 or N-1, but the next value was 1; this causes Miller-Rabin to output "Composite"
The initial value was 1; or an intermediate value was N-1; this causes Miller-Rabin to output "Probably Prime".

Case 1 will happen only if $W^{N-1} \neq 1 \bmod N$, however, that we get that inequality for Carmichael numbers only if $W$ is a multiple of a factor of $N$; in this case, $gcd(W, N)$ gives us a nontrivial factor.

For Case 2, well, that gives us a nontrivial value $X$ for which $X^2 = 1 \bmod N$; as you correctly point out, a nontrivial square root of $N$ immediately gives us the nontrivial factors $gcd(X+1, N), gcd(X-1, N)$

Hence, in the specific case of Carmichael numbers, if the Miller Rabin test outputs "Composite", we always have enough information to immediately factor.  And,  when Miller-Rabin is given a composite number, then it will output "Composite" with probability > 3/4; hence, a single iteration will allow us to factor with high probability.

In fact, for Carmichael numbers, the probability of success with Miller Rabin is actually > 7/8; Carmichael numbers are not the worse case for Miller Rabin.

This gives us a practical factorization method; however for pedantic reasons, it doesn't actually answer the question.  It's not a poly-time algorithm; it is a probabilistic poly-time algorithm which, per iteration, has a good probability of yielding a factor, but it also has a probability of not finding a factor.


CSPRNG in JavaScript using Audio and Video

window.crypto.getRandomValues() is the best you can do.  Unfortunately, at the time of writing, too many browsers don't support window.crypto.getRandomValues(): see Compatibility of window.crypto.getRandomValues().

The alternative is to use fallback methods.  However, those fallback methods are kind've hacky, of dubious security, slow, and have other limitations.  For more on the available fallback methods, see Generate cryptographically strong pseudorandom numbers in Javascript?.

Therefore, life kinda sucks.  Basically, the best you can do is test for the existence of window.crypto.getRandomValues() using feature testing.  If it exists, great! use it.  If it doesn't exist, fall back to one of the fallback methods -- in that case, life is unhappy, but what can you do, there's no better option.


How much entropy is generated by 'random' human keystrokes?

http://csrc.nist.gov/publications/nistpubs/800-63/SP800-63V1_0_2.pdf

This publication from NIST tries to estimate the entropie of user choosen passwords. I know, it is not exactly what you requested, but i think it could be a good indication for the entropy of "random" keystrokes.

Especially Appendix A2 is relevant. The assume the following:

The first character is taken to be 4 bits of entropy
The next 7 characters are 2 bits per character
For characters 9 - 20 the entropy is taken to be 1.5 bits per character
For characters 21 and above there is 1 bit per character

There is a "bonus" of 6 bits of entropy is both upper case and non-alphabetic characters are used

For more detail read the Appendix A.


Can two different seeds produce the same output from a PRNG?

Well, yes, but the output should be limited by chance. It's kind of obvious that repetition is possible if you just consider a single bit of output. However, when you request more bits then the chance that the bits are equal should become less.

The seed or seeds are an entropy source for the PRNG. The PRNG should not disregard any bits that contain entropy, so the seed should be integrated into the state of the PRNG. A cryptographically secure PRNG should have quite a large state; the chance that a seed recreates a previously known state should be computationally impossible. The output is created using this state, and the output should therefore be random given a specific seed. So if the output is identical then it is by chance alone.

PRNG's are often constructed from secure hash functions. Getting collisions from output created by a secure hash is a computationally hard problem.

The output of stream ciphers using the same seed / key may not be able to repeat at all, for any amount of data that contains a full block. For instance counter mode encryption will never repeat the same block.

This is inconsequential for any block cipher with a block size of 128 bits or higher, as the likelihood of generating a repeating block by chance is also quite low, even if bounded by the birthday problem.

If a stream cipher has equivalent keys then the key stream may of course repeat if one of the seeds results in equivalent keys being used (as indicated by the comments below the question). Those stream ciphers however should not be considered secure PRNG's.

Note that stream ciphers usually lack procedures for e.g. adding seed material (re-seeding) to the state or extracting the entropy. A stream cipher doesn't fully comply with the interface for DRBG's as stated in NIST SP-800 90Ar1 although they are normally thought of to be PRNG's.


Yes combining anything with the output of a good RNG will result in good random numbers (as long as they don't have information from your RNG)
Yes it would remove the bias (but there are other ways to do this whitening also)
No that doesn't really do anything interesting, but a simple way to unbias your numbers is a Von Neumann extractor

Also try to find non deterministic sources, be suspicious of random data from strangers.


RSA Signature : Process of Sign the message and Verify

We do use the secret key to sign the message as otherwise anybody would be able to sign messages (in your name!)
You can hash a message by passing it to cryptographically secure hash function, like SHA-2/3 and interpret the resulting digest as integer $m$.

The verification (of plain RSA, please note: RSA is never deployed like this) of RSA-signatures works as follows:

Obtain the message $M$ and the signature $s$ and the public key $(N,e)$
Hash the message $M$ to get the "numerical" message $m=h(M)$.
Compute $m'=s^e \bmod N$.
Accept the signature (= return true) if and only if $m=m'$, otherwise reject the signature (= return false)

The third step is the plain RSA-encryption, hence it is sometimes referred to as "encryption".
The signing equation you cited above corresponds to the decryption operation of RSA public key encryption, therefore to ease understandability for beginners it is often described as "encryption using the private key" or as "decryption".


Asymmetric algorithm to generate compact unique messages that can be validated

It sounds like the main obstacle to using RSA signatures is the size of the signature. If that's the case, consider using Elliptic Curve Digital Signature Algorith (ECDSA).

EC signatures are much shorter than RSA signatures with equivalent strength. For example, an ECDSA signature with a 256-bit key is about 70 bytes long in its standard encoding. This is as strong as an RSA signature with a 3072-bit key, which is 384 bytes long. ECDSA is also a NSA Suite B recommendation, while RSA is not.


Nonces being used in SSL and MAC to prevent replay attacks

Well, you have it right in how nonces are used to make sure that the keys in different SSL sessions; this effectively prevents someone from taking an SSL record from one session, and injecting it into another -- because the keys aren't the same, it won't pass the integrity tests.

However, that's not the only place we care about replay attacks; we can also be concerned about someone taking an SSL record from one session, and replaying it latter in that same session.  Because the keys are the same, we can't use the above logic.

So, what SSL transmitter does when it computes the MAC for a record is logically prepend the current byte count; that is, the number of bytes that have passed through this SSL connection so far.  This byte count is not sent over the wire, but it is implied.  When the receiver gets the record, it also logically prepends its current byte count (which should match the transmitter's); and so it should compute the same MAC.  After processing the record, both the transmitter and the receiver updates its current byte count (based on how long the record was).

Now, if someone should replay that record, the receiver would then logically prepend its current byte count (which would not match what the transmitter prepended when it originally generated the record); because that count is different, the receiver would generate a different MAC, and so the record would be rejected.

That gives you the answer, I want to close with one clarification; you mentioned SSL; well, the current version of the protocol is known as TLS.  There are several versions (TLS 1.0, 1.1 and 1.2); TLS 1.2 handles the byte count slightly differently; however it does the same job.  There's also something known as DTLS; for that protocol, the count (which is a count of records, and not bytes) is explicitly sent within the record.


Trivial Broadcast Encryption Scheme for video conferencing how well does it handle users joining or leaving a call?

For participants joining the call, the broadcaster would have to send the session key encrypted with their and joining user's long lived shared key. Which is simple enough.

When a user leaves the call, if the session key is unchanged, they can still decrypt the stream. The only secure option is change the session key and rebroadcast encrypted copies of it to all remaining participants. This ensures that when a user leaves, they can't continue to listen in.

Less obviously, when a user enters, if the key is not changed, the key they are sent decrypts data from before they joined.

The best solution is to rekey anytime the set of authorized users changes.


What if we XOR it multiple times with different keys, like this:
  $Cyphertext=((((((Plaintext⊕K1)⊕K2)⊕K3)⊕K4)⊕K5)....⊕Kn$

This is equivalent to XOR with a single key $K$ where $K = K_1 \oplus K_2 \oplus K_3 \oplus ... \oplus K_N$. As such, it would be no stronger than a regular OTP.

  Even if the key is biased or contains low entropy, the Xor function is known for it's de-biasing features, so Xor-ing multiple keys togeter would decrease the bias,

This is not accurate: Xor is a bitwise operation, and it only operates on 2 values at a time. The bit at position $i$ in word $K_1$ only interacts with the bit at position $i$ in $K_2$. If a bit at position $i$ happens to be biased, and all of the rest of the bits are not biased, then Xor with similarly biased data will not de-bias any of the other bits in the key word.

Put another one, if the adversary knows that the first bit of each $K$ is $0$, then you can Xor as many $K$ together as you want, and the adversary can still be certain that the first bit will still be $0$.

  I think 5-6 rounds are enough, the bias will definitely shrink after 6 rounds to insignificance.

So we can see this is not useful or accurate.

  But it also adds entropy into the system. By having 1 weak key with unknown entropy, we can have more keys mixed into the system thus increasing the overall entropy of the keys.

For our purposes, entropy is the number of secret bits of information the adversary does not know and must guess/obtain if they are to evaluate the desired function. So "unknown entropy" is redundant. We assume the secret key to be unknown to the adversary - that is why it is called a secret key.

Now, there are branches of cryptography that focus on retaining security even when some key bits are leaked, but I don't think they focus on the OTP. This is probably because if your key generation process for the OTP is flawed and produces weak keys, then you would be better off using a better key generation process, rather then trying to compensate for the inadequacy further down the line.

  Would this be a perfect OTP design?

No; The "perfect" one is the regular old, unmodified OTP, which is information theoretically secure. "More"/"newer"/"complex" is not necessarily better when it comes to cryptography.


How can the Enigma's plugboard settings be found with partially known plaintext?

There is a much better explanation available. See Graham Ellsbury's page here for full details, and a summary below:

Intuitively, what one does first is to drag the crib (known plaintext) accross the ciphertext and rule out relative positions which map a plaintext letter to itself in the ciphertext (since it is known that the Enigma mapping has no fixed points).

Afterwards, for each hypothesized setting that is compatible with the plaintext ciphertext pair, one iterates the enigma machine according to the setting, until one gets a contradiction, for example, say that in the hypothesised setting X maps to Z. But after a number of iterations, X then maps to G. This rules out the initial hypothesized setting.

This requires automation of the process of checking all these settings in parallel, and that's where the bombe mechanism comes in.

I have condensed the example from that page below:

Example After the crib dragging, there is the possibility that

RWIVTYRESXBFOGKUHQBAISE

is the encryption of

WETTERVORHERSAGEBISKAYA

(since there is no letter mapping to itself in this shift of the crib with respect to the ciphertext), for one of the 60 rotor orders, 17576 rotor positions, 676 Ringstellung positions and 150,000,000,000,000 stecker swappings.

One still needs to find out which setting.

Now numbering the positions, we obtain the table

12345678901234567890123
RWIVTYRESXBFOGKUHQBAISE
WETTERVORHERSAGEBISKAYA

where the number above X and H is 10, that above B and K is 20, etc.

This means we can derive a relationship graph

So, if the crib is correctly matched with the ciphertext, we know that some setting of the Enigma will encode R as W and W as R in a particular position which we will call position 1, the Enigma rotor(s) step and then in the next position, which we call position 2, it will encode W as E and E as W, then the rotor(s) step and then in the next position which we call position 3, it will encode I as T and T as I, and so on.

The linked page then goes through a fully detailed argument as to how the setting hypothesis can be verified or ruled out. This would have been done with the Bombes eventually, though Turing et al worked through this procedure by hand as well.


Prove that the following private-key encryption scheme is not CPA-secure

If you choose $m = (1, \ldots, 1)_n$ then

$$(r, F_r(k) \oplus \overline{m}) = (r, F_r(k) \oplus (0, \ldots, 0)_n) = (r, F_r(k))$$

what reveals $k$.


Access control problem in oblivious transfer

OT is typically not used as an application in its own right. In the context of access control, OT limits the number of messages received by B but not which messages. I don't know of any real applications for this (you could talk about a subscription where B has purchased the right to read any $k$ articles, but this is pretty artificial in my opinion).

However, OT is a very important and basic building block used in constructing secure computation protocols. It is used in generic protocols like Yao and GMW, and is often used in specific protocols for things like secure set intersection and others.


How was this Mersenne Twister seed for a 20-character string known a priori found?

How did he do this?

Actually, you gave much of it away when you mentioned:

  You can generate the state of the Mersenne twister with as little as 624 outputs, then predicting future output from it.

This is true, but you can do other things with it.  You can also generate previous output (that is, what the Mersenne twister output would be on blocks previous to the one you saw),previous states (that is, what the twister state had to be so that, after an iteration of the twister, you would get the selected state) and also compute the necessary seed to obtain a specific state.

Hence, most likely here's what he did:

Created an output of 624 integers, which consisted of the "9!dlroW ,olleH"ck,@ (which is 20 bytes or 5 integers), along with 619 arbitrary values.  These last 619 integers will be ignored, and hence it doesn't matter what values you select for them.
Reconstructed the internal twister state needed to generate this output.
Generated the previous twister state needed to generate this state after going through the twister permutation
Generated the seed needed to generate this twister state

And that's it.  The above is a bit tedious to do by hand; it'd be fairly trivial for a program.


Interpretation of certain results of NIST Test Suite

Randomness is pesky, and can wax and wane between samples.  That's why there is no one specific categorical test that can validate an IID sequence. You need to statistically combine several (perhaps contradictory ones)  together to gain a broader perspective. The P values in columns C1 thru C10 are distributed as:-

Each column is a P value of width 0.1. So what seems to have happened is that all your individual P values  fell 0.4 < P < 0.99, which is the NIST 0.01 significance level. So individually they passed, hence 100/100.

But when you plot this distribution of P values, it looks unlikely. The test suite is designed so that all of the P scores are uniformly distributed 0 - 1 under an is-random null hypothesis.  And when you calculate a probability of these scores occurring randomly (via a Chi test), you get your P = 0.000000 (plus star!).  So you failed the test. Badly :-(

There's more interpretative stuff in §5 of the Special Publication 800-22 document.  I won't say any more regarding your PRNG as there is limited information in this question.


Assuming a 1024qb quantum computer, how long to brute force 1024bit RSA, 256bit AES and 512bit SHA512

Adding more qubits does not increase the computation speed. A quantum computer with 4 qubits does not factorize faster than one with 2. The qubits are the "memory" of the quantum computer. More qubits mean you can factor bigger numbers. If I remember correctly, you need a superposition of $\Theta(N^2)$ terms, which means $\Theta(\log(N^2))$ qubits to factor N.
The running time of Shor's algorithm is $O((\log N)^3)$ to factorize $N$. What is important to remember is that Shor's algorithm can only factorize (by solving the discrete log problem). See wikipedia's entry on Shor's algorithm.
As for Grover's algorithm, it provides quadratic advantage over classical computers for "black-box" queries. So a quantum computer could perform a brute-force attack in $O(\sqrt{N})$ trials whereas a classical computer would need $O(N)$ trials. Again, increasing the number of qubits does not lower the running time, but increases the "memory" of the quantum computer. In order to run Grover's algorithm to brute-force a key, you need a superposition of all keys, which requires $\log K$ qubits where $K$ is the number of possible keys.


(EDIT: question before edit asked about case where $r_v$ is missing from hash, that's why the answer is mostly about it:)

This would totally break security of the scheme. Assume that protocol looks like this (only change is in step 2 - missing $r_v$):

$V\rightarrow P:r_V$
$P\rightarrow V:r_P,h_k(r_P)$
$V\rightarrow P:h_k(r_P,r_V)$

Let's assume that Eve sees message from step 2. She can now start another authentication session and send to $V$ the same pair $r_P,h_k(r_P)$ again and get authenticated as $P$ (in as many separated sessions as she wants).

You can prevent this by requiring that each $r_P$ can be used only once but tracking used values is way more expensive and error-prone than simply including challenge from $V$ in hash.

Please note that if you drop $r_P$ from step 3 as well and Eve sees all messages then she can pretend to be $V$ in communication with $P$ as well.

If protocol looks like:

$V\rightarrow P:r_V$
$P\rightarrow V:r_P,h_k(r_V)$
$V\rightarrow P:h_k(r_P)$

then you can force $P$ to sign whatever message you want (impersonating $V$ ) or force $V$ to sign whatever you want performing man-in-the-middle attack and changing $r_P$. This can potentially lead to some replay attack if you use strong MAC or to secret key recovery if MAC is not chosen plaintext secure.


What makes crypto code vulnerable to timing attacks is data dependent timing variations. Branching according to a round counter, or to the key size, does not create a vulnerability. Most implementations of AES make no branch according to key or data value, and supressing other branches won't help.

The main source of data-dependent timing variations in AES is in the table lookups for the S-boxes: according to if the entry is in cache, or not, the table fetch will take different time. See for example Daniel J. Bernstein, Cache-timing attacks on AES (2004) [direct link to pdf] for more info.

Among ways to make AES code free of any timing dependencies are:

using AES-NI or other hardware support;
using a CPU without data cache (and being careful about alignment of the table);
changing the S-table to a logical expression, possibly using bitslicing to regain at least some of the lost speed; unfortunately the AES S-table is rather hard to express  in this way (this has been studied by Joan Boyar and René Peralta, A new combinational logic minimization technique with applications to cryptology and A depth-16 circuit for the AES S-box; here are some of their equations).


Why $\alpha$ in ElGamal cryptosystem has to be a primitive root?

Everything works, except the key and signature space, reduced greatly;

  The result is that the signature space (when the key is used for     signing) or the public key space (when the key is used for encryption)     may be greatly reduced from its expected size of log(p) bits, possibly     down to 1 bit (the worst case if the order of g is 2)1.

It not hard to detect a $g$ is the generator or not.


Yes, and that's how it's normally done. This even applies to AEAD schemes like GCM, CCM, and EAX (which all encrypt with CTR and MAC as a separate matter with some other algorithm); with non-AEAD schemes, you have systems like CBC+HMAC in TLS, and (with stream ciphers for encryption) ChaCha20+Poly1305 (which are two completely independent algorithms). However, this is something that's really hard to get right, which is why standardized AEAD schemes are so nice (AEAD means there's a well-analyzed specification of exactly how to combine them).


Password re-use by another person or on another service

Salt is usually stored along with the hashed password. When an attacker knows that your password is "abc123" in "pqr.com", he can try your username and password "abc123" in site "efg.com". Now "efg.com", would retrieve the stored hash against your username and extract the salt from it. Then the extracted salt is used to calculate the hash of the entered password and then matched with the stored hash.

The purpose of salt is to ensure that just by looking at two hashed passwords, the attacker can't tell whether they are same or not.

Salt is not a secret. The only requirement is, it has to be unique within a given DB. Its existence is just for preventing the attacker to prepare a pre-computed lookup table with passwords and their hashes to do a dictionary attack. But if the password itself is known to the attacker, salt cannot save the user.


Does Off-The-Record protocol provide future (backward) secrecy?

I think so. OTR generates a new DH key pair for each round of message, similar to the DH ratchet in Signal. Also, OTR stands out by having a property called deniable authentication. This basically means the messages are only authenticated during a session between the communicating parties but not after the session. In fact, the MAC key will be revealed after the session is closed.


Why is a smaller value preferred for the public key in RSA?

As you said, choosing a large $e$ can make you vulnerable to attacks such as Wiener attack's because a big $e$ makes it possible to have a small $d$. It will also make the cost of your encryption higher. So big $e$ is not necessarily a problem (if make some verification on $d$, such as $d>\frac{1}{3}\times n^{\frac{1}{4}}$), but not the best choice.

A very common value for the public exponent is  $e=65537$, because $65537 = 2^{16}+1$, which has a nice binary representation (like all Fermat primes):
$$10000000000000001$$
This allow a fast computation using algorithm such as the sliding windows

You could choose $e=3$ for more efficiency, but you have to use a proper padding (RSA OAEP for instance). Using $e=3$ without proper padding will weaker your encryption scheme.

More details can be found in fgrieu's answer to a similar question.


Proper method of writing pseudo random sequences into binary files?

Blum Blum Shub requires larger parameters for security than parameters that are typically suggested for factoring (or QR). See this answer for references.

The short of it is that there are likely no issues with using struct, but that you likely need to use a modulus of $\approx 6800$ bits and extract no more than $5$ bits per iteration to a concretely secure PRNG from BBS.


Testing implementation of cryptography algorithms: Brainstorm

My own algorithm validation for block ciphers consists of the combination of the AESAVS KAT and MCT tests from the NIST CAVP, plus the NESSIE test vector sets, plus an additional MCT of 400 key changes and 10000 inner loops (like the TDES tests). The probability of a block cipher passing all these tests but failing in production is astronomically low.

Once I have generated an entire set of test results, the file is hashed and compared to a known good hash. Each test set is hashed individually. That way I do not need to compare each of the 1000s of results individually. For a complete validation, each result MUST be compared individually.

Stream ciphers are tested similarly, a variety of keys/nonces are used, outputs are generated, and sections of the output are compared against the known answer. Additionally, the entire output can be hashed and compared, although this is slower.

There are also implementation tests, where data is passed to the algorithm that should not be passed, such as invalid key and block sizes. These are necessary to test against fault and overflow attacks, but do not test the algorithm itself.

For hash functions there are similar NIST validation systems in place, one for the SHA1/2 families, which can be applied similarly to other MD type functions like Blake and MD5. This is in addition to the "health test" checks which process about a dozen values of known size and compare the outputs.

SHA3 has a similar validation system, which can be applied to Keccak and other sponge based hash functions.

ECCDH validation is routinely done by KAT and MCT testing, the NIST test only uses 24 KATs. X25519 sometimes (depends on implementation) uses a MCT with 10000 operations, and a short list of KATs.

Other algorithms use similar tests. HMAC testing for example assumes the hash function being used already passed its component test, so the HMAC test is really only testing the HMAC implementation and not the hash function.

Of course, none of these are testing for side channels. Some algorithms have been designed to be free of cache timing and power analysis side channels, but only if they are implemented precisely as designed. A 32-bit integer implementation of X25519 will not be free of side channels. Side channel testing is usually targeted at specific algorithms and implementations, and there is not a one-size-fits all method.


It's been a while since I've read this paper, and I remember having a lot of trouble with this derivation. I'm sure there is an easy way to see it, but I don't see it, so I'll just brute force through with the algabra.

First, some context:

  When the simulator is given a random element as the last term in the tuple the simulator will either abort (and guess $\beta' = 1$ with probability $\frac12$) or guess $\beta' = 1$ [exactly] when the adversary is correct in guessing $\gamma$. However, the $\gamma$ will be completely hidden from the adversary in this case so the adversary will be correct with probability $\frac12$.

I have added the word exactly because actually if the simulator doesn't abort, then $\beta' = 1$ iff $\gamma = \gamma'$. This is seen in the simulator description at the end of section 5.1.

We'll start from your simplified expression for $\mathcal{P}_{BDH}$. We then have
$$\begin{align*}
\mathcal{P}_{BDH}
  &= \frac12\Pr[\textbf{abort}] + \Pr[\beta' = 1|\overline{\textbf{abort}}]\Pr[\overline{\textbf{abort}}] \\
  &= \frac12 + \left(\Pr[\beta' = 1|\overline{\textbf{abort}}] - \frac12\right)\Pr[\overline{\textbf{abort}}]
\end{align*}$$

For the non-aborting case, we know that $\beta' = 1$ if $\gamma = \gamma'$. So if split the case $\overline{\textbf{abort}}$ into two, $(\overline{\textbf{abort}} \land \gamma = \gamma')$ and $(\overline{\textbf{abort}} \land \gamma \neq \gamma')$, we get

$$\begin{align*}
\Pr[\overline{\textbf{abort}}]
  &= \Pr[\overline{\textbf{abort}}] \\
  &= (\Pr[\overline{\textbf{abort}}|\gamma = \gamma']\Pr[\gamma = \gamma']
  + \Pr[\overline{\textbf{abort}}|\gamma\neq\gamma']\Pr[\gamma\neq\gamma'])
\end{align*}$$

Since the adversary has no knowledge of $\gamma$, we may set $\Pr[\gamma=\gamma'] = \frac12 +\epsilon$ (and therefore $\Pr[\gamma\neq\gamma'] = \frac12-\epsilon$). This gets us
$$ \Pr[\textbf{abort}] = \Pr[\overline{\textbf{abort}}|\gamma = \gamma'](\frac12 + \epsilon)
  + \Pr[\overline{\textbf{abort}}|\gamma \neq \gamma'](\frac12 - \epsilon)$$
so our total probability is
$$ \frac12 + \left(\Pr[\beta' = 1|\overline{\textbf{abort}}] - \frac12\right)\left(\Pr[\overline{\textbf{abort}}|\gamma = \gamma'](\frac12 + \epsilon)
  + \Pr[\overline{\textbf{abort}}|\gamma \neq \gamma'](\frac12 - \epsilon)\right)$$

So far so good. Here's where the silly algebra comes in: let's rename these big terms as
$$ \frac12 + (A - \frac12)(B + C) $$
and notice that the desired form, with these new names, is
$$ \frac12 + \frac12(B - C) $$

Next, notice that
$$ A = \Pr[\beta' = 1|\overline{\textbf{abort}}]
  = \frac{\Pr[\beta' = 1 \land \overline{\textbf{abort}}]}{\Pr[\overline{\textbf{abort}}]} = \frac{B}{B + C}$$
so that
$$\begin{align*}
(A - \frac12)(B + C)
  &= \left(\frac{B}{B + C} - \frac12\right)(B + C) \\
  &= \left(\frac{2B - B - C}{2B + 2C}\right)(B + C) \\
  &= \frac12(B - C)
\end{align*}$$
and there you go!


As a high level concept, nondetermistic encryption is where the encryption function takes three inputs, the key $k$, the plaintext $P$ and a random value $R$, generating a ciphertext $C = E_k(P, R)$; the idea is that a) two different random values $R$ gives completely different ciphertexts $C$, even if the plaintexts where the same (or related), and b) no matter what value $R$ we picked, decryption still works, that is, $P = D_k( C )$ (where, in an assymetric system, $k$ may be the private key).

All this should have been covered in your math class; your question is "how does this work in practice?"  Since you mentioned RSA, I'll give you a simple version of it:

RSA has a relatively large plaintext size; for example, 2048 bits.  So, to encrypt a 256 bit plaintext $P_{256}$, what we do is select 1784 random bits $R_{1784}$, and generate an RSA block:

$$01 || R_{1784} || P_{256}$$

The initial byte is a fixed 01 value (so that the resulting plaintext will always be less than the modulus size); the resulting block is precisely 2048 bits long.  We can then give it to RSA, which converts it into a ciphertext.

$$(01 || R_{1784} || P_{256})^e \bmod N$$

We can see that:

Depending on what values we select for $R_{1784}$, the resulting ciphertext will look completely different
The decryptor can easily recover the original plaintext (by decrypting the ciphertext, and just looking at the last 256 bits).

Now, it turns out simple RSA padding schemes like this tend to have issues with chosen ciphertext attacks, and so in practice, we generally use more sophisticated ways of padding the message (that is, don't use the simple scheme I mentioned directly).  However, it should clarify how deterministic encryption can work in general.


What happens after sharing the secret key in quantum cryptographic schemes to send the message bits?

The actual "process upto which the quantum key is shared securely" is nontrivial from an information theoretic perspective, to the point that few people understand it fully (I don't), and some do not even realize that prerequisites include a shared secret. See sections A and B in this for an overview, and section E.1 for why we should take the security claims with more than a grain of salt.

What occurs after that Quantum Privacy Amplification (often called Quantum Key Distribution) step depends on the objective:

If we want confidentiality without unproven mathematical hypothesis (as in the previous step), we need as many key bits as data bits enciphered; and some more for integrity. See C.1 in above link.
Alternatively, if we want a fast link, we use classical cryptography with the key established (perhaps, periodically) by Quantum Privacy Amplification. But we must trust the (symmetric) crypto used, despite lack of mathematical proof that it is safe. See C.2 in above link.


What security risks does exposing the size of the plaintext entail?

Exposing the size of the plaintext has no security risks. The size of the plaintext is always considered public data. It's not done because it has limited benefit.

With a mode like CBC, you cannot encrypt a fractional block. You must pass a whole number of blocks to the encryption function. So you need padding in some form. The ciphertext is a whole number of blocks. If the ciphertext itself doesn't encode the message unambiguously, you need to pass the size separately, at least the size of the last block (or equivalently the size of the padding). In practice, that means you need at least one extra byte to indicate the size. If you do this, then the padding doesn't need to be unambiguous, so you can allow it to be empty if the plaintext happens to be a whole number of blocks. Compared with unambiguous padding, this method results in ciphertext-plus-size that's one block minus one byte shorter if the plaintext is a whole number of blocks, and one byte otherwise. So in terms of ciphertext size, it's a wash.

In terms of ciphertext and decoding complexity, passing the size separately makes things a little more complicated. The ciphertext isn't a black box anymore: the padding size needs to be sent with it. The ciphertext-plus-size can be a black box, but it's a little harder to process: the last pseudoblock is one byte longer than the others.

This scheme does have a security benefit. Since the recipient does not need to decode the padding, it eliminates direct padding oracle attacks, if done right. However this was poorly understood when CBC was in vogue: people generally followed the usual wisdom to verify everything, thus revealing information about the content of the last block. Today, serious protocol designers are well aware of the dangers of padding oracle attacks, but the solution is not to use padding at all.