What is the significance of IV in stream ciphers like Trivium?

Role of IV in stream cipher?

Like in block ciphers; it helps to achieve randomized encryption. Also, using different IV under the same key prevents the crib-dragging attack like in all stream ciphers. This enables us to reuse a key without causing the crib-dragging attack ( that works on two or many-times pad) by using different IVs.

If the IV repeats under the same key, the keystream will be repeated and an attacker will x-or the two or more encrypted messages to the x-or of the messages

$$C_1 = M_1 \oplus keystream$$
$$C_2 = M_2 \oplus keystream$$ then

$$M_1 \oplus M_2 = C_1 \oplus C_2$$ and a passive attacker has the access $C_1 \oplus C_2$ since they are listening the channel. Now, they need to execute crib-dragging and that can be automated.

A Natural Language Approach to Automated Cryptanalysis
of Two-time Pads

  Our method, which is related to HMMs, recovers the most probable plaintext of this
  type by using a statistical language model and a dynamic
  programming algorithm. It produces up to 99% accuracy on
  realistic data and can process ciphertexts at 200ms per byte
  on a $2,000 PC.

It should also be noted that the IVs of such (synchronous) stream ciphers play an important role as a means of resynchronization, e.g. on a per-message basis.

  Can we make IV a secret parameter? and

IV's are public values and never intended to be secured, otherwise, we can call them as the part of the key. Remember the Kerckhoffs's principles; only the key is the secret.

  How IV values are chosen/updated in Trivium?

The Trivium specifications doesn't mention about generating the IV values. We, however, can use the common knowledge about it.

Since the repeat of the IV under the same key can cause catastrophic failures as in all stream cipher that confidentiality is failed. One must guarantee that is is not repeating.

Random IV: Since Trivium uses 80-bit IV, after $2^{40}$ random IV generation it is expected that the IV will be repeating with 50% probability due to the birthday attack. Actually, one must stop way earlier to use the current encryption key and generate/exchange a new one.
Counter/LFSR based IV: Counter/LFSR bases solutions are fine except that on the system failures where the last value of counter/LFSR may not be stored correctly that cause repeats. To mitigate this either generate/exchange a new key or see the next solution.
Random combined with counter/LFSR: This time the randomized part can help to eliminate the system failure even the last values of counter/LFSR are repeating after the system recovery.

$$\text{IV} = \text{[40-bit random]} \mathbin\| \text{[40-bit  counter/LFSR value]}$$

Some Nice crib-dragging answers for more details;

Taking advantage of one-time pad key reuse?
How does one attack a two-time pad (i.e. one-time pad with key reuse)?
Little problem with Vernam Cipher


We are talking about attacking double-DES here, which encrypts a 64-bit block $P$ with two 56-bit keys $K_1,K_2$ as $C = E_{K_2}(E_{K_1}(P))$. As noted by Diffie and Hellman already in late 70s, to attack it with a one or two plaintexts as follows. Suppose we know that $P_0$ is encrypted to $C_0$, then

for all possible $K_1$ compute $E_{K_1}(P)$ (partial encryption) and store the intermediate state $S$ and $K_1$ in a hash table;
for all possible $K_2$ compute $E_{K_1}^{-1}(C)$ (partial decryption) and store the resulting intermediate state $S'$ and $K_2$ in another table;
check if exist such $S = S'$. If so, a pair $(K_1,K_2)$ is a candidate pair of keys.

Since the states are 64-bit, our filter yields $2^{56+56-64} = 2^{48}$ candidate key pairs, which can be tested on a second (plaintext, ciphertext) pair. The complexity of the attack is $2^{56}$, hence Double-DES provides only 56 bits of security.

Meet-in-the-middle attack can be done memoryless in the same way as memoryless collision search with the Pollard's $\rho$-method. Let's recall it.

The collision search for function $F:\{0,1\}^n\rightarrow\{0,1\}^n$ works as follows: start with random $x$ and iterate in parallel $x\rightarrow F(x)\rightarrow F^2(x)\rightarrow \ldots$ and $x\rightarrow F^2(x)\rightarrow F^4(x)\rightarrow \ldots$. When two iterations collide after $i$ steps, we get that $F^i(x) = F^{2i}(x)$, which in turn implies that $F^{i-1}(x)$ and $F^{2i-1}(x)$ are collisions for $F$. This method works for most randomly-looking $F$ and has complexity $O(2^{n/2})$.

For the meet-in-the-middle attack you slightly modify the algorithm. Suppose that you have to find $x,y$ such that $G(x) = H(y)$. In our Double-DES example $G(x) = E_{x}(P)$ and $H(y) = E_{y}^{-1}(C)$. Then you define

$Q(z) = G(z)$ if $z$ ends with 0 (or any other predicate)
$Q(z) = H(z)$ if $z$ ends with 1.

Then you iterate $x\rightarrow Q(x)\rightarrow Q^2(x)\rightarrow \ldots$ and $x\rightarrow Q^2(x)\rightarrow Q^4(x)\rightarrow \ldots$. When you get a collision $Q^i(x) = Q^{2i}(x)$ then with probability $1/2$ the last call for the first iteration was with $G$ and for the second iteration with $H$ or vice versa, so you actually have $G(Q^{i-1}(x)) = H(Q^{2i-1}(x))$, which solves the meet-in-the-middle problem.

Note that we implicitly converted states to keys. This is easy as states are wider, and can be done by simply trimming any 8 bits. If states were shorter, then a more sophisticated procedure had to be used, and the complexity would grow.


Uses of digital signature in asymmetric cryptography

The outer signature protects the ciphertext against change. If the signature is verified before decryption then the signature can for instance protect the ciphertext against padding oracle attacks, both on the asymmetric encryption as well as the symmetric encryption that is commonly within a hybrid cryptosystem.

The encryption of the plaintext and inner signature of course offers confidentiality of the message (see the last section why the signature itself also needs to be encrypted).

The inner signature protects the integrity of the message after decryption. Obviously the outer signature (over the ciphertext) cannot be used on the plaintext message.

