Is it possible to have multiple RSA private keys? I just did some math:

Pick $p$ and $q$ distinct primes;
Calculate $N=p\cdot q$;
Calculate Euler`s totient => $\phi=(p-1)\cdot(q-1)$;
Pick an $e$ (public key), coprime with $\phi$;
Calculate $d$ (private key) which is equal to $e^{-1} \bmod \phi$.

And figured out that $d$ (private key) can be multi-valued:

$$d = (\phi * k + 1) / e$$

This $k$ lets calculate a lot of different $d$`s. And are all of them correct private keys?

Where did I go wrong?

You are wrong in assuming that any $(\phi * k + 1) / e$ gives modular inverse of $e$ modulo $\phi$; actually if $e$ and $\phi$ are coprime the modular inverse $d \in [0..\phi-1]$ such that $de = 1 (\mod \phi)$ is unique, and only a single $k \in [0..e-1]$ gives the modular inverse.

As an example consider $(p,q) = (5,11)$, $\phi= 4\cdot 10 = 40$. Let us choose $e=3$, coprime with $\phi$: $gcd(3, 40) = 1$; then $d=e^{-1}(\mod 40) = 27$.

Using your expression:

$(k = 0) : 0$ (wrong)
$(k = 1) : (40 + 1) / 3 = 13$ (wrong)
$(k = 2) : (40\cdot 2 + 1) / 3 = 27$ (got it, $27 * 3 \mod 40 = 1$)

But the choice of decrypting exponent is indeed not unique. To obtain the minimal decrypting exponent one should use $d^\prime=e^{-1}(\mod lcm((p-1),(q-1)))$ instead of $d=e^{-1}(\mod (p-1)(q-1))$. For the above example, $lcm(4,10) = 20$ and $d^\prime=7$, which is less than $d=27$ and so a better (faster) decrypting exponent.

As a sanity check, let us encrypt/decrypt number $8$:

encryption:  $8^3 \mod 55 = 17$
decryption using $d=27$:  $17^{27} \mod 55 = 8$
decryption using $d^{\prime}=7$:   $17^{7} \mod 55 = 8$

Any $d=7+k\cdot 20$ where $k = 0, 1, 2, ..$ is a valid decryption exponent for the above example.


Input existence proof for known partial input and hash Let $h$ signify the hash (Merkle–Damgård construction) generated from some input of known length $n$. Given $h$ and an input $k$ of length $n_1$, is there a way to prove that there exists (does not exist) some (any) $r$ of length $(n-n_1)$ such that $h=H(r||k)$?

It depends on what exactly do you ask for:

You know such $r$ that $h$=$H(r||k)$ and want to provide someone proof that you know it or
You have only $h$, $H$, $n$ and $k$ and you want to check if $r$ exists

First case should be possible with something like zkSNARKs.

In second case there's no way to do it in polynomial time for any $H$ that is second-preimage attack resistant. Proof:

Let $n_a$ means bit length of $a$. We have some secret input $M$ and $h=H(M)$. Let's assume there exists algorithm $A(H, h, n, k)$, polynomial in terms of security parameter $n$, that :

  returns $1$ if there is $r$ such that $h=H(r||k)$ and $n_r=n-n_k$

  returns $0$ otherwise.

We can use $A$ to efficiently create collision with $M$ with the same length. In pseudocode:

  $M' = \{\}$

  for each $1\le i \le n$ do:
  $M'=A(h, n_M, 1||M')||M'$

