ECDSA signing and verification between Python and JS I'm trying to have Python (2.7) and JS solutions for ECDSA signing (with secp256k1 curve) where ideally signatures generated by one side can be verified by the other.

For the python side, I'm using the ecdsa library:

from ecdsa import SigningKey
from ecdsa.curves import SECP256k1
ecdsakey = "59b1ad799522457fa5ed171cb850800fe511e55181d81250e66d42ff536427a1"
sk = SigningKey.from_string(ecdsa_privkey, curve=SECP256k1)
hash = "b93b25c03a2238e749272a99d8a47dbcc19c2db65b9b27671f1ec6b5defd279b"
print(hash)
hash = codecs.decode(hash, 'hex')

sig = sk.sign_deterministic(hash)
print(codecs.encode(sig, 'hex'))
vk = sk.get_verifying_key()
print(vk.verify(sig, hash))

For JS, I'm using secp256k1:

let hash = "b93b25c03a2238e749272a99d8a47dbcc19c2db65b9b27671f1ec6b5defd279b";
hash = Buffer.from(hash, 'hex');

// generate privKey
let privKey = "59b1ad799522457fa5ed171cb850800fe511e55181d81250e66d42ff536427a1";
privKey = Buffer.from(privKey, 'hex');

// sign the message
const sigObj = secp256k1.sign(msg, privKey)

console.log(sigObj.signature.toString('hex'));

// get the public key in a compressed format
const pubKey = secp256k1.publicKeyCreate(privKey)

// verify the signature
console.log(secp256k1.verify(msg, sigObj.signature, pubKey))

Both of the above work fine on their own, the signature is verified as expected. The problem arises when I try to get the signature from JS and verify it using Python or vice versa.

The signature generated by Python is:
3fa041c044403331c19767e2c4ff3a44e764ec7bdbb7fffa190157ffbe3f9ba317c1ff5254fef28597862a7adec3699cb0fda0ec003b3d9d28b554b321006ee8
So I feed it into secp256k1.verify:

let signature = "3fa041c044403331c19767e2c4ff3a44e764ec7bdbb7fffa190157ffbe3f9ba317c1ff5254fef28597862a7adec3699cb0fda0ec003b3d9d28b554b321006ee8";
signature = Buffer.from(signature, 'hex');
console.log(secp256k1.verify(msg, signature, pubKey))

The signature generated by JS is: 062a87f01f86a540c6c28dcfb7b59ed85ea72ef3549bc1ddff8bb08cbabcc6b444a13bab43c82521cf3440db8619ab1ac14d46b4b696dd506fd5b104c06366dc
So I feed it into the verifying key:

sig = "062a87f01f86a540c6c28dcfb7b59ed85ea72ef3549bc1ddff8bb08cbabcc6b444a13bab43c82521cf3440db8619ab1ac14d46b4b696dd506fd5b104c06366dc"
sig = codecs.decode(sig, 'hex')
print(vk.verify(sig, hash))

Above throws BadSignatureError

So my question is: is there any setting or something else I'm missing that I need to set in order to have the two solutions be cross-compatible?

It seems that the python library is actually re-hashing the hash you're passing it, since you are using the verify method of a VerifyingKey object, which is performing a hash computation on the data you're passing to it.
You might want to try passing the hash's pre-image to Python, or try hashing that hash again for JS, to have them interoperate...

You can also read this part about OpenSSL compatibility for Python's ecdsa lib.

I'm not really sure what secp256k1 library you are using for JS, but my answer assumes that the library is directly signing the data you're passing it, without hashing it first, or that the hash used by default by both library is not the same.


Is it safe to use signed messages from a private key to send to clients as tokens? My custom web server software uses a 'server identity' which is a public/private bitcoin keypair. It's for extremely limited resource environments ie..IOT, which is why I don't use a common stack with OAuth etc..
I use the private key to sign certain messages I send to the app clients, so they can verify authenticity.  The server is very much stateless, I don't wish to store any more data that I need to (auth tokens).
Are there implications to just signing a message, sending it to client as token, which they will send back in the authorization header with an expire timestamp? I will verify on the server. Not storing any tokens.

They should be. As long as your signature scheme is resistant to existential or at least selective forgery, [under chosen message attack]. Well, I am not sure if the scheme requires resistance to forgery under chosen message attack unless you set up your application in which your server works as a signing oracle but no worries, most state of the art signature schemes are resistant to existential forgery under chosen message attack. As long as you don't use outdated signature schemes, the ones that hash the message directly using MD5 or SHA1, the signature can be forged by creating hash collisions.
In fact that's what popular JWT tokens are. They are just base64 encoded json objects with some content (like who it is issued to, expiry time etc),which may or may not be encrypted, and appended with a signature of that content produced using server's private key (or alternatively contains a MAC of the object produced using a key secret to the server but this method has a disadvantage in that no one else can verify the authenticity of the token).


Shamir's Secret Scheme : Knowing the threshold If I am decoding a key by applying shares, is it possible to know when the threshold has been reached, and the secret revealed, without having to be told what the threshold is?

Also, is it possible to determine if a share is a "valid" share (ie originally generated by SSS for a given secret)?

Yes. If all of the shares you have are valid, you can tell when you have reached the threshold. Reconstructing the secret from $t+1$ shares will yield the same result as reconstructing the secret from $t+2$ shares. Reconstructing it from $t-1$ will however (always) yield a completely different result. Reconstructing the secret from $t-2$ or fewer shares will yield a different result with probability $1-1/q$, provided that all of the coefficients (except order $0$ and order $t-1$) are selected uniformly from $\mathbb{Z_q}$ and the high order coefficient uniformly from $\mathbb{Z_q^*}$. If "weak sharings" are avoided by selecting all coefficients to be non-zero, the probability will be slightly off.

For instance, if you are using Lagrange basis polynomials for reconstructing the original polynomial, adding more shares over the threshold will not increase the degree of the resulting polynomial and the zero degree term will remain constant.

There exist variants of Secret Sharing that will allow you to verify if a share is valid or invalid, such as Pedersen Verifiable Secret Sharing.


Hill's Cipher - Known Plaintext Attack I know this question has already been asked few times but I'm struggling a bit on a problem.

I have a plaintext FRIDAY and its ciphertext PQCFKU, using $M = 2$, with corresponding integers $x = fr id ay = (5, 17),(8,3),(0,24)$ and $y = pq cf ku = (15, 16),(2,5),(10,20)$.

In order to find the key $k$:

$$\pmatrix{y1 \\y2 \\} = \pmatrix{x1 \\x2 \\}k$$
$$\pmatrix{15&16 \\2&5} = \pmatrix{5&17 \\8&3 \\}k$$

Now $x$ determinant, $det(x)$ is given by:

$$det(x)=5*3-8*17 = -121$$ and, using modulo 26:
$$-121\pmod{26} = 9$$
Then, $det(x^{-1})$ is given by:
$$9^{-1}\pmod{26} = 3$$

Now $X^{c}$ is:
$$X^{c}=\pmatrix{3&8\\-17&5}$$
And $(X^{-1})^{T}$ is:
$$(X^{-1})^{T}=\pmatrix{3&-17\\-8&5}$$

So, In order to find $k$:
$$k=(\pmatrix{3&-17\\-8&5}det(x^{-1}))\pmod{26}$$
Which is:
$$k=(\pmatrix{3&-17\\-8&5}3)\pmod{26}$$
$$k=\pmatrix{9&-51\\-24&15}\pmod{26}$$
$$k=\pmatrix{9&1\\2&15}$$

  Now comes the problems, doing the decryption using $k$ and $pq$ I
  can't get $fr$ back.

If I'm not wrong:

$$x1 = (15,16)\pmatrix{9&1\\2&15}=(15*9+16*1, 15*2+16*15)=(151, 270)$$

And now, to obtain the plaintext:

$$(151, 270)\pmod{26} = (21, 10) $$

  and, $$(21, 10) $$ leads to $vm$ which is clearly not $fr$

Is my reasoning wrong? Am I doing errors?

I've been scratching my head for a while but I was unable to find  valid solution. Thanks in advance.

Actually it seems to me that you are using the wrong basis and got the key for the other way around:

Suppose you have the plain text $x_1 = \pmatrix{5\\17}$ and $x_2= \pmatrix{8\\3 \\}$ and the corresponding ciphertexts $y_1=\pmatrix{15 \\16}$ and $y_2=\pmatrix{2\\5}$ and please note how I represent those as vectors and not line matrices, then everything seems to work fine with your method:

Hill's cipher translates into:
$$\pmatrix{k_{11}&k_{12}\\k_{21}&k_{22}}\times x_1 \equiv y_1 \mod 26$$
$$\pmatrix{k_{11}&k_{12}\\k_{21}&k_{22}}\times x_2 \equiv y_2 \mod 26$$

This leads to the system you are solving (but you may also represent it using 4 equations) and you get:
$$\begin{cases}5k_{11}+17k_{12} &= 15\\
5k_{21}+17k_{22} &= 16\\
8k_{11}+3k_{12} &= 2\\
8k_{21}+3k_{22} &= 5\end{cases}$$
Which correspond, once represented using matrices, to solving:
$$\pmatrix{5&17 \\ 8&3} \times \pmatrix{k_{11}\\k_{12}} \equiv \pmatrix{15\\2} \mod 26$$
$$\pmatrix{5&17 \\ 8&3} \times \pmatrix{k_{21}\\k_{22}} \equiv \pmatrix{16\\5} \mod 26$$
Since you have computed it, you know that
$$X^{-1} \equiv \pmatrix{9&1 \\2&15 \\} \mod 26$$
for $X=\pmatrix{5&17 \\8&3 \\} $.

But now, this is where it seems to me that you are doing something wrong: to get the key, you can simply solve the above equations by left-multiplying by $X^{-1}$ so that:
$$ \pmatrix{k_{11}\\k_{12}} \equiv X^{-1}\times X\times \pmatrix{k_{11}\\k_{12}} \equiv X^{-1}\times y_1\equiv \pmatrix{9&1 \\ 2&15} \times \pmatrix{15\\2}\mod 26$$
and the same holds for $X^{-1}\times y_2$:
$$ \pmatrix{k_{21}\\k_{22}} \equiv X^{-1}\times X\times \pmatrix{k_{21}\\k_{22}} \equiv X^{-1}\times y_2\equiv \pmatrix{9&1 \\ 2&15} \times \pmatrix{16\\5}\mod 26$$
 and you end up with the key which seems to be, after computing the latest results:
$$\begin{cases}k_{11}=7\\ k_{12}=8 \\k_{21}=19\\k_{22}=3\end{cases}$$
And which translates into $$K=\pmatrix{7&8\\19&3}$$
And you can check that $ay$ get encrypted into $ku$
$$ K \times \pmatrix{0\\24}\equiv \pmatrix{10\\20} \mod 26$$
But to decrypt anything, you'll need to invert the key to get:
$$K^{-1}=\frac{1}{det(K)}\pmatrix{3&-8\\-19&7}\equiv 25 \pmatrix{3&-8\\-19&7} \equiv \pmatrix{23&8\\19&19} \mod 26$$
And so you can decode the $fr$ from the $pq$ by:
$K^{-1}\times \pmatrix{15\\16} \equiv \pmatrix{5\\17} \mod 26$
which checks out.