So you would either have to store the ciphertext (which means you'd have to decrypt the message with your private key each time to view the verified contents) or you would loose the ability to verify the plaintext message.

However, if you sign the plaintext message as well then you can still verify the message using the sender's public key even after decryption.

Note that encrypting the inner signature prevents an attacker of retrieving information about the plaintext. If it was directly available then the attacker could verify hashes over possible plaintext using the public key of the sender.

For instance, an attacker could verify that the message is "Yes" or "No" by guessing either message and then verifying the signature.


Which is the simplest cryptographic algorithm which is close to commercial-level security?

I would say MiMC is the simplest block cipher with plausible security. The idea is to cube the state, add a random constant, and repeat. This is typically done in a large prime field, but it is trivial to implement field arithmetic in any language with big integer support. Here's a Python implementation:
def mimc(x, p, k, constants):
    x = (x + k) % p
    for c in constants:
        x = (x**3 + k + c) % p
    return x

Notes:

x is the input.
p is the (prime) order of the field.
k is the block cipher key.
constants is a list of r random field elements, where r is the number of rounds. (The paper uses r - 1 constants, since adding one in the final step does nothing for security, but it doesn't hurt either.)
The authors recommend r = ceil(log(p)/log(3)).
The field must be one in which cubing is a permutation, which holds if gcd(3, p - 1) = 1.


The proof is loosely as below.

Lets assume a one round Feistel network, where $2n$ bits are divided into $n$ bits each $L_0, R_0$

The encryption is defined as

$L_{1} = R_{0}, \\ R_{1} = L_0 \oplus f(R_0) $

where f is any random function (PRF) and $\oplus$ is XOR operation

Now the cipher text is $L_{2} = R_{1}, R_{2} = L_1 $

Decryption is same as encryption circuit as defined above.

The input to decryption is $L_2, R_2$.

So decryption is defined as below

$ L_{3} = R_{2} \\ R_{3} = L_{2} \oplus f(R_2) $

Where the plain text should be considered $R_3, L_3$

Now lets substitute from
$ L_{3} = L_{1}, \\ R_{3} = R_{1} \oplus f(L_1) $

Now lets substitute further to get the plain text is $R_3, L_3$ which is $L_0, R_0$ as shown below
$ L_{3} = R_{0}, \\
 R_{3} = L_0 \oplus f(R_0) \oplus f(R_{0}) ,\\
 R_{3} = L_0 $

So it does not really matter if $f(R_0)$ is reversible or not. And the same holds good for any number of rounds.

There is also an intuitive explanation here


Relationship between $N$ and $\phi(N)$ in the RSA algorithm

RSA is based on some mathematical theorems. The first theorem that you need to learn is the Euler's Theorem;  if $n$ and $a$ are coprime positive integers, then

$$a^{{\varphi (n)}}\equiv 1\bmod n.$$ when $n$ is a prime it is the Little Fermat Theorem.

This theorem tell us that in the power we use modulo $\varphi(n)$, i,e, $$a^{x} \equiv a^{x \bmod\varphi(n)} \bmod n $$

When one performs the textbook RSA encryption one calculates $$c = m^e \bmod n$$ and decryption performed as $$m = c^d \bmod n$$

Now, explicitly;

$$c^d = (m^{e})^d = m^{ed}$$ Since we choose $d$ as the inverse of $e$ modulo $\varphi(n)$, $e\cdot d = 1 \bmod \varphi(n),$ then

$$ m^{ed \bmod \varphi(n)} = m^1 = m \bmod n$$

  I tried different N than the actual N (33), it didn't work for any other number other than 33. Why is it so?

Because the calculations that you performed uses modulus other than defined. $m^e$ will be a different number in a different modulus.

Note that: You used $\varphi(n) = (p-1)(q-1)$ when $n=pq$. Normally Chamichael lambda $\lambda(n)$  is used $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ and $$\varphi(n)=\lambda(n)\cdot\gcd(p-1,q-1).$$ This gives smallest $d$ to operate.

Note 2: In the above textbook RSA is used which should never be used without proper padding. For encryption, one should use RSA-OAEP which is introduced by M. Bellare, P. Rogaway. Optimal Asymmetric Encryption -- How to encrypt with RSA and PKCS#1 v1.5 padding. The former is preferable since it has security proof and PKCS#1 v1.5 PKCS1v1.5 encryption is inherently hard to use securely and should not be used.

Actually, we don't use RSA for encryption, We prefer hybrid encryption. RSA is mostly used for signatures and for signatures RSA is used with Probabilistic Signature Scheme (PSS). Again this is introduced by M. Bellare, P. Rogaway; PSS: Provably Secure Encoding Method for Digital Signatures

Remember, RSA Signing is Not RSA Decryption


Performing simple arithmetic operations on compressed, and both compressed and encrypted data

Using generic homomorphic encryption the answer for all three is essentially yes. Although 3. in general is probably mainly of theoretical interest as it would be impractically slow.

For simply compressed data this is simple since compression should not do anything to hide the data. Just decompress, do the operation and possibly compress the result if needed.
For encrypted-then-compressed data this is also easy. Simply decompress and do the operation using the homomorphic encryption and compress the resulting ciphertext. However, you should note that ciphertexts rarely compress very well so it is not often you gain anything from doing this.
For compress-then-encrypt things get a little more difficult. However, in principle fully homomorphic encryption allows you to compute any function on a ciphertext. This includes decompression of your compression function. So what you could do is to run the decompression algorithm using the homomorphic encryption to get an encryption of the decompressed message, then apply any operation needed and finally apply the compress function using the homomorphic encryption to get an encryption of the compressed result. The problem here is that fully homomorphic encryption is really not practically efficient for anything but very simple computations. So doing compression and decompression would probably be completely impractical.


In which order are the round keys used during AES decryption?

If you want to undo the encryption, you'll have to undo the whole sequence of the encryption procedure - i.e. undo each encryption step, in the inverse order.

Encryption has these steps (here for AES-128, the number of rounds differs for other Rijndael versions):

AddRoundKey(State, ExpandedKey[0]

SubBytes(State);
ShiftRows(State);
MixColumns(State);
AddRoundKey(State, ExpandedKey[1]);

SubBytes(State);
ShiftRows(State);
MixColumns(State);
AddRoundKey(State, ExpandedKey[2]);

...

SubBytes(State);
ShiftRows(State);
MixColumns(State);
AddRoundKey(State, ExpandedKey[9]);

SubBytes(State);
ShiftRows(State);
AddRoundKey(State, ExpandedKey[10]);

So, for decryption, you'll have go through this list from bottom to top, undoing each step by applying its inverse transformation.
Luckily, the inverse of AddRoundKey is just AddRoundKey with the same round key, so we get something like this:

AddRoundKey(State, ExpandedKey[10]);
InvShiftRows(State);
InvSubBytes(State);

AddRoundKey(State, ExpandedKey[9]);
InvMixColumns(State);
InvShiftRows(State);
InvSubBytes(State);

...

AddRoundKey(State, ExpandedKey[2]);
InvMixColumns(State);
InvShiftRows(State);
InvSubBytes(State);

AddRoundKey(State, ExpandedKey[1]);
InvMixColumns(State);
InvShiftRows(State);
InvSubBytes(State);

AddRoundKey(State, ExpandedKey[0]);

(Yes, ExpandedKey[0] is the original encryption/decryption key for AES-128.)

So, to answer your question: Round key 9 is the first which gets XORed with the subbytes result, but before that (at the very start of decryption), round key 10 gets XORed with the ciphertext.

As we have to use the same subkeys for encryption and decryption, you'll have to do the same (or equivalent) key schedule, too.

Note that in addition to this straight-forward (or actually straight-backward) decryption, there is an alternative (equivalent) one which uses a different ordering of the operations, and a mixed version of the sub keys (i.e. a changed key schedule).

But I recommend you to stick to this one here, as it is easier to understand. (No, actually I recommend not to implement AES yourself, but use an existing implementation.)


Does selectively generating keypairs with particular public-key hash prefix weaken the security?

Does selecting only keypairs, where a hash of the public key has a particular property, weaken security?

No, if the hash used is independent of the public key cryptosystem. Then the selection of private keys made is equivalent to a random selection, and can't harm security. That's even provable.
In theory you'd have to use separate hashes for this selection and other uses. That can be implemented with separate prefixes for multiple uses of the same hash. In practice, if hashing data starting with the public key is nowhere to be found (e.g. because the public key is only hashed as part of a certificate with a non-empty prefix), one is likely OK with just selection from the hash of the public key, as in the question.


Why does SHA-1 rotate the variables A and B?

Most the other operations you see in the round – XORs and $f_t$ – are bitwise functions. Without rotations every bit would only affect the corresponding bits in the other words and the higher bits in some words due to carry propagation. That means the low order bit would be affected by only the low order bits of the inputs $W_j$ and $K_t$, allowing simple inversion in the case of SHA-0 (where $W_j$ themselves are straight up combinations of input words) and significantly weaken SHA-1 (where $W_j$ are rotated).

So you need some rotations – or other operations like right shifts – to allow bits at different positions to mix completely.

The particular numbers (rotation constants) are not quite as important, but 5 and 30 are are different enough and not large factors of the word size (e.g. consider 16). There are some possibly better ones (pdf), but 5 and 30 (= -2) are also small, which at least used to matter in some low performance computational units.


Find first two blocks of plaintext given a final plaintext block, the IV and ciphertext for CBC?

Let's consider what you know: you have the last block, the IV, and the entire ciphertext. What you don't know is the key or the plaintext. Since CBC-mode encryption uses the IV directly only with the first block you must find the first block, before the IV even becomes useful for your attack. Since the CBC mode uses AES(plaintext[i] XOR ciphertext[i-1], key) and you know the plaintext of the last block, as well as the ciphertext of the previous block you end up with a generic known-plaintext case. So what can you do?

Padding oracle attack:

You already said there's no server for a padding oracle attack so that's not possible

Find the key using a known-plaintext attack on AES itself:

AES is designed to be secure against known-plaintext attacks, so there's not really much you can do. Unless, of course, you know something that the rest of the cryptography community doesn't...

Knowing the IV won't help since the IV only applies to the first block.
You know AES(something XOR iv, key) = ciphertext[0] but since you don't know the plaintext or the key it might as well be AES(something, key) = ciphertext[0]. Knowing what (something) is won't help either since you'll simply end up with another known-plaintext scenario, so even if you got the first block of plaintext as well the key is unobtainable - that's the point of encryption, and a padding oracle is an issue with the mode of operation, not the algorithm itself.
I'm sorry to say, you're SOL.


Can a random permutation be restored / decrypted?

This is basically just a single transposition cipher. The key to the transposition cipher would be a list of the source and destination locations, or just a list of final destinations of the blocks. It's not a very good one because it may well be that you do not swap certain blocks or that you swap something back and forth a few times.

It is not possible for somebody to recover the original file with any kind of certainty. This is not because of the cipher but because a file filled with randoms has no distinguishable information; even if the attacker would guess the key correctly, there is no way for the attacker to verify the result.

It would be easy to guess a few of the blocks right though: just return the ciphertext. The blocks are not shuffled that well, so chances are some of them never changed position; this chance for each block is higher than 1/1000 making the cipher insecure.

For multiple files just containing random information the chances of each file is the same as for a single file. If they were somehow interrelated then the contents would not be random. QED.

(Of course if you'd guess the location of one block right for the first file you'd guess them right for all of them when using the same permutation, but again, no way to verify this.)


What are rounds in the context of ciphers?

Many block ciphers are defined by specifying a round and then running that specification multiple times. For example, in AES, a round consists of the operations SubBytes, ShiftRows, MixColumns, AddRoundKey. That is one round and, to get AES, you run that multiple times (plus some setup and some post-processing).

Thus a round is defined by each cipher and typically consists of a number of building blocks that are composed together to create a function that is run multiple times.


Is it possible to have identical public keys for different ciphers?

There's not really a good way to answer your question other than to explain the concepts involved. The answer can be any one of "yes", "no", or "it depends".

Asymmetric encryption algorithms use public keys that have some structure. For instance, RSA public keys are a tuple of $(n,e)$, where $e$ is the exponent, and $n=pq$ for some primes $p$, $q$ unknown to all but the holder of the private key. In modern systems, $n$ will typically be on the order of 2,048 or 4,096 bits. ECC keys, on the other hand, consist of a point $(x, y)$ on an agreed-upon elliptic curve. In typical ECC schemes, each of these points will be on the order of 192, 256, or 384 bits.

Semantically there will not be colliding keys between these algorithms, because the constituent components of these keys have different meanings. On the other hand, it's technically possible (but exceedingly unlikely in practice) to create, say, a 512-bit RSA key whose $(n, e)$ is also a point $(x,y)$ on an elliptic curve used in ECC. Or, whose bit representation of $n||e$ is equal to the bit representation of a point on an elliptic curve $x||y$.

On the other hand, if two different ECC elliptic curves intersect, you could have a point $(x,y)$ that lies at that that intersection and works for both curves. One could also hypothesize the existence of a future cryptosystem that uses public keys of the form $(n,e)$ as RSA does, but isn't RSA.

However, most cryptosystems that handle public/private keys encode the type of key and additional parameters into the public key file, so it's impossible in practice to ever have a public key that will work natively for two different types of cryptosystems.

TL;DR, it's plausible that one could find colliding keys between different ECC schemes. It's not totally inconceivable to find a colliding key between RSA/ECC by either bit representation or by actual colliding $(n,e)=(x,y)$. And it's not out of the question for some new cryptosystem to reuse keys from an existing cryptosystem verbatim. But in practice, no real world software is likely to be able to use an single public key file for more than one cryptosystem.


One property that this unpadded system is that it is homomorphic; if $A^d = X$ and $B^d = Y$, then we know that $(AB)^d = XY$, and it doesn't matter if we don't know what $d$ is.  More generally, if we have a collection of $H_1, H_2, H_3, ... H_n$, and a collection of signatures $S_1, S_2, S_3, ..., S_n$, then for any set of integers $e_1, e_2, e_3, ..., e_n$, we have:

$$(S_1^{e_1} S_2^{e_2} S_3^{e_3} ... S_n^{e_n})^d = H_1^{e_1} H_2^{e_2} H_3^{e_3} ... H_n^{e_n} $$

So, if we take a large collection of valid message and signatures pairs, hash the messages, and then factor the hashes.  Then, we look for multiplicative combinations of those hashes that yield a hash that we haven't seen (going through a long list of messages to hash); if we find a message that hashes to a value we know a linear combination of, we can immediately deduce the signature.

The attack works for any value of $e$


Can a public key be same as private key?

That's correct. In some cases, you could, if you really wanted, make a public key equal the private key. It would completely negate the benefit of using a public key cryptosystem, though, because access to the public key would imply access to the private key. It would turn it into a crappy symmetric scheme.

As noted in comments, most common RSA implementations set the public exponent to a fixed value, usually a Fermat prime like 3 or 65537. In that case, for an appropriately-sized modulus, there is no chance for the private exponent to equal the public exponent. The private exponent is always larger.


Alternative for RFC 6238/4226 - one time password via SMS (single-factor authentication)

From a security standpoint it is not necessary to reduce the time interval to one second. Your implementation has to assure, that there will be no second login attempt in this time interval.
I recommend to save the latest timestamp and during authentication verify, if enough time has passed, and only then create a new TOTP value and send this via SMS.
This is also, what the TOTP RFC recommends.

Also, the RFC says, that you should use 30 or 60 seconds time intervals.
You should ask yourself: how often will the users try to login?

alphanumeric

The original OTP algorithm by Lamport creates alphanumeric values.
But the problem is, that the use case for the lamport algorithm was a bit different. In my opinion the orignial intend was not to introduce a second factor but to disallow replay attackes.

It is a challenge response algorithm. I.e. you have to make a challenge all the time, you could calculate the response and save the response in the session and send it via SMS. But you also need to assure, that you really create different challenges.

TOTP alphanumeric

The thing with the HOTP and TOTP algorithm is that they were defined by hardware vendors to provide a second (possession) factor. This is probably why the output is ment to be digits and not alphanumerics. digit LCDs are cheaper and digits are easier to display than alphanumerics.

But you could however change the truncation algorithm to generate hex strings or some kind of alphanumeric values.
The 6 digits or 8 digits is just a transformation from a sha1 output. You can also convert the sha1 ouput to lets say to 10 alphanumeric characters.
See https://tools.ietf.org/html/rfc4226#section-5.3

OCRA Algorithm
If you want to be absolutely RFC complient you can take a look at the OCRA Algorithm, which is the third member of the three musketeers HOTP, TOTP, OCRA. This RFC officially allows you to define the truncation function and even skip the truncation completely:
https://tools.ietf.org/html/rfc6287#section-5.2

But honestly running the OCRA add some layer of complexity. I probably would go with HOTP and a modified truncation method.


converting finite field elements to octet strings

Ok,
if there is no standard, then "I do it my way":

Let $i$ be a root of a fixed minimum polynomial of $GF(p^2)$ and $x$ be an element in $GF(p^2)$. Then $x:= x_1+x_2*i$ can be represented as a vector $(x_1,x_2) \in GF(p)^2$.
Now convert $x_1$ and $x_2$ with the FE2OSP function form IEEE P1363 and concatenate them
$FE2OSP(x_1)|| FE2OSP(x_2)$.

An elliptic curve point $(x,y) \in E(GF(p^2))$ can then be represented either compressed or not compressed.

not compressed:

$04|| FE2OSP(x_1)|| FE2OSP(x_2)|| FE2OSP(y_1)|| FE2OSP(y_2)$

compressed:

$02|| FE2OSP (x_1)|| FE2OSP (x_2)$ if $LSB(FE2OSP(y_1))=0$
$03|| FE2OSP(x_1)|| FE2OSP (x_2)$ if $LSB(FE2OSP (y_1))=1$


Does AES encrypting /dev/zero and feeding output to AES again increase entropy of the ciphertext?

First lets quickly analyze your commands:

$(dd if=/dev/urandom bs=128 count=1 2>/dev/null | base64) : take a block of 128 pseudo-random bytes and put it into a single line encoded as base 64, throwing away anything printed to standard error
openssl enc -aes-256-ctr -pass pass:(1) -nosalt < /dev/zero :

perform OpenSSL key derivation on the base 64 string from step (1) without a salt: basically two subsequent runs of HMAC-MD5 to create 256 bits of output;
use the resulting key to perform AES-256 CTR encryption on an endless stream of zeros to get to the counter mode key stream;

pv -pterb > file : perform some metrics before dumping the key stream to file.

Now your question is if you would replace the /dev/null with the input file, using a new block of 128 bytes taken from /dev/urandom as password. Well, the good news is that it will add another amount of randomness to the original stream. How much entropy that entails depends on the internal characteristics of the used /dev/urandom implementation. Of course, if you would use the original password then you would cancel out the operation and produce a file with all zeros.

Using CTR to create a fast PRNG is a good idea that is used quite a lot. But remember that although it is very fast, it doesn't reseed. Using /dev/urandom is a bad idea if you want to have as much entropy as possible though. For this kind of use /dev/random is a better choice.

Using a bad password generation mechanism such as the default OpenSSL one will however bring back the maximum amount of entropy to 128 bit max due to MD5 being used to derive the key. If you consider that you could have up to 128 bytes of entropy, that's quite a shame. You would be better off using the -K option which allows for hexadecimal encoded keys instead. In that case you retrieve 32 bytes of randomness and use the full 256 bits of that directly for AES-CTR.

So if you want to increase the possible entropy, try and use this:

openssl enc -aes-256-ctr -K "$(dd if=/dev/random bs=32 count=1 2>/dev/null | od  -v -An -tx1 | tr -d ' \n')" -iv 00000000000000000000000000000000

and use it on any number of zeros. Note that on some systems this may deplete the entropy pool if you perform a lot of these commands.

Here -K is used to replace the password with a 256 bit key, which is supplied in hexadecimals using the dd if=/dev/random bs=32 count=1 2>/dev/null | od  -v -An -tx1 | tr -d ' \n') command, where od creates hexadecimals including spaces and newlines, which are removed using the tr command. The IV can be kept to all zero as the key will differ for each command anyway.

Final note: writing random data to an intermediate file is usually not a good idea. You are much better off programming this. In case you require OpenSSL then you could use C or any wrapper library for your choice of language that gives you enough functionality.


Finding the subgroup in isogeny-based cryptography

While there is a sub-exponential attack to compute isogenies on ORDINARY elliptic curves (the basis for the Rostovev and Stulbunov paper that you reference) there is not (yet at least) a sub-exponential attack to compute isogenies on SUPERSINGULAR elliptic curves.  The cryptosystem proposed by DeFeo, Jao, and Plut back in 2011 is based on Supersingular rather than ordinary elliptic curves.  Microsoft Research recently published a paper on this cryptosystem.  The paper contains a good overview of research on this problem to date. An preprint of Microsoft's paper is found here.


Is this an acceptable All-or-Nothing Transform?

Have I missed something? is this really an AONT?

An iterated hash doesn't make a secure stream cipher. If the attacker can guess $m_i$, they can calculate $w_i \oplus m_i = H^i(m_0)$, then decrypt the rest of the message by taking hashes of that value.

An option would be to use the hash function like a block cipher in counter mode $w_i = H(m_0||i)$. That should be secure.

  I'm sure there are faster / better approaches to AONTs, but is this terribly bad? is it any better than others in any respect?

If will likely be significantly slower than just using AES or a stream cipher for the encryption and a hash to make the key depend on the rest. Hash functions don't always produce a lot of output fast.

The advantage is that you only depend on one primitive. If you wanted that, you could use a hash function with a stream cipher mode, like Keccak (which SHA-3 is based on). That should be faster.

  What should be asked of the hash function H? collision resistance? pre-image resistance?

The hash function should be (first) preimage resistant and a PRF. Collision resistance doesn't matter unless the attacker can control or at least predict the random $m_0$.

  Is it having a (pseudo-)random source a bad thing? would it be any better if the construction above were to replace m0 (randomly generated) by H(m)? would it be any worse? (at the very least, it would make the wrappings of two identical messages the same).

No, it's a good thing. A deterministic $m_0 = H(m)$ would, for example, let an attacker verify any guess of the message $m$ with high likelihood from just a single $w_i$. Just transform the guess message and see if any block matches.


Can ElGamal encryption and ElGamal signatures be used together sharing the same key-pairs?

It depends.

It depends on a lot of things. For example a generator of 2 is great for encryption, but makes for awful signatures. If you use a generator of 2, then no. Your signatures will get broken. Then the encryption will.

Elgamal signatures are pretty controversial. They're tetchy to get right (see above) and there are many things you can get wrong. Also, they're large, when compared to DSA. DSA is a modification of Elgamal signatures and designed so that the size of the signature is proportional to the size of the hash, not the size of the key. They're thus smaller.

They were added into OpenPGP for RFC 2440, and implemented in GnuPG but not in PGP, because of security/implementation concerns that PGP developers had. A serious bug was found in the GnuPG implementation and then were removed from GnuPG, and then from RFC 4880 as no one was implementing them.

Ask yourself why you're doing them rather than DSA, research the problems people had in the past, and make sure you've done it right.

Jon


Pollard's Lambda algorithm ecdlp with Pohlig Hellman

If the question is "can I solve the ECDLP by combining Pohlig-Hellman and Pollard's lambda", then the answer is yes, provided your $p-1$ is smooth enough.

First off, as mentioned in the comments, a search interval of $[0, 2^{40}]$ is quite doable with Pollard's lambda.

Factorize $p-1$ to get all the $B$-smooth prime factors; let's say there are $k$ of them, the ${r_k}$. Then run Pohlig-Hellman on each of them and obtain the secret key mod $r = \prod_i^kr_i$. If the order of your base point on your curve is $Q$, then your search interval looks like $[0, Q/r]$. So $Q/r$ puts the bounds on how long you would expect the lambda algorithm to find a collision.

What's a good $B$ for smoothness? Now this is implementation-dependent, so that depends on what you're working with and how long you have to wait. In practice, I found that if you factorize $p-1$ up to about $2^{20}$, and you have a few primes of that size, and the order of your base point is much smaller than $p-1$, that cuts $Q/r$ down to a reasonable size, but of course your experience may differ.


Can this be considered as Encryption

If the sequence of necessary moves is treated as the key, yes.

  how secure can this encryption scheme be?

First some details about the cube:

6 faces, each with 9 pieces visible each. Because the faces share some pieces, and the immovable cube center is not visible, there are only 26 pieces in total: 6 centers (of faces), 8 corners (each with 3 colored sides), and 12 edges (each with 2 colored sides).
The center piece of each face is, like the cube center itself, not movable. If it is "moved", in reality everything else moves.
The 8 corner pieces always are corner pieces, independent of any moves. Same goes for the. 12 edge pieces.
There are 8! possible position combinations of the 8 corner pieces (naturally). In their position, 7 of the 8 can have 3 possible "rotations", just the last one depends on the others. With this, there are corner $8! \cdot 3^7$ possible corner positions
Similarly, 12! combinations of edge pieces are restricted to $\frac{12!}{2}$ by the corner pieces (for details to everything, see Wikipedia).

Now, we have 9 pieces that contain "good" data: 1 face center, 4 edges (each has two more sides with nonsense data), and 4 corners (each 1 more side with nonsense data). The other 17 pieces contain only nonsense data.

If an attacker wants to (bruteforce-)find the center piece with the good data on it, there are 6 possibilities (6 face centers, just turning the whole cube around to find the right one).

Then there are 4 corner pieces where position and orientation matters, and 4 others that don't matter to find the one good-data face. Meaning, $\frac{8!}{4!} \cdot 3^4$ possibilities to try here.

Finally, 4 edge pieces where position and orientation matters, and 8 others that don't matter to find the one good-data face. Meaning, $\frac{12!}{2} \div \frac{8!}{2} \cdot 2^4$

Multiplying...

$6 \cdot \frac{8!}{4!} \cdot 3^4 \cdot \frac{12!}{2} \div \frac{8!}{2} \cdot 2^4 = 155196518400$ or about $2^{37}$

Your key has 37 bit. With todays computer, that's nothing =>
completely insecure

Aside from that ...

A "padding" of 45 byte for 9 byte payload is impractical
A cube that contains the same symbol multiple times is less secure
The scheme isn't protected against things like known-plaintext attacks etc.etc.
Properties like the avalanche effect etc., etc. are completely missing
Depending on the choice of padding data, just making statistics what symbols exist might be enough to figure the plaintext out
... and many more


Is it bad to tell someone what encryption algorithm your system uses?

No, it's not bad to tell this info. In fact, it's suspicious when someone doesn't reveal the design of the system. Kerckhoffs's principle states that a system must remain secure so long as an attacker knows everything except a designated secret "key".
For symmetric encryption, "key" means secret keys. For asymmetric cryptography (signatures and key exchange) that means private keys. For password storage, that means the passwords themselves (and possibly a "pepper" value, if used).
I'd personally assume that anyone who isn't familiar with this is hiding a backdoor in their system. If the cryptography isn't auditable, it's safer to assume it's insecure and use an auditable (open-source or at least source-available) implementation whenever possible.


Does side-channel attacks offer any difficulty to Stinson's concept of `provable security'?

Say there is a proof that a cryptosystem X satisfies Stinson's definition. An attacker builds a method to break X by side-channel attacks. Does that offer any trouble to the definition or to my proof?

Not generally: The proof covers the algorithm, and side channel attacks target the implementation.

If someone threatens to hurt you unless (or until) you give them your private key, that doesn't violate the provable security claim of the algorithm.

The algorithm is an abstract idea, and the provable security guarantee would indicate that no other abstract idea (algorithm) could violate the security without providing a solution to another abstract problem.

  Or would you say side-channel attacks have nothing to do with provable security?

More or less, yes; You can't have provable security against rubber hose cryptanalysis, you can't provide security if the attacker is watching over your shoulder as you perform the algorithm with pencil and paper, you can't have security if your program prints it's state at every step of the way to a log file the adversary has access to, etc.

Basically

Proofs rest on assumptions (even if they're not stated explicitly). If you violate those assumptions, then you can skirt around the guarantees provided by the proof.

This is one reason why provably secure algorithms would ideally be combined with side channel resistant techniques (e.g. constant time code, blinding, etc) and formally verified implementations.


What is the difference between authenticating and signing a document?

Authentication can either mean entity authentication or data authentication.

Data authentication is a means to demonstrate that some specific data originates from a specific source and has not been modified during transmission and/or upon storage. It can be achieved by the use of digital signatures in a public key, i.e., asymmetric, setting or message authentication codes (MACS) in a secret key, i.e., symmetric, setting. Digital signatures support public verifiability and thus using the respective public key (which is assumed to be known by anyone) given the signature and the data anyone can check if the data has been authenticated by the holder of the corresponding private key. In contrast, using MACs only support private verifiability, i.e., only parties holding the respective secret key can verify whether a given data has been authenticated by any of the other parties holding the respective secret key.

Entity authentication is a means to prove to someone else that the entity it is speaking to is indeed the entity it is claiming to be. This can be achieved by various means such as challenge response authentication protocols (which may be based on digital signatures).

Often this is not explicitly stated, but it should be clear from the context what type of authentication one is referring to.


Example of partial homomorphic encryption over $\mathbb{F}_{2^k}$?

I think you are making a classical mistake: $\mathbb{Z}_{2^k}$ is not $\mathbb{F}_{2^k}$. Concatenating $k$ ciphertexts homomorphic over $\mathbb{Z}_{2}$ gives an encryption scheme homomorphic over $\mathbb{Z}_{2}^k \approx \mathbb{F}_{2^k}$, but this is not $\mathbb{Z}_{2^k}$ - intuitively, $\mathbb{Z}_{a} \times \mathbb{Z}_{b} \approx \mathbb{Z}_{ab}$ only when $a$ and $b$ are coprime.

So, if what you want is really an additively homomorphic encryption scheme over $\mathbb{Z}_{2^k}$, there is one: this paper describes an extension of the Goldwasser-Micali encryption scheme which does exactly this.

If, however, you need an encryption scheme over $\mathbb{F}_{2^k}$, then there is not really any alternatives to concatenating encryptions over $\mathbb{Z}_{2}$, except using an appropriate scheme based on LWE - but I'm not sure whether this would improve a lot over the "naive" solution, I do not have a good knowledge of lattice-based cryptography.


Why does TinyJAMBU-128 claim only 112-bit security?

I believe this is simply a statement of the intention to meet the submission requirements set out by NIST for lightweight ciphers.  Note that the paper linked in the question refers to "security goals".
As per section 3.1:

An AEAD algorithm shall not specify key lengths that are smaller than 128 bits. Cryptanalytic attacks on the AEAD algorithm shall require at least ${2}^{112}$ computations on a classical computer in a single-key setting. If a key size larger than 128 bits is supported, it is recommended that at least one recommended parameter set has a key size of 256 bits, and that its resistance against cryptanalytical attacks is at least $2^{224}$ computations on a classical computer in a single-key setting.

Note that these are the final submission requirements from 2018.  It seems the figure for 192-bit is deduced from the requirements for 256 bit, or is perhaps referencing earlier requirements.


Does RSA-OEAP have integrity and authenticity properties?

INT-CTXT and INT-PTXT are usually on considered for private-key encryption.  For public-key encryption, no correct encryption scheme can satisfy those requirements.  (Proof:  The adversary can run the encryption algorithm on an arbitrary message and submit it as its output.  Since it made no queries to its encryption oracle, this ciphertext violates both INT-CTXT and INT-PTXT security.)


In NTRU digital envelope, do everyone know the hash function $H$ used?

Yes, these are public parameters of the system.

Note that NTRU is not implemented exactly this way any more. The most up-to-date current spec is EESS#1, which can be obtained from https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/doc/EESS1-v3.1.pdf.


Early propagation of carries in the BLAKE hash function

This is already covered by Ella's response, but in short the added nonlinearity at the start buys you very little in terms of security, compared to its cost in number of operations. It would be more effective, and make for a simpler design, for example, to trade all these constant xors by an extra round. Since that part of BLAKE was not pulling its own weight, as noted by the cryptanalysis of the various weakened versions of BLAKE, it was removed.

But besides the small effect on nonlinearity, there is another reason for the existence of the constants—to eliminate symmetries on the underlying block cipher. BLAKE, as well as BLAKE2, are modes of operation on top of a $\{0,1\}^{1024}\times\{0,1\}^{1024}\to \{0,1\}^{1024}$-bit (or $\{0,1\}^{512}\times\{0,1\}^{512}\to\{0,1\}^{512}$) block cipher $E(k, m)$, inspired by the ChaCha core. And like the ChaCha core, when the message words $m_i$ are all 0, or more generally all equal, if the inputs $x_i$ are also, say, all equal, the output words $y_i$ will also be all equal. For example,
$$
E\left(
\begin{pmatrix}
m & m & m & m \\
m & m & m & m \\
m & m & m & m \\
m & m & m & m \\
\end{pmatrix},
\begin{pmatrix}
x & x & x & x \\
x & x & x & x \\
x & x & x & x \\
x & x & x & x \\
\end{pmatrix}
\right) =
\begin{pmatrix}
y & y & y & y \\
y & y & y & y \\
y & y & y & y \\
y & y & y & y \\
\end{pmatrix}\,,
$$

for some 32- or 64-bit word $m$, $x$, and $y$. This property, often called a symmetry of the round function, makes the underlying block cipher of BLAKE—without the constants—easily distinguished from an ideal cipher. Likewise with BLAKE2. This is even exploited in the "chosen-IV" attacks of a weak variant of BLAKE2.

However, in the actual mode of operation of either BLAKE or BLAKE2, these so-called symmetric states are unreachable by design, via the inclusion of the $IV_0$–$IV_7$ constants in the initial state, so this property is not a security liability.


"Double Encryption" using the same cipher?

When I think of encryption and doubling it, I believe the strength of encryption, in the case of AES, as being tied to the number of rounds through the algorithm.

I don't believe that's the best way to think of things.
The strength of the encryption really is 'how much work does an attacker need to do to perform the attack'.
For a cipher, there are two strategies:

We can just go through all possible key values, and see which one 'works'

We can rely on cryptographical weaknesses within the cipher itself

Increasing the number of rounds can plausibly (not always, but in practice, appears to) make the cryptographical weaknesses within the cipher harder to exploit, but (unless increasing the number of rounds also increases the number of key bits), doesn't do anything to slow down brute force attacks (apart from a constant factor).
As far as we know, there are no known cryptographical weaknesses in
AES-256 (apart from some related key attacks, typically not applicable), and so adding more rounds doesn't increase security in any meaningful sense.
Now, it would look like running the text through two separately keyed AES-256 would double the number of key bits, and so significantly increase security.  However, it turns out that there is a better-than-bruce force attack; this involves encrypting the plaintext with all possible AES-256 keys, decrypting the ciphertext with all possible AES-256 keys, and then searching for a match.
Of course, the amount of work involved is ridiculous; it will never be the case that anything involving $2^{256}$ operations will be feasible; this can be shown by thermodynamics and the minimal amount of energy needed to perform any operation.
This implies that, barring a cryptographical advance that allows us to break AES-256 with significantly less than $2^{256}$ operations, it'll be safe.
Which leads us directly to the next topic:

I have read some whitepapers on cascading encryption, but they referred to using two different ciphers, not the same cipher twice.

This potential cryptographical weakness is precisely why people use distinct ciphers.  There might be a weakness in AES-256 that makes the cipher significantly weaker than our current understanding; however, if we perform AES-256 encryption, and then (say) Camellia-256 encryption, then the resulting cipher is strong unless both AES-256 and Camellia-256 are weak.  It is possible that there is a weakness in one of the two ciphers; it is considered far less likely that both contain weaknesses.


RSA and other public-key protocols assume that the keys are securely delivered. To quote "Introduction to Modern Cryptography" by Lindell and Katz:

  Call the receiver Alice and the sender Bob. [...] We emphasize that the channel between Alice and Bob may be public, but is assumed to be authenticated, meaning that the adversary cannot modify the public key sent by Alice to Bob (and, in particular, cannot replace it with its own key). [...] An [...] approach is for Alice to generate her keys (pk, sk) in advance, independently of any particular sender. (In fact, at the time of key generation Alice need not even be aware that Bob wants to talk to her, or even that Bob exists.) Alice can widely disseminate her public key pk by, say, publishing it on her webpage, putting it on her business cars, or placing it in a public directory.

(Bold emphasis mine)

So, having said that, you're right that the system assumes the keys will be communicated in an authenticated manner. But also the committee member is right in that hacking the website would constitute a valid attack. When you define your threat model, it should be clear if an undetected hack of the website is within it and appropriate measures be taken. For example, if it is considered a reasonable threat, then the keys can be communicated by business cards handed in person or through a web-of-trust, among many key distribution mechanisms.


What is the impact of different modes on pseudo randomness of AES?

Yes, of course other modes have been studied.

See this paper for one study, and that paper for another study.

The bottom line is that CFB, OFB and CTR modes are also good PRFs (assuming you use random IVs).

As for ECB mode, it is a good PRF if you limit it to inputs of precisely one block (128 bits for AES); it is not a good PRF if you are allowed to submit larger inputs.


How to choose the reduction function in rainbow tables?

No, the way to define the reduction functions isn't related with the hash function used.

Let's consider that we want to recover a password $pwd$ knowing $hsh = H(pwd)$ where $H$ is a hash function. So we will compute a rainbow table for a certain set of passwords $\mathcal{P}$. Note that when the hash chains are computed, at each step $i$ we apply the hash function $H$ and a reduction function $R_i$ (note that several reduction functions are used to avoid collision problems).

A distinction must be made between the hash function $H$ and the reduction functions $R_i$. The reduction functions are used to map hash values produced by $H$ back into values in $\mathcal{P}$.

So the way to define the reduction functions $R_i$ depends on how you chose the set $\mathcal{P}$. For example $R$ can be the decomposition in base $n$ where $n$ is the size of $\mathcal{P}$ (the incrementation functions $R_i$ can be simply defined by incrementing the input of $i$ and then apply the decomposition).

The Wikipedia page also gives an example:

  An example for a reduction function: Given a 32 bit hash, get the last
  6 characters in the hash.


Does homomorphic encryption hide the algorithm itself?

FHE does not offer circuit privacy by default, but can it can be upgraded to do so:

https://eprint.iacr.org/2016/164.pdf
https://eprint.iacr.org/2016/381.pdf

In brief, the extra cost for circuit privacy is actually very small (just a few noisy-dummy bootstraps at the end of your circuit)... in the honest-but-curious model ! For stronger variants of circuit privacy, you need to certify that the FHE public key is correctly generated; and FHE public key are already quite large, so I let you imagine how proving ZK statements about them would be.


1/4 oblivious transfer construction from 1/2?

No, your proposed alternative allows the attacker to deduce things beyond the value he selects.

For example, suppose that during his OT transfers, he decides to learn the values $s0$ and $s2$, allowing him to recover $m0 = c0 \oplus s0 \oplus s2$.  That is intended to be allowed, and so is fine as far as it goes.

However, the receiver can also deduce the value $m1 \oplus m2 \oplus m3 = c1 \oplus c2 \oplus c3 \oplus s0 \oplus s2$.  As the receiver is supposed to learn only the value he selected ($m0$ in this case), and nothing about the other messages, this is a violation of the OT properties.


Usage of different size chunks during AES encryption/decryption

To see the problem, let's see how I would chain up a single function (call it $AES\,CBC_k(iv, m)$) which only encrypts a single block at a time into something that can encrypt "chunks" of any size.

Let $m=m_1||m_2||m_3||m_4$ be the message I want to encrypt. Each $m_i$ is a single block (in AES it is 128 bits). I want to use $AES\,CBC_k$ to encrypt $m$. The proper way to do this would be to compute:

$$c_1=AES\,CBC_k(iv, m_1)$$
$$c_2=AES\,CBC_k(c_1, m_2)$$
$$c_3=AES\,CBC_k(c_2, m_3)$$
$$c_4=AES\,CBC_k(c_3, m_4)$$

Then let $c=c_1||c_2||c_3||c_4$ be the ciphertext. Using this process (note how the iv changes from block to block), we could build another function, say $E_k$ which encrypts messages of any length (actually a multiple of the block size).

To illustrate your problem, let's split $m$ into two chunks: $m_1||m_2$ and $m_3||m_4$ and see what it sounds like you are doing. It sounds like you are calling $E_k(iv, m_1||m_2)$ then $E_k(iv, m_3||m_4)$. This is like doing the following.

$$c_1=AES\,CBC_k(iv, m_1)$$
$$c_2=AES\,CBC_k(c_1, m_2)$$
$$c_3=AES\,CBC_k(iv, m_3)$$
$$c_4=AES\,CBC_k(c_3, m_4)$$

Notice the iv for $c_3$ and compare it with the iv for $c_3$ in the correct operation above.

So, if you really want to encrypt the way you are talking about doing, you would need to use the last block of the previous chunk as the iv for the next chunk. Managing this yourself in code, while do able, is somewhat of a pain. I'm willing to bet there is an encryption library for PHP that can so this for you (on file streams or something so the whole file doesn't have to be in memory).

The real question
So it sounds like your real question is how to encrypt large files in php without having to read the whole thing in to memory. I don't use PHP much, so I can't really comment. I will say don't use the solution here as it was obviously not designed by anyone who knows anything about cryptography. I know in other languages (Java, c#) you can pass in a file stream to be encrypted in most libraries, which probably solves the problem of having to read in all the memory. Not sure if PHP has something like that though.

Update
It looks like php has encryption filters that you could use with stream_filter_append to encrypt streams so that the file doesn't have to be loaded into memory. Then you would have a stream to read from and a stream to write to. Simply read from the input stream and write to the output stream. The encryption happens automatically thanks to the filter.


HMAC is a type of MAC. The output of a MAC is called a "tag". Not all MAC (algorithms) are HMAC.

MACs are not required to be one-way or collision resistant for someone who knows the key. HMAC, however, inherits the one-way-ness and collision resistance of the underlying hash function.

A CBC-based MAC is mentioned as a hint because it is almost trivial to find preimage values for any given tag value. That also makes collision attacks trivial.


Trying to find an algorithm to share portions of a key with multiple people

What you are looking for is called secret sharing. It is a well studied problem and you should be able to find lots of information now that you know what to search for.


If the resulting hashes were the same, a non length-constant check would compare every byte of the resultant digest. This would take the most time to compare.

Lets say it takes 90.00ms to run the KDF, and 0.90ms to do a full length compare (not real numbers but good enough for the example)

If the password was "hello" instead of "Hello", it is probable that the digest will have a different first or 2nd byte, which means a comparison would determine they are different much faster than if they were the same. Instead of 90.90ms, it may take 90.10ms.

If the attacker is capable of measuring the cpu usage or cpu power draw, they may be able to measure the quantity of keystrokes, giving the attacker the length of the correct password. They may also be able to compare the time it takes between key presses to better determine what combination of key presses was entered. The attacker may be able to get much more information that that, maybe less, but every bit of information the attacker gets will help them attack the KDF and recover the password. Knowing that a specific combination is correct is a huge amount of information.

This is why constant time comparisons are so important, because it is extremely easy to put in bogus passwords and get a timeframe of how long it takes to compare incorrect results, so when the correct result is compared it will take longer, and be detected by whatever mechanism (software or hardware) is measuring them.


Why is RSA preferred over Diffie-Hellman if they're both used to establish shared key?

RSA is rarely appropriate instead of DH for key exchange. It's mostly only appropriate if backwards-compatibility is required, or if keys need to be sent from one party to the other instead of generated for each session (eg for encrypting e-mail).

RSA is much, much harder to use securely. RSA requires padding of the messages, which is quite easy to screw up in ways that catastrophically break the security of the system. RSA is far more expensive to use in an ephemeral mode, and thus typically cannot provide forward secrecy. RSA keys are substantially larger than ECDH (Elliptic Curve Diffie-Hellman) keys. RSA key generation is much more complex (and harder to get right) than (some) ECDH key generation: RSA needs to generate large prime numbers & ensure that they are safe, while X25519 or X448 ECDH systems can use any random number of the appropriate length.

Where possible use ECDHE (Elliptic Curve Diffie-Hellman, Ephemeral). If you can't do that, use DHE. If you can't do that, use ECDH. If you can't do that, use DH. If you can't do that, THEN use RSA.

RSA can also be used as part of a signature scheme, but that's not relevant to this question since it's not comparable to DH which only does key exchange. TLS 1.3 uses RSA only for signing the DHE or ECDHE key exchange, and also supports ECDSA for signing.

NaCL, Libsodium, Libhydrogen, TLS 1.3, monocypher, and probably a few other libraries and cryptographic standards have dropped the use of RSA for key exchange.


In general, assumptions that have been around for a long time are considered far preferable to new ones. Although a new curve is not strictly a new assumption, these curves do have special structure and so may contain surprises. This is not to say that they do contain surprises, and indeed they are not vulnerable to any KNOWN attacks (but that is only what is known). Also, note that EdDSA may be less side-channel resistant than expected, as shown in Daniel Genkin's talk at RWC 2018.


Forge CBC-MAC by creating a new message, given the MAC of two messages

That doesn't look likely.

Given $\text{CBC-MAC}(d||e) = y$, we know that, saying at the initial IV state of $0$, then processing the blocks $d$ and $e$ gives us $y$; that doesn't say where we end up at any other starting state.

If $c$ was a single block, what we'd need to happen is to have it reset the state to 0 (and then the $d$ and $e$ would be processed as expected).  That is, we would need to set $c$ so that $\text{Encrypt}_k( c \oplus x ) = 0$, or in other words, $c = x \oplus \text{Decrypt}_k(0)$.

That's where we get stuck; we can use $\text{CBC-MAC}$ as an encryption oracle (given a block $t$, what's $\text{Encrypt}_k(t)$?), but not as a decryption oracle; there's no query we can make that we tell us, given $t$, what's the value of $\text{Decrypt}_k(t)$.


I hashed my bag and in it I put... "Is there a hash for unordered items?"

You could use a hash tree for this purpose. It wouldn't have the properties of your "hash", exactly, but it would work for the game.

Use a secret key to derive individual keys for the leaves, e.g. $k_i = H(k, i)$. Have each leaf be a keyed hash of an item in the bag, $h_i = H(k_i, v_i)$.

Then produce a normal hash tree by hashing two leaf values, then pairs of those values, etc. until you get the root, which you publish. You could add any number of dummy leaves (random values) and make the leaves exist at different depths to hide the number of items in the bag.

To show something was in your bag, you'd reveal the leaf key for that item, as well as all the internal sibling hashes up to the root. That would not reveal any other items, since their leaf keys would be secret.


Why are bitwise rotations used in cryptography?

A bit rotation of a $w$-bit word by $r$ bits to the right transforms a $w$-bit word $X=(x_{w-1},x_{w-2},\dots,x_1,x_0)$ into the $w$-bit word $\operatorname{ROTR}(X,r)=(x_{r+w-1\bmod w},x_{r+w-2\bmod w},\dots,x_{r+1\bmod w},x_{r\bmod w})$.
Depending on context, $r$ is arbitrary in $\mathbb Z$, or constrained to some interval thereof, e.g. $0\le r<w$.
Rotation to the left can be defined as $\operatorname{ROTL}(X,r)=\operatorname{ROTR}(X,(-r\bmod w))$.

For any fixed $r$, $X\mapsto \operatorname{ROTR}(X,r)$ is a bit permutation. Under function composition, bit permutations of $w$-bit words form a finite group of $w!$ elements, of which bit rotations of $w$-bit words for fixed values of $r$ form a commutative subgroup of $w$ elements, isomorphic to $(\mathbb Z_w,+)$.

Bit permutations of $w$-bit words, including bit rotations by a fixed $r$, are not by themselves useful cryptographic transformations, because the above groups are so small subgroups of the group of bijections over $w$-bit words (which has $(2^w)!$ elements), or of the monoid of functions over $w$-bit words (which has $2^{w\cdot 2^w}$ elements).

However, bit rotations are useful in cryptography when combined with other common operations on $w$-bit words, such as other bitwise operations ($\operatorname{AND}$, $\operatorname{OR}$, $\operatorname{XOR}$, $\operatorname{NAND}$, $\operatorname{NOR}$..), and addition modulo $2^w$. That's for a number of reasons:

Rotation combined with other operation(s) allows to build arbitrary transformations of $w$-bit words. For example, by combining (a sufficient number of) $\operatorname{ROTR}$ (with $r=1$), $\operatorname{NAND}$, and some fixed constants, any function over $w$-bit words can be constructed (thus including any bijection, thus any bit permutation). By contrast, when $w>1$, this can not be achieved using any combination of $\operatorname{AND}$, $\operatorname{OR}$, $\operatorname{XOR}$, $\operatorname{NAND}$, $\operatorname{NOR}$, and addition modulo $2^w$ (because none of these operations can make bit $x_1$ on input influence bit $x_0$ on output). Stated otherwise: rotation is one of few ways to achieve diffusion from high to lower-order bits (right-shift, division, and table lookup are others).
More generally, rotation allows a cipher designer to create diffusion, at will, among bits of different rank in computer words, as emphasized in this other answer. Shifts allow that too, but when shifting by more than a few bits are too strongly surjective have too many distinct inputs reaching the same output for many cryptographic uses. Other techniques are used to create diffusion among different computer words.
Availability, speed and low cost: on many CPUs, rotation is the only bit permutation available as a single native CPU instruction (discounting the possibility to implement a permutation by a table read for small $w$). All modern computer CPUs, and many modern embedded CPUs, have a dedicated barrel shifter that can rotate over its natively supported word size(s) $w$, for any $r$, as fast as any other data manipulation goes. Rotation for other width $w$ not supported in hardware can be efficiently constructed in software. In hardware, rotation by a fixed $r$ requires no gate at all (like any bit permutation) thus is extremely fast and cheap.
No timing dependency: on all CPUs, rotation for fixed $r$ has duration independent of the data manipulated; this extends to variable $r$ when there is a barrel shifter. By contrast, table-lookup (another popular way to achieve diffusion to the right) often exhibit timing dependency, due to cache misses or memory alignment, which might allow timing attacks.

Many symmetric cryptographic primitives (hashes, block ciphers..) make heavy use of rotation by a fixed $r$, for the above reasons. Some (notably RC5) use variable rotation, though I have not seen this trend catching. I guess that could be (rightly) for fear of timing dependencies and other side-channels on CPUs without a barrel shifter supporting the rotation's width.


How to let CA signed x509 key work in OpenPGP mailing system?

The fact that you bought a certificate from an X.509 certification authority doesn't matter to any OpenPGP implementations I know of: when your friend opens the message you just sent them in their OpenPGP-enabled mailer, it won't care a whit about the X.509 CA a priori.

Not only would you have to shoehorn your certificate into the OpenPGP message format, but you would have to teach their mailer software to interpret it, and teach your friend to accept that particular CA.  It might be easier to teach your friend to accept S/MIME, if you really insist on this particular X.509 CA, with the caveat that S/MIME is a dumpster fire of shoddy '90s crypto engineering—or it would be easier to just use OpenPGP, which is also a dumpster fire of shoddy '90s crypto engineering but gets incremental improvements from time to time.


What should be the size of a Diffie-Hellman private key?

Well, yes, that is generally good advice about DH.

Here is some background on this: support you were given a value $g^x \bmod p$, and you were also told that $1 \le x \le A$ for some value $A$.  If so, then there are several known attacks (such as Big Step/Little Step and Pollard's Rho) that can recover $x$ in about $\sqrt A$ steps.  If we have as our security goal that it should take at least $2^{128}$ steps, then means that $\sqrt A \ge 2^{128}$, or $A \ge 2^{256}$, that is, we take our private exponent $x$ to be a random 256 bit number (note: in this context, we count it as a 256 bit number even if the msbit happens to be zero).

Now, there are a few other notes I want to leave you with:

There isn't much point in making the private exponent much larger than that; there is another avenue (Number Field Sieve) which also can solve the Discrete Log problem in time which is independent of the size of the exponent, but only depends on the size of the modulus.  For realistic modulus sizes, this will also be around (or, at least, not significantly more than) $O(2^{128})$ steps, so making the private exponent significantly bigger will just make your computations more expensive, without making the system any more secure in any real sense.
One minor point about SRP (as opposed to straight DH); the protocol does leak the LSbit of the initiator's private exponent (by leak, I mean that someone listening to the messages being exchanged can deduce that bit value).  I don't believe that that's a big deal (as it's only 1 bit, and nothing else is leaked).  If you want to be pedantic, I suppose you could have the initiator pick a 257 big private exponent (so there will still be 256 unknown bits).


Why does the WhatsApp protocol require elaborate computation when verifying user keys?

I agree with the comments, in that the aim of step 1 is likely to increase the cost of performing a man-in-the-middle attack. When two users want to verify their keys, the only information they rely on is that the 60-digit number derived from both their keys matches. Hence, an attacker would need to generate an expected $2 \cdot 10^{30}$ random Curve25519 keys to find two keys that generate a matching 60-digit number. Since a security level of $2^{101} \approx 2 \cdot 10^{30}$ is a little weak, additional SHA-512 operations are added to make brute force costlier (although this technically does not raise the security level, since that is generally measured in terms of the key length and not the number of operations).

Steps 2 to 5 are just to make the output human readable. See this blog post on Signal for more information on why they chose this format.

Hashing both public keys and then concatenating the first 30 bytes would also be fine, and it would in fact give you a higher security level, but then you'd end up with 60 bytes, or 120 hexadecimal characters, to compare.


Securely rekey/re-encrypt AES-encrypted file

Well, if you use AES in counter-mode, you could give the proxy the XOR of both counter-mode streams; he could then XOR in that XOR with the file encrypted with one key, and that'll give him the file encrypted with the other.

This does have the drawbacks:

This XOR is as large as the file you've encrypted
This XOR is specific to the IV you used to encrypt (and so if multiple files are encrypted this way, you'll need a separate conversion key for each one)
There is no integrity checking on the encryption format.

On the other hand, if we allow the use of public key encryption methods, we can do this with Integrated Encryption Scheme.

Here, the public key is a value $A = g^a$, and ciphertext consists of a pair $g^x$ and the actual message encrypted using symmetric crypto keyed based on the value $C = A^x$ (and so the holder of $a$ the private key can compute $A^x = C^a$, and then use that to decrypt the symmetric portions.

Now, this allows a conversion key $y = ab^{-1} \bmod q$ (where $q$ is the size of the subgroup we're working in); then, the proxy can compute $D = C^y$, and then substitute $D$ in place of $C$ in the ciphertext.  Then, the holder of $b$ the other private key can compute $D^b = C^{(ab^{-1})b} = C^a = A^x$, and then use that value to decrypt.

And, the value $y$ (and the values of the public keys $A, B$) does not give the proxy enough information to deduce the private key values.


To sign a message $M$ under RSA, one should NOT build the signature as $\mathcal{Sign}(M)=M^d\bmod N$, for several reasons:

either that limits to messages $M$ in range $[0..N-1]$, or that allows forgeries of the form $\hat M=M+k\cdot N$, because $\mathcal{Sign}(\hat M)=\mathcal{Sign}(M)$;
that allows forgeries of the form $\hat M=R^e\cdot\prod{M_j}^{a_j}$ because $\mathcal{Sign}(\hat M)=R\cdot\prod{\mathcal{Sign}(M_j)}^{a_j}\bmod N$.

For some safe ways to use RSA to build signatures, see PKCS#1 or ISO/IEC 9796-2 (the first signs short messages only, therefore it is customary to use it to sign a hash of a message, rather than the message; the second always use a hash).

Public key certificates are signed messages including a public key, and additional informations usually including the identity of the legitimate holder of the corresponding private key, the identity or/and reference of the signer,  the rights of the holder of the private key...


Discrete logarithm on Montgomery curve twist

So I guess I'll answer myself as I finally figured it out:

twist of a curve is a curve - all possible curves with same A are isomorphic to either $B=1$ (your base curve if you use usual curve) or $B=-1$ (your twist curve) curve, so just pick whichever and be consistent.
every Montgomery curve has Weierstrass curve. Your choice of B matters which one you get exactly, but end result will be same.
(not every Weierstrass curve has Montgomery curve, but you already have equivalent curve - your original twist curve)
so map points to Weierstrass form, get logarithms by baby step giant step (or other fast algorithm), map points back, for each prime on the twist you'll get two answers ($k$ and $-k$).
if there are z primes, then $2^z$ answers can be reduced to just $4$ in $O(z)$ steps with Chinese Reminder Theorem and filter.
that doesn't give you unique answer, but very small number ($4x4$ in my case), so you can just test them all.

I didn't completely follow the math for factors of $2$ and duplicate primes. Twist order has factor of $2^2$ and then only unique primes, that's presumably why it's been $4$ not $2$.

I'm sure there's some way to optimize higher powers of same prime, I just didn't need it.


Is the following protocol perfect zero knowledge or computational zero knowledge?

This is Blum's protocol for Hamiltonicity. The answer to your question depends on the commitments. There are two possibilities:

The commitments are perfectly hiding: in this case, the proof is perfect zero knowledge, but is only an argument (meaning that soundness is computational, and so only holds against a polynomial-time cheating prover).
The commitments are perfectly binding: in this case, the proof is only computational zero knowledge, but is a proof (meaning that soundness is unconditional).

Note that no commitment scheme can be both perfectly binding and hiding. In addition, the class of perfect zero knowledge proofs (unconditional soundness) is contained in $AM \cap co-AM$ and so is very unlikely to contain an $NP$-complete problem.


However, none of these suggestions have been accepted in the NIST standard.

The suggestions are to use a different group. Those are not changes that could be done to the standard without complete loss of compatibility. They are things to consider when designing and choosing new algorithms, however.

  Or is the probability to get a weak key (assumed that one is using secure random number generators) still so so small that the existence of weak keys is negligible?

Yes. From Saarinen's risk analysis:

  The probability of randomly hitting an exploitable weak key with a real-world AES-GCM cryptographic protocol such as SSH [4], IPSec [6] or TLS [12] is vanishingly small.

No protocol that I know of uses GCM with a 64-bit cipher (like 3DES or Blowfish), which Saarinen calls out as risky and recommends against.


Yes, actually it is rather trivial.

First we need to dive a little bit into how elliptic curves work. Take a finite field, usually $\mathbb F_p$ for some fixed prime $p$. We call the set of all pairs $(x,y)\in\mathbb F_p^2$ satisfying the equation $y^2\equiv x^3+ax+b\pmod p$ the elliptic curve $E_{a,b}(\mathbb F_p)$.

First we note that $(0,0)$ is on the curve if and only if $b=0$. However, for practically used curves this is not the case. So we can conclude that your request doesn't actually ask for the point which gets encoded to $(0,0)$ (because it isn't on any curve) but rather for the semantic point $0$ that fullfills the same role as the $0$ for the integers, the rationals, the reals, that is the role of the additive neutral element in a group. The encoding of $\mathcal O$ as all-0x00 bytes is confirmed in SEC 1 v2 section 2.3.3 (PDF).

Now we commonly write the points on an elliptic curves as a group, because we can add them, we can subtract them, they have a neutral element $\mathcal O$ ("the point at infinity") and addition is associative.

Now that we have made use of 3 of the 7 usual parameters for elliptic curves, let's look at the rest. Two parameters encode the base point, that is a point $G=(g_x,g_y)$ on the curve which is fixed and used as the reference element for all cryptographic operations. In fact the private key $d$ to your public key point $Q$ has to satisfy the relation $Q=[d]G$, that is addition of $G$, $d$-times with itself yields $Q$.

So now for the last two parameters. Remember when we talked about the curve being the set of all points? It turns out that we actually need to know how many there are. This is called the order of the curve and is not encoded usually in the domain parameters. However, the order of $n$ of the base-point is encoded and that is precisely the integer such that $\mathcal O=[n]G$, so the "private key" to "0x0000...000" is actually directly encoded in the domain parameters.

To satisfy the curiosity you surely have: The last value encoded is the co-factor, that is the quotient of the curve's order and the base-point's order, we need this for some computations.

If you are now asking yourself, whether $n$ is the private key, then the answer is "no". It is the private key that is smaller or equal to $n$ and larger than $0$, however, any multiple of $n$ will work. That is $d'=2n$ will work just the same as $d''=3n$, because in this setting they designate the same as all scalar factors are reduced $\bmod n$ and $0\equiv n\equiv 2n\equiv 3n\equiv\ldots\pmod n$.

On a final note (as pointed out by @fgrieu in the comments): No sane implementation would accept $\mathcal O$ as a public key (section 3.2.2.1 of SEC 1 v2 (PDF)), because it would offer no security as discussed above. On key generation there's also the standard restriction that $0<d<n$, meaning no sane implementation would ever generate $\mathcal O$ as the public key (section 3.2.1 of SEC 1 v2 (PDF)).


Cryptsetup | Given Enough Passphrase Entropy, Is It Necessary To Use a High Iteration Count?

If you are certain that the passphrase contains enough entropy, then iteration is not needed. The iteration is only required when the entropy is low. The only way to preclude brute force search through a small search space is to make each guess take a prohibitively long amount of time. This is why the iteration count is recommended to be high: To ensure that nobody can guess more then a small number of passwords per second.

If the passphrase contains 256 bits of entropy, then it does not matter how fast the hash can be computed - the search space is simply too large for anyone to search through, regardless of how fast they can look.


How do I prove that this PRNG is easily distinguished from a random sequence of numbers (modulo m)?

Well, this is essentially homework (it wasn't assigned, however you are attempting to learn from it), and so I won't give you an explicit answer; instead, I'll try to point you in a direction where you can figure out the answer yourself.

First of all, how would you solve this if you were given the values $a$ and $m$?

Once you have answered that, let us assume that you were given the output of such a sequence, and also given the value of $m$.  How would you recover the value $a$?

Now comes the hard part, let us assume that you were given the output of such a sequence, but did not know either $a$ or $m$; how would you recover the value $m$?

Hint on the last question: let us assume we were given three consecutive values $b_1, b_2, b_3$ with $b_2 = a b_1 \bmod m$, $b_3 = a^2 b_1 \bmod m$; how can we combine the values $b_1, b_2, b_3$ to come up with some value which is a multiple of $m$?  (Hint: consider $b_2^2$ and $b_1b_3$)?  How can we use that to recover $m$?

Last question: let us assume that the sequence we were given was not generated by such a generator; what happens when we attempt to recover $m$ using the above procedure?


Arbitrary length to multiple of block size

In CTR mode, Enc is done as

CT = Enc(k,PT) = Enc(k,ctr) xor PT

The decryption is similar to encryption except you XOR Cipertext(CT) instead of Plaintext(PT).

PT = Dec(k,CT) = Enc(k,ctr) xor CT

So there is no need for plaintext to be multiple of block length and no need of padding because the PT or CT never become the input of the block cipher. Its the counter which is encrypted to generate a random stream and then Xored with plaintext or ciphertext. You can use the required length of generated bit-stream and discard the remaining.

More Details and picture Credit of CTR MODE


I don't know the solution, but since you say you're only asking for hints, here's a few that occurred to me:

If this is a Vigenère cipher, the missing character at the beginning should not matter (much): if you encrypt a message with the key FOOBAR and drop the first letter of the output, you can decrypt the resulting ciphertext with the key OOBARF.
As ewanm89 notes, the obvious way to attack a Vigenère cipher, after you've determined the key length is $n$, is to write it with $n$ letters per row and attack each column as if it were a Caesar cipher.  There are automated tools for doing that, such as pygenere; they may not always give the correct answer for very short messages, but yours looks long enough that they should at least have a decent chance.
The most notable feature I see in your ciphertext is that the string HIMFTF occurs twice, at offsets 26 and 86.  That does strongly suggest that the key length may be a divisor of 60; alas, 60 has lots of small divisors (including 6, which you believe the key length to be), so that doesn't really give that much information.  It does at least rule out 7, 8 and 9 as likely key lengths.


Universal hashing techniques based on matrix multiplication

The source of this result, although it can be found in many other places, is the  Wegman-Carter paper 'Universal classes of hash functions'. More specifically, Proposition 9 in page 151.


What is the use of SCRAM-SHA-256 (over SCRAM-SHA-1)?

Nobody should use a primitive which is known to be broken in any new development or deployment. Anything involving SHA-1 is basically deprecated at this point.

A break in collision-resistance is a crack that might be exploited further by follow-on research; this happened with other hash functions in the past. Attacks only get better, they never get worse.

Besides, SCRAM-SHA-1 really isn’t deployed widely enough  for interoperability to matter.


s = 4(10 - 9 * 7) mod 17 = 8

That should be:

s = 4(10 + 9 * 7) mod 17 = 3

If you modify the rest of the example to account for this, the example works.


security of a block cipher mode of operation

No, this mode as listed does not provide integrity of the decrypted plaintext.

An active attacker can flip arbitrary bits from the first 64 bits of the decrypted plaintext freely without causing a decryption failure.  He can do this by modifying the $iv$; the decrypted $tag_0$ will authenticate (because the $iv$ is not used to compute that), and then the decryption process will apply the modified $iv$ to the decrypted $plaintext_0$


Non-malleable file encryption using AES XTS 256?

As Paŭlo Ebermann notes in a comment above, the time cost of a proper MAC calculation is almost certainly negligible compared to the cost of reading or writing the data on the disk.

Applying a MAC to each encrypted sector (and the sector number used to derive the IV) will fully protect your data against most forms of tampering.  The main drawback of this method, of course, is the need to store the MAC outputs somewhere so that they can be verified when the data is read back.  But, of course, the same drawback applies to your proposed "encrypted CRC" method as well.

As for the security of using an encrypted CRC as a MAC, it probably depends on details of the way the encryption is done (and I'm not aware of any security analyses of such a scheme in combination with XTS mode).

In particular, if the sector data was encrypted using CTR or OFB mode (or something similarly malleable), then the linearity of CRCs would allow bit-flipping attacks to be done in a way that does not change the CRC checksum.  As Wikipedia notes, this was one of the main weaknesses in the (by now thoroughly broken) WEP protocol, which used an encrypted CRC for integrity protection.

On the other hand, if one were to encrypt both the data and the CRC using a wide-block encryption mode like CMC or EME, this would probably be secure, at least if the CRC was long enough to resist brute force.  Then again, in that case we could presumably achieve equivalent security just by replacing the CRC with a block of zero bytes of the same length, and checking that they're still zero after decryption.  And it would presumably still be slower than XTS plus a proper MAC.

Note that one form of tampering that even proper per-sector MACs will not prevent is a "reversion attack" where the attacker replaces the entire contents of a sector with previously captured ciphertext from the same sector, in effect reverting the corresponding plaintext data to an earlier version.  To prevent such attacks, you could for example compute an additional MAC (preferably of the Carter–Wegman type, such as VMAC or Poly1305, since those can be efficiently updated when part of the input data changes) over the per-sector MACs, and verify that global MAC when the disk is mounted.

Of course, even such a global MAC will still not protect you against whole-disk reversion attacks, where the entire content of the disk is replaced by an earlier copy of it.  In general, there is no way to prevent such attacks unless some data (like a copy of the global MAC) can be securely stored somewhere outside the disk itself.

Also, avoiding accidental MAC verification failures e.g. in the event of a power loss during a write is possible but rather tricky.  Basically, it would require some kind of a secure intent log where you first write an (encrypted and MACed) record of the data you intend to write and the way this will affect the global MAC, flush it to disk, and only then perform the actual write to the rest of the disk.  Done properly, that should ensure that, at any given point in time, either a) the rest of the disk is in a consistent state and properly MACed, or b) the intent log is consistent and properly MACed, and the rest of the disk can be brought to a consistent and properly MACed state by replaying the planned changes recorded in the intent log.  Of course, if you do all that, as a nice side effect you'll also gain extra resiliency against accidental (as well as deliberate) data corruption.


I have encountered PGP quite often in the business world, but never any use of the "Web of Trust". People just send each other their public keys over email and then check fingerprints over a phone call, or merely hope for the best. (I really encountered a customer who insisted on checking the fingerprint over a phone call, but that happened only once over the last 15 years.)

The "Web of Trust" mechanism does not map well to the business world. Arguably, it does not map well to the world in general. The main problem with the Web of Trust is that it conflates two concepts into one property: the identity, and the ability to authenticate.

For instance, suppose that Alice sign's Bob's key, then Bob sign's Charlie's key. The "Web of Trust" posits that if I already know Alice's public key, then I can gain some confidence in Bob's and Charlie's public keys. However, this is not really true. I know Alice and I know that she would not sign Bob's key unless she has thoroughly verified that she was talking to the real Bob, and signing a public key that is really under the control of Bob. However, I do not know Bob. For all I know, Bob could be very gullible, or prone to sign keys late at night after too many whiskies. Thus, I cannot really trust that the apparent Charlie's key really belongs to Charlie. In other words, Alice asserts that a given key belongs to Bob, but not that Bob is a reliable person who will apply all proper identity checks before signing other keys.

In the PKI world (X.509 certificates), things are hierarchical, and when a CA signs a key (i.e. issues a certificate), it can make an assertion on the reliability of the target entity: a CA may issue a CA certificate to a sub-CA (the Basic Constraints extension in that certificate will contain the cA flag set to TRUE), or an end-entity certificate (the cA flag is FALSE). In the former case, the CA delegates its power, while in the latter it does not. This is the main difference between X.509 PKI and the PGP Web of Trust. PGP lacks the distinction that is expressed by the cA flag in X.509 certificates. A consequence is that the PGP Web of Trust is rather useless, and this may go a long way towards explaining why nobody uses it.


Sequence of Encrypting RSA like Chaum Blinding scheme

A much better way to choose r is

while 1:
    s = random.getrandbits(KEYSIZE+privacyparameter)
    r = 1+(s%(n-1))
    if gcd(r,n) == 1: break;

.
privacyparameter is chosen by the blinder.

If $\:$ gcd(m,n) = 1 $\:$ then the statistical distance between the distribution of blinded_token and

the uniform distribution on units mod n is less $\:$ n/((2^(KEYSIZE+privacyparameter+1))-(2*n)) $\;$.

The signer does not need to know or care what that value is.

It's much better to create $\;\;$  blinded_token $\:$=$\:$ (m * (r^e % n)) % n $\;\;$,

so that the size of the output won't leak much information about m.

The signer computes $\:$ (blinded_token)^d % n $\:$ and sends that to the blinder. $\:$ If the signer instead

signed or decrypted the token in the standard way, then the blind signature scheme wouldn't work.

If $\;\;$ (signers_response)^e % n $\:$=$\:$ blinded_token $\;\;$ then output

((signers_response)*modinv(r,n)) % n $\;$ as the unblinded signature, else reject.

There are two further subtleties for this blind signature scheme:

gcd(blinded_token,n) = 1 $\;$ if and only if $\;$ gcd(m,n) = 1

However, as alluded to in the one of the OP's comments to this answer,

the hash can to chosen to guarantee that $\:$ gcd(m,n) = 1 $\;$.

(So, hopefully, "sha_digest" is something that does so, rather than just one of the SHA functions.)

Also, if the RSA function does not define a permutation over $\mathbb{Z}_n^*$, then blindness

does not necessarily hold even if all relevant values of m satisfy gcd(m,n) = 1.


Give a distinguisher to differentiate between PRP and RPO

As you do not specify what the domain of the function is, I'm going to assume that we're talking about functions of the form $f:\{0,1\}^n \to \{0,1\}^n$.

The distinguisher works as follows:

Let $q(n)$ be some polynomial.
Choose $q(n)$ many distinct elements from $\{0,1\}^n$. Call them $x_1,\dots,x_q$.
Query each $x_i$ to the oracle and record the result as $y_i$.
If there exists any $y_i=y_j$ with $i\neq j$, output $0$, otherwise output $1$.

If the oracle is a PRP, then it is by definition a permutation (i.e. has no collisions) and since $x_i\neq x_j$ for all $i\neq j$ the distinguisher outputs $1$ with probability $1$.

If the oracle is a truly random function, then each $y_i$ is uniformly and independently distributed. The probability that there is at least one collision among $q(n)$ randomly sampled elements of $\{0,1\}^n$ is $$1-\prod_{i=1}^{q(n)}\frac{2^n-i}{2^n} \geq 1$$ and therefore the distinguisher will output $1$ with probability $1-\varepsilon(n)$ for some $\varepsilon(n)\geq0$.


Do PBKDF2 keys generated at a lower iteration count leak information?

Knowledge of server_password computed with 3,000 iterations instead of 50,000 makes it over 16 times faster to brute-force inputted_password and find encryption_key than was otherwise possible.

server_password can take much more values ($2^{256}$) than inputted_password can be tested, and PBKDF2 behaves like a random function, thus the first inputted_password found matching (if any) is the true one with overwhelming certainty.

Having found inputted_password, the adversary computes encryption_key by applying the same relatively low cost technique that generated it in the first place. That also allows to check that inputted_password is right (that is, the user did not misskey while s/he was tricked to use a lower iteration count; but even if that was, that could be worked around by trying small variations).


Imagine you have a function like this: $$f(x) = p_3(p_2(p_1(x))).$$
Now imagine that you find a pair $\Delta_0, \Delta_1$ such that $p_1(x \oplus \Delta_0) = p_1(x) \oplus \Delta_1$ with probability $2^{-n_1}$, $\Delta_2$ such that $p_2(x \oplus \Delta_1) = p_2(x) \oplus \Delta_2$ with probability $2^{-n_2}$, and $\Delta_3$ such that $p_3(x \oplus \Delta_2) = p_3(x) \oplus \Delta_3$ with probability $2^{-n_3}$. Then:

$\Delta_0 \xrightarrow{f} \Delta_3$ is a differential for $f$ (with probability at least $2^{-n_1 n_2 n_3}$ if we can assume independence);
$\Delta_0 \xrightarrow{p_1} \Delta_1 \xrightarrow{p_2} \Delta_2 \xrightarrow{p_3} \Delta_3$ is a differential trail, also known as differential characteristic, for $f$ (with probability $2^{-n_1 n_2 n_3}$ if we can assume independence).

So, a differential trail contains not only the input and output differences going into your function, but also all of the intermediate values (and respective probabilities). You can also say that a differential is the combination of all the differential trails with the same input and output values.


What you are looking for is so called white-box cryptography. That said, you should definitely check if you can't get away with digital signatures. The reason is that white box cryptography is a special case of program obfuscation that is quite hard to achieve. Existing, practical schemes do not rely on hard problems but rather on not being broken so far. So you do not get rigorous security guarantees but only the statement that nobody that tried did succeed (which says nothing about how many tried and who tried...).


Yes the adversary can guess the plaintext, and there is some probability $p$ his guess is correct. There is no way we can prevent that, and this is not a security flaw of the encryption scheme.

If the homomorphic encryption scheme you use is IND-CPA secure (or equivalently, semantically secure), the ciphertext should be indistinguishable. It entails that any (PPT) adversary cannot gain useful information from the ciphertext about the plaintext, hence the ciphertexts do not give the adversary any advantage in guessing the correct plaintext. So without the ciphertext, the probability of guessing correctly is $p$, and with the ciphertext, the probability of guessing correctly is $p+\epsilon$ where $\epsilon$ is negligible. Thus the ciphertexts, although are produced from the plaintexts, are useless from the adversary's point of view.

So the takeaway message is that security of an encryption scheme is not defined in term of "plaintext cannot be recovered" (which is impossible to achieve), but in terms of "the scheme does not make it easier for the adversary to recover the plaintext".


Even in a perfect world (the random oracle model) there's no way to ensure first-preimage and second-preimage resistane of more than $2^n$ and collision resistance of more than $2^{n/2}$. (Wie $n$ bytes as the output size of the hash function.) That's the maximum you will ever be able to archive.

Cutting off some bytes of the output of a secure hash algorithm doesn't hurt the security more than you have to expect. With an output of $8$ bytes ($n = 64$ bits) from (for example) SHA-256 you have first-preimage and second-preimage resistance of $2^{64}$ and collision resistance of $2^{32}$.


Does the adversary know the random seed s?

No. Let $G$ be an arbitrary PRG. Given the seed $s$ and a string $y$, it is trivial to check whether $y = G(s)$, thus the output of a PRG cannot be indistinguishable from random if the seed is known. Therefore, this definition would be uninstantiable and thus not useful.

  If he does not, isn't one possible construction simply the random seed itself?

A family of functions $G : \{0,1\}^{i(\lambda)} \to \{0,1\}^{o(\lambda)}$ needs to have two properties to be called a PRG.

It needs to be expanding, i.e. it must hold that $o(\lambda)>i(\lambda)$.
It must hold that or a uniformly chosen seed $s\gets\{0,1\}^{i(\lambda)}$, the value $G(s)$ is computationally indistinguishable from a uniformly chosen string $y \gets \{0,1\}^{o(\lambda)}$.

The PRG you are suggesting is the identity function, which does indeed fulfill property 2 from, above, but not property 1.

  if the output needs to be bigger than random seed s cant I just add a hardcore bit to the random seed s?

Well, the identity function does not have any hardcore predicates, so this does not work.

  Also, regardless of the number of leading bits of the output that are revealed (even n-1 where n is length of output), will the output be computationally indistinguishable from a truly random string?

By definition of a secure PRG, the entire output is computationally indistinguishable from a truly random string. So by a trivial reduction, so is any prefix of the output.


Breaking ElGammal encryption of two different mesagges

Further hint: suppose we computed $q = (p-1)/2^\lambda$ odd, and given $(u_1, v_1) = (g^r, m y^r)$, we compute $(g^r)^q, (m y^r)^q$.  Once we have done that, how can you distinguish the $m=1$ and $m= -1$ cases?


Creating cryptographic algorithms at runtime

This doesn't add new security as much as it just shifts it.

Encryption algorithms are carefully studied.  Hmm... I didn't make that emphatic enough.  Encryption algorithms are C A R E F U L L Y studied.   There. That's better.

There are all sorts of tiny nuances to be had when designing an algorithm.  A famous example were some of the  S-Boxes in DES which were developed in a classified environment.  Many thought they were a NSA backdoor.  Several years later, differential cryptoanalysis was "discovered," and suddenly we found that these S-Boxes were the thing that prevented such an attack (thus the NSA had clearly known about these attacks for some while).  This was not a "just got lucky by combining the right bits" thing.  It was carefully thought out.

So the likelihood that your mix-and-match algorithm is breakable is far greater than any of the carefully studied algorithms.  Far greater.  Its basically guaranteed that a dedicated attacker will break your algorithm.  The thing you have bought is anonymity.  By using a publicly accepted algorithm, you are using an algorithm that provides great value to attackers to break.  If they get access to your little secrets, they also get access to things like bank mainframes.

So you make yourself weaker against a reasonably determined attacker while making yourself a bit stronger against a very strong attacker like a state.  Or do you?

A final issue to deal with is that you're mixing and matching known algorithmic pieces, and from your comments the pieces you choose are know in public.  These algorithms were carefully studied, as I said before.  This also means the attacks that these algorithms had to be tuned against are also well known.  So all one needs to do is identify which basic pattern you are using, pull up a list of known attacks against it, and find out what attacks work.  Which puts you in a strange corner where an AI might actually have enough data available to it in a convenient enough form to take your encryption on.

And that would be something a highly skilled attacker would be able to do, so you didn't really solve anything.