After that you have $M'$ that satisfies $H(M')=h=H(M)$ and $n_{M'}=n_M$. So $H$ wouldn't be second-preimage attack resistant.

You can of course iterate through every value of $r$ and check if $h=H(r||k)$ but that takes $2^{n_r}$ steps (in case there's no such $r$).


Can you tell me how to create a cipher please? just a little simple one I don't how to make a cipher text at all, can you help me?

I was in your shoes about a year ago. The biggest help to me was Kahn Academy's crypto lessons (https://www.khanacademy.org/computing/computer-science/cryptography). The best thing it did for me was to define what many of the terms were without going too deep into the math.
To directly answer your question, the most basic cipher is letter substitution: A = D, B = E... So to create the cipher, add three letters to each plaintext letter. To get the plaintext back, subtract the same number from each letter. Tada! You have a cipher text!


Can DH shared secret provide integrity? Assume that A and B have exchanged their public keys beforehand. Now, A and B wants to communicate over an insecure channel and want to provide integrity and confidentiality on the message. A use the shared secret calculated using DH to encrypt the message using a symmetric cipher. If B can decrypt the message, can B be assured that this message is written AND encrypted by A?

In general the answer is no.

First, you need to make sure that your DH key agreement is authenticated. Otherwise you have no guarantee that you are talking to A at all.

Second, the symmetric cipher you use needs to provide authenticity so you should use some AEAD scheme. Otherwise somebody could just change the symmetrically encrypted messages.


Could a fixed RSA encryption be used instead of a salt to prevent rainbow table attacks? It's common to use a salt before hashing a password in order to prevent an attack by rainbow tables.
Would it also work to encrypt the password for instance by RSA encryption - by a permanent RSA private key stored on the server - before hashing?
In other words: $hash = SHA(RSA(password))$
For me this looks secure because rainbow tables wouldn't work with the encrypted cipher $RSA(password)$, would they?
(Side note: Since that RSA private key is not used for encryption at all, it would never have to been replaced...it would just work as a totally deterministic pseudo-random function in this case!)

I don't see a point of using RSA for password hashing. Using SHA and RSA will not make the bruteforce attack slower. The massive GPU/ASIC attacks will still work if we assume the public key $(e,n)$ is known. That is why we need memory hard functions to make the attacks slower. Sticking the standard is still better like using Argon2id ( Argon2 was the winner of the Password Hashing Competition in 2015). The unique salt also helps to eliminate the rainbow tables. Rainbow tables are dead for passwords system that deploys unique salts!.
A minor point is that one doesn't need to store the RSA private key $(d,n)$ since one cannot reverse the SHAx. So it is useless.
Back to Rainbow
in case of protection against the rainbow tables, one needs to make sure that every password needs a domain separations. This is achieved by unique salt for all. If you want to use the RSA then you need to use OAEP padding or PKCS#1 v1.5. padding. Both are probabilistic encryption scheme that as long as you have a good random number source like /dev/urandom then if you encrypt the same message again and again you will get different results, up to a huge limit of course ( the size of $r$ in the OAEP). One can think of the salt as this randomization.
A side note: the pepper, which is unique salt for each application server, is used to separate the domains of the applications in the case of hitting the same salt for the same user. Also, If an attacker downloads the users' table with only an SQL injection, then they cannot apply even brute-force without the pepper of the server.
Note 2: According to Hashcat list, only OpenSSH uses RSA in a combined mode RSA/DSA/EC/OpenSSH

Addendum
This part is based on the comments of @fgrieu in the case that @marcus considered these;

$(\text{salt},hash = \text{PasswordHash}(\text{salt},\text{DeterministicPadding}(\text{password})^d\bmod n))$

$(\text{salt}, hash = \text{Hash}(\text{DeterministicPadding}(\text{salt}\mathbin\|\text{password})^d\bmod n))$

Here the deterministic padding stands for padding the message for RSA encryption, but deterministically, like RSASSA-PKCS1-v1_5.
It is obvious that if the salt is unique for each user then it is already secure against the rainbow tables. The password crackers if access to the passwords' hashes, cannot test it without the knowledge of the private key.
The biggest problem is the protection of the RSA private key. The usual approach is using HSM to handle those encryptions where the RSA key is stored, too, however, for heavy systems, it may be a bottleneck for the speed. This is no a real comparison, and the usual advice for the password hashing algorithms is adjusting the iteration so that it takes around 1 second per user. This is for user-friendliness. i.e. the general user may not want to wait too much for the login process.
Knowing the public key $(n,e)$ won't help the attackers since they, as of public knowledge, cannot break RSA > 829-bit. See current records on How big an RSA key is considered secure today?
We can consider this RSA operation as a pepper of the application server, too. Also, instead of RSA, one can use HMAC-SHA256 for the same usage, which has a lower key size.
In short, if the key can be protected, It has more protection against the usual approach.


Is it safe to compute HMAC(Base64(IV) || "," || Base64(CipherText)) instead of HMAC(IV || CipherText)? Let || be the concatenation operator.

Let CipherText = AES(Key1, IV, Message).

Let us assume AES is used in CBC mode.

I want to compute an HMAC tag on the IV and CipherText.

Normally, one would do the following:

Tag = HMAC(Key2, IV || CipherText)

I want to know if the following would also be equally secure:

Tag = HMAC(Key2, Base64(IV) || "," || Base64(CipherText))

I want to know if the following would also be equally secure

Yes, both schemes are equally secure. Also for what you are trying to achieve you really shouldn't puzzle things together yourself but rather use pre-made modes like AES-GCM, AES-EAX or ChaCha20-Poly1305.

In fact, we can prove the above claimed security equivalence. Because Encrypt-then-MACis easily proven secure if the MAC is a vector-PRF (or vector-MACs) (i.e. a PRF that takes a triple of IV, associated data and ciphertext instead of a string as input) we're gonna prove the equivalence of these two vector PRFs and argue why the first one is a vector PRF.

$F_K(IV,\perp,C)=\operatorname{HMAC}(K;IV\|C)$ is a vector-PRF assuming HMAC itself is a normal PRF. To see this first note that IV has fixed length in all cases and thereby the concatenation is unambiguous, that is you always know what part is the IV and which part the ciphertext. Now because of this whenever the input to $F$ is different, so is the input to HMAC and because HMAC is a PRF we get a freshly chosen random string in that case which makes the behaviour indistinguishable from a vector MAC.

Next we'll prove that if $f_1$ and $f_2$ are injective and if $f_1$ has a data-independent output length (which we assumed earlier remember!), then $G_K(IV,\perp,C)=\operatorname{HMAC}(K;f_1(IV)\|f_2(C))$ is a vector PRF as well. For your case imagine $f_1$ being the base-64 encoding of IV and $f_2$ being the base-64 encoding of the ciphertext prepended by the comma literal.
So first note that because both functions are injective there's never a case when there's two distinct inputs that map to the same output. Because of this all non-repeated inputs to the underlying vector PRF are unique and therefore we always get freshly random outputs making this on a vector PRF as well.

If you might be wondering whether it's safe to assume that HMAC is even a PRF, then note that this is the basic use-case that HMAC was designed for and the entire reason it is a secure MAC.


Williams' $p+1$ in tandem with Pollard's $p-1$? Since the success of the $p - 1$ algorithm depends on $p - 1$ having "small" prime factors, or at least smaller than a reasonable smoothness bound, and Williams' $p + 1$ method has the same constraint for $p + 1$, it seems to me that it would be extremely unlikely for neither $p - 1$ nor $p + 1$ to be smooth. So if we were to construct, say, a tough 500-bit (RSA-type) semiprime such as

$n = pq = \ $ 2218295966162666629041316944231086113195058068148716022472522769336934503490317077398434252307822130896437753111872862038992461352826985916137012449841,

where $p$ and $q$ are both "safe" primes to guarantee worst-case performance for the $p - 1$ algorithm (that is, $(p - 1) / 2$ and $(q - 1) / 2$ are both Sophie Germain primes), would it make sense to attempt the $p + 1$ algorithm after $p - 1$ had bailed out? In other words, is there anything to be gained by trying that before ECM or bringing out the "big guns" of QS or NFS?

Oh, and I also generated the above semiprime with $\frac{p}{q}$ large enough to thwart factoring via Fermat's difference of squares method:

$\left|p - \sqrt{n}\,\right| \gt \sqrt[4]{4n}$.

These attacks are not relevant today because ECM, QS, and NFS are more cost-effective at modulus sizes providing serious security, which these days must be well above 1024 bits, preferably at least 2048 bits.

See past questions [1], [2] for more background on these criteria in historical RSA key generation recommendations, which these days are obsolete since the development of ECM, QS, and NFS.


Signing many small messages with minimal overhead I have a distributed system where each client writes many small messages, roughly the size of messages in a chat system, e.g. ~100-200 bytes each. I want each message to be signed so that we know for sure who sent each message, but the overhead of an RSA signature on each message is huge, so I need another approach.

One idea would be to sign the first message like normal, and include a hash of a random value. Then, in the next message, include that random value and a new hash of another random value. Each message "unlocks" the previous message's hash, showing that they were authored by the same client. Using a bcrypt/scrypt/argon2 hash with a work factor to meet about 10ms would mean that the random value could be kept small, say 64bit. Each message also has a unique id, which would be used as a salt. This is a huge improvement in overhead, but I have no real idea how secure such a system would be. Also, messages store ordering information, so once a message has been "unlocked", that random value cannot be used to "sign" a second message.

Some messages would contain encrypted fields, using some form of hybrid encryption. The servers only need signed metadata, not the actual messages.

I'd say this is a great example of where "don't roll your own 1. distributed system 2. crypto" applies. I've got the distributed system part, but I need your help with the crypto.

How can I sign many small messages (tens of thousands) with as little size overhead as possible, while still being secure? I've got 50MB of RAM and about 10ms of cpu time for decryption of each message. The client must be able to sign, encrypt and send messages without getting a response from the recipient(s).

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

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

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

Alternatives that immediately come to mind:

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


How can I attack a Triple-Block cipher with 2 keys (like 3DES) with a cost of ≤ 2⁵⁶ I am trying to solve something and I have but I have no idea anymore. Maybe anyone of you has an idea/solution/hint.

Given is a block cipher $F$ with key length $n$. It looks like this:
$$c = ENC_{k1}(DEC_{k2}(ENC_{k1}(m)))$$
with key length $2n$. I have to figure out a key recovery attack with $O(2^n)$. There is an additional information that a few plaintext/ciphertext are enough to verify the found keys.

I’ve already been reading some papers like On the security of 2-key triple DES, which describes the van Oorschot-Wiener attack and a generalized method. But even after reading the paper, it seems that the complexity is still larger than $O(2^n)$.

I even had a look for questions which are similar to mine and which might have described better attacks than the van Oorschot-Wiener attack I’m currently fiddling with, but none of them offers a usable answer to what I’m trying to find. For example, in the Q&A “Why is triple-DES using three different keys vulnerable to a meet-in-the-middle-attack?” they are doing a meet-on-the-middle which costs $2^{112}$ operations, which would be $2*keylength$.

The van Oorschot-Wiener attack I’m trying obviously has a lower attack cost. Here it seems that the cost can be reduced to $2^{56}$ but I have no clue how; meaning: even when I use the van Oorschot-Wiener attack and calculate the attack costs for 3DES, I get $2^{57}$ and not $2^{56}$ as expected.

Am I simply missing something somewhere (like: is the $2^{57}$ I’m getting actually correct)? How can the cost of the attack be reduced to $2^{56}$? Or does something better than van Oorschot-Wiener’s attack exist, which enanbles us to attack this scheme with an attack cost $\le 2^{56}$?

What I did so far:

I have a couple plaintext/ciphertext pairs. I put them into
table 1 and sorted it by the plaintext.
For $k1 = 1, ... , 2^{56}-1$ :
$P_{k1} = DEC_{k1}(A)$ where $A$ is a fixed value.
Lookup $P_{k1}$ in table 1 and if it is in, take the corresponding C and  compute $B=DEC_{k1}(C)$.
Store $B$ with $k1$ in table 2.
For $k2 = 1, ... , 2^{56}-1$ :
$B_{k2} = DEC_{k2}(A)$
Lookup $B_{k2}$ in table 2. If it is in, $k2$ and $k1$ are possible candidates.

Step 2 and 3 need each $2^{56}$ computations and if I am not mistaken, this would be $O(2^{57})$. This does not consider the search in the table.

Here is the answer to this question. There is an attack based on the following paper: http://cs.jhu.edu/~sdoshi/crypto/papers/p465-merkle.pdf

Here is a visualization on what happens:

Here is the algorithm:

Two things happen in step 1 (a). The decrypted value of 0 is interpreted once a M2 with the key $k_{2}$ and once as $P_{0}$ for the key $k_{1}$. This means with just one operation we get 2 values!

In step 1 (b) the value gets saved in a table with $i$ which represents the key $k_2$, and a label middle. This table will be used for a table look up (TLU) later on.

In step 1 (c) you see there is an $ENC(S^{-1}_{i}(0))$ where $S^{-1}_{i}(0) = M2$ from step 1 (a). This is a CPA request. We ask the algorithm to encrypt the value from the first step. This goes into another decryption $S^{-1}_{i}$, where $i$ represents $k_{1}$.

The value from the previous step is saved in the table with $i$ ($i$ = $k_{1}$) and a label ends.

The last steps should be self explanatory.

The question is: Why is it working?
Let's have a look at step 1 (c) again:

$S^{-1}_{i}(Enc(S^{-1}_i(0))) = S^{-1}_{i}(S_{k1}(S^{-1}_{k2}(S_{k1}(S^{-1}_i(0)))))$

You see, that if $i = k1$ we get the following:

$S^{-1}_{i}(Enc(S^{-1}_i(0))) = S^{-1}_{k2}(0)$

This is saved in the table and that is the reason why we look for adjacent entries in the table with the labels.

Complexity:

The for loop goes from 1 to n: $O(2^n)$
Within the loop we have $2^n$ CPA requests
Space: When I am not mistaken: $O(2^{2n})$

I hope it helps some people :)

As far as I know your attack is the best attack known, unless something better has very recently been published.

Please note that for DES as the basic cipher the chosen $A$ may not work, but you can choose another $A$ and try again

Also, for a generic cipher with $k$ bit key, the complexity is $$2^{k+1}=2\times 2^k=O(2^k),$$
as $k$ increases.


Short Ed25519 keys: can I use as ID? I am building the distributed system, where each user sends signed messages. I dont want to have a certificates system for public keys, like it is done in SSL, so I thought to use public keys themselves as user id.
Like:

a message from My public key to Your public key: hello!
and here goes a signature of "hello!", made with sender's secret key.
and anyone can validate the message by sender's id,
which also happens to be his public key, making the message self-contained

One thing I am not sure about...
Ed25519 public keys are so short, isn't it risky to use it as unique user id? What's the odds of system generating same user ID for more than one users? given that when public key is generated - system is unable to check if this user ID already exist (because of the distributed nature of the system)

What's the odds of system generating same user ID for more than one users?

You need to have way more than $2^{100}$ key-pairs / users for a collision.

With Ed25519, the public key is $P=[a]G$ with $a$ being the private key and $G$ being the public generator point of the curve. Now because of the determinism of the scalar multiplication, if $P=P'$ then $a=a'$ and thus the users share the same private key. If both users are using a good random number generator, they never pick the same private key. More precisely: If you generate less than $2^{126}$ key pairs there shouldn't be any two key pairs with the same private key, because you would be looking for colliding random 256-bit strings.


Using ECDH for encryption and decryption I'm playing with cryptography and its use with typescript on one side and PHP on the other side. Now I'm looking for routines that can encrypt and decrypt with ecdh's private and shared keys. Any recommendations? At the moment its in a testenvironment to figure out how it works basically. The keys (private and shared) are generated with elliptic.

Edit:
The plan is to use tweetnacl and tweetnacl-utilities for Typescript on the clientside and sodium from php 7.2 on the backend. The tweetnacl is well documented and it works to create two keypairs and two shared keys. I can encrypt a string for 'Alice' and decrypt it for 'Bob'. But on the backend I did not found the right corresponding functions...

Next steps after this is a save key exchange...

Use crypto_box_curve25519xsalsa20poly1305 from libsodium/nacl.

How it works, roughly summarized with all details of encoding and coordinates omitted:

Alice and Bob have public keys $A = [a]G = \underbrace{G + \dotsb + G}_{\text{$a$ times}}$ and $B = [b]G$.
Here $G$ is the standard base point of Curve25519, $a$ is a secret 256-bit integer known only to Alice, and $b$ is a secret 256-bit integer known only to Bob.
When Alice wants to send the $n^{\mathit{th}}$ message $m_n$ to Bob, she sends the box $c_n = \operatorname{crypto\_box}(m_n, n, B, a)$ to Bob.  What this does is:

Computes the shared secret key $k = H([a]B) = H([a\cdot b]G)$, where $H$ is HSalsa20.
Uses $k$ as the key and $n$ as the nonce to authenticate and encrypt the message $m_n$ using crypto_secretbox_xsalsa20poly1305.

When Bob receives the alleged $n^{\mathit{th}}$ box $c'_n$, which may be $c_n$ or may have been modified in transit or otherwise forged, he opens it with $\operatorname{crypto\_box\_open}(c'_n, n, A, b)$—but he makes sure to immediately drop it on the floor if crypto_box_open fails, meaning that it was a forgery.  What this does is:

Computes the shared secret key $k = H([b]A) = H([a\cdot b]G)$.
Uses $k$ as the key and $n$ as the nonce to authenticate and decrypt the box $c_n$ using crypto_secretbox_xsalsa20poly1305_open.

In other words, crypto_box and crypto_box_open first do a static/static Diffie–Hellman key agreement, and then use the resulting key for an authenticated cipher.

Alice and Bob must never reuse any message number or nonce $n$ with a single pair of sender/receiver public keys or else the security will evaporate.  If the communication is bidirectional, i.e. if Alice and Bob both need to send messages to each other, you might have Alice choose even values for $n$ and Bob choose odd values.


How do I multiply two points on an elliptic curve? Tell me if there is a way to multiply two points on an elliptic curve?
For example, as in secp256k1
Pcurve = 115792089237316195423570985008687907853269984665640564039457584007908834671663 # The proven prime
GPoint = (Gx, Gy) # Generator Point
N = 115792089237316195423570985008687907852837564279074904382605163141518161494337 # Number of points in the field
Acurve = 0; Bcurve = 7 # This defines the curve.