This is because decoding Hill's cipher necessitate to left-multiply the cipher by the inverse of the key.


Should the nonce passed to GCM be authenticated? This answer recommends authenticating the IV with HMAC when using AES and then HMAC.

Since AES-GCM provides authentication too, should the external nonce passed to GCM be authenticated separately when passing over network? If not, why not? If it should be what is the recommended way to do it?

Should the external nonce passed to GCM be authenticated separately when passing over network?

No, that is not necessary; it is implicitly authenticated by GCM itself, pretty much as the AAD is also authenticated.  That is, if someone in the middle modifies the nonce, then that will alter the authentication tag that the decryptor computes as a part of the GCM decryption process (and alters it in a way that cannot be predicted by someone without the key).  Because the tag will not match the authentication tag that comes with the encrypted packet, the altered packet will be rejected.


Splitting a password for dual roles I would like to prompt users for a single passphrase to establish trust with separate, normally (but not always) complementary systems from one password input.

I'm essentially looking for a box where one password enters and two leave, where maximum of entropy is maintained and the ability of an attacker using either output password to derive the other is minimized.

There are some constraints:

The algorithm must be public knowledge.
No other secret keys can be involved.
Output passwords must be deterministic for any given input password.

A simple answer seems to be:

$\rm pass1 = HMAC(password, \text{ "Magic One"})$
$\rm pass2 = HMAC(password, \text{ "Magic Two"})$

With this method, it should be as difficult for someone who knows $\rm pass1$ to derive $\rm pass2$ as it would be for them to guess $\rm password$.

Are there better existing algorithms?  The only reference I have been able to find is Steve Bellovin's Hashed Password Exchange Internet-Draft using the same basic method.

Specifically, is it practically possible to increase the difficulty of someone with knowledge of $\rm pass1$ to derive $\rm pass2$ to be more than the difficulty of guessing $\rm password$ itself, even if it requires spending portions of available $\rm password$ entropy?

For example, let's assume that $\rm pass2$ is exposed in an environment where it is being attacked "offline", while $\rm pass1$ is less vulnerable.  In this case, $\rm pass1$ is effectively also exposed to the "offline" risk as much as $\rm pass2$.

You want a pair of functions $(f_1,f_2)$ from a set $S$ of possible passphrases to a key set $K$, that is $f_1,f_2: S \rightarrow K$. The functions are public, in the sense that they can be computed by anyone.

Your security goal is that the cost of finding $f_2(pw)$, knowing $f_1(pw)$, should be roughly as expensive as finding $f_2(pw)$ by searching for $pw$, using $f_1(pw)$ to confirm a correct guess, then simply computing $f_2(pw)$.

In this setting, using a sensible KDF is the best you can hope for. You compute a long bit string $s = \mathit{KDF}(pw)$. The string splits into two parts, $s = s_1 || s_2$, and $f_1(pw) = s_1$, $f_2(pw) = s_2$.

It is good because: Under reasonable assumptions (the KDF looks like a random function). If the KDF looks like a random function, then unless you know the input to the function, you cannot use part of the function value to say something about any other part of the function value.

It cannot be improved upon because: The requirement that $f_1(pw)$ should contain as much entropy as $pw$ means that the function value $f_1(pw)$ more or less uniquely determines $pw$, which means that exhaustive search will work.

Trivial remark on the proposed solution: We could have said that $f_i = \mathit{KDF}(pw, i)$, in line with your HMAC proposal, but then in practice the workload for someone trying to confirm a guess is half that of the legitimate user. With the above proposal, the workloads are equal.


ciphers depend on Elliptic curve cryptography IS there any cipher dependent on the Elliptic curve cryptography?
and it is Accredited by any  origanization like RSA or El GAMAL

Which are the ciphers depend on the Elliptic curve cryptography?

Yes. ElGamal encryption can be instantiated with Elliptic Curve Cryptography. That's essentially the asymmetric cryptography part of ECIES, which adds symmetric cryptography to become CCA-resistant. ECIES has wide endorsement, e.g. in SEC1 v2, ANSI X9.63, IEEE 1363a, ISO/IEC 18033-2.


Difference Between Gravity-SPHINCS and SPHINCS+? What are the differences between Gravity-SPHINCS and SPHINCS+ from security and practicality standpoints?  Are they just different implementations of the underlying SPHINCS algorithms or are they functional variations on the underlying algorithms?

Gravity-SPHINCS and SPHINCS+ are two different improvements of the original SPHINCS algorithm. Both change the few-time signature scheme HORST (used in SPHINCS) in slightly different ways. However, both are variations of HORST.
This leads to variable length signatures for Gravity-SPHINCS and fixed length signatures for SPHINCS+ which are as long as the signatures one would obtain from using the Gravity-SPHINCS few-time signature scheme in SPHINCS+ in the worst case. However, the often shorter variable length signatures come at the cost of far more complicated signing and verification.

Moreover, both change the way the index of the used few-times signature scheme gets computed. While different, both achieve that the index can be verified by the verifier which was not the case for SPHINCS. Finally, Gravity-SPHINCS uses the assumption that collision-finding for quantum computers is as slow as second-preimage finding under certain assumptions about storage access times. Hence, Gravity-SPHINCS slightly simplifies the way hashing is done in the construction at the cost of only achieving a security reduction from collision resistance of the internal hash function. On the opposite, SPHINCS+ gets a security reduction from second-preimage resistance of the internal hash function (there are different assumptions on the hash function used to compress the message in both proposals).

So to summarize, the schemes follow the same high level design principle but instantiate it in very different ways. Which one is better probably depends on what you want.


security of a sponge construction I don't get why the size of C (the capacity) of a sponge construction influences the security of the sponge construction. And what is the influence of the size of R?

The capacity of the sponge construction refers to the section of the state that is not revealed to the adversary.

By effectively zeroing/truncating one side of the output of a permutation, it becomes difficult to apply the inverse permutation to the output and recover the original input: In order do so and end up back at the correct input, you would first need to recover the capacity bits that were not revealed. By ensuring that the capacity is large enough, it becomes computationally infeasible to guess what the capacity bits were and by extension computationally infeasible to recover the initial input to the function. This is a technique to make an invertible permutation into a one-way function.

The rate refers to the bits that are directly input/output into the permutation. A larger rate provides higher performance: Consider the extreme where the rate is only 1 bit - it would require $n$ invocations of the permutation to digest $n$ bits of data, which would be quite slow.

Conclusion

The capacity influences the security of the construction, while the rate influences the performance; Increasing one will decrease the other, as the size of the state is otherwise fixed.


Is there a downside to encrypting too much data with the same key? Is there a downside to encrypting too much data? If so, what?

I'm guessing things like

too much data encrypted with the same key, possibly leaking information due to a collision
encrypting non-essential data, wasting resources

could be a problem, but that's just a hunch, and that's not how we do cryptography.

On the other hand, failing to encrypt some data can leak some very sensitive information, and encrypting everything is an easy way to avoid that.

Yes, but the answer is more or less embedded in the question here; you can only say that you encrypt too much data in case the secret key and / or plaintext becomes vulnerable.

Most modes of operation define how much data can be encrypted. This could mean real limits to the amount of data (approx. $2^{36}$ bytes or 64 GiB for AES-GCM) or it may be completely impossible to ever reach the limit (e.g. $2^{128}$ bytes or blocks of data).

When it comes to wasting resources: that's more a question of encrypting the wrong data rather than too much data.

And yes, failing to protect sensitive data is a sin as well. But that's a generic statement that also comes down to categorizing the data correctly.

First categorize the data, then find the right method to encrypt the amount of data that needs confidentiality. Encryption itself is not the goal.


Are password salts equivalent to keystream? I was reading up on keystream when I came upon the definition of it:

  A keystream is a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message (the ciphertext).

  The "characters" in the keystream can be bits, bytes, numbers or actual characters like A-Z depending on the usage case.

I am wondering conceptually if the stream of random pseudorandom  character is equivalent to a salt which are commonly appended to passwords?

No, they are not conceptually related.

A keystream is the output of a stream cipher and is of (effectively, for modern ciphers) infinite length. If you need to encrypt more plaintext, you use the cipher to produce more bytes of keystream.

On the other hand, password salts are of fixed size and their purpose is to make every password effectively unique. A simplification is that if two people have the passwords password but different salts, one password might be hashed as if it were passwordxSFsz8sl while the other is hashed as if it was passwordRsRb58yd. Without this protection, an attacker could (for instance) hash the 100,000 most common passwords and compare them to all of the hashes in your database. With salts, an attacker can't share this work between users in the database; to try those same 100,000 passwords, s/he must compute all 100,000 for every user in the database.

A much closer analogue of password salts is an initialization vector (or IV), used in encryption. Their purpose is very similar; they ensure that each instance of a cipher will encrypt the plaintexts differently so that even two identical plaintexts will encrypt to a unique ciphertext.


Is a keyed MAC sufficient for integrity protection? I'm working with the above figure which shows a challenge-response protocol.

Kc - shared key between the host and the client
B' - is a biometric captured by device
BT' - biometric template computed from B'
D' - device authenticator.