y ^ 2 = x ^ 3 + Acurve * x + Bcurve

(Gx1, Gy1) * (Gx2, Gy2) = (Gx3, Gy3)

Unfortunately I do not know their private key from which they were generated, but I really need to get a common point (Gx3, Gy3)
What algorithm is used to multiply two points on the secp256k1 elliptic curve?

There is no point multiplication operation on secure elliptic curves*, there is only scalar multiplication apart from the point addition of the group.
Scalar multiplication
Scalar multiplication with a scalar $t$ is adding a point $P$ it self $t$-times
$$ [t]P : = \underbrace{P + P + \cdots + P}_{t-times}$$ and it is well defined operation since the group is operation is the addditon of the points. Scalar multiplication is a natural writing of the adding $t$-times.
If you want to execute a Diffie-Hellman here it is;
Elliptic Curve Diffie-Hellman Key Exchange (ECDH)
ECDH is executed with the parties' public keys. Let say Alice has secret key $a$ and public key $A = [a]G$ and Bob has secret key $b$ with public key $B = [b]G$ with the base point $G$ defined by the standards.
Then both parties can agree on the key as;

Alice: get Bob's public key $B$ and multiply it with secret key $a$; $S = [a]B=[ab]G $
Bob: get Alice's public key $A$ and multiply it with secret key $b$; $[b]A=[ab]G = S$

So both arrived at the same point $S$, now they can use the $x$-corrdinate point $S$ with a Key Derivation Function (KDF) like HKDf to derive a symmetric key.
Ephemeral
Originally, Diffie-Hellman is defined as ephemeral, that is for each key generation, Alice and Bob generates new uniform random points by selecting a uniformly random $a$ and $b$ per run of the protocol. This provides forward secrecy if you delete the keys after decryption.
If you don't generate new uniform random keys, it is called the static DHKE. Therefore you will see around static-static, ephemeral-static, static-ephemeral, and ephemeral-ephemeral usages of the DHKE on around. Hopefully, the static case is no longer available in TLS 1.3.
MITM attack
DHKE is vulnerable to a man-in-the-middle attack especially the ephemeral case since the public points are changing all the time. A signature must be used to prevent this attack.

* As noted by CodeinChaos in the comments we can define a multiplication on curves with $[a]G \cdot [b]G = [ab]G$. This, clearly, have commutativity, associativity, identity, and distribution law. The inverse depends on the order of the $G$. This multiplication, however, is exactly the Computational Diffie-Hellman (CDH) problem. If you solve the Discrete Log (DL) problem on the curve then you can solve the CHD, the reverse is not known in the general case.
Since we required that the DL (or CDH) must be infeasible for security, this multiplication operation is not a feasible operation on the secure curves.


Cryptool - DES (ECB and CBC ) - double encyption So, I uploaded a text file in Cryptool and encrypted it with DES-ECB with the key FF FF FF FF FF FF FF  FF. I encrypted the cipher text again, with DES-CBC using the same key. Then, I encrypted the obtained text with DES-CBC again.

The first 8 characters match the encrypted text of ECB. The rest of it is different. I would like to know why those 8 characters are similar and why the rest of it are not? It would be very helpful if anyone could explain this to me.

There are a couple of things going on:

First of all, the DES key FF FF FF FF FF FF FF FF happens to be a "DES weak key"; by that, we mean that if you send a block through the cipher twice, it'll end up with the original value; that is:

$$X = DES_{weak}( DES_{weak} ( X ))$$
You are obviously encrypting in CBC mode with a zero IV.

So, let us look at what happens to the first block during your encryption.  He's call the initial value of that plaintext block $A$ (which is 44 6F 75 62 6C 65 20 65 in your example)

First you encrypt the text in ECB mode.  For the first block, this just sends it through DES, resulting in a ciphertext block we're call $B$ (which is A3 77 A8 0A AD 2B EA 6E in your example:

$$B = DES_{weak}(A)$$

Then, you encrypt that in CBC mode (with a zero IV).  For the first block, this exclusive or's the block with the IV, and sends it through DES.  Because we are using a weak key, this results in the original $A$ block, as:

$$DES_{weak}(IV \oplus B) = DES_{weak}(B) = DES_{weak}(DES_{weak}(A)) = A$$

Lastly, you encrypt the text again in ECB mode.  For the first block, this just redoes what we did in the first pass (because the first block is the exact same value it was):

$$B = DES_{weak}(A)$$

Now, this doesn't happen with the second block; that's because of the CBC mode in the second pass.  CBC mode exclusive or's in the value of the first block, and since that is not zero, the second equation does not hold.


Nonce for AES GCM to prevent replay attacks I am wanting to encrypt a message with a pre shared key that uses AES GCM from the OpenSSL library to do so.

I generate my key for the AES crypto via hashing my pre shared key with a salt using the PKCS5_PBKDF2_HMAC_SHA1 function which gives me a key of 32 bytes.

Once this is done I generate a crypto secure pseudo random byte sequence using RAND_bytes to generate 12 bytes to use as my IV.

Then I proceed with my crypto of the message, generation of the MAC, and packaging of my encrypted message in the form of [Length (Message + IV + MAC)][MAC][IV][Encrypted Message]

Now my question is, how can I implement protection against replay attacks. Or is there already protection built in?

From what I understand is that AES GCM only authenticates (preventing modification to the encrypted data) and encrypts data. It does not actually have a mechanism to recognize if a message has been received already, or at least in the OpenSSL implementation.

So for me to add replay protection to this message encryption, how should I add a nonce to the crypto scheme.

Should I simply keep track of each random IV for the given communication session and comparing any incoming message IV against the list of already received IVs?
Should I subtract 4 bytes from my 12 byte IV to use the free 4 bytes as a counter? ([Random Bytes X 8][00 00 00 01]) Incrementing it per message and when a message is received see if the message comes from the past until the session is over.
Prefix or Suffix a nonce counter to the message being encrypted, using a fully random IV and use the same detection mechanism as #2 except checking the decrypted message for the nonce rather than the IV?

A session usually only lasts for less than 50 messages, and there is no way to implement a stream cipher (SSL,TLS) encryption.

I feel that #1 may be resource consuming since I have to iterate an entire list of IVs in search for a duplicate and if the sessions ever grew in size this could be costly. #3 is alright besides the fact that the nonce is joined with the message, although since it is known in size (4 bytes) this can easily be extracted from the message. #2 seems like the best option, since all you need to keep track of is the previous messages counter and the message is left unmodified.

Is there a proper and safe way to implement a nonce to prevent replay attacks?

Thanks for your time.

Any of the ways you listed would work.

If you're collecting alternatives, yet another one (which I have seen in practice) is to include the message counter as the AAD (additional authenticated data), which is another input to GCM.

When we consider which one would be the best, we note that GCM has absolutely no requirement that the nonce be "random", or for that matter, unpredictable.  So, there is no particular reason you couldn't use 4 of the bytes (or, for that matter, all 12 bytes) as a counter; given that all the options on the table are secure, this option (which is the cheapest) would appear to be the best.


Difficulty to find the pre-images of a pair of hash result such that given $a,b$, $H(x_1)=aH(x_2)+b$? Suppose given fix values $a,b$, how difficult to find a pair of sha256 pre-images $x_1,x_2$ such that $H(x_2)=aH(x_1)+b$? How difficult to find 4 hash pre-images $x_1,x_2,x_3,x_4$ such that $\dfrac{H(x_2)-a}{H(x_1)+b}=\dfrac{H(x_3)-a}{H(x_4)+b}$?

Case 1: Assuming $\mathbb{F}_2^n.$ The only scalar constants you can have in characteristic $2$ to are $0$ or $1$? So, you need to define multiplication for quantities in $\mathbb{F}_2^n$ for this to be non trivial.

Let $n=256.$ For any  vectors $b\in \mathbb{F}_2^n,$ your first equation with scalar $a$ is equivalent to

$H(x_2)=b$ if $a=0,$ which takes $O(2^n)$ work (preimage problem).
$H(x_1)\oplus H(x_2)=b,$ which takes $O(2^{n/2})$ work (collision problem).

As for your second equation, it reduces to a quadratic relation which doesn't look meaningful in this context since the multiplication has to be defined for it to make sense.

One can use $\mathbb{F}_{2^n}$ as a representation for $\mathbb{F}_2^n,$ under some canonical basis, maybe a self dual basis, but more cryptographic justification for what you seem to be attempting needs to be provided for such an operation, given that solving quadratics is no easier than solving linear equations.

Case 2: (Thanks to @kelalaka) If you mean to take $\mathbb{Z}_{2^{256}},$ then one might guess that if the hash function is strong, the $a-$multiple $a H(x_1):=H_a(x_1)$ can itself be modeled as a random function and you are now solving a generalized collision problem between two random functions
$$
H(x_2)-H_a(x_1)=b
$$
which again should have complexity $O(2^{n/2}).$

For the second question things are trickier. Firstly there are zero divisors in the ring $\mathbb{Z}_{2^{256}},$ and you should not divide but cross multiply and consider
$$
(H(x_2)-a)(H(x_4)+b)=(H(x_1)-a)(H(x_3)+b)
$$
Let $u_i$ be the largest exponent of $2$ which divides the value $H(x_i)- c_i$ modulo $2^{256}$  where $c_1=c_3=a$ and $c_2=c_4=-b$. If $u_1+u_3\geq 256,$ then we need to have either $H(x_2)=a,$ or $H(x_4)=-b,$ (either happen with probability $2^{-256}$ or $u_2+u_4\geq 256,$ for this equation to have a solution.

Again, modeling these translated hashes as pseudorandom functions $Pr[u_i\geq k]=2^{-k},$ for $0\leq k\leq 255.$ For example, $Pr[u_i\geq 1]=1/2,$ which happens if the LSB of the hash output is 0.

Using this, one can derive actual probabilities for these equations to hold, based on the argument in italics.


One Time Pad - does it work for long plain texts? Reading Dirk Rijmenants's work on One Time Pad and he frequently mentions that it is suited to short plaintexts.

I presume this is just because of the practicality of encrypting and decrypting one time pad ciphers? If not why is it not mathematically appropriate for longer plaintexts 1000 characters plus?

Presumably if the one time pad was longer and totally plaintext this cipher works with plaintexts of lengths through to infinity.

Thanks for the help with this small point.

The one-time pad guarantees secrecy for messages of arbitrary length, assuming the key is uniformly random of (at least) the same length. There are no caveats to this information-theoretic theorem, it's just that securely exchanging big amounts of key material may be considered to be impractical in some scenarios.

(But frankly, nowadays you would just hand over an SD card or something and have enough key material for hundreds of gigabytes of messages. If you were to engage in that kind of activities rather than using a modern cipher, that is.)


Strong LRSW assumption for type 3 pairing groups Why does the "strong LRSW" assumption by Ateniese et al. [Untraceable RFID Tags via Insubvertible Encryption, CCS'05] hold ONLY for type 3 pairings and NOT for symmetric pairings? Whereas, the LRSW assumption by Lysyanskaya et al. [Pseudonym Systems, SAC'99] does hold for all types of pairings.

In a type-3 group, after an oracle query you get to see $(g_1^a, g_1^{at}, g_1^{as+axst}, g_1^{ax}, g_1^{axt})$ but not $g_1^s$ or $g_1^t$ (those are in $G_2$). Suppose you had a homomorphism $G_2 \to G_1, g_2 \mapsto g_1$ so you could recover $g_1^s$ and $g_1^t$.

Call your tuple from the oracle $(A, B, C, D, E)$ and compute $(Ag_1^r, B(g_1^t)^r, C(g_1^s)^r, D, E)$ for an $r$ of your choice. There is a unique value of $u \in \mathbb Z_p$ (where $p$ is the group order) such that $a+r = ua$ and if my math is correct, the modified tuple is now a correct tuple for $a' = ua$ and $x' = u^{-1}x$, which the oracle never signed.

Indeed, for the $D, E$ components the change of variables $a \mapsto ua, x \mapsto u^{-1}x$ does not affect the product $a'x' = ax$ so we can leave them alone. For $C$, the exponent was $as + axst$, the second summand is ok but the first one has $as = a'u^{-1}s$ so we want to change that $a$ to $a'$. We can't do that directly, but since $au = a + r$ we can make up the difference by adding $g_1^{rs}$. This change from a multiplicative relationship (that leaves the product $ax$ alone) to an additive one (that we can use to adjust the remaining terms) is what makes this attack work. For $A, B$ we then do the appropriate adjustment as well.

Note that you never actually get to know the value of $u$, or $x'$. That's why this doesn't work against plain LRSW, where you need to output $x'$ as well.


Cryptanalysis to reverse engineer a hash? I understand this may not be the best place to ask a question like this, but I believe that this community may be the  best/only place I can ask such a question.

I have inputs and outputs from an in-house hash developed years ago and the developer is no longer working with us any more. I need to determine the process that is the hash. Before you mention how this may be impossible, it appears to be a relatively simple hash and I have a few theories that appear to get me started in the right direction. First, the data:

 Input   Hash
1293239 EHELKHE
1331487 ILZXFZF
1320709 IKYJXWH
1328166 GUVUMMY
1156693 HFXLFYZ
1313273 ELHZLZV
1287367 GKDMWGM
1318623 EHDHYYF

This does not appear to be a very good hash, in my opinion. For starters, the output length matches the input length, this may be coincidence though. The main thing that catches my eye is that the output characters seem to all exist in a particular pool of possibilities. Here's a list of unique output characters: DEFGHIJKLMUVWXYZ. This lines up exactly with the hex values of 0123456789ABCDEF, in fact, in ASCII values, the two sets are 20 off from eachother. So I hypothesis:

D = 0
E = 1
F = 2
G = 3
H = 4
I = 5
J = 6
K = 7
L = 8
M = 9
U = A
V = B
W = C
X = D
Y = E
Z = F

From there, I'm out of ideas. I've compared the hash results with many standard hashes and have seen no correlation and have determined that it is most likely an original process. I've played with the numbers as best as I can and I have made no progress. What techniques are available to analyze this hash?

You are correct that it is a "bad hash". In fact it is not a hash at all. I've worked at a company that used a slightly different scheme for obfuscating database keys/numbers in URLs. And I also worked for another company that used a scheme that looked surprisingly similar for unlock codes for electronic devices.

The formula for converting "hashes" back into inputs looks like:

Take the "hash" (column "hash" below") and use your substitution cipher (E goes to 1, etc) to turn it into hex (column "subs" below).
Convert the result into decimal (column "to dec" below).
You have an 8 digit number, swap the first and last half of the digits (column "swap" below).
Divide the result in 3 by 13 to obtain the customer id (column "divide" below).

"hash".....subs......to dec......swap.....divide
EHELKHE - 1418741 - 21071681 - 16812107 - 1293239
ILZXFZF - 58FD2F2 - 93311730 - 17309331 - 1331487
IKYJXWH - 57E6DC4 - 92171716 - 17169217 - 1320709
GUVUMMY - 3ABA99E - 61581726 - 17266158 - 1328166
HFXLFYZ - 42D82EF - 70091503 - 15037009 - 1156693
ELHZLZV - 184F8FB - 25491707 - 17072549 - 1313273
GKDMWGM - 3709C39 - 57711673 - 16735771 - 1287367
EHDHYYF - 1404EE2 - 20991714 - 17142099 - 1318623

For folks who might find this in the future, it helps to make a spreadsheet and multiplication tables (customer id * 1 through customer id * 50). Formulas like these are usually simple linear formulas like $mx + b$, sometimes with a modulo involved (such as $mx + b \mod c$). And sometimes with "junk" digits added to make things harder to reverse engineer.

D.W.'s idea of "chosen plaintext" attack is also a good one. If you had pairs of customer id and "hashes" that varied by a single digit in the customer id, that would probably make it easier to attack.

And "security by obscurity" is no security at all. I spent about 2 hours avoiding homework tonight.


Is it possible to recover the seed used by Python's pseudo-random number generator? I generated some random numbers using a Python script. I have the first 40 numbers of the sequence. Is there a way to recover the seed or find the next 460 numbers in the sequence?

The numbers were generated using the following code.

import random

i=1
mn = 1
mx = 2
while i<500:
    print(random.randint(mn,mx))
    mn=mn*2
    mx=mx*2
    i=i+1

I have the first 40 numbers of the sequence. Is there a way to recover the seed or find the next 460 numbers in the sequence?

The first thing to know is that Python's random module uses Mersenne Twister as the PRNG. That is not a cryptographically secure RNG, in fact it is easy to recover the state as long as you have enough samples.

40 numbers of the sizes you use is not sufficient to recover the full MT state and find the next outputs that way.

It is more than enough to recover a time seed as Python uses when OS randomness is not available. You can just run a brute force of time values in the recent past. Latest versions of Python 2/3, however, initialize the full state from urandom or similar where available, and that cannot be inverted with this little output.

(Of course you can still call random.get_state() but presumably you were not asking that ;)


Effective security of block cipher – equal the key size, or half the key size? The Wikipedia “Key Size” article states:

  The security of an algorithm cannot exceed its key length (since any algorithm can be cracked by brute force), but it can be smaller. … … … Most symmetric-key algorithms in common use are designed to have security equal to their key length.

(emphasis mine)

The book “Secure Programming Cookbook for C and C++: Recipes for Cryptography, Authentication, Input Validation & More” by John Viega and Matt Messier states (on page 161, 2nd half of 4th §):

  The general rule of thumb is that the effective strength of a block cipher is actually half the key size, assuming the cipher has no known attacks that are better than brute force.

(emphasis mine)

Now…

To avoid nit-picking, let’s keep it simple and assume that an individual block cipher does not use an algorithm that loses some of the effective security a key provides. Also, let’s assume that no known attacks exist.

Would it be more correct to claim that the effective security of that cipher is equal the key size, or is it half the key size? Simpler asked: which of the two quoted statements is correct, and why?

I just read that chapter of the book, and the authors don't really justify their claim.

They also talk about "using random data to prevent collision and precomputation attacks" (which would then give you back the full key-size crypto strength) – this is about using random initialization vectors and such.

But if you are using an insecure mode of operation, or a non-random IV where a random one is required, using a bigger key-size doesn't really help, as the attacks possible here are not really key-recovery attacks.

Where such stuff could work would be for hash functions (which have at most $2^{n/2}$ tries collision resistance, assuming $n$-bit output), and a secret key included in the hash makes the brute-forcing impossible. But this certainly is not "symmetric encryption".

Another possibility which would reduce complexity to half the key-size would be assuming a (large enough) quantum computer – that could do a brute-force key search in $2^{n/2}$ steps instead of $2^{n}$ steps. But the text in the chapter doesn't really look like they are referring to this.

The crypto strength of an ideal symmetric cipher in absence of new generic attacks is equal to its key size (i.e. you need in average $2^n/2$ tries for a brute force key search attack).

Generally this is valid for all non-broken encryption algorithms, too (just by definition of "non-broken"): A symmetric cipher with key-size $n$ bit should offer $n$ bit crypto strength.

So my say would be: "Use a bigger key-size if you are concerned about future quantum computer attacks (or generally attacks on the algorithm which shave off some of the security, but not all of it), otherwise stay at 128 bit."


How to prove this LFSR equation? I am having difficulty solving part (ii) of Excercise 5.17 from Becker's Cipher Systems.

Exercise 5.17
$\quad$If $f(x),g(x)$ are any two polynomials over $GF(2)$ with $f(0)=g(0)=1$ show that
(i) $\Omega(f)\cap\Omega(g)=\Omega((f,g))$
(ii) $\Omega(f)+\Omega(g)=\Omega([f,g])$.

It is easy to prove that $\Omega(f)+\Omega(g) \subseteq \Omega([f,g])$, but could I have some hints to prove $\Omega([f,g]) \subseteq \Omega(f)+\Omega(g)$?

Background:

An infinite sequence $c_0,c_1,c_2,\dots$ is generated by a (linear feedback shift register (LFSR) with) polynomial $f(x) = \sum_{i=0}^n f_i x^i$ if for any $j$, $$\sum_{i=0}^n c_{j+i} f_{n-i} = 0 \text.$$

We can consider the sequence as a power series $\sum_{i=0}^{\infty} c_i x^i$. If we multiply this power series with the polynomial $f(x)$, we get
$$f(x) \sum c_i x^i = c_0 f_0 + (c_0 f_1 + c_1 f_0)x + (c_0 f_2 + c_1 f_1 + c_2 f_0)x^2 + \dots $$
We get that the $(j+n)$th coefficient is $\sum_{i=0}^n c_{j+i} f_{n-i}$. Which means that the sequence $c_0,c_1,c_2,\dots$ is generated by $f(x)$ if and only if the product of $\sum c_i x^i$ and $f(x)$ is a polynomial of degree less than $f(x)$.

We denote the set of all sequences generated by $f(x)$ as $\Omega(f(x))$. If we consider $\Omega(f(x))$ as a set of power series, we find that
$$\Omega(f(x)) = \left\{ \sum_{i=0}^{\infty} c_i x^i : \deg\left(f(x) \sum c_i x^i\right) < \deg f(x) \right\} \text.$$

If $f(0) \not= 0$, then $f(x)$ is invertible in the power series ring. This gives us a different characterization of $\Omega(f(x))$:
$$\Omega(f(x)) = \{ f(x)^{-1} r(x) : \deg r(x) < \deg f(x) \}\text.$$
As you observe, it is now easy to prove that if $f(x)$ divides $h(x)$, then $\Omega(f(x)) \subseteq \Omega(h(x))$, since if $h(x) = v(x) f(x)$, then for any $r(x)$ with $\deg r(x) < \deg f(x)$, we have that
$$f(x)^{-1} r(x) = f(x)^{-1} v(x)^{-1} v(x) r(x) = h(x)^{-1} v(x) r(x) \in \Omega(h(x)).$$
The fact that $\Omega(h(x))$ is closed under addition and scalar multiplication then implies that $\Omega(f(x)) + \Omega(g(x)) \subseteq \Omega(\mathrm{lcm}(f(x), g(x)))$.

Direct approach hint:

If you write $f(x)=u(x)w(x)$ and $g(x)=v(x)w(x)$, with $\gcd(u(x),v(x))=1$, then any polynomial $r(x)$ can be written as $s(x)u(x)+t(x)v(x)$ for some $s(x)$,$t(x)$. The trick is to ensure that $s(x)$ and $t(x)$ don't end up with too high degrees, so you can't use the obvious approach.

Indirect approach hint:

You can also consider the dimensions of the (finite!) vector spaces involved, which together with (i) should give you a proof. This approach is probably easier.


Is the SHA1 hash of MD5 hash of a password secure? Cryptography is not my area, so pardon me if the question is annoying.

Some time ago, I implemented an Internet site, which database had a users table. To keep the password in its user table field, I used

encrypted_password= sha1(md5(raw_password));

What are the pros and cons of the approach I used?

Pros: The only pro is that your method is very slightly better than storing passwords in plaintext.

Cons: If an attacker gains access to your database, he will easily be able to recover 99% of passwords with only a bit of work, and he won't even need anything more than a laptop.

The lesson here is the usual one. Never build your own crypto. Use a secure password hasher like Argon2. All the information you could need on secure password hashing can be found in this post.

Also, a minor nitpick: "encryption" is not the term you are looking for. Encrypting a value implies a transformation that is invertible, e.g. the result can be decrypted to recover the original value. Hashing, on the other hand, implies a one-way transformation that cannot easily be reversed (other than trying all possible inputs and checking the result).


Combatting traffic shape analysis with spurious packets I was reading a question about combatting traffic analysis, and a thought occured. If I send random junk messages periodically, would that defeat traffic analysis?

The messages would contain some form of header to specify "this is junk", and would otherwise be comprised of random data of a random (plausible) length. In fact, the data could just be produced by a CSPRNG, such that the packets would not be decryptable. Someone who knows the key would be able to verify that the decrypted message was invalid, but an attacker wouldn't be able to tell which messages are part of the conversation and which are random, making it difficult to perform cryptanalysis.

Does this idea have merit?

Well, this isn't a new idea.  One place (and probably not the first place) this has appeared before is in IPsec RFC4303, see dummy packets in section 2.6.

Now, IPsec differs from your suggestion in that it isn't using some output from a CSPRNG.  Instead it just grabs some arbitrary amount of data of the right length (with the marker that it is a dummy packet), and just encrypts it just like it would a real packet.  This is just as indistinguishable as a CSPRNG would be, and (at least for IPsec) it is a bit more convenient (because you can reuse the same infrastructure that does encryption, rather than having a separate CSPRNG infrastructure).

Now, the problem with this idea is that it can be hard to do, at least, if you want something that can fool an intelligent listener.  For example, suppose that you are protecting some TCP traffic.  Now, with TCP, one side sends a message (a TCP packet with data), and the other side immediately responds with a reply message (the TCP acknowledgement).  The problem that this behavior causes is that if one side just sends a dummy packet, and the other side doesn't reply, well, the attacker can pretty much figure out that the two sides aren't really communicating, and that's what we're trying to hide.  To effectively hide this, what we'd need to do is send a dummy packet, and have the other side respond with its own dummy packet (with approximately the same timing as a real TCP ack would have).  To further complicate things, TCP isn't the only protocol in use; another example might be RTP (which is mostly unidirectional); disguising that would take a different strategy.

On the other hand, if you do know enough about the protocol you're protecting to effectively mimic it, this idea can work.


How would you explain stateful encryption? I have recently started reading on encryption protocols and their counter attacks. I came across the term Stateful Encryption particularly used in encrypting data that is stored in the cloud. So far I think it is just another variable that is used to calculate ciphertext and gets updated after every generation and storage of ciphertext from a plaintext. Can you explain why statefulness was needed and how it solved that need?

Stateful encryption aims at reducing the number and/or volume of data exchanges and/or computational burden in recurrent communications between entities, compared to what would occur if, at the beginning of each communication chunk, everything was redone as for the first chunk. This is obtained by sharing some data, called the state, from chunk to chunk. Depending on context, "chunk" can be a block of information of some small fixed size, a packet, a session for some communication protocol like TCP/IP or HTTP...

Perhaps the simplest stateful encryption is CBC encryption with a block cipher $E$ (though that predates the term stateful encryption, which is not used for CBC). The stateless version of CBC would, for each plaintext block $P_i$, draw a random $\text{IV}_i$ and send cryptogram $(\text{IV}_i,C_i=E(\text{IV}_i\oplus P_i))$; this is secure from a confidentiality standpoint, but overall cause the ciphertext to be twice the size of the plaintext. While CBC encryption draws a single random $\text{IV}$, sends $(\text{IV},C_0=E(\text{IV}\oplus P_0))$ for the first packet, and $(C_i=E(C_{i-1}\oplus P_i))$ for all the next ones, thus reducing communication overhead to a single block. Here chunk is a block, and the state is simply the last block encrypted, initially $\text{IV}$.

The term stateful encryption has been used for similar techniques to reduce the overhead in direct encryption with asymmetric ciphers like ElGamal; but practice is to use hybrid encryption instead, since that's much more efficient computationally.

Transport Layer Security Session Resumption is a practically used form of stateful encryption. As an utter oversimplification of that, when resuming a TLS connection that got broken for some reason, one side proposes to reuse the previous session key, and if the other agrees, that saves the authenticated Diffie-Helmann key exchange (or similar) for the negotiation of that session key.


The pairing description (type, q, h, r, etc.) is the definition of the field that the elliptic curve of some type operates on. The actual curve is identified by its type and is baked into the framework (e.g. PBC) you're using.

This definition corresponds to $q$ (group order, same as q), $\mathbb{G}, \mathbb{G}_T$ (groups defined by pairing description and curve) and $\hat{e}$ (pairing function $\hat{e}:\mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G}_T$). $\hat{e}$ greatly depends on the actual elliptic curve, because different algorithms or parameters are used. All the other parameters are unique to the scheme that is devised using bilinear pairing.

The pairing description is necessary to have for doing any calculation with the described scheme. It must be known to all participants. Of course, if you're always using the same pairing description, you don't have to send it along with every message of your system. It can be baked into the client software.

Remember to generate a fresh and valid pairing description before you deploy your system into production. This makes it a little harder for attackers to break a system. If every one uses the same defaults, then pre-computation on that single group can break a lot of systems.


Honest players in ZKP proofs Trying to study ZKPs, I have seen that proofs qualify players (a part from -of course- simulator and extractor): so honest prover, honest verifier.
Is it needed because usually examples deal with interactive schemas which require players to act in specific ways (so it's not needed when Fiat-Shamir heuristic is used on sigma-protocols to get non-interactive flavours)? Or are there more technical, subtle reasons?
Thanks!

In the example you mentioned, you must have an honest verifier, because a dishonest verifier would be able to extract the witness (see).
It is important to remark that there are transformations from honest to dishonest protocols, therefore studying honest protocols makes sense in practice. You may find this useful.


Can the TLS 1.3 PSK-DHE handshake be turned into a PAKE? Recently, we had the question whether there's a PAKE that uses more standard, higher-level primitives than what SRP offers.

Now this made me think and ask myself: TLS does have a PSK mode, can't we leverage that? This shall be the theme of this question.

What I would imagine is the following exchange:

Client -> Server: "Hi, I'm potato@po.ta.to"
Server -> Client: "Here are your key derivation parameters: ..." and the server also sends his regular key exchange message assuming the client is who he claims to be
Client -> Server: sends his key exchange part

The idea is that we basically do standard TLS-PSK using the hashed password, so the server can store this hashed version and the client can re-calculate the hashed password (the PSK) on-the-fly.

Now at least for TLS 1.2 this is impossible if you don't have a custom ClientHello extension, because the ClientKeyExchange is sent after the ServerKeyExchange.

For TLS 1.3 (draft 18) things are more intriguing. It appears that Client can send a list of key labels and the server picks one. I don't exactly understand whether there is another message from the client with his key exchange part.

So now very concretely my question:

Can we somehow fit the above flow of log-in into the TLS 1.3 handshake, without defining our own custom extension?

The current TLS 1.3 draft proposal with PSK does not have PAKE properties; in particular, a client can send a single message, get a reply, and then check every entry in his dictionary to search for the PSK used by the server.

To do this, the client would send a valid hello, specifying the identity that the client is interested in (and a valid keyshare).  The server will also generate its key share, generate a key that's based on the psk, and the key share shared secret, and encrypt some data based on that key.  Then, the client computes the key share shared secret (which doesn't depend on the PSK), and then for each entry in his dictionary, compute what the key would be if that guess was correct, and then see if that decrypts the encrypted region into something readable; if it does, he has recovered the PSK.

I believe that the same approach would work against your proposal, with the possibility that it's the server that can do the dictionary attack; it's the first guy to receive a message encrypted by a key that's a function of the PSK.

Hashing the password doesn't add PAKE properties; the attacker can just as easily hash each entry in his dictionary, and use those.

To make TLS 1.3 into something that does PAKE, the right approach would be to integrate some protocol with PAKE properties (such as SRP or EKE) into it.


Can compression + encryption sometimes be beneficial? I hope this question hasn't been asked before: I searched and couldn't directly find it.  It is known that in specific applications, compression followed by encryption leaks information of the length of the compressed message, which, combined with the possibility to inject known plain text in the message, can leak sufficient information as to break the encryption entirely.  There are real-world examples where such plain text injection is a possibility, and there, compression+encryption is a bad idea.  There are other applications, like VoIP, where data packets have comparable length before compression, but compression will change these lengths in ways that betray sufficient aspects of the data to allow, again, for a leakage of plain text information.

In all these cases, the vector is the variable length of the compressed plain text that is leaked.

This counter-intuitive result is opposite to the old cryptographic idea that "pre-whitening" which is also an effect of compression, is beneficial.

So, my question is: are there cryptographic applications where compression + encryption is beneficial over simply encryption (as old wisdom would have had it), or is compression in several cases dangerous, and at best, sometimes harmless, but never beneficial to encryption ?  In other words, is "pre-whitening" still sometimes an advantage, or not ?  I'm not talking about the gain in room or bandwidth.  I'm talking on the cryptographic side only.

Regarding your comment about the CRIME attack, I think I can write an answer:

TLS is one of the common ways for encrypted communication, which gave the CRIME attack a lot of attention. However, I think you drew the wrong conclusions there:

First and foremost, not the encryption scheme was broken. The attack broke the protocol. That is a massive difference.
It only affected those TLS versions, which used a different algorithm: DEFLATE. And the attack works only with that, not a general compression algorithm.

And now I have to say, that your conclusion is probably going into the wrong direction. It is the wrong conclusion to say that coupling compression and encryption is bad in general.   Here are some conclusions I would draw from this:

It's very important to design protocols properly. Someone will find the most unlikely weakness.
Think of all possibilities - especially when it comes to user input and third-party libraries and programs. When it comes to security, better expect the worst than missing something crucial.
The functionality of DEFLATE is quite horrible when you have to consider that linking backwards with short tokens is actually bad. We can only speculate, that it might have been an oversight when it was permitted as compression algorithm.

Regarding the VoIP weakness: Again, that has nothing to do with the security of the encryption schemes itself. It does not break the encryption, but the conidentiality of the communication.

And the reason for that is the combination of timing, the length and number of each individual message etc. All those criteria are not hidden by encrypting the individual messages, and the error here is from the designers, who might not have considered that it's a bad idea if the flow of the messages (length and density of messages over time) actually reflects the content of the messages.

However, that's a sidechannel in this specific scenario. It is not a weakness in general for compression algorithms, but a very specific situation and the information used is actually outside the scope of the encryption (the meta-data).

  I considered this known problems... I didn't know there was anything controversial about it.

The examples are not controversial - but the generalization of them is IMO unreasonable. Also, those incidents actually are not an ideal fit for this site but security-SE would be much more fitting.


Choosing asymmetric pairing for Elliptic Curves I'm trying to implement a Provable Data Posession protocol using elliptic curves, but am stuck at the $\text{KeyGen}$ phase of choosing a subgroup $G_2$. Here's an excerpt of it.

  On input $\mathcal{K}$, choose an elliptic curve $E(\mathbb{F}_q)$ with a subgroup of large prime order $p$ generated by $P\in E(\mathbb{F}_q)[p]$, such that the bitlength of $p$ is $\mathcal{K}$. Choose an asymmetric pairing $e: E(\mathbb{F}_q)[p] \times G_2 \rightarrow \mathbb{F}_{q^k}^*[p]$ with $G_2$ being a p-order elliptic curve subgroup over (an extension of) the field $\mathbb{F}_q$ with generator $P'$, where the choice of $G_2$ depends on the specific instantiation of the pairing.

If I've understood it right, I can choose some curve, e.g. p256, secp256k1, or something else. But then I also need a subgroup $G_2$.

How do I choose a $G_2$ that satisfies the asymmetric pairing that is stated above?

Link to paper (page 7): https://eprint.iacr.org/2013/392.pdf

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

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

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

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

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

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

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

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

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


Process of dividing 168bit key into 56bit keys in TripleDES I used TripleDES so many times but never thought about this. In TripleDES it requires 168bit key in option 1. I don't enter three single 56bit keys while implementing instead I only enter 168bit key.  So, I'm guessing 168bit breaks into three 56bit keys. What it process of this breaking mechanism? is it linear?

Yes. The keys are indeed used in a linear manner.

In particular, they are used in $E$-$D$-$E$ mode: encrypt using first 56 bits as key, decrypt using next 56 bits as key and then again encrypt using final 56 bits.

This way its possible to use triple DES (which is officially called TDEA) for the DES, 2-DES and 3-DES variations. The first would use $K_1$-$K_1$-$K_1$ as keys, the second would use $K_1$-$K_2$-$K_1$ as keys and the full 3-DES would use $K_3$-$K_2$-$K_1$ as keys. Sometimes the 2-DES and 3-DES keys are also called ABA and ABC keys respectively.

DES uses one bit of each byte as parity, but this bit is not always validated by implementations. So triple DES keys with parity use 64, 128 or 192 bits. This explains why some implementations allow the output of an MD5 hash - which is 128 bits - to be input as 2-DES key without any error.

References :

FIPS 46-3
Wikipedia on triple DES


Why does NTRUEncrypt lack a formal security proof? Is there any particular reason why NTRUEncrypt lacks a formal security proof? That is, a demonstration that it achieves certain security notion (e.g. IND-CPA). I know there is a provable-secure variant from Stehlé and Steinfeld, but my question is regarding the original NTRU proposal.

NTRU, as it was originally introduced, is based on what people now call the "NTRU assumption", which really just assumes that it is difficult to break NTRU.  Annoyingly circular, but that's how it is.  Similar to how breaking RSA is not provably as hard as factoring (technically it is based on the "RSA assumption"), but people still think it is hard, NTRU was conjectured to be secure based on the fact that it is hard to find the shortest vector in a lattice (which is the private key).  The SVP problem is actually NP-complete.  However, you can't really make a secure cryptosystem based on an NP-complete problem.  You need some related problem with good average-case hardness to work with.  This was in 1996.

The paper you reference by Stehlé and Steinfeld does modify NTRU to be provably reducible to some standard lattice problems.  However, the problem they use (Ring Learning with Errors) was not formalized or studied until 2005.  So the answer really is that there was a lot of work on the complexity of lattice problems that still needed to be done when NTRU was published, and the authors didn't have the tools necessary to prove it secure at the time.


Mathematical definition of deterministic and non-deterministic random bit generators Can anyone give the mathematical definition of deterministic and non-deterministic random bit generator?

Providing a reference will also be very helpful.

Deterministic random bit generator is a function that takes as input a secret seed and possibly other inputs and produces (long) strings of output bits with the following property: for all adversaries with (polynomially) bounded computational power, the distribution of output bits is indistinguishable from a uniform, independent distribution of bits.

I don't think there is a strictly "mathematical" definition of true random bit source (I guess this is what you mean by 'non-deterministic') since it would need to define something that is now well captured by mathematics (external, physical source of entropy).

NIST in its standard SP800-90Ar1 defines non-deterministic random bit generator as:

  An RBG that always has access to an entropy source and (when working properly) produces output bitstrings that have full entropy. Often called a True Random Number (or Bit) Generator. (Contrast with a deterministic random bit generator).

A good reference book that covers the topic of randomness and random bit generators is "Random Number Generators - Principles and Practices".


What's the fundamental difference between Diffie-Hellman and RSA? What is the difference in the purpose of DH and RSA?  Aren't they both public-key encryption?

The difference is subtle.
DH is used to generate a shared secret in public for later symmetric ("private-key") encryption:

  Diffie-Hellman:

  Creates a shared secret between two (or more) parties, for symmetric cryptography
  Key identity: (gens1)s2 = (gens2)s1 = shared secret    (mod prime)
  Where:

  gen is an integer whose powers generate all integer in [1, prime)    (mod prime)
  s1 and s2 are the individuals' "secrets", only used to generate the symmetric key

RSA is used to come up with a public/private key pair for asymmetric ("public-key") encryption:

  RSA:

  Used to perform "true" public-key cryptography
  Key identity: (me)d = m    (mod n)    (lets you recover the encrypted message)
  Where:

  n = prime1 × prime2     (n is publicly used for encryption)
  φ = (prime1 - 1) × (prime2 - 1)     (Euler's totient function)
  e is such that 1 < e < φ, and (e, φ) are coprime     (e is publicly used for encryption)
  d × e = 1    (mod φ)     (the modular inverse d is privately used for decryption)

It just so happens that -- in practice -- RSA's results are subsequently used to generate a symmetric key.
Furthermore, it also happens that you can also modify DH to be used for public-key encryption.
But they are fundamentally different, even though both of them have "public" and "private" components.


Why does libSTARK use binary fields as opposed to prime fields for zk-SNARKs? zk-STARKs make use of FRI for low degree testing of polynomials.

The zk-STARKs paper states on page 11:

  we stress that ZK-STARK could also operate over prime fields but we have not realized this in code

With a footnote

  the FRI system requires p to contain a sufficiently large multiplicative subgroup of order $2^{t+\mathcal{O}(1)}$; such prime fields abound, as implied by Linnik’s Theorem.

This helpful blog post which explains and implements code similar to libSTARK states:

  STARKs “in real life” (ie. as implemented in Eli and co’s production implementations) tend to use binary fields and not prime fields for application-specific efficiency reasons

If binary fields give some kind of advantage, what advantage do they provide?

Caution: This answer is about the basics of why binary fields $\Bbb F_{2^k}$ are sometime preferred to prime fields $\Bbb Z_{p}$. It does not cover the specifics there may be for zk-STARKs, libSTARK or FRI.

Binary fields allow the use of XOR rather than addition with carry, and carry-less multiplication. That makes computations of field arithmetic easier, because carries requires code (for large arguments as used in cryptography, especially for SIMD implementations including SSEn), or circuitry, thus power and time. Removing carries removes the need for a trade-of between simplicity and propagation delay in carry lookahead, which is significant for wide-word hardware implementations.

The estimation of a quotient in modular reduction is simpler for a binary field: it can't be off-by-one as occurs in ordinary multi-digit Euclidean division, which makes constant-time implementations easy, removing a possible side-channel.

Squaring in a binary field can be reduced to bit rotation by using a normal basis representation for the field. This in turn allows more efficient scalar multiplication on Elliptic Curve groups defined on some Koblitz curves over binary fields.


how to solve discrete logarithm problem information requested I have seen your example about ecdlp solver :The Problem is as follows:

$$E\backslash GF(p):y^2=x^3+17230x+22699$$

where $p=23981$, point $G$ with prime order $|G| = 109$

Alice creates a public key by selecting a private key $d<q$, public key $Q=[d]G = (3141,12767)$

Therefore;

public information : $a,b,p,G,q,Q$
private key : $d$

However, this curve has the following characteristic:

$\Delta= −16( 4a^3+27b^2) \bmod p =0$
That is, the discriminant is 0. and embedding degree is 2

I, however, don't understand where comes out the value  (23796,0) i.e how can I calculate it? and then the following formula equation: after which we obtain the corresponding curve
$$y^2=x^3+23426x^2$$

is it possible for a further explanation of how you determine the point $(27396,0)$?

Let $f(x,y) = -y^2 + x^3+17230x+22699$ over $\Bbb F_p$ with $p=23981$. A point on the curve is a singular point if and only if the partial derivatives are vanishes at that point. The partial derivatives are;

$\frac{\partial f}{\partial x} = 3x^2 + 17230 =0 \pmod p$ and vanishes at $x=\{185,23796\}$ found by WolframAlpha or it can be found by Tonelli-Shanks.
$\frac{\partial f}{\partial y} = -2y = 0 \pmod p$ and vanishes at $y=0$

The vanishing point $(185,0)$ is not on the curve, however, $(23796,0)$ is.

Therefore $(23796,0)$ is a singular point for the Curve.

Then we then translate the origin to this singular point $(23796,0)$, that is replace $(x,y)$ by $(x+23796,y+0$) in the equation of $E$, yielding the equation of the curve in the shifted referential:
$$y^2 = x^3 + 23426x^2$$
The rest is in the answer which the OP had trouble with.

Note: credit goes to @kelalaka for the better of the present answer, in particular introducing $f(x,y)$ and its partial derivatives.


Encryption that purposefully take hours to decrypt My problem:

I want to block sites on my router.
I want to generate new password for my router after blocking sites.
This new password I want to encrypt.
But to decrypt it, I want it to take 2 to 8 hour to decrypt.

Is there any solution that could solve my problem?

The reason to do that is I want to lock myself out. By generating a random password that I can't memorize and doing the encryption, I can be sure that it's impossible for me to login. As Joseph Sible-Reinstate Monica commented:

  I think the actual goal here is that the OP is trying to focus on something important for a while, and so block access to distracting sites, and needs to lock themselves out so they don't just unblock them when they want to look at them.

Related: How to hide a code from myself until a specified time?
on Super User.

Time-lock puzzles appear to be what you want (see for example this).
A basic construction is via "Repeated Squaring in the RSA group".

Let $p,q$ be large primes, and let $N = pq$.
The goal is, for fixed $t>0$, to compute $2^{2^t}\bmod N$.
There are two "obvious" ways to do this, depending on whether you know the factorization of $N$ or don't.

If you do know the factorization of $N$, you can first compute $2^t\bmod \varphi(N) = 2^t\bmod (p-1)(q-1)$, and then compute $2^{2^t\bmod \varphi(N)}$ via Repeated Squaring. The complexity of this is at most $O(\log N)$ multiplications within $(\mathbb{Z}/N\mathbb{Z})$.

If you don't know the factorization of $N$, then there are some conjectures [1] that computing $2^{2^t}\bmod N$ must be done "directly" (and that it cannot really be parallelized).
One can do this by repeated squaring to give a complexity of $2t$ multiplications within $(\mathbb{Z}/N\mathbb{Z})$.
Here $t\in\mathbb{N}$ is an arbitrarily large number, allowing you to make this as "difficult" as you want.

Note that someone could always factor $N$ if they want to ignore this (so it's not "arbitrarily hard"), but if you make factoring $N$ appropriately hard it gives you fine-grained control over the difficulty of computing $2^{2^t}\bmod N$ (which is the "easier option" in comparison).
One can then use $2^{2^t}\bmod N$ as the basis of any symmetric-key crypto scheme (or hash it into any suitable domain first).
Your algorithm could then look as follows:

To encrypt something, generate an RSA instance, compute $2^{2^t}\bmod N$, use this value (or its hash) to encrypt something, then only store $(N, t)$.
To decrypt, start by recomputing $2^{2^t}\bmod N$, then decrypt using whatever "base scheme" you encrypted with.

This has the benefit of allowing you freedom to "tune" the parameter $t$ to take however long you want to decrypt.

[1] For more information I'd suggest looking into Verifiable Delay Functions, but I'm not too familiar with the area admittedly.


Is it possible to determine a PGP public key from encrypted data? Is it possible to find out which public key was used to generate the message?

Scenario is like this :

I got data which is encrypted with a public key. Now a "bad guy" hast the encrypted data, and knows the decrypted content and wants to know who was the receiver of the data. The "bad guy" has all possible public keys which could have been used to encrypt the data.

Is it possible for the "bad guy" to find out who was the receiver(or witch public key was used).

Thanks a lot.

From this answer:

  The key ID of the recipient is included in plain-text in the encrypted file. Other possibly interesting information "hidden in plain sight" is just the size of the file, or the name of the encrypted file (if someone just sends it without alteration of course.)

  What you might not realise is that the recipient Key ID is effectively an optional field. ...

and

  You can encrypt using the -R (or --hidden-recipient) flag with gpg to avoid revealing the recipient's public key in an encrypted message.

and

  ... However, also see this answer for ways to differentiate between recipients if the attacker has access to a large number of messages.

  A practical aside -- secondary clues may be in various logs. For instance, an attacker who obtains such a message might also be able to access (say) a .bash_history file with the recipient's address, or a web-server log with IP addresses that provide clues to who POST'ed or GETs the file, etc.


modified AES-CMAC algorithm I want to use AES-CBC for secure firmware upgrades on a microcontroller, with AES-CMAC for checking the integrity of the firmware image. The AES-CMAC algorithm needs a AES-128 encryption funtion. For the firmware upgrade, I need decryption only. Thus, I'd like to replace the AES-128 encryption by AES-128 decryption to reduce the program size by omitting the AES encrypt function.

Are there any implications on security if the AES-CMAC algorithm is modified in this way?

Are there any implications on security if the AES-CMAC algorithm is modified in this way?

There is no security implications by modifying $\text{AES-CMAC}$ by replacing the $\text{AES}$ block cipher component with $\text{AES}^{-1}$.  Both are equally strong block ciphers; if $\text{AES}^{-1}\text{-CMAC}$ were found to have a weakness, that would imply that $\text{AES}^{-1}$ could be distinguished from a random permutation, which would imply that $AES$ could be distinguished from a random permutation, which could imply that $\text{AES-CMAC}$ might not be as strong as we hoped.

BTW: CMAC assumes that the device has a secret key; if someone else learned that secret key, they could generate their own images (which would validate just as well).  Do you have such an unlearnable secret key?


cryptographic function that changes with time? Is it possible to create a function that varies with time but is also useful when encrypting information that is meant to later be decrypted?

Or in other words, we have the function $T(t)$ where $t$ is the input and the output is a function $f(x)$ where $f$ is an encrypting function that takes $x$ as input, $x$ is the information we want to encrypt and the output of $f(x)$ is the encrypted information.

Is it possible to decrypt the output of $f(x)$ knowing function $T$ but not the input $t$ and $f(x)$?

By the way if it wasn't obvious already I’m far from knowledgeable about cryptography.

Normally we don't keep functions secret (Kerckhoffs principle). But let's assume that $T$ depends on a secret key $s$ and that we keep that secret. See $s$ as a rather large constant within $T$ if you must.

In that case we can use $T_s(t) = \operatorname{KDF}(s, t)$ to derive a secret $k$ that depends on the time. We can use $k$ as input of a key pair generation function $\operatorname{Gen}(k)$ that outputs a private key $sk$ and public key $pk$. If we choose Elliptic Curve cryptography we could just use $sk = k$ and then calculate $pk$ by multiplication with base point $g$, an efficient calculation.

So now the function $f(p)$ could simply be $\operatorname{Enc}_{pk}(p)$, giving $c$. The function $f'(c)$ would be $\operatorname{Dec}_{sk}(c)$. Here $p = x$ is the plaintext message and $c$ is of course the ciphertext. For Elliptic Curves the $\operatorname{Enc}$ and $\operatorname{Dec}$ functions would be provided by the ECIES encryption / decryption scheme.

So we now have an $sk$ that can only be created if $s$ and $t$ are known. The function $f(x)$ is simply encryption with a public key that can be published - you don't even need $t$. And you can only decrypt if you know $s$ and $t$: otherwise you would not be able to calculate $sk$ required for decryption.

Of course having $T$ both create $f$ and perform the decryption is not really possible. You need a function $T$ to create the key pair and a function $f'$ to decrypt.


Why is c25519 in the GPG “expert” options? The only way to access the c25519 curve in GPG is through gpg --expert --full-gen-key. Why is that? From my knowledge, Curve25519 is one of the most secure (and fast) elliptic curves in cryptography. So why is RSA fine, but Curve25519 is considered a risk only experts should take?

The risk mainly resides in compatibility.
See, not all GPG users/systems are updated to the latest version. If you look at the GPG changelogs, you'll notice ECC was first introduced to GPG with version 2.1 in 2015:

Support for Elliptic Curve Cryptography (ECC) is now available. ⇒more

None of the pre v2.1 versions of GPG support ECC, which is something that can and most probably will cause several annoyances and interoperability issues — hence the "expert" toggle which can be interpreted as "herewith I confirm that I know what I'm doing and that I'm aware of related compatibility problems that may come within it".
Note that this is only an annoyance for the time being; things will surely brighten up while time goes by and more users/systems adopt newer GPG versions by updating
Also note the related dependencies and — last but not least — the OpenPGP specification "draft" status, which additionally influence adoption speed:

Encryption ECDH — RFC7748: Curve25519
OpenPGP specification: RFC4880bis draft
Dependencies:

libgcrypt >= 1.7.0

Gnuk >= 1.2.0

(Source: https://wiki.gnupg.org/ECC)


Can any hash function based on the sponge construction work as extendable output function? Keccak provides a sort of very useful XOFs.

Can other sponge construction hash function like  Spongent work as XOF?
Is there any lightweight XOF for hardware or software implementation?

Can any hash function based on the sponge construction work as extendable output function?

Yes.

Pick any permutation $\pi\colon \{0,1\}^n \to \{0,1\}^n$, and capacity $c < n$.  For example, you could pick Keccak-p[1600, 24] like SHA-3 uses, with state size $n = 1600$ and capacity $c = 2\lambda$ for a $\lambda$-bit security level—that is, SHAKE128 uses $c = 256$ for 128-bit collision resistance (provided, of course, the output is at least 256 bits).  Let $r = n - c$ be the rate.

Start with the initial state $x_0 = 0^n$, i.e. a string of $n$ zero bits.  Break the padded input message $m$ into $r$-bit blocks $m_1 \mathbin\| m_2 \mathbin\| \cdots \mathbin\| m_\ell$.
Absorb.  For each block $m_i$, update the state $x_i = \pi(x_{i-1} \oplus (m_i \mathbin\| 0^c))$; that is, pad the $r$-bit block $m_i$ with $c = n - r$ zeros, xor it into the state, and permute the state.
Squeeze.  Reveal the first $r$ bits of $x_\ell$, the first $r$ bits of $\pi(x_\ell)$, the first $r$ bits of $\pi^2(x_\ell)$, the first $r$ bits of $\pi^3(x_\ell)$, and so on, until you've produced the number of output bits you want.

  Is there any lightweight XOF for hardware or software implementation?

There are many permutation-based designs these days.

Keccak comes in many sizes: SHA-3 uses Keccak-p[1600, 24] with parameters that were overdesigned partly out of paranoia and partly for political reasons, but KangarooTwelve uses Keccak-p[1600, 12], i.e. half the number of rounds of SHA-3, and higher rates $r$, and still has a good security margin against the best collision attacks.  You could possibly even tune the Keccak parameters to be even smaller if collision resistance isn't important for your application, and there are other options for smaller word sizes.

NORX, a 512- or 1024-bit permutation, was designed like an ARX network but with the approximation $a + b \approx a \oplus b \oplus ((a \wedge b) \mathbin\ll 1)$ to make hardware designs a little cheaper, since integer addition has a high cost for carry propagation; Gimli is a newer design with a 384-bit permutation that improves on NORX.  The CAESAR winner Ascon uses another 320-bit permutation.


Can I get successful signature verification with just altering message and signature? Assuming I can modify a message and also modify the verification signature, and I also have the public-key but not the private-key. Can I create a message that can be verified with a signature that I can create and get a successful verification operation ?

I'm using the RSACryptoServiceProvider.VerifyHash method, we calculate rgbHash = sha1(message)

RSACryptoServiceProvider.VerifyHash(
      byte[] rgbHash,
      string str, //we used SHA1
      byte[] rgbSignature
)

Is there any possiblity to make a successful verification with just modifying message and signature, and without modifying public-key ?

Is there any possibility to make a successful verification with just modifying message and signature, and without modifying public-key ?

One would certainly hope not.  If you can, then you've just shown that the signature algorithm used is broken, and not to be trusted.

For a signature method to be considered secure, then it is required that someone without the private key cannot somehow cobble up a signature to any message that has not be specifically signed by someone else with the private key.  The attacker is allowed access to valid signed messages (and we even allow him to pick the messages to be signed).  If he could take a valid message and signature, and somehow alter the message, and come up with a valid signature, he has just violated the security property of the signature.

Now, you do use SHA-1 as the hash function - what this means is that it is believed to be feasible (nobody has actually done it and published it) to create two messages that has the same SHA-1 hash; if he then gets one signed, then that signature would be a valid signature to the other message.  Because of this, we're urging people to use a stronger hash (such as one of the SHA-2 or SHA-3 hashes).  I bring this up because this is the one known way (assuming that your RSA key is strong) that someone could generate a forgery with what you are doing.


How can I construct a proof that the decryption of a certain encrypted file matches a hash? Let's say Alice has file $F$ and she generates key $K$. She widely publishes the $hash(F)$ for identification. She wants to sell the file to Bob. She encrypts the file with $K$ and sends both $E_f = E(F, K)$ and $hash(K)$ to Bob. However, Bob wants to verify that this encrypted file really is the one he has asked to buy.

How can Bob verify that $hash(Dec(E_f, K)) = hash(f)$ knowing only $hash(K)$ and $E_f$? He shouldn't be able to decrypt the file, but should be able to prove that the encrypted file Alice sent, when decrypted, matches the hash, $hash(f)$.

It seems like I might need to use some sort of ZK-proof, but that may not work because the proof would be prohibitively large.

This question may be similar to: Proof that a hash matches an encrypted file, however, knowing only the hash of the key seems to present a different problem.

This could also be looked at as a Proof-of-Knowledge of a key $K$ such that $hash(K)$ matches the one Alice revealed to Bob and $Dec(E_f, K) = hash(f)$.

What you describe is very close to Zero Knowledge Contingent Payment (ZKCP) proposed for exchanging digital goods for bitcoins.

The setting is that Alice has a file $F$ and Bob would pay to have it. However they don't trust each other. So Alice generates a key $k$ and encrypts the file $E_f=E_{K}(F)$ using a cipher $E$, and hashes the key $y=H(K)$. Then she sends $(E_f,y)$ to Bob, along with a proof of knowledge $(F,k)$ such that $c$ is an encryption of $F$ under the key $K$ which satisfies $H(K) = y$. If Bob is satisfied with the proof, he will publish a transaction on the bitcoin network saying that there are some bitcoins locked in an account such that whoever can submit the pre-image of $H(K)$ to the account address can take the coins.

In your case, you have an additional hash value $z$ of the file published by Alice. It seems that you want Bob to also be able to verify the file matches $z$. In this case, Alice's proof would be a conjunction, i.e. $c$ is an encryption of $F$ under the key $K$ such that $H(K) = y$ AND $z=hash(F)$.

To do such proof, you would need SNARK (Succinct Non-Interactive Arguments of Knowledge). Conceptually it is simple, the prover shows that some secrets he knows, if computed correctly by some publicly known functions, will produce some values which the verifier knows. However the actual implementation can be quite complicated, and there are some caveats as well regarding the security properties.

A paper that contains more details and is worthy reading: Zero-Knowledge Contingent Payments Revisited: Attacks and Payments for Services by Campanelli et al, published in CCS 2017.


Code families in McEliece cryptosytem What are the families of codes frequently used in McEliece cryptosystem or its variants? I know that binary Goppa codes were used in the original system but many codes with efficient decoding algorithm can be used. Are there any other requirements on the code or generator matrix for that matter? I don't care about parameters used, just the names of families like Goppa, Hamming , Reed Solomon etc. is enough.

The modern approach is still to use binary Goppa codes.  See, e.g., McBits from 2013:

  Daniel J. Bernstein, Tung Chou, Peter Schwabe. "McBits: fast constant-time code-based cryptography." Pages 250–272 in Cryptographic hardware and embedded systems—CHES 2013—15th international workshop, Santa Barbara, CA, USA, August 20–23, 2013, proceedings, edited by Guido Bertoni, Jean-Sébastien Coron. Lecture Notes in Computer Science 8086, Springer, 2013. ISBN 978-3-642-40348-4.

https://binary.cr.yp.to/mcbits-20130616.pdf

Other proposals, such as Niederreiter's using generalized Reed–Solomon codes, have been broken:

  V.M. Sidelnikov, S.O. Shestakov. "On insecurity of cryptosystems based on generalized Reed–Solomon codes." Discrete Mathematics and Applications, 2(4), pp. 439–444, 1992.

https://doi.org/10.1515/dma.1992.2.4.439 (paywalled, sorry!)


Does this implementation of a function operate in constant time? Suppose we have a function that takes $n$ parameters, each being one bit in size, and returns a single bit. Internally, this function has a bit string $N \in \{0, 1\}^{2^n}$ and it operates by using the $n$ inputs to form a pointer to bit $i$ in $N$, where $i$ is equal to the input bits being concatenated and treated as an integer.

As an example, imagine we have $F(a, b, c)$ and $N = 01110001_{2}$. If we have $F(1, 0, 1)$, then the output will be found by retrieving bit $101_{2} = 5$, which would be $1$ (or $0$ if you want the left-most bit to be bit $0$).

Would implementing a function this way run in constant time? If it's implemented in hardware? If it's implemented in software?

Update: I thought it was obvious, but selecting the bits from $N$ would be implemented using a bitwise shift followed by a bitwise AND (with the value $1$).

Would implementing a function this way run in constant time?

This is not an implementation, it is an abstract description of the algorithm.

You need an implementation of the function in an actual programming language (or actual hardware) to determine whether or not it executes in constant time. You can't determine this by the description of the abstract algorithm, as there are (usually) many different possible ways to compute it.

An example of an implementation of the function would be some C code. Note how there are no operators or instructions in your description - an implementation would have a difficult time producing results without processing a series of instructions.

Additionally, the actual platform that you execute the algorithm on can influence whether or not the operation takes a constant amount of time. Even the programming language that you use can make implementing constant-time anything challenging.

Note also: Constant time in regards to cryptography means "time taken is independent of any secret data", as opposed to "takes the same amount of time to execute on all possible inputs".

If you branch on data that is supposed to be secret, you will probably leak information about it via how long it takes the operation to be performed.


X509 converted to Encrypted and Signing keys We have proprietary tool which takes a p12 file and generates a .key file. Inside the key file, I see two PEM formatted sections: Encrypting Certificate and Signing Certificate. When I open them on my machine they have the same CN, Expiration and Issuer, etc.
This key file is used for mutual 2-way authentication and we provide the key file to the client.

What is happening here? I understand the regular mutual authentication where you and client exchange public keys and trust them but why do you need to implement this method?

The PKCS12 (p12, pfx) is a standardized keystore where you may store multiple keypairs (key and certificate) or certificates themselves. It can be read/manipulted by multiple tools (OpenSSL, Keytool, keytool-explorer, ...).

You may have multiple certificates in you PKCS12 archive, it's usually a certificate chain with the certificate itself and its issuer (certificate authority). The certificates should be 'chained' (in a hierarchy).

Mutual SSL is used where the trust needs to be mutual (it's not only you want to be sure you speak to the right server (server only SSL), the server wants to be sure the client is who it claims to be). During the SSL handshake (or SSL renogotiation) the SSL server passes a set of trusted certificate authorities and the client then provides its own certificate if it is trusted by one of the offered CAs. Then the identity (private key ownership) is ensured by exchanging encrypted piece of data. It is a very effective method ensuring that only trusted clients are able to connect to the service.

Updated: why are there two certificates with the same user data but different purpose?
You have 2 certificates to the same key? Do they have the same issuer? Technically any certificate could be used to authenticate or to sign data. Legally - it may be different. It is common (e.g. on the eID cards) to have separate certificate for authentication and for signing. So you don't sign anything (legally binding) while you think you are authenticating to a service.. But -if they are both in the same keystore - don't you have the certificate chain there?


How simple can the PRP used in the Even-Mansour scheme be? For example, in the question “Is there any reason not to use Single-Key EM with AES and a constant key?” it is proposed to use AES with a fixed key as the permutation in a xor-permute-xor construction. In the paper linked in the answer – “Key-Alternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations” (PDF) – there is a proposal for a cipher that uses the full AES cipher with a fixed key(s).

Why is the full round AES required? How would the situation change if AES with only half the number of rounds was used? What about AES with only two rounds? If I recall correctly, two rounds of AES is the minimum required for complete diffusion of the input, so I wonder why 2 rounds wouldn't work just as well.

Why would one use an iterated construction, if the XOR-permute-XOR construction is providing all the security?

What requirements does the permutation need to fulfill, specifically? In the paper “Minimalism in Cryptography: The Even-Mansour Scheme Revisited” (PDF) they appear to just use the term "fixed random permutation" or "publicly known permutation".

The permutation used for Even-Mansour needs to approximate a random permutation. This is the model in which all of the $r$-round Even-Mansour proofs are done. If you have a permutation that is distinguishable from random in a small number of queries, those proofs become null and void—though in some cases the cipher may still be secure.

Now, it is perfectly reasonable to wonder about the exact limits of this approach like you did, and in fact people have: this is a popular cipher design approach otherwise known as "key-alternating cipher". The AES itself is probably the most famous instance of it. You can model the AES as
$$
P'(\dotsc P(P(m \oplus k_0) \oplus k_1) \oplus k_2) \dotsc) \oplus k_{10},
$$
where $$P(x) =\mathsf{MixColumns}(\mathsf{ShiftRows}(\mathsf{SubBytes}(x)))$$ and $$P'(x) = \mathsf{ShiftRows}(\mathsf{SubBytes}(x)),$$ and $k_i$ are the keys produced by the key schedule.

While the AES is not provably secure, since each of those permutations is way too simple to behave as a random permutation, heuristically this works out against known attacks given enough rounds. But in this case, the Even-Mansour results are of little use (besides confirming that the high-level design approach is sound), and concrete analysis against differential, linear, etc cryptanalysis is much more valuable.