Match(BT', BT) returns yes if the user computed biometric matches with the template, no otherwise.

Verify(D', D) checks the validity of the authenticator. If all succeed at the host, host returns yes.

My question is, does message 3 from client > host need to be encrypted for integrity protection?

My instinct is no it doesn't, and using a keyed MAC is sufficient, because encryption does not guarantee integrity protection.

My question is, does message 3 from client > host need to be encrypted for integrity protection?

Encryption doesn't provide integrity protection at all. Authenticated encryption may provide such protection, but it would provide the same security as the MAC, which is already performed.

  My instinct is no it doesn't, and using a keyed MAC is sufficient, because encryption does not guarantee integrity protection.

You are correct.

However, you are also sending a biometric template unencrypted. This will leak information about the person's biometrics, and may compromise the entity authentication of the system. It is unclear from the question what use the template is to an attacker, but generally just sending out biometric data from a person is not secure in any form.

Leaking biometric data is morally wrong. If you send out biometric data without preserving confidentiality then you may be in violation of various laws and privacy regulations even at the UN-level. Note that even if the template doesn't directly spill biometric information of a person, maybe it can be used for others to perform entity authentication.

In short: you are in violation of the integrity of the person you are trying to protect (if you don't encrypt) rather than violating the integrity of the message; that is indeed covered by the MAC.


Are there any specific requirements for the function $F$ in a Feistel cipher? In a Feistel cipher (as shown below), it seems that the security of the cipher would be entirely dependent upon the function $F$. What requirements on $F$ are necessary for a secure Feistel cipher? Is there any relationship between the function $F$ and the number of rounds necessary to have a secure cipher?

Luby and Rackoff published a famous article on that subject (SIAM Journal on Computing, 1988, Vol. 17, No. 2 : pp. 373-386 ). Namely, they showed that if the $F$ functions are pseudorandom, then four rounds are sufficient to achieve security.

There are subtle details, though:

Each round has its own $F$ function. We usually say that there is a single $F$ function indexed by the subkey for that round. In the Luby-Rackoff construction, the function for each round must be indistinguishable from a function taken at random, uniformly, among the set of possible functions which take an input as large as $R_i$ and produce an output as large as $L_i$; and that "random selection" must also hold between rounds (the round function for round 2 must be selected independently of the round function for round 1).
The security proof holds for balanced Feistel schemes ($L_i$ and $R_i$ have the same size).
If the block size is $n$ bits, then the security proof is valid up to $2^{n/2}$ elementary operations. So, if you want "proven" 128-bit security, the block cipher must use 256-bit blocks (or larger).

There is also the (technically unpublished) construction by Matt Blaze called Turtle: it is a four-round Feistel scheme for which each round function is itself a four-round Feistel scheme, recursively. Blaze links the security to an NP-complete problem, which is nifty, although it does not tell much about the security of the construction in practice (NP-completeness is about asymptotic behaviour; whether it applies on a given finite computational budget is a matter of guess and faith). Since Turtle was not formally published, it is a bit unclear whether the lack of cryptanalytic result is due to its inherent security, or lack of academic visibility.

A much more recent article from Morris, Rogaway and Stegers explores the security of unbalanced Feistel schemes where the "left part" ($L_i$) is a single bit. They show that, given enough rounds, one can get almost ultimate security, i.e. resilient against chosen ciphertext attacks up to $2^{n(1-1/r)}$ oracle requests, where $r$ is the number of rounds. This work is mostly useful in situation where we want small blocks. There again, the proof holds as long as the round functions are pseudorandom.

An empirical rule about Feistel ciphers is that, most of the time, complexity of attacks raises somewhat exponentially with the number of rounds. This holds as long as successive rounds are sufficiently dissimilar from each other; otherwise, you can have weaknesses due to slide attacks. For instance, one can say that if the best differential for the first half of the cipher has probability $P_1$, and the best differential for the second half has probability $P_2$, then the best differential for the whole cipher has probability at most $P_1 P_2$ -- but only if the two halves are independent of each other (i.e. use independent subkeys), which is an ideal but hard-to-get property.


How many encryptions are needed before OpenPGP key privacy is violated? According to an excellent answer describing the pitfalls of key privacy in OpenPGP:

Theoretically, an all-zero key ID can be used as a way to discourage traffic analysis, but this is not a complete solution. For instance, with RSA keys, the packet still contains an integer between 0 and n-1, with n being the RSA modulus, with a fairly uniform distribution. Thus, observing many messages can yield, statistically, the first (most significant) few bytes of that modulus, which can be used to discriminate recipients from each other.

For an RSA key with an $n$-bit modulus, how many messages must be encrypted with that public key before it can be distinguished from $k$ other keys of the same size with non-negligible probability?

I'll leave alone the OpenPGP spec, and consider the problem of identifying among $k$ public keys $(n_i,e_i)$ the RSA public key $(n_j,e_j)$ used to encrypt $m$ messages per RSA with proper encryption padding. The only way is by examining the $m$ cryptograms $c_\ell$, which essentially are indistinguishable from uniformly random in $[0,n_j)$ (I assume the $c_\ell$ are computed with no countermeasure to foil identification attempts, except in last section).
An identification algorithm can use two facts:

If $n_i\le\max c_\ell$ , that rules out $i=j$.
The mean $x=\frac1m\sum c_\ell$ , which the attacker should compute, has Bates distribution, with mean $(n_j-1)/2$, standard deviation $(n_j-1)/\sqrt{12m}$. That distribution quickly becomes close to normal when $m$ increases, and the 68-95-99.7% rule quickly becomes applicable.

I think the optimum attacker's strategy in practice is to pick $j$ as $i$ with $n_i/2$ closest to $x$ among the $n_i$ surviving test 1. It's possible to estimate the confidence in a guess by computing $t_i=\lvert n_i/2-x\rvert\sqrt{12m}/n_i$ for the values of $i$ with $n_i/2$ the closest to $x$: the higher $t_i$, the less likely $i$ is (ignoring information obtained from other $n_i$): $t_i>1$ with 32% probability, $t_i>2$ with 5% probability, $t_i>3$ with 0.3% probability.

To go deeper in the analysis, we need an idea of the distribution of the $n_i$.
By making the say 256 high-order bits of the $n_i$ equal at generation time (fixed to some haphazard constant), which is easy and does not harm RSA security or interoperability, we could make identification hopeless.
For a common generation method with the prime factors $p_i$ and $q_i$ of $n_i$ independent and roughly uniform in $[2^{(b-1)/2},2^{b/2}]$ where $b$ is the bit size of $n_i$ (e.g. $b=3072$), I think an attacker would need $m$ in the order of a few times $k^2$ for a good success rate, and significantly more to conclude with good success rate and confidence for most users. Keys with the highest $n_j$ tend to be easier to guess correctly, because rule 1 prunes best, and there tends to be less other keys with nearby $n_i$. The second effect also makes keys with the lowest $n_j$ easier to guess than those in the center of the pack: those with the high byte in [0xB0,0xC1] (for $b$ multiple of 8) tend to be the most resistant to guessing, while giving no strong sign they have been chosen for this purpose.
All this is amenable to simulation and detailed analysis. I called for help. In the desert so far.
Update: this comment by Squeamish Ossifrage points a relevant paper: Jean Paul Degabriele, Victoria Fehr, Marc Fischlin, Tommaso Gagliardoni, Felix Günther, Giorgia Azzurra Marson, Arno Mittelbach and Kenneth G. Paterson: Unpicking PLAID - A Cryptographic Analysis of an ISO-standards-track Authentication Protocol, in proceedings of SSR 2014. Start with section 3.1 Tracing Cards via Shill-Key Ciphertexts.

I'm told a simple and clearly correct countermeasure to foul identification attempts even if we don't want to change pre-existing $n_i$ of the same bit size $b$: pick the first RSA cryptogram below $2^{b-1}$. Adversaries will be facing a uniformly random integer in $[0,2^{b-1})$.


Change initial hash value of SHA-512/$t$ Fips 180-4 defines under 5.3.6 how to calculate initial hash values for SHA512/$t$ for a given value $t$.
Can someone explain me how the t actually affects the outcome of the procedure (which, as far as I understand, just calculates the eight 64-bit words XOR with a5a5a5a5a5a5a5a5)? Furthermore I don't understand how to pass the new calculated initial hash values to the hash function instead of the default values for SHA-512.
Can someone explain how to do it in Java using the java.security.MessageDigest class (or something else)?

Can someone explain me how the t actually affects the outcome of the procedure (which, as far as I understand, just calculates the eight 64-bit words xor with "a5a5a5a5a5a5a5a5")?

That's not right.

Both hex 5 and A are encoded setting two bits out of 4; a5 translates to 1010 0101 in bits. I.e. half the bits are flipped. This kind of XOR value is often used (see e.g. HMAC).

The XOR calculation just creates the internal IV for the SHA-512 calculation over the ASCII value of "SHA-512/<t>" where T is a number expressed in normal digits. It is not possible to use a black box implementation of SHA-512 as it would not allow changes to the internal IV. The same goes for the SHA-512/t calculation after that.

How the result of the SHA-512 hash with the special IV is used can be seen in section 6.4 of the document referred to. Basically first initialize SHA-512' with the XOR'ed values. Now calculate the result of SHA-512'("SHA-512/<t\>"). That in turn is used as initial value for SHA-512/t.

Note that the result of SHA-512'("SHA-512/<t>") remains static for a given t. The internal IV values for SHA-512/224 and SHA-512/256 are actually given in the document in section 5.3.6.1 and 5.3.6.1. SHA-384 uses otherwise defined IV, see section 5.3.4.

  Furthermore I don't understand how to pass the new calculated initial hash values to the hash function instead of the default values for SHA512. Can someone explain how to do it in java using the java.security.MessageDigest class (or something else)?

This is not possible because the IV (the initial $H^0_x$ values) is fixed for SHA-512. It is required to use the code of the implementation instead. In principle you can use the GPL'ed OpenJDK source for that, but that might get you in trouble because of Oracle's antics.

Fortunately Bouncy Castle already has an implementation of org.bouncycastle.crypto.digests.SHA512tDigest. I would not take the implementation of that class - and especially of the method tIvGenerate - as prime example of good coding practices, but it does clearly implement the scheme described above.


Diffie Hellman Exponentiation Implementation Problem im trying to work on key agreement schemas on embeded systems. for diffie hellman, ive written a 256 bit multiplication, on AVR core it takes about 2 seconds on 1Mhz frequency, lets say my algorithm is weak and it'll work in 1/10 of this time. if we multiply the clock and say were working on 3Ghz PC, we have to exponentiate a 256 bit digit to a 256 bit digit, which means doing the multiplication 1.15e77 ( 2^256) time. with a simple relation, it'll take  e-4*1.15e77 seconds then?? right??? it is really to long to be practical? what am i missing out here?
ty for your answers!!

thanks for your usefull answers so far, but i think my question is a little diffirent!! im not asking a general question, im asking the exact implementation problem, pierre said i would need at most 256 time multiplication, but isn't the public key 256 bits?  then diffie hellman would need 2^256 time multiplication at most? what am i missong here?  thanks for your previous and upcomiong answers!!

There is a well known technique for exponentation, you might read this http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method . The same techniques and its variants are used for matrix exponentiation ... You only need 256 squaring and at most 256 multiplications.


Why is MAC using nonce+message+hash(nonce+message+identifier) not the standard? Given that we know that nonce + message + hash(nonce + message + mac-key) all inside the encryption makes it possible to detect if any bits of the message have been changed by the attacker (in essence converting a malleable cipher into a non-malleable one), why do they still say encrypt then MAC?

Furthermore, doesn't adding the mac-key that is split into pairs like the symmetric cipher authenticate the attacker by proving the rest of the material not subject to attack on the cipher is known (assuming adequate length)?

Of course if we had full asymmetric we'd sign then encrypt but that's not the question being asked.

EDIT: The encryption algorithms I prefer all have the property of not having invalid inputs, in that any ciphertext + any key -> some "plaintext", usually garbage. There cannot exist an attack on the algorithm that would crash the implementation.

EDIT: OK I get the part about HMAC not being hash(a + b) due to most hash functions being unsuitable. I prefer to replace a hash function as unsuitable for any use once it reaches the state of unsuitable for that use but no matter. I don't get the part about why we care if the ciphertext has been altered. The way my stuff is set up it is not faster to MAC before attempting decryption due to rewinding streams.

It has the disadvantages of any MAC-then-encrypt scheme, which I'm quoting from the linked answer below. In addition:

It has the property that you need both a nonce and a hash, so for equivalent security it requires more message space.
The nonce has to be random, so it requires strong random numbers for each message, unlike e.g. AES CTR + HMAC.
Doesn't work if you need deterministic encryption, for some reason.

From the link:

  Does not provide any integrity on the ciphertext, since we have no way of knowing until we decrypt the message whether it was indeed authentic or spoofed.

This means that it may allow some chosen-ciphertext attacks that encrypt-then-MAC would protect from. It also means more time is wasted on incorrect messages, which could e.g. help with denial-of-service attacks.

  If the cipher scheme is malleable it may be possible to alter the message to appear valid and have a valid MAC code. This is a theoretical point, of course, since practically speaking the MAC secret should provide protection.

In your scheme the nonce and ID take the place of the MAC secret, which could be weaker if the encryption is weak and the hash function isn't a strong MAC in that mode, but can't be any stronger. Still theoretical, as long as you choose a strong, unknown nonce.


How do you represent a compressed point on an elliptical curve over F2m? I understand for prime curves it is just

bytes(0x02 + flag) + bytes(x)

where flag is the LSB of y. For the F2m curves I cannot make out how to do it.

IEEE P1363 section 5.6.6.1.2 appears to say flag is '1 if y of point > y of inverse point else 0' which I think just means if y > x.
These slides (slide 15) by Julio Lopez and Ricardo Dahab appear to suggest my interpretation of the IEEE method is off (I think).
And this PDF - which I think is the standard reference - has yet another notation in section 2.3.3 part 2.2.2 that I do not understand.

Which of the above references represents the "standard" to handle this? And can someone please explain the proper/correct way to handle things; preferably from a programmer's perspective?

There are many different but similar ways to do point compression. To make sure we are all aligned, we need to standardize what we do. Let me summarize the content of the documents you cite:

This is P1636.3, which is meant for Identity-Based Public Key Cryptography using Pairings, as can be seen on the IEEE P1636 homepage. It only considers elliptic curves over fields of odd order, and therefore is irrelevant for curve-based crypto over $\mathbb{F}_{2^m}$.
The presentation by Lopez and Dahab shows distinct ways to do point compression over the field $\mathbb{F}_{2^m}$. They seem to propose a novel method, so this is really a perspective from researchers. On slide 15 they show a particular way to do compression, and they refer to the standard IEEE P1636 which contains it. Note that they refer to the general standard P1636, not P1636.3.
This is the actual SEC1 standard, which among other things shows how to do point compression for elliptic curves over $\mathbb{F}_{2^m}$. This is described, as you say, in 2.3.3 part 2.2.2. They show how to do decompression in 2.3.4 part 2.4.2 and 2.4.3. Judging from Lopez and Dahab's slides (I don't have access to P1636 itself), this is done exactly the same way as in IEEE P1636.

Conclusion: in all your documents there is only a single standardized method to do point compression. This would be the most likely option, although I don't have enough experience "in the field" to guarantee this.


Older key as PGP subkey? Currently I have a 2048-bit PGP key. Suppose I create a new 4096-bit key. Can I add that old key as a subkey of this new one?

Yes, PGP allows different-sized subkeys and subkeys are not derived of the main key, so it is possible to have the earlier key be a subkey of the new one.

How to do it is off topic here, but this should get you started if you use GnuPG.


looking for BKZ earliest algorithm and its application in cryptography I am reading lattice based cryptography for my master thesis,
I am looking for the earliest version of BKZ algorithm, and its applications in cryptography, to understand it very well, I already know about LLL algorithm.
and thanks in advance

BKZ was described in Lattice basis reduction: improved practical algorithms and solving subset sum problems by  C. P. Schnorr, M. Euchner in 1994. As the title suggests, it was first used for solving the subset sum problem.
https://academic.microsoft.com/paper/2126483728


Prove the correctness of decryption process of Paillier cipher The definition of Paillier cryptosystem is the same as the one on wikipedia.
Now the random integer $g$ is chosen of the form $$g=(1+n)^{\alpha}\beta^{n}\bmod n$$, where $\alpha$ and $\beta$ are in $\mathbb{Z}_{n}^{*}$. Prove that
$$m\;=\;L(c^{\lambda}\bmod n^{2})\mu\bmod n\;=\;\frac{L(c^{\lambda})\bmod n^{2}}{L(g^{\lambda})\bmod n^{2}}\bmod n$$, where $L(x)=\displaystyle\left\lfloor\frac{x-1}{n}\right\rfloor$ denotes the quotient when $x-1$ is divided by $n$ and $\mu=\left(L\left(g^{\lambda}\bmod n^{2}\right)\right)^{-1}\bmod n$.
(Carmichael's theorem: For any $r\in \mathbb{Z}_{n^{2}}^{*}$, we have $r^{n\lambda}\equiv1\bmod n^{2}$.)
The above is the question description. The following is what I came up with.
\begin{align*}
L(c^{\lambda}\bmod n^{2}) &= \frac{c^{\lambda}\bmod n^{2}-1}{n} \\
&= \frac{g^{m\lambda}r^{n\lambda}\bmod n^{2}-1}{n} \\ &= \frac{(g^{m\lambda}-1)r^{n\lambda}\bmod n^{2}}{n} \\ &= \frac{g^{m\lambda}-1 \bmod n^{2}}{n}
\end{align*}
\begin{align*}
L(g^{\lambda}\bmod n^{2}) &= \frac{g^{\lambda}\bmod n^{2}-1}{n} \\
&= \frac{g^{\lambda}-1 \bmod n^{2}}{n}
\end{align*}
But I have no idea how to proceed. I still haven't used the formula for $g$. I think the solution may involve some finite field theorems but I really cannot recall any.

First, we simplify $\mu$.
\begin{align*}
    g &= (1+n)^{\alpha}\beta^{n} \bmod n^{2} \\
    g^{\lambda} &= (1+n)^{\alpha\lambda}\beta^{n\lambda}\bmod n \\
    &= (1+n)^{\alpha\lambda}\bmod n^{2} \\
    &= (1+n\alpha\lambda)\bmod n^{2} \\
    L(g^{\lambda}\bmod n^{2}) &= (\alpha\lambda)\bmod n^{2}
\end{align*}
Then, let's take a look at $L(c^{\lambda}\bmod n^{2})$.
\begin{align*}
    c &= g^{m}r^{n}\bmod n^{2} \\
    c^{\lambda} &= g^{m\lambda}r^{n\lambda}\bmod n^{2} \\
    &= g^{m\lambda}\bmod n^{2} \\
    &= (1+n\alpha\lambda)^{m}\bmod n^{2} \\
    &= (1+mn\alpha\lambda)\bmod n^{2} \\
    L(c^{\lambda}\bmod n^{2}) &= (m\alpha\lambda)\bmod n^{2}
\end{align*}
Hence, $\frac{L(c^{\lambda}\bmod n^{2})}{L(g^{\lambda}\bmod n^{2})}=m\bmod n$, the decryption process of Paillier cipher is correct.


In constraint systems for ZK proofs, why are multiplications counted but are additions not? For example, If I wanted to prove that:

$$x^2 + x^3 = 45$$

This cost of this would be calculated by counting the number of multiplications that need to be done, and not the addition of $x$ squared and $x$ cubed.

Your question seems to assume this is true for any constraint proof system. I'm quite confident that this property is on a case-by-case basis. Bulletproofs, for example, have this property: proof size is $\log(n)$, with $n$ the amount of multipliers in the arithmetic circuit. In the rest of my answer, I'll talk about how a bulletproof achieves this.

I'll give a very condensed sketch of how bulletproofs achieve this property. For a more in-depth explanation, I suggest to read the above paper, or the (in my opinion) simpler notes of the good folks at dalek-cryptography.

Bulletproofs writes their constraint system in a single vector equation like follows:

\begin{aligned}
\mathbf{W}_L \cdot \mathbf{a}_L +
\mathbf{W}_R \cdot \mathbf{a}_R +
\mathbf{W}_O \cdot \mathbf{a}_O =
\mathbf{W}_V \cdot \mathbf{v} +
\mathbf{c}
\end{aligned}

Here, the $\mathbf{W}_{\{L,R,O,V\}}$ are weight matrices: they map secrets from their right hand side to constraints. $\mathbf{v}$ are the input secrets. Note that this equation contains the linear constraints, not the multipliers. In what follows, they combine it with the multipliers ($\mathbf{a}_L\circ \mathbf{a}_R=\mathbf{a}_O$), and then this equation is molded into a form $t(x)=\langle\mathbf{l}(x),\mathbf{r}(x)\rangle$, in which $x$ is a challenge of the verifier. Here's the first clue: $\mathbf{l}(x)$ and $\mathbf{r}(x)$ are of length $n$, the amount of multiplication gates.

The proof process links $t(x)$ and the two vectors $\mathbf{l}(x)$ and $\mathbf{r}(x)$ to the secret input commitments (in constant size), and then goes on to prove that their inner product relation holds: the inner product proof. This was introduced by Bootle et al., in Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting, and improved upon in the bulletproofs paper. This is your second clue: this inner product argument that proves something of the form $t=\langle \mathbf{l}, \mathbf{r}\rangle$ needs $\log(|l|)=\log(|r|)$ communication.


Decrypt simple CBC message with known IV using XOR encryption I've been given a ciphertext message, encrypted using CBC. I know that the block size is 12 bytes and I know the plaintext value of the first block.

I also know that the encryption function is a simple XOR:

$$C_i = K \oplus (M_i \oplus C_{i-1})$$

where $C_0 = IV$.

Now I supposedly should be able to deduce the complete plain text message, but I'm lost. What sort of XOR'ing magic should I perform here to get hold of the plain text?

That's easy: $C_1 = K \oplus (M_1 \oplus C_0)$. You know $C_1$, $M_1$ and of course $C_0$, the IV. You can easily rewrite this as $K = C_0 \oplus C_1 \oplus M_1$.

What is left is simply decryption with $K$. In case of XOR encryption, decryption is the same as encryption, so $M_i = (K \oplus C_i) \oplus C_{i-1}$.

Notes:

XOR is associative and commutative, so you can leave out the parentheses in the formulas and rewrite the formulas like I did above.
this will obviously not work with secure block ciphers since retrieving $K$ is not supposed to be possible, even when given a known plaintext / ciphertext pair.


If cryptographic hashes are completely unique, could they theoretically be used to transfer data? I know it sounds ridiculous, but hear me out. We know that good hashing algorithms would generate hashes that are pretty much unique. If, in the future, we create a perfect (or just really near perfect) algorithm, could those hashes be used to represent larger chunks of data in a totally unique way? If they truly were unique and determined entirely by the file, could a powerful enough machine work backwards and reconstruct the file?

Now, this is a bit of a stretch from what we currently know, but I'd think it might be possible. Quantum computers can perform many different tasks at once, and we know that they pose a significant threat to modern forms of encryption because of this ability. While that isn't exactly the same thing as guessing every possible file that could've produced a particular hash, but I'd imagine there might be a way to make the process more efficient.

Maybe you get a hash that's a couple kilobytes long, allowing for billions of different input types. Combine that with a computer capable of generating and testing every possible input simultaneously and you'd be able to send tons of information in a couple kilobytes of transmission.

I'm not asking if it's possible to do with our current technology, as I'm fairly sure it isn't. I just want to know if the process of hashing a file could (in theory) support it.

No.

They can be used to identify data you've stored elsewhere.  For example, you can probably find a preimage under MD5 for 6f5902ac237024bdd0c176cb93063dc4 by searching the web, and it might even be meaningful English text.  And you probably won't find more than one preimage.

This is the idea of content-addressed storage, which is widely used, e.g. by Tarsnap—although it would be a mistake to use MD5 or SHA-1 for content-addressed storage, because collisions are readily available to anyone who wants them, which have hilarious effects on systems doing just that.

But even if you had a practical preimage attack on MD5—say, an array of quantum computers large enough to run Grover's algorithm—it would give you a preimage, but not necessarily (and probably not) the preimage I have in mind that you'll find with a web search.  Instead, it would probably give you 128 or 192 or so bits of gibberish.  And if you ran it for longer it would probably give you many such blocks of gibberish, long before finding anything that resembles English text.

If the messages you want to transmit cover only a small subset of all bit strings, and are structured with a distribution you know something about, you could invent a better compression scheme for it.  Maybe if there are few enough messages with convenient enough structure, you could compress them into 128 bits.  This depends on specific information about the distribution of messages, and it depends on having no more than $2^{128}$ pigeons to stuff into holes.

But a preimage-resistant cryptographic hash function like MD5 would be about the stupidest compression scheme imaginable, because not only was it designed without knowledge of your distribution of messages, but it goes to great lengths to obscure the original message and to make ‘decompression’ as hard as it can so that the best way is to guess a possible original message and check it.


Why must we hash lot of times in rainbow tables? I don't get the utility to chain and reduce in generating rainbow tables.
Hash functions are made to not have collisions, or at least chain only 2 times so we don't return to the concept of the hash dictionary.

So why do we bother the machine to hash and reduce thousand of times to only store the latest value?

The comments attempt to answer by looking at the details of how rainbow tables work; however if you examine the problem they're attempting to solve, you can see that they would require a large number of hash computations, no matter how they operate internally.

Now, rainbow tables are a generic way to find preimages to an arbitrary function; that is, given a function:

$$Y = H(X)$$

where $H$ is a deterministic function.  Then, given a value $Y$, it tries to find an $X$ that satisfies the above equation.  It does this by evaluating $H(X_i)$ when building the rainbow table, and encoding all those into the table.  Then, given a specific $Y$, we search through the table to see if there was an $X_i$ that we evaluated that happened to hash to $Y$.

Here's the rub; the rainbow table method is generic; it does not attempt to examine the internals of $H$.  So, the obvious question is: if we give it a hash value $Y$ where we did not evaluate the corresponding $H(X)$ during the build phase, how can it work?  Well, obviously it can't.  That means that, if we build a rainbow table that covers a dictionary of a trillion possible passphrases, that means that the we need to evaluate $H$ for those trillion possible passphrases.  That is, building a rainbow table is going to be expensive, and unless we can rely on some cryptographical weaknesses of $H$ or some other special property, there isn't anything we can do about it.

So, since rainbow tables do not decrease the amount of work, does this mean that they are useless?  No, it doesn't.  For one, we need to build the table once.  Yes, that is expensive, but looking up an entry in a rainbow table is cheap. Once we've evaluated those trillion hashes, we can later reuse that rainbow table many times to attack many hashes (and we don't need to know those values when building the rainbow table).

In addition, the other obvious question is "if that's what rainbow tables do, why don't we just build a large table of $(X_i, H(X_i))$ pairs, when we get a hash, we can then just look it up.  Yes, that would work; however if we expressed that table in the obvious way, it'd be huge -- disk space is getting cheap, but not that cheap.  Rainbow tables are essentially a clever way of making up such a table, but in a way that makes the table much smaller (that is, take up less disk space) than what you'd expect.


Large file validation on an embedded system through hash and encryption As a preface, I have to say that I am a noob in this area.  Having said that, I will ask the question.

I have a situation where I need to validate and protect against tampering a handful of large binary files (~1GB each with ~10GB total) distributed on an embedded system (think Android Tablet).  These original files will have a need to have a hash which can ensure that the files have not been tampered with.

Now, the challenge is that these files can be updated with a patch periodically downloaded from a webserver.  These patch files will also be distributed with a hash which will ensure that the patch is authentic.  (The files will be downloaded over a secure connection.)

Finally the patch needs to be applied to the original files on the embedded system which will then result in the need to regenerate the hash for the newly patched files so that they can be subsequently verified in the future.

There are several challenges:

Since these are large files running in an embedded system, the 'recommended' algorithms for hashing like SHA256 may prove to be too expensive to compute at runtime on a mid-range embedded system.  The back of the napkin calculation says that may take upwards of several minutes to compute.  Since this verification must occur every time an application launched to read this data, it must be very fast for 10GBs of data - less than 5 seconds.
Since the patch is being applied on the embedded system, the actual hash for the newly patched file must be computed on the embedded system itself.

My idea:

I was thinking that we could simply compute a faster, "weak" hash (like MD5) on the large files first.  Then I would make a server request (with mutual auth) to encrypt the MD5 hash with a private key and return an encrypted hash to the embedded system.  Then whenever I want to verify the file integrity, I would use the public key to decrypt the encrypted hash and then verify the hash against the actual files.

Any thoughts on this approach?  Does my idea work?

Thanks for your thoughts.

You can make incremental changes that only touch small pieces of the file faster, at a cost in complexity.

Multiple hashes can help with that.  Rather than a single hash value, you can amortise the cost of computation by storing multiple hashes.  If you hash the large file in pieces, then you can create a single hash that covers the entire file by hashing all the resulting hashes, which should be quick.

Then you only have to calculate the hashes over the chunks that the patch touches, plus a final pass to combine them all.

This effectively splits the big file into many.  The main consequences is that if the patch alters the size of chunks, the chunk boundaries have to move too.  That means that you have to maintain the chunk boundaries too, so what you store is a list of offsets and hashes.  And you'll have to be careful about applying the patch across a boundary.  That makes cumulative patches tricky to get right.

As long as the hash reported with the patch (you'll want to authenticate this somehow) has the same understanding of the chunk boundaries, then you are ok.  You could include the boundaries with the patch itself.

Don't use md5 if you care about preventing tampering, its collision resistance is miserable.  SHA-2 is plenty fast if you don't have to run it over your entire data set all the time.


half-gates in garble circuit Recently I've been reading papers about MPC protocol, but when I read the paper by Zahur, S., M. Rosulek, and D. Evans. 2015 Two Halves Make a Whole- Reducing Data Transfer in Garbled Circuits Using Half Gates.
The researchers proposed the state-of-art technology of optimizing garbled circuit.

Their main idea is to divide the AND gate into two half-gates.
\begin{align*}
  c &= a \land b \\
    &= a \land (r+r+b) \\
    &= (a \land r)+(a \land (r+b))
\end{align*}

As far as I can see, it seems that the generator half-gate is enough for an AND gate. based on the input value that the garbler has, it produce the garbled table:
$H(B)+C,H(B+R)+C+aR$. the evaluator can calculate the output label based on the label of its own input $B$ or $B+R$, and that's it, that's all for an AND gate.

I don't see why the authors construct the gate by combining two half gates.

I don't really see the intuition behind this construction, after reading the book A Pragmatic Introduction to Secure Multi-Party Computation written by David Evans, he wrote:

  It remains to show how the two half gates can be used to evaluate a gate vc = va ^ vb, in a garbled circuit, where neither party can know the semantic value of either input`.

As classical Yao circuit, two-party have their own input independently, why he assumes that they both know neither input?

As classical Yao circuit, two-party have their own input independently, why he assumes that they both know neither input?

Consider the circuit $(a_1 \oplus b_1) \land (a_2 \oplus b_2)$ where Alice's input is $a_1,a_2$ and Bob's input is $b_1,b_2$. The bits going into the AND gate are not known to either party, so you can't use one of the half-AND constructions.

Parties know their inputs to the circuit but not the input to every gate in the circuit. The bits going into an internal gate in the circuit can be influenced by both parties' inputs, so that neither knows the value in the clear. (You can indeed replace AND gates with half-AND gates at the input layer of a circuit.)


Are there cryptographic hash functions with homomorphic properties? Are there cryptographic hash functions that have homomorphism-like properties?

E.g. satisfying following relation $h(a || b) = h(a) · h(b)$, where $h(x)$ is hash function itself, $x || y$ is concatenation and $x · y$ is some hash-specific combination function making single hash given two of them. If that makes any difference, it can be also assumed $a$ and $b$ are of equal length, and $h(x)$ is expected to produce hash sums of same length regardless of $x$.

I can think of basic, non-cryptographic example — $h(x)$ can be plain arithmetic sum of character codes modulo 256, and $x · y := (x + y) \bmod 256$, so

$$ h(\texttt{"foo"}) = (102 + 111 + 111) \bmod 256 = 68 $$
 $$ h(\texttt{"bar"}) = (98 + 97 + 114) \bmod 256 = 53 $$
 $$ h(\texttt{"foobar"}) = (102 + 111 + 111 + 98 + 97 + 114) \bmod 256 = 121 $$
 $$ h(\texttt{"foo"}) · h(\texttt{"bar"}) = (68 + 53) \bmod 256 = 121 $$

So, is there something similar, but with high collision resistance?

My understanding is that, for the even more special case where a and b are not only of equal length but some power of two times a fixed block size, all hash tree systems (also called a Merkle tree system or a binary hash chain) meet your criteria.

  E.g. satisfying following relation h(a || b) = h(a) · h(b), where
  h(x) is hash function itself, x || y is concatenation and x · y
  is some hash-specific combination function making single hash given
  two of them.

In particular, the hash specified by the Tree Hash EXchange format (THEX) spec
uses the hash-specific combination function x · y == SHA1( 0x00 || x || y ).
whenever the underlying pieces of text a and b are the same length and are both some power of two times a fixed block size.

When c and d are exactly one block in size,
the tree hash T() used in THEX is defined something like

T(c) == SHA1( 0x01 || c ) # only for 'c' exactly 1 block long
T(d) == SHA1( 0x01 || d ) # only for 'd' exactly 1 block long
T( c || d ) == SHA1( 0x00 || T(c) || T(d) )
            == SHA1( 0x00 || SHA1( 0x01 || c ) || SHA1( 0x01 || d ) )

Typically a block has a size of 1024 bytes; Dan Williams and Emin G¨un Sirer have written a paper on picking an optimal block size.

There are apparently two common ways to avoid the easy collisions described by
" What is the purpose of using different hash functions for the leaves and internals of a hash tree? ":

some Merkle trees -- such as the THEX described above -- use one hash function for the leaves, and a different hash function for the internal nodes.
Other Merkle trees -- such as the one used by BitTorrent -- keep track of both the file length and the root SHA1 hash value, and files are considered "the same" only if both match. This allows them to use the same unmodified SHA1 hash function for both the leaves and the internal nodes. (Some people think of this as a single "tree hash value" that includes two parts, the file length and the cryptographic hash value).

Merkle trees can handle files with size that is not a power of two --
How does a "Tiger Tree Hash" handle data whose size isn't a power of two? --
but if the first file isn't a power of two times the fixed block size, concatenating 2 files doesn't give the nice relationship you wanted between the hash of the two smaller files and the hash of the bigger combined file.


Why does RSA give better security on longer messages? I am trying to understand the notion of RSA security.

Choosing a public exponent where $e = 3$ facilitates the calculations, considering that it is secure if the plaintext or message is long.

If the message is short, it affects security but why?

Does that relates to the $2^n$ possibilities, if the message is short the probability of knowing the message is high?

This only applies to "text book" RSA, i.e. plain modular exponentiation with the public or secret exponent.

If you have a $n$-bit modulus, and use a message $x$ shorter than $n/3$ bits, the modular part of modular exponentiation doesn't come to play when calculating the ciphertext as $c = x^3 \bmod n$. The effect is that you can simply calculate the (integer) cubic root of the ciphertext $c$ to extract the plaintext, and don't have to deal with the key at all.

I think similar attacks are possible if the message is only slightly longer than $n/3$ bits.

This is one of the reasons that you normally don't use textbook RSA, but standard RSA, which uses non-zero padding to fill up the message to the size of the modulus, so the modular reduction actually comes into effect. Another reason is that you need some randomness in the padding, to avoid that the same message encrypted twice with the same public key gives always the same result.

Also, in practice you are not encrypting the message directly, but encrypt a key for a symmetric algorithm, which then is used to encrypt the actual message, in a hybrid scheme.


Layered encryption in mixnets with post-quantum cryptography I am trying to implement a mixnet using post-quantum public-key crypto. Each message may be encrypted by up to 10 levels of public keys, shuffled, before the layers of encryption are stripped off one by one.

This is traditionally achievable in RSA, because the ciphertext is barely larger than the plaintext, but in the many popular post-quantum public key cryptosystems (based on lattice crypto), such as NTRU, it appears the ciphertext becomes an order of magnitude larger than the plaintext. So encapsulating a message in multiple layers of encryption is infeasible as the ciphertext doesn't scale.

Are there post-quantum public key exchange schemes suitable for this purpose? I've looked at the Open quantum safe project, but am unsure whether any of protocols there mitigate this issue, or are mature enough.

Might I suggest using traditional hybrid cryptography to cut down on the ciphertext growth size?  This is the straight-forward approach where you don't directly encrypt the message with the public key; instead, you pick a random symmetric (e.g. AES) key, encrypt the symmetric with the public key, and then AES encrypt the message with the symmetric key.

That way, the message expansion is the size of the encrypted symmetric key (which is fixed, independent of message size), and the message expansion caused by the AES encryption (which is tiny, perhaps 16 bytes).

If we estimate that an encrypted symmetric key is about 1kbyte (roughly true for NTRU), then iterating this 10 times with 10 public keys will cause a total expansion of about 10kbytes; certainly tolerable.

And, this can be done postquantum, by using a postquantum symmetric encryption (256 bit keys), and a postquantum public key encryption algorithm (that is, I haven't solved that problem for you...)


Are there any key exchange schemes that only require entropy on one side? Are there any cryptographically secure (in terms of confidentiality) key exchange schemes which are usable if one partner in the connection is entirely deterministic and has absolutely no entropy? I know the basics of the operation of several asymmetric ciphers but am not a cryptographer. I wonder this because it seems like it would be easy to provide initial entropy to embedded devices through an encrypted connection without running into the chicken and egg problem of needing entropy to securely connect to a service to retrieve entropy. If this is possible, is authentication also possible?

No.

A deterministic device initially holding no secret information can no establish any secret information thru public channels.

The argument is elementary: that device can be fully simulated by an adversary, which can thus determine any information that device may contain.


How are the AES inverse S-Boxes calculated? I would like to know, how to calculate the inverse S-box.
I followed this
link (with affine transformation first, then multiplicative inverse), but the result is wrong. For example, if I use the value 0x52 (01010010 in binary), reverse of this value would be 01001010.
The inverse matrix (for inverse S-Box) is:

Input = 0  1  0  0  1  0  1  0 (LSB First)
Row 0 = 0  0  1  0  0  1  0  1
Bit 0 = 0  0  0  0  0  0  0  0 = 0

Row 1 = 1  0  0  1  0  0  1  0
Bit 1 = 0  0  0  0  0  0  1  0 = 1

Row 2 = 0  1  0  0  1  0  0  1
Bit 2 = 0  1  0  0  1  0  0  0 = 0

Row 3 = 1  0  1  0  0  1  0  0
Bit 3 = 0  0  0  0  0  0  0  0 = 0

Row 4 = 0  1  0  1  0  0  1  0
Bit 4 = 0  1  0  0  0  0  1  0 = 0

Row 5 = 0  0  1  0  1  0  0  1
Bit 5 = 0  0  0  0  1  0  0  0 = 1

Row 6 = 1  0  0  1  0  1  0  0
Bit 6 = 0  0  0  0  0  0  0  0 = 0

Row 7 = 0  1  0  0  1  0  1  0
Bit 7 = 0  1  0  0  1  0  1  0 = 1

The result is 01000101, MSB first that would be 10100010, XOR-ed with final vector 0x52 is 0xf0. The inverse of 0xf0 is 0x5b, which is wrong. It should be 0x48. Where did I make a mistake?

You performed the matrix component of the affine tranformation correctly, what you did wrong was the addition of the vector prior to field inversion.

The value 10100010 (0xA2) is the correct result of the inverse affine matrix. The final vector of the inverse affine transform however is 00000101 (0x05).

The resultant 0xA7 is then inverted, which is 0x48, the correct inverse s-box value.


Public key crypto without modular arithmetic? This comment from Reddit math, in response to a statement about how people can communicate secrets to each other with a third party listening, has a very small, simple example of public key cryptography:

Take your message, treat it as a number and multiply it by a bunch of primes.
Send it to me. I will then multiply by a bunch of primes too.
I send it back to you. You then divide by all of your primes.
Send it back to me. I divide by all of my primes and get the original message.

This comment has 5700+ upvotes by Reddit math, but it strikes me as unusual because there's no modular arithmetic used, only primes.
Does this example actually work, if sufficiently large primes are used?

Breaking such a scheme is easy.

Suppose Alice wants to transmit a message $M$ to Bob. First thing, Alice picks an integer $R_a$ and sends the cipher text $C_a = M \times R_a$ to Bob. Bob then picks another integer $R_b$ and transmits $C_b = C_a \times R_b$ back to Alice. Alice calculates $D_a = \frac{C_b}{R_a}$ and sends $D_a$ to Bob. Bob calculates $D_b = \frac{D_a}{R_b}$ and clearly $D_b = M$.

Now, Eve intercepts the messages $C_a, C_b, D_a$ and might easily calculate $R_a = \frac{C_b}{D_a}$ and consequently $M = \frac{C_a}{R_a}$. Eve is clearly not supposed to be able to do this, so this constitutes a break.

Furthermore, it doesn't really matter if the multiplication is done in a finite group or not. In a group, division would be defined as multiplication with the inverse element of the divisor, e.g. $D_a = {C_b} \times {R_a}^{-1}$. Eve would still be able to calculate $M$.


HMAC computation using AES key I want to compute an HMAC value of a data set using CKM_SHA256_HMAC mechanism with AES key. I have the error code CKR_KEY_TYPE_INCONSISTENT because it seems that I need to use a key of key_type GENERIC_SECRET instead.
Is it possible to use AES key_type with this mechanism? If yes, how can I do it? Can you provide an example?

I see no way. Typed keys are typed to prevent them from being used for another task than being the key to the designated algorithm.

What you maybe could do is use the key to derive another, and use it as an HMAC key. But I do not immediately see how we could avoid that the HMAC key could leak of the PKCS#11 device.
Note: this comment sketches an option. But I can't remember of a key derivation mechanism in a PKCS#11 device that allows to derive a key remaining internal but where the new key is for a completely unrelated algorithm (even as a proprietary extension). Also, if the intended algorithm is not fed to the derivation, that could be susceptible to attack by using the same key for a variety of algorithms. For example DES to get 56 bits out of the first 64, then two-keys 3DES for 112 out of 128, then AES-128 for 128 out of 128, and so on.

If compatibility with standard HMAC is not needed, then an option is to compute an AES-based MAC of the SHA-512 of the message, which is possible with the key in the PKCS#11 device, and can likely be much faster since the SHA-512 of the message can be computed externally.


Extracting secret image from cover image I want to develop a steganography project with using exploiting modification direction method. I started to try and understand how the method works, but I have some questions about decryption.

I hid the secret image in a cover image larger than the secret image by 9 times. So when it comes to decryption I'm not going to use all of the pixels of the cover image: I only need to use those pixels used during encryption. But if the pixel count isn't provided before then how can I know how many pixels should be used to extract the secret image?

If I use all pixels of the cover image the resulting image's size doesn't match the original one and it is quite likely there will be flaws in the image.

The EMD method is a little outdated. The state of the art are Syndrome Tellis Codes. Please, check:

http://dde.binghamton.edu/filler/pdf/Fill10tifs-stc.pdf

In the EMD method, n pixels are used to carry one secret digit. Therefore, to extract this digit you need to use the same n pixels. The receiver needs to know what pixels are used by the sender.


Hard Problems in Pairings I want to know whether the following problem is considered as a hard problem in complexity theory or not?
Given $g,g^a,g^b \in G_1$ (for unknown $a,b\in \mathbb{Z}_p^{\ast}$), compute $e(g,g)^{ab^2}\in G_2$.
If yes, could you please help me to know the name of this problem in the literature?

There is a generalisation of the Diffie-Hellman problem to multi-linear groups known as the multi-linear Diffie-Hellman problem (MDHP, see this paper for example). Specifically, for a group $G_1$ endowed with an $n$-multi-linear map $e$ to a group $G_2$ the MDHP is: given $g, g^{a_1}, g^{a_2},\ldots, g^{a_{n+1}}\in G_1$ compute $e(g,g,\ldots,g)^{a_1a_2\cdots a_{n+1}}\in G_2$.
Your problem is clearly no harder than the MDHP for $n=2$ (take $a_1=a$, $a_2=b$, $a_3=b$), and if we can take square roots in either $G_1$ or $G_2$ then a solution to your problem solves MDHP with $n=2$.
To turn your problem into a 2DHP solver in the case where we can take square roots in $G_1$, $a=a_1$ and let $g^{b_1}=g^{a_2}g^{a_3/2}$ so that $b_1=a_2+a_3/2$ and $g^{b_2}=g^{a_2/2}/g^{a_3/2}$ so that $b_2=a_2/2-a_3/2$, then
$$e(g,g)^{ab_1^2}/e(g,g)^{ab_2^2}=e(g,g)^{a_1a_2a_3}.$$
Likewise if we can take square roots in $G_2$ let $b_1=a_2+a_3$ and $b_2=a_2-a_3$, then
$$\left(e(g,g)^{ab_1^2}/e(g,g)^{ab_2^2}\right)^{1/4}=e(g,g)^{a_1a_2a_3}.$$
Note that square roots are easy to take in cyclic groups of known odd order, which covers a great deal of cryptographic applications.


Generate fixed length cipher text from arbitrary length plaintext Using an encryption algorithm like AES, is it possible to generate a fixed length cipher text no matter how long the plain text becomes?

That is quite impossible. Lets assume that such an encryption scheme would exist and assume that it always outputs ciphertexts of length $n$ bits.

Then, because the scheme is assumed to encrypt plaintexts of arbitrary length, it in particular encrypts all plaintexts of length $n+1$ to ciphertexts of length $n$.
However, there exist twice as many plaintexts of length $n+1$ than ciphertexts of length $n$. So by the pigeonhole principle there exists at least one ciphertexts that encrypts more than one plaintext. This directly implies, that decryption would be impossible in such a scheme.


Sequential delayed release of chained HMAC keys for use as asymmetric signature Iterative hashing of a private random seed can yield keys for use in HMAC, which if revealed publicly in reverse order and on predetermined schedule, can be used in a manner similar to other asymmetric key signing protocols, where released intermediate key authenticity is verifiable in terms of its relationship to the first released (last in chain) key. The seed is like a private key, and the last of the chain (first released) is like the public key. Useful elaborations are possible, e.g. converting the chain into a branched hierarchy for delegation purposes.

This can't be a new idea. Is it? Does anyone know of existing work on this, either in the journals or in the wild?

This link restates the above with more detail, some diagrams, and a few elaborations:
http://ben.mord.io/p/delayed-chained-key-revelation-dckr.html

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


AES Padding (Nullbytes vs PKCS7) I currently implement the AES(128,192,256)(ECB,CBC). Does the type of padding affect security?
I just want to fill the blocks with null bytes.

Padding
You cannot fill the remaining blocks with the null bytes unless

The message has a fixed size that doesn't require sending file sizes.
The file size is sent over the channel.
The message doesn't contain null-bytes.

In the general, the padding must be unambiguous. 10..0 padding can be fine.

if data is 1234567890000000
now the data is 123456789 or 1234567890 or 12345678900 or..

if you use 10..0 then with the data 1234567890001000
it will be clear that the data is 123456789000

You can use PKCS#7 padding for ECB and CBC mode. PKCS#7 supports modes have block sizes larger than 64-bit block up to 255. The previous one, PKCS#5 padding had support up to 64-bit block size that was fine for DES.
In PKCS#7 padding, the remaining bytes count is padded as a byte value. For example;
123456789ABCDEF1     here consider the integers as bytes like 1 = 0x01
123456789ABCDE22
123456789ABCD333

Then the removal of padding bytes result in
123456789ABCDEF
123456789ABCDE
123456789ABCD

If the last block is full an additional block is filled with 1F
0123456789ABCDEF next block is full of `1F`s

The known padding methods are not limited to the above methods see more in Wikipedia: Padding_(cryptography).
For the complete difference between PKCS#5 and PKCS#7 see this canonical question What is the difference between PKCS#5 padding and PKCS#7 padding

CBC padding Oracle attack
For CBC mode operation, if padding oracle is applicable then the server can act like a decryption oracle. This attack academically first published  in 2002 by Serge Vaudenay. Although the servers are patched there are attacks based on the downgrade like Lucky13 and Poodle. Keep your servers on the secure level! TLS 1.3 has huge clean ups and it has no more CBC mode of operation. The TLS 1.3 encryption modes with their IDs;

{0x13,0x01} - TLS_AES_256_GCM_SHA384
{0x13,0x02} - TLS_CHACHA20_POLY1305_SHA256
{0x13,0x03} - TLS_AES_128_GCM_SHA256
{0x13,0x04} - TLS_AES_128_CCM_8_SHA256
{0x13,0x05} - TLS_AES_128_CCM_SHA256

One can see how the padding oracle attacks work in these answers and remember if applicable the attacker can decrypt all of the message not only the padded part.

If there is no such padding oracle attack then it is secure. Example the data stored as data-at-rest.

Padless modes
It is better to use a mode like CTR and OFB modes that don't require padding at all. They can work with arbitrary byte sizes.
Forget ECB
Don't use ECB which is insecure leaks patterns, it is not a probabilistic encryption, not even secure against KPA attacks on multi-block messages. Some even don't call it as a mode of operation.
Modern Modes
The all above modes are also called archaic mode of operation and they can have at most CPA. In modern Cryptography, we use and suggest to use Authenticated Encryption (AE) (AEAD: AE with associated data) modes like AES-GCM and ChaCha20-Poly1305 which can have IND-CCA2. These will provide you Confidentiality, Integrity, and Authentication, all in one. And remember, never use a key-IV pair again in these modes. If you want only leak about the same message is sent nothing more then use a misuse-resistant mode like SIV. AES-GCM-SIV will be the future.
There is a new mode
Daence: Salsa20 and ChaCha in Deterministic Authenticated Encryption with no noNCEnse as of 2020 by Taylor R Campbell

We present Daence, a deterministic authenticated cipher based on a pseudorandom function family and a universal hash family, similar to SIV. We recommend instances with Salsa20 or ChaCha, and Poly1305, for high performance, high security, and easy deployment.

This mode uses the Associated Data (AD) to eliminate the case that even the same message is sent under the same key-IV pair if the AD is different than the ciphertext messages will be different up to some probability.


How android apk file signing works? There are a number of pages on web to tell how to sign apk file for Android. But none I've found telling how it works under-the-hood. The (e.g from here https://github.com/appium/sign) command is java -jar SignApk.jar testkey.x509.pem testkey.pk8 my.apk my.s.apk and it has two files with keys - .pem (certificate) and .pk8 (as far as I understood it contains private key).

Official Android docs page app-signing says "Android requires that all APKs be digitally signed with a certificate". But certificate contains public key...

Do they mean app should by signed (presumably hash with private key) + with certificate (which is plainly attached to apk file)? That would explain why command above needs two files...

The APK signing is well documented by Android, actually:

You have here a high level overview of the process.
A new APK signature scheme (v3) has been introduced with Android 9, that is detailed  here. However notice the v2 can still be used.

The documentation about v2 has a good overview of what is contained in a signature block in an APK:

  For each signer, the following information is stored:

  (signature algorithm, digest, signature) tuples. The digest is stored to decouple signature verification from integrity checking of the APK’s contents.
  X.509 certificate chain representing the signer’s identity.
  Additional attributes as key-value pairs.

Now, what does that mean?

Well, the signer has to own the secret key corresponding to a certificate, that has to be verified by some Certificate Authority. The signer can then sign an APK and has to bundle their certificate chain inside of the APK, so that anyone can verify the certificate chain, and if it checks out, then check that the signature verifies under that certificate.
And the certificate is required in order to be able to link the public key we are using to verify that APK with a given identity. (Because otherwise, without certification, you have no link between a given secret/public key and an identity.)

Here "digitally signed with a certificate" is a misuse of language to mean that one is signing the APK using the private key corresponding to a public key stored in a certificate.

This is effectively done in practice by computing the signature of a digest (a hash) of the  of APK contents that is computed as indicated here.


Example of a Two-party GMW Protocol I have been looking for a concrete example of GMW protocol for two parties. I was trying with the following example for computing $XOR$ of two parties:

A's secret bit is $a = 0$, B's secret bit is $b = 1$.
A chooses a random string of length 2, namely $a_1a_2 = 00$, so that $a = a_1 \oplus a_2 = 0 \oplus 0 = 0$. B does the same, his secret string is $b_1b_2 = 01$, so that $b = b_1 \oplus b_2 = 1$.
A sends the second bit of her secret string, $a_2$ to B. B sends the first part of his secret string $b_1$ to A.
A now has $a = 0, a_1 = 0, b_1 = 0$. B has $b = 1, a_2 = 0, b_2 = 1$.
Now, GMW protocol says that A and B can locally compute $c_i = a_i \oplus b_i$ and the result should be same for both. However, as you can clearly see, in this particular example, they are not the same. A's xor is 0, B's is 1.

I think I have a misunderstanding somewhere, but I don't know where. Help, please?

GMW protocol says that A and B can locally compute $c_i = a_i \oplus b_i$ and the result should be same for both.

I highlighted the part that is incorrect. They started with secret shares of $a=0$ and secret shares of $b=1$. Now they have secret shares of the XOR $c= a \oplus b =1$.

Only if the secret value $c$ is zero will their shares be the same (and of course, they have no way of knowing whether this is the case). In your example $c=1$ so their shares will be opposite.

Basically, you can see that $c_1$ and $c_2$ are valid secret shares of $a \oplus b$ since:
$$
  c_1 \oplus c_2 = (a_1 \oplus b_1) \oplus (a_2 \oplus b_2) = (a_1 \oplus a_2) \oplus (b_1 \oplus b_2) = a \oplus b
$$


What's the difference between a known-plaintext attack and a ciphertext-only attack in terms of performance? I know that in the KPA the attacker has access to both the plaintext and the ciphertext, but in the end it all comes down to performing an exhaustive key search. I'm not sure if having the corresponding plaintext for a given ciphertext makes such an attack any less laborious. So I wonder, are they equally effective? And why do we make this distinction if they're practically identical?

Usually we are talking about various attacks which are better than brute force, these attacks can very greatly depending on what we can do.
Ciphertext only is usually the most restrictive setting. Known Plain text where we have several plain&cipher text pairs is common. But we also have other attack modes. chosen cipher text, adaptive chosen plain text and mode.

If we take some classical ciphers for example. We will see a significant difference between the cipher text only and known plain text attacks. We know how to perform ciphertext only attacks on Viginere or substitution ciphers using only statistical knowledge about the plain text such as letter frequencies. But with a known plain text the key is trivially revealed. In Viginere subtract the cipher from plain and receive a repeating key. Without any tricks for finding key length or matching column frequencies.

Even with the simplest ciphers we see differences.

Also with modern attacks, different attacks published require different kinds of access. For a more modern example, let's look at a stream cipher with a limited internal state. For instance A5 family used for cell phone encryption. With cipher text only we don't have much to do in the way of generic attacks. we can brute force internal state and do a crib drag over cipher text to see if we find something that looks like plain text.
However when we know parts of the plain text (and we almost always do, due to protocols used and other reasons). We can do better, we can get parts of the key stream by xoring the known plain text with the cipher text. And not only brute force the internal state more efficiently looking for matches in the key-stream fragments we have, we can even off load most of the work and do Time-Memory-Date trade-off attack.

Better access, often leads to better more efficient attacks, though these are still specific to the cipher of cipher family.


Are GPUs inefficient for calculations on big numbers? Is RSA and EC cypto generally done on CPU only? Looking specifically at RSA and EC algorithms which imply doing operations on integers >= 256 bits (>> 64 bits), I have noticed (from my limited experience) that 99% of the software for crunching big numbers is designed for CPU. For example, there appears to be no actively maintained CUDA package for big-number operations (arbitrary length or even 256-512 bit numbers for EC calculations).
Is there a reason for big number calculations (and thus RSA and EC calculations) to remain on CPU? Is it sub-optimal to run such computations on GPU (I understand that GPUs are not optimized for big number calculations because there is no such requirement in graphics, but can't it be efficiently done anyway)? Will this change in the future or will RSA & EC remain on CPU?

If you run RSA speed tests in OpenSSL you'll see that many operations are pretty fast, with the possible exception of RSA key pair generation. However, for that reason key pair generation is generally not used very often - RSA is generally not used to provide forward security in transport protocols, for instance.
CPU's have been upgraded as well, and they can perform up to 512 bit operations on large numbers nowadays - see e.g. Intel's AVX-512. Although those still come with some drawbacks I would expect that those disappear as the technology matures.
Using GPU instructions has the following drawbacks:

for top performance you generally need vendor specific code;
not all (security minded) servers will have fast GPU support;
the CPU instructions used for the asymmetric primitives are generally not the bottleneck - bulk encryption would take much more CPU power.

Furthermore, latency introduced by the PCIe bus makes the GPU most applicable for parallel operations, and the amount of parallelism for e.g. performing private key operations is usually limited.
Of course, I would imagine that e.g. a double ratchet that uses a lot of (EC)DH operations could still benefit from CUDA. But it would be a lot of work to create, to secure and to maintain.
Note: that said, I didn't perform or lookup any benchmarks for GPU's - I do run OpenSSL speed tests now and then - if just to test the new hardware that I buy.


Double Encryption Using same key I am new to crypto and wondered what would happen when we encrypt twice using any algorithm and the same key.
Consider two block ciphers A and B.
We generate the ciphertext as c = A(B(m)) for any message m.
If they are in the same message space and they map to the same ciphertext space, why would using the same key on both schemes make the encryption insecure?
I have understood meet in the middle attack and the general idea of collisions when using two functions mapping to the same ciphertext space.
Is there any other approach?

Edit: I am also looking for attacks except the case where one encryption undoes the decryption of the other.
eg. B is inverse of A

I'll be answering the question as in its body, which does not match the title (double encryption implicitly refers to using the same block cipher for each encryption, when the question is explicitly about two block ciphers).

With only the hypothesis that $A$ and $B$ are secure block ciphers sharing block size and key size, we can't conclude that the compound block cipher $G$ defined by $c=G_k(m)=A_k(B_k(m))$ is secure. An extreme example is that $G$ could be the identity function (e.g. $B$ could be AES-256 encryption, and $A$ AES-256 decryption).

And we can't make a rigorous exception for that case: $A$ and $B$ can interact badly in many ways to that $G$ is weak when $A$ and $B$ are secure (e.g. $B$ could be AES-256 encryption except for a modified S-box in the first SubBytes, and $A$ straight AES-256 decryption, so that $G_k$ is a transformation with no diffusion between bytes of a block, and quite a weak transformation of each byte).

On the other hand, there are (overwhelmingly many) cases where $G$ is more resistant to attack than either $A$ or $B$ is (e.g. $B$ could be AES-256 encryption reduced to the initial AddRoundKey and first 7 rounds, and $A$ AES-256 encryption reduced to the last 7 rounds, so that $G$ is the full AES-256). Thus we can't hope for general attacks working against $G$.

Thus, sorry to say, but what's explored with the question's body appears to be a dead end.


How Will Quantum Computing Change Cryptography's Future? Quantum computing is at the intersection of math, physics, and computer science.

It seems so complicated that only large organizations could build such algorithms and have their own quantum computing devices and the other essentials to calculate such complicated equations.

If there is a major advance in the production of quantum computing science and its equipment becomes available to either hackers or intelligence services, can cryptography survive quantum computing?

P.S: If we could not upgrade to quantum or post-quantum signature schemes, then what happens?

It depends on the kind of quantum computer and how many logical qubits it has. Not all quantum computer designs are capable of breaking cryptographic systems. The popular adiabatic quantum computers, while very useful for certain tasks, have no cryptanalytic utility. Designs that are capable of running, say, Shor's algorithm are currently in their infancy. It isn't known how well they'll scale.
Realistically, when/if such quantum computers become mainstay, we will need to have moved from algorithms based on factorization or the discrete log problem (or any other hardness problem in the BQP complexity class) to a post-quantum variant. Key exchange algorithms must be upgraded sooner. If you need 25 years of protection, you have to discontinue vulnerable algorithms 25 years before quantum computers can attack it, because they are vulnerable to retroactive cryptanalysis.
It's not as important to upgrade to post-quantum signature schemes. You can delay upgrading a digital signature algorithm until the very day a cryptanalytic quantum computer becomes available. This is because breaking a signature must be done at the time of the attack, not after. This isn't unique to quantum computers. Someone who used PGP in the 90s with a 512-bit key doesn't need to worry about someone forging their signatures because that key has long-since expired or been revoked, so obtaining such an old private signing key is useless.
NIST is currently working on standardizing post-quantum key exchange and signature algorithms for this very reason. They have set a tentative completion date for 2024.


RSA with small decryption exponent I've heard that textbook RSA is insecure when decryption exponent $d$ is smaller than  $N^{1/4}$ where $N$ is the public modulus. Why is it the case and what would be  a simple explanation of the attack ?

RSA without proper padding using randomness (plain old RSA) is not to be used in practice, and the attacks on small exponents assume plain old RSA, or a means of getting past the padding, such as the so-called million message attack.

The original attack on plain old RSA using such small exponents was due to Wiener. There has been further work showing that an even larger $d$ than $d>N^{1/4}$ is required, such as work by Maitra and Sarkar.

In addition, please see the extensive discussion in the question RSA with small exponents.


One way permutation and its inverse Is the following statement correct?
Let $F$ be a OWP. Then the inverse $F^{-1}$ of $F$ is also a OWP.

In general, unless the OWP also happens to be a trapdoor permutation, there is no way to efficiently evaluate the inverse. So, no.


Constant time implementations of crypto algorithms To protect against cache attacks (side channel attacks) generally constant time crypto implementations are advised. In some cases DJB released new algorithms (chacha) that are designed with this in mind (as one of objectives). If so --

Are constant time implementations feasible for all popular algorithms?
 I ask because AES, RSA, SHA*, EC* and DSA algorithms (at least some of them) are not designed with side channel attacks in mind. Given that, are these secure to use in software? ( I know secure is a loaded term here but I am speaking strictly from a side channel perspective).
Do all the standard libraries support this constant time implementations? I would like to see an implementation that does this compare against something that does not.
I know using an algorithm in hardware is the way to go. When a crypto algorithm is "implemented in hardware", does it usually mean its implemented completely in hardware or are parts of it implenented in microcode? I know AES is probably completely implemented in hardware, what about ECDSA or something thats a bit more complicated?

Any function can be made timing attack resistant, and may be more expensive. I.e. AES can be made safe by using a hardware-simulated constant time circuit for lookups (and maybe more magic).

If you need AES: use hardware with a constant time fallback in software. If you don't need AES then prefer it by hardware, then negotiate to a fast software cipher such as chacha20.

I'm yet to investigate (as I don't use these "standard libraries"). Which libraries are we including in standard? OpenSSL? LibreSSL? BoringSSL? Libsodium?
The AES round function is implemented in hardware. This enables the caller to decide the mode I.e. CTR vs CBC vs GCM etc. Last I checked AESNI included sha1 and sha2, but not any ECDSA nor ECDH nor EdDSA nor RSA. Hardware can implement any of these, however, not all functions have a significant speedup in hardware such that using hardware is preferred.


Proving Pseudo Random Generator from other Pseudo Random Generator? How can I prove that if $G$ is a Pseudo Random Generator, then other generator is a PRG (while the range's size is different)?

For example: for the PRG $G$ (from $n$ to $t(n)$ where $n < t(n)$), the generator $G'$ (from $n$ to $n+1$), where $G'$ returns the first $n+1$ bits of $G$) is PRG too?

Is the fact that the ranges are different affect the indistinguishability between the PRGs?

Well I think you can prove it by reduction:

If there exist an efficient predictor $P$ that given the first $n$ bits of $G'$ is able to predict the $n+1$ bit then we can construct a distinguisher $D$ for $G$ defined as an elementary wrapper of $P$, that can distinguish $G$ from a truly random generator.
Since by assumption $G$ is a (secure?) pseudo-random generator there is not such a $D$.


Could using sequential plaintext uncover AES key? I am encrypting a string in a format like this:

Byte 1: 1 (this byte is CONSTANT and KNOWN)
Byte 2-18: a random string of characters that is never the same.
Byte 18-34: unknown number that is sequentially incremented each time
            (it's a primary key from a mySQL AUTOINCREMENT column)

The entire 34 bytes is encrypted using 128 bit AES key.

Let's assume the attacker has access to several million of these strings that were generated sequentially and the attacker has them in order. This means the attacker knows that Bytes 18-34 are several million integers, each exactly 1 apart (eg, 100, 101, 102, 103, etc).

Could the attacker:

Figure out the AES key if the IV used to encrypt all the strings is the same?
Figure out the AES key if the IV used to encrypt all the strings is NOT the same (one IV per string), but known?
WITHOUT figuring out the full key, would it be possible for the attacker to compose their own string that allows them to set their own known value for bytes 18-34, and simply put garbage in the rest of the bytes?

AES is supposed to be immune from known plaintext attacks, but I am having trouble wrapping my head around how far that extends in practice.

Many thanks in advance.

Could the attacker figure out the AES key if the IV used to encrypt all the strings is the same?

No; the AES key is secure against such an attack.

  Could the attacker figure out the AES key if the IV used to encrypt all the strings is NOT the same (one IV per string), but known?

No, the AES key is secure against such an attack.

You say that you are having trouble wrapping your head around how strong AES actually is; it extends pretty far. In fact, AES is secure against a chosen plaintext attacker; that is, even if the attacker supplied Gigabytes of data for you to encrypt, and you encrypted them, we still don't know how an attacker would be able to use that to reconstruct the key.  This attack model is obviously much tougher on AES than your model (where the attacker just knows some information about the plaintext, but doesn't get to pick it).

  WITHOUT figuring out the full key, would it be possible for the attacker to compose their own string that allows them to set their own known value for bytes 18-34, and simply put garbage in the rest of the bytes?

Ah, that's a different question; that actually depends on the mode of operation that you use AES in.  The mode of operation is how you use AES (which just defines a transformation between 16 byte blocks to 16 byte blocks) to actually do something interesting, such as encrypting a long text.

What you are asking is 'suppose an attacker takes an encrypted message; could he modify that encrypted message, so that the modified message decrypts into something that the attacker wants (or, at least, parts of the decrypted message is what the attacker wants).  Now, there are multiple encrypting modes of operations defined for AES; they differ about how well they handle this.

If you are in a scenario where an attacker might be able to modify the ciphertext, you usually want to use something that detects such games; there are two standard ways of handling this:

You can encrypt the message (using any mode of operation that does encryption), and also apply a separate Message Authentication Code (such as HMAC or CMAC) on the ciphertext.  The MAC has the property that if anyone modifies it, the computed MAC and the MAC in the message will not agree, and so you know that someone modified the message.
You can use a mode of operation that does that inherently (such as GCM); these modes effectively both encrypt and perform a MAC on the message.