Differences between DSA and RSA Algorithms Despite having learned much related to RSA and DSA, I cannot understand their differences. Can anyone tell me at least 4-5 differences between these algorithms? I have just used them for two-factor authentication (Linux OpenSSL).

If you're the user of some software using cryptography under the hood, knowing the mathematics of how RSA and DSA work won't help you. What you need to know is what configurations of your software are good for the way you use it, and the choice of algorithm is often not the most important factor, although between RSA and DSA the choice today is usually ECDSA, or failing that RSA over plain DSA.

RSA and DSA are both families of digital signature algorithms. A digital signature algorithm is a way to authenticate a message. When a message has a valid digital signature, it must have been signed by the holder of the private key that was used to sign. They are both instances of public-key cryptography: only the signer knows the private key, but the public key which is used to verify a signature can be known to everyone.

Today there are four families of digital signature algorithms in common use for computer users: RSA, DSA, ECDSA and EdDSA. The TLS protocol which powers most secure channels on the Internet can use RSA, DSA or ECDSA. SSH (specifically its most common implementation OpenSSH) can use RSA, ECDSA or EdDSA (older versions could use DSA). DSA has fallen into disuse; it isn't broken, but its performance is very poor compared to ECDSA for the same security level. EdDSA is still very new and not widely supported. RSA is on a slow path to obsolescence because it struggles to cope with the required increases of key sizes as computing power for cracking keys increases, but it still has a very broad installed base, and while it is much slower than ECDSA for signature generation, it is faster for verification.

Quantum cryptanalysis may come and force all these algorithms out, but for the time being it's still a research topic and nobody knows what post-quantum cryptography might end up looking like. There's an ongoing competition to find good algorithms that resist quantum cryptanalysis as it's currently thought to work.

If you're still using DSA, consider migrating to ECDSA. You're paying extra CPU power and using code that is probably not getting as much scrutiny these days. Don't migrate to any of the post-quantum algorithms because they haven't been studied much yet, and for all we know they'll be broken as soon as a cryptographer who isn't their author looks at them.

The security of RSA relies on the difficulty of the factoring problem, i.e. given only a product of two integers $p q$ the difficulty of finding $p$ and $q$ (with $p$ and $q$ chosen to make the problem difficult, i.e. being primes or at least probable primes). The security of DSA relies on the difficulty of the discrete logarithm problem, i.e. given $n$, $g$ and $y$ finding $x$ such that $g^x = y \bmod n$ (with $n$ and $g$ chosen to make the problem difficult). ECDSA and EdDSA also rely on the discrete logarithm problem, but on elliptic curves instead of $\mathbb{Z}/n\mathbb{Z}$.

There is also a family of public-key encryption algorithms called RSA. It uses the same mathematical problem under the hood, with different constructions on top. DSA does not have a corresponding encryption scheme in widespread use. ECIES is a standard for encryption using elliptic curve cryptography which can be thought of as a parallel to ECDSA, but it's markedly less common. The Edwards curves that power EdDSA can also be used for public-key encryption but I'm not aware of a standard for that.


Direct Anonymous Attestation to replace CA In term of authentication, I have the impression that to trust an entity it is mandatory to have a Certification Authority involve. Today I stumble upon an article something called Direct Anonymous Attestation is possible to get rid of CA. How is that possible when a verifier holds no information nor a trusted party to crosscheck with and yet able to trust an entity. I am not a math genius, can anyone explain how Direct Anonymous Attestation work in layman terms?

I briefly went through the paper - and interesting article you found. Though I see some gaps and assumptions. If someone understands it better, please feel free to comment or improve. So - in Layman's terms (how I understood it):

Once a subject could prove its identity, its identity (attributes, certificate) is written in a blockchain ladder (and assumed it is difficult to falsify).  The identity proof is not explicitly stated, but control over a domain admin addresses are mentioned several times.

What is not explicitly written (and I consider that as assumed knowledge) what would be the blockchain quorum confirming each transaction. In simple terms (very simplified) - it would need mutiple participant to confirm that the identity is ok. Every blockchain participant would become partial CA.

The idea looks good but I see a few issues (at least what I immediately see, unrelated to the math):

it is not related to the paper itself, but more to the blockchain ladder properties. If an organization would be able to take over the blockchain (having more participants, more computing power, ...) the trust would be completely broken. The benefic (and thus incentive) for malitious behaviour would be enormous.
current CA issued certificates have legal value in many countries (the CAs are not only used for validating domain names) for authentication and signing. That would not work with schema where institutions are unable to enforce legal control.


generating prime p and q, with alpha of element of order q I'm working on VSSS (Feldman) but I cannot understand the statement as follows:

I'm not good in reading mathematical statements (but working on it). Can anyone explain this in simple mathematics. Example will be appreciated. Thank you.

Edit:

This is what I got so far.
Given the following values: n=4, k=3, s=12, p=5, q=3, g=4
wherein n is no. of shares, k is threshold, s is the secret, p and q are prime, g is the generator

Using the polynomial function f(x) = 12 + 3x +2x^2.
then, f(2) = 68 mod q = 68 mod 3 = 2

Computing on commitment:
c1 = g^12 mod p = 4^12 mod 5 = 1
c2 = g^3 mod p = 4^3 mod 5 = 4
c3 = g^2 mod p = 4^2 mod 5 = 1
wherein, cx are commitments and 12,3 & 2 are coef
Verifying:

g^f(2) mod p = 4^2 mod 5 = 1

c1^x^0 mod p = 1^2^0 mod 5 = 1
c2^x^1 mod p = 4^2^1 mod 5 = 4
c3^x^3 mod p = 1^2^2 mod 5 = 1
where x is the value of x in f(x) which is 2.

1+4+1 <> 1 ????

What's wrong??? Am I doing it right?

There are generated the primes $p$ and $q$ such that $q | (p-1)$

What that means is that we search for two prime numbers $p$ and $q$, with the constraint that $q$ is a divisor of $p-1$.  That is, $kq = p-1$ for some integer $k$.

In practice, this is easy to do; we first pick a prime $q$ of an appropriate size, and then search for the value $k$ values of the appropriate size until we find a value $p = kq + 1$ which is also prime.

  and $\alpha \in \mathbb{Z}_p^*$ ...

$\mathbb{Z}_p^*$ is the multiplicative group modulo $p$; its elements have an obvious identification to the between 1 and p that are relatively prime to $p$ (and since $p$ is prime, that means the values $[1, p-1]$), and

  an element of order $q$.

What this means is that the smallest positive value $\lambda$ for which $\alpha^\lambda \equiv 1 \pmod p$ is $\lambda = q$.

It turns out to be a lot easier to find such a value $\alpha$ than you'd expect; you pick an arbitrary value $\beta \in [2, p-2]$ and set $\alpha = \beta ^ {(p-1)/q} \pmod p$.  As long as $\beta \ne 1$, then $\alpha$ will have an order precisely $q$.

We know that $\alpha^q = (\beta ^ {(p-1)/q})^q = \beta ^ {p-1} = 1$ by Fermat's Little Theorem (and because $p$ is prime)
We know that $\alpha^r \ne 1$ for any $0 < r < q$, because if $\alpha^r = 1$, then we could show that $\alpha^{\gcd(q, r)} = 1$, and as $q$ is prime, $\gcd(q, r) = 1$, and so we'd have $\alpha^1 = 1$, which we had verified is not the case


"Jitterentropy" vs CPU RDRAND in VeraCrypt 1.24 Veracrypt 1.24 just came out.  It uses a true random number generator based on hardware events; namely, on CPU timing jitter, or "Jitterentropy".

As an alternative to CPU RDRAND, I am a bit jittery about "Jitterentropy" in Veracrypt 1.24, and would like to hear some expert advice. The paper I just cited, by Stephan Müller, is very detailed.

Is Jittentropy a reliable cryptographic alternative to RDRAND in Veracrypt 1.24?

I too am perturbed ~~~.  A few relevant points that cause my own knees to wobble:-

A TRNG is a special cryptographic case in that it has information theoretic security.  And proving this requires accurate entropy estimation which is very difficult and pretty much still an open question for general sources. Killmann and Schindler,  Schürmann and Grassberger, Herrero-Collantes, Garcia-Escartin and I have shown this measurement to be intractable.  Even NIST acknowledges it.     Jitterentropy injects raw entropy into pools via a primitive LFSR (§3.1.3), and then Shannon entropy is measured via the school boy  log formula.  That’s not possible for raw general sources and it’s done on a flawed IID assumption.    $  \frac{d^2t}{di} $  is not a de-correlator (it's a low pass filter), and there was no permutation testing undertaken to prove the counter.

Stephan Müller is  indeed long.  I don’t like that.  The source of entropy should be plainly obvious to even the stupid and be there right up in your face.  Period. It should not take hundreds of lines of explanation and countless graphics. The entropy either comes from God, or doesn’t.    This is too complicated for me to inspire confidence that it’s not just a non OTP capable CSPRNG akin to /dev/urandom or a Modular Entropy Multiplication TRNG do-da :-

There are no obvious safety factors for entropy measurement.  I use a conservative 2 or 3 in my designs, but  Jitterentropy has none.  Lifting apparatus had a safety factor of 6, so it would seem prudent to have some factor if your life depends on it.  Even /dev/random has accommodation for one (although it's unwritten).

An (insurmountable?) fundamental problem with instrumentation of any OS kernel is the Observer Effect.  If you're hunting single bits of OS entropy, the signal to noise ratio is ~1:1.  A 0dB entropy signal is even worse than some of those really poor supposedly quantum TRNGs you find lurking in ePrint.

Finally, VeraCrypt’s random number generator documentation does not mention Jitterentropy as the source of it’s secrets.  They talk of:-

• Mouse movements
• Keystrokes
• Mac OS X and Linux: Values generated by the built-in RNG (both /dev/random and/dev/urandom)
• MS Windows only: MS Windows CryptoAPI (collected regularly at 500-ms interval)
• MS Windows only: Network interface statistics (NETAPI32)
• MS Windows only: Various Win32 handles, time variables, and counters (collected regularly at 500-ms interval)

All the chatter in the VeraCrypt forums seems to concur.  We know unequivocally that         reading Java's System.nanoTime on a modern CPU generates true entropy, and that forms the basis of real time operating systems (RTOS).  Nullifying propagation delay by going to an expectation of $ x\delta $ mean execution times  in an RTOS does not necessarily allow you to quantify it in multi-tasking desktops.    But it’s very difficult to measure decisively. And the entropy rate is unstable, or at best meta stable. Especially within domain of all dedicated CPUs, IP CPU blocks and wacko software environments.

In management if you can't measure it, you can't manage it (Peter Drucker). There are other issues that perturb me as well, but this is getting waay too long.  I’m convinced that it’s a good CSPRNG, but remain unconvinced that it’s a TRNG, suffering the same basic mensuration problem that haveged and RDRAND/RDSEED do.


Many time pad attack (XOR) The question is quite similar to Many time pad attack and I was trying to rely on the top answer, but still am a bit confused, so any explanation and help will be much appreciated.
Assume I have a bunch of ciphertexts with the same key. I need to decipher one of them.
At the moment I understand that I need to XOR the desired one with each of the rest, but I am confused whether I should do it one by one or XOR it will all at once?
Where do I go from there checking whether there's been a space or no, surely all of them will have spaces in different places?
How do I recover the symbols then?
Thank you so much.

A character is usually encoded as an ASCII. This means that it uses up one byte. That's a number from $0 - 255$. It can be represented as a hexadecimal $\text{0x00} - \text{0xFF}$. All your operations must be done character by character. From now on by "message", "key" and "cipher" i mean a single $0-255$ number.
$$
message1 \oplus key = cipher1 \\
message2 \oplus key = cipher2
$$
when we xor two ciphered letters
$$
cipher1 \oplus cipher2 = \\ message1 \oplus key \oplus message2 \oplus key = \\
message1 \oplus message2
$$
So when we xor one character of the cipher with corresponding character of a second cipher we remove the key from the equation, and receive a character of first message xored with character of second message. Now we do some deduction. We look for numbers looking like $\text{0x42}$ I did some calculations previously and I know that we can get this number within a-z(space)A-Z only by xoring "b" (lowercase b) and " " (space). Rest is pretty much a lot of guessing.

To get that byte of the key all you need is to xor byte of message with byte of cipher.
$$
key = message \oplus cipher
$$
Example:
We have two ciphertexts from which we take the third character:
$$48A6\color{red}{48}3C\\7692\color{red}{0A}A2$$
We xor them together:
$$\text{0x48} \oplus \text{0x0A} = \text{0x42}$$
I made myself a table of all possible letters xored with space, and I see that $\text{0x42}$ is in that table. This means that it's possible that one of the letters is "b" ($\text{0x62}$) and second is " " ($\text{0x20}$)
Let's assume that " " is encrypted in first ciphertext and get the key:
$$\text{0x48} \oplus \text{0x20} = \text{0x68}$$

If we assume that " " is encrypted in second ciphertext we get another possibility of the key:
$$\text{0x0A} \oplus \text{0x20} = \text{0x2A}$$

So the key can be:
$$\_\_\_\_\color{red}{68}\_\_$$
or
$$\_\_\_\_\color{red}{2A}\_\_$$

We just decreased the number of possibilities for this byte of the key from 256 to 2.


Do q-ary lattices have parallelogram kind of structure? An $m$-dimensional lattice is defined by a basis $A \in \mathbb{R}^{m \times n}$ is the set of points $\{Az : z \in \mathbb{Z}^n\}$. A picture of these points would be like a nice parallelogram kind of structure.

In crypto, we use $q$-ary integer lattices defined by basis $A \in \mathbb{Z}_q^{m \times n}$ and is defined as $\{x \in \mathbb{Z}^m : \exists z \in \mathbb{Z}_q^n, x = Az \mod q\}$. I couldn't imagine how these lattices look like. Do these also have the same kind of parallelogram structure? Why do cryptographers use these lattices?

Actually, the matrix $A$ defines a $q$-ary lattice $L$, but it is not a basis of $L$.

Let $m \ge n$, write $A$ in blocks, as follows: $A = \begin{pmatrix} A_1 \\ A_2 \end{pmatrix}$, where $A_1 \in \mathbb{Z}_q^{n\times n}$ and  $A_2 \in \mathbb{Z}_q^{m-n\times n}$. Additionally, let's also write the vectors $x \in L$ as "block" vectors $(x_1 \quad x_2)$.

Now, suppose that $A_1$ is invertible over $\mathbb{Z}_q$.

Then we see that $x \in L \Leftrightarrow x = Az \mod q \Leftrightarrow x_1 = A_1z \mod q \text{ and } x_2 = A_2z \mod q $.

But that means that $A_1^{-1}x_1 = z \mod q$ and $x_2 = A_2(A_1^{-1}x_1) \mod q$.

Therefore, over the integers, there is an $(m-n)$-dimensional vector $u$ such that $x_2 = A_2A_1^{-1}x_1 + qu$.

Thus, it is easy to see that the columns of the following matrix form a basis of $L$:

$$B = \begin{pmatrix} I_n & O \\ A_2A_1^{-1} & qI_{m-n} \end{pmatrix} \in \mathbb{Z}^{m\times m}.$$

If we do $B\begin{pmatrix} x_1 \\ u \end{pmatrix}$ we get exactly $\begin{pmatrix} x_1 \\ A_2A_1^{-1}x_1 + qu \end{pmatrix}$, as expected.

Now, answering your other questions:

  Do these also have the same kind of parallelogram structure?

Yes, all lattices have such structure. The parallelogram in this case is defined by the columns of $B$.

  Why do cryptographers use these lattices?

Those lattices appear naturally in cryptography because of problems like SIS and LWE.

There is plenty of material about that on the internet, for example, this tutorial on lattice-based crypto.


Decrypt a public encrypted message and Sign a signature, how the math is different? As I understand, when you want to send a confidential message to someone, you encrypt the message with his public key. And he use his private key to decrypt the message.

At the same time, one can use his private key to sign a message, and other people use his public key to verify that it's him who sign it.

How the math is different between decrypt the message and sign a message?

The simplistic view that signing uses the same math as decryption is descriptive with textbook RSA; has some relation to practice in safe use of RSA; and is just wrong with most other common asymmetric cryptosystems, beside the commonality that a private key is involved.

In textbook RSA, the math to decrypt an encrypted message and compute a signature is the same: it is applied the textbook RSA private key function $x\to y=x^d\bmod N$, with $(N,d)$ the private key, and $x$ the encrypted message in decryption, or the message to sign in signature. Problem is, textbook RSA is unsafe for both encryption and signature.

When we move to secure use of RSA, the math becomes different:

To decrypt we check the bound of the cryptogram $x$, apply the above textbook RSA private key function, then

Extract the encrypted message from the result $y$, in a certain way that removes random padding that was added at encryption (and perhaps checking certain fields). There are at least two common classes of RSA encryption padding and corresponding decryption removal, defined in PKCS#1, and several implementation variants (not all are safe). That can be enough for very small messages (like few hundred bytes).
And/or what we really obtain is a secret key, which is then used to decipher the bulk of the message using symmetric-key cryptography (that's hybrid encryption).

To generate a signature we typically hash the message to sign then add redundancy in a certain way, then apply the above textbook RSA private key function to obtain the signature $y$ (in some variants we further keep $\min(y,N-y)$ ). There are at least three common classes of RSA signature padding: two in PKCS#1, and ISO/IEC 9796-2, which comes with several variations.

When we move to asymmetric cryptosystems other than RSA, one thing remains: the private key is involved in decryption, and/or computing a signature. Other than that, there is typically profound disjunction between decryption and computing a signature (one notable exception is the Rabin cryptosystem, which can be seen as a variant of RSA with even public exponent); and very often, one of the two features is just not offered by a particular cryptosystem.

For example, we have DSA, ECDSA, and Lamport signatures, but these cryptosystems do not offer encryption.

The converse can be true: we have Pailler encryption, but no useful signature analog. We have NTRUEncrypt, which latest versions are unbroken; but it is quite different from the related NTRUSign, and last time I checked work on the later stopped in the broken phase of multiple break/repair cycles.


How secure is my OTP program? I'm writing a one-time pad encryption program because I got really interested in the idea of "encryption which has been proven to be impossible to crack if used correctly".

I'm writing the program just for fun, as programming and cryptography are my hobbies. Therefore, I don't expect the program to be used for highly vulnerable data.
I just wonder how secure my program is, and what I can improve (considering that the hacker won't have any access to the key file).

The program starts off by:

Making a list of 50 numbers from the mouse movement coordinates at the
    start of the program.
That number list is then the seed to the ISAAC
    Random Number Generator (More info here).
A key file is generated based on the size of the file to be encrypted. The key file is generated from random numbers from the ISAAC Random Number Generator.
The file-to-be-encrypted and the generated Key file are XOR'ed and saved to a new file--the ciphertext file.
(deciphering) Happens by XOR'ing the key file and ciphertext file, and you get the plaintext file.

The perfect security of OTP hinges on the fact, that keys must be chosen truly at random and uniformly from the domain of all possible keys, i.e. all bitstrings of a certain length.
The problem with your approach is that you use a pseudorandom number generator to generate the key.

It does not matter how good the generator is, because the entropy that can be used to generate the key is limited by the seed you use.

Let's, assume that the 50 numbers you use are really random and distributed uniformly -- and that is at least debatable for mouse movement.
If you use 50 number in some range, lets say between $0$ and $x-1$, then for files of any size, you only ever produce at most $x^{50}$ different keys.

Obviously, for large enough files, this is much smaller than the total number of all possible keys and therefore, your perfect security does no longer hold.

An attack would for example consist of deciding which of two messages $m_1,m_2$ is encrypted in a ciphertext (your basic indistinguishability game). Keep in mind that for perfect security the runtime of the adversary is unbounded. That means that $\mathcal{A}$ could enumerate all $x^{50}$ possible keys and check if any of those decrypts the ciphertext to one of the two messages.
This works basically, because the number of possible keys is much smaller than it should be and the chance that the ciphertext could also be decrypted to the other message is very small (for large enough messages).


VKO GOST R 34.10-2001 (described in RFC4357), Key Agreement Algorithm. Looking for its implementation/detailed description/examples VKO GOST R 34.10-2001 was described in RFC4357 Page 7
But the description is very poor. Here it is:

  This algorithm creates a key encryption key (KEK) using 64 bit UKM, the sender's private key, and the recipient's public key (or the reverse of the latter pair).

  Let $K(x,y,UKM) = ((UKM*x)(mod q)) . (y.P)$ (512 bit), where

  $x$ - sender's private key (256 bit)
  $x.P$ - sender's public key (512 bit)
  $y$ - recipient's private key (256 bit)
  $y.P$ - recipient's public key (512 bit)
  $UKM$ - non-zero integer, produced as in step 2 p. 6.1 [GOSTR341001]
  $P$ - base point on the elliptic curve (two 256-bit coordinates)
  $UKM*x$ - $x$ multiplied by UKM as integers
  $x.P$ - a multiple point
  Calculate a 256-bit hash of $K(x,y,UKM)$:

  $KEK(x,y,UKM) = gostR3411 (K(x,y,UKM))$

  Keypairs $(x,x.P)$ and $(y,y.P)$ MUST comply with [GOSTR341001].

  This algorithm MUST NOT be used when $x.P = P, y.P = P$

I want to implement it. Would be great to get more detailed description of that alogirthm with standard values for all parameters, with several examples (to be used in testing my own implementation) of all intermediate and final values on both sides. Here’s an example of a great description for Signature Algorithm GOST R 34.10-2012 (PDF, Russian language).

There is an implementation in OpenSSL of VKO GOST “engines/ccgost/gost2001_keyx.c”, but I'm not familiar with OpenSSL, so understanding of those functions internals is difficult for me. Maybe someone has at least some C++ (or any other language) implementation of VKO GOST key agreement algorithm (could be through OpenSSL) so that I can run it and get golden test values for testing my own implementation.

I just finished with implementing my own Big Integer C++ library with elliptic curves support. I've implemented Key Agreement from RFC4357 and surprisingly it works! You get the same$ K(x, y, UKM)$ on both sides while only sharing public keys and UKM between both parties.

Just found a nice description of VKO GOST in the next document Using cryptographic algorithms related to GOST R 34.10/11-2012 (PDF, Russian language). It has reference examples of computing shared key $K(x, y, UKM)$ after hashing it with Hash GOST R 34.11-2012.

Still looking for real detailed standards with real values. Maybe some other Key Agreement standards that are well used in Russia or related to GOST R 34.10 standard.

You can start by reading:
https://github.com/openssl/openssl/blob/OpenSSL_1_0_2-stable/engines/ccgost/README.gost
It has examples on how to generate GOST certificates.

After that I would suggest running a test SSL/TLS connection with those certificates and openssl s_client and openssl s_server utilities. If it works, you may then recompile OpenSSL and make it dump all needed intermediate data during SSL handshake to stdout. You can then have as many reference examples as needed.

Also, have a look at
https://github.com/openssl/openssl/blob/c64879d3f3cc4c7f1c436a9fe3bd109847a23629/test/gost2814789test.c
to have an idea on how to call GOST algorithms from OpenSSL.


Hide secrets in an article composed with Machine Learning? Say that Alice wants to communicate with Bob, but she does not want any direct contact with him. Instead, Alice will put the secret in public, such as a discussion board, and Bob will come there to get the info.

Assume that the secret is "attack", Alice can come up with the sentence "Apple is the best to eat, and it can really keeps you healthy." Assume Bob knows the magic key 2, he can retrieve the secret.

My question is, how possible it is to generate an article (that makes sense) out of a longer secret, such as a sentence? Is AI good enough to do it?

Of course, the shorter the word-span, the harder it is to compose a suitable article. But if I require a relevant word appears at the location 1, 51, 101, 151, ..., I think it is not too hard.

Update: thank you all for your reply. As you see, the example I gave is rather simple. I can easily improve the "magic number", instead of using 2 or 50 or 100, I can generate a series of random number from the same seed, owned by Alice and Bob.

To go for the low-hanging fruit, train your machine to be really good at swapping synonyms based on context.  Then just have it find suitable synonym replacements for every word of covertext located at a multiple of your magic number.

EDIT:  I don't have enough reputation to comment so I'll reply to another post here.  Someone objected that the keyspace is quite small.  For example, there are only a handful of possible keys in the OP's example, only one of which yields meaningful text.  But this can be remedied quite easily.  Instead of using simply the first letter of a word, use the letter at an arbitrary position determined by a second key, wrapping around if the word is too short.

For instance, take the key KEY as numerals derived from the position of K, E, Y in the alphabet: 11 5 25.  Choose a magic number like 3, and beginning with the first word, hide a secret letter at position 11 (wrapping around if the word is shorter than 11 characters). In the 3rd word after (since 3 is your magic number) hide the next secret letter at the position indicated by the next numeral of your key, etc.

An apple is healthy to eat. They keep doctors away. You can cook them
in pockets of bread and enjoy!
[A]n apple is heal[t]hy to eat. [T]hey keep doctors aw[a]y. You can
[c]ook them in poc[k]ets of bread and enjoy!
Word 1, position 11: A

Word 3, position 5: T

Word 6, position 25: T

Word 9, position 11: A

Word 12, position 5: C

Word 15, position 25: K

This approach is not trivially broken.


Is there really no use for MD5 anymore? I read an article about password schemes that makes two seemingly conflicting claims:

MD5 is broken; it’s too slow to use as a general purpose hash; etc
The problem is that MD5 is fast

I know that MD5 should not be used for password hashing, and that it also should not be used for integrity checking of documents.  There are way too many sources citing MD5 preimaging attacks and MD5s low computation time.
However, I was under the impression that MD5 still can be used as a non-cryptgraphic hash function:

Identifying malicious files, such as when Linux Mint's download servers were compromised and an ISO file was replaced by a malicious one; in this case you want to be sure that your file doesn't match; collision attacks aren't a vector here.
Finding duplicate files.  By MD5-summing all files in a directory structure it's easy to find identical hashes.  The seemingly identical files can then be compared in full to check if they are really identical.  Using SHA512 would make the process slower, and since we compare files in full anyway there is no risk in a potential false positive from MD5. (In a way, this would be creating a rainbow table where all the files are the dictionary)

There are checksums of course, but from my experience, the likelihood of finding two different files with the same MD5 hash is very low as long as we can rule out foul play.
When the password scheme article states that "MD5 is fast", it clearly refers to the problem that hashing MD5 is too cheap when it comes to hashing a large amount of passwords to find the reverse of a hash.  But what does it mean when it says that "[MD5 is] too slow to use as a general purpose hash"?  Are there faster standardized hashes to compare files, that still have a reasonably low chance of collision?

I know that MD5 should not be used for password hashing, and that it also should not be used for integrity checking of documents. There are way too many sources citing MD5 preimaging attacks and MD5s low computation time.

There is no published preimage attack on MD5 that is cheaper than a generic attack on any 128-bit hash function.  But you shouldn't rely on that alone when making security decisions, because cryptography is tricky and adversaries are clever and resourceful and can find ways around it!

  Identifying malicious files, such as when Linux Mint's download servers were compromised and an ISO file was replaced by a malicious one; in this case you want to be sure that your file doesn't match; collision attacks aren't a vector here.

The question of whether to publish known-good vs. known-bad hashes after a compromise is addressed elsewhere—in brief, there's not much that publishing known-bad hashes accomplishes, and according to the citation, Linux Mint published known-good, not known-bad, hashes.  So what security do you get from known-good MD5 hashes?

There are two issues here:

If you got the MD5 hash from the same source as the ISO image, there's nothing that would prevent an adversary from replacing both the MD5 hash and the ISO image.

To prevent this, you and the Linux Mint curators need two channels: one for the hashes which can't be compromised (but need only have very low bandwidth), and another for the ISO image (which needs high bandwidth) on which you can then use the MD5 hash in an attempt to detect compromise.

There's another way to prevent this: Instead of using the uncompromised channel for the hash of every ISO image over and over again as time goes on—which means more and more opportunities for an attacker to subvert it—use it once initially for a public key, which is then used to sign the ISO images; then there's only one opportunity for an attacker to subvert the public key channel.
Even if you got the MD5 hash from a known-good source, collision attacks may still be a vector in cases like this.  Consider the following scenario:

I am an evil developer.  I write two software packages, whose distributions collide under MD5.  One of the packages is benign and will survive review and audit.  The other one will surreptitiously replace your family photo album by erotic photographs of sushi.
The Linux Mint curators carefully scrutinize and audit everything they publish in their package repository and publish the MD5 hashes of what they have audited in a public place that I can't compromise.
The Linux Mint curators cavalierly administer the package distributions in their package repository, under the false impression that the published MD5 hashes will protect users.

In this scenario, I can replace the benign package by the erotic sushi package, pass the MD5 verification with flying colors, and give you a nasty—and luscious—surprise when you try to look up photos of that old hiking trip you took your kids on.

  Finding duplicate files.  By MD5-summing all files in a directory structure it's easy to find identical hashes.  The seemingly identical files can then be compared in full to check if they are really identical.  Using SHA512 would make the process slower, and since we compare files in full anyway there is no risk in a potential false positive from MD5.

When I put my benign software package and my erotic sushi package, which collide under MD5, in your directory, your duplicate-detection script will initially think they are duplicates.  In this case, you absolutely must compare the files in full.  But there are much better ways to do this!

If you use SHA-512, you can safely skip the comparison step.  Same if you use BLAKE2b, which can be even faster than MD5.
You could even use MD5 safely for this if you use it as HMAC-MD5 under a uniform random key, and safely skip the comparison step.  HMAC-MD5 does not seem to be broken, as a pseudorandom function family—so it's probably fine for security, up to the birthday bound, but there are better faster PRFs like keyed BLAKE2 that won't raise any auditors' eyebrows.
Even better, you can choose a random key and hash the files with a universal hash under the key, like Poly1305.  This is many times faster than MD5 or BLAKE2b, and the probability of a collision between any two files is less than $1/2^{100}$, so the probability of collision among $n$ files is less than $\binom n 2 2^{-100}$ and thus you can still safely skip the comparison step until you have quadrillions of files.
You could also just use a cheap checksum like a CRC with a fixed polynomial.  This will be the fastest of the options—far and away faster than MD5—but unlike the previous options you still absolutely must compare the files in full.

So, is MD5 safe for finding candidate duplicates to verify, if you subsequently compare the files bit by bit in full?  Yes.  So is the constant zero function.

  (In a way, this would be creating a rainbow table where all the files are the dictionary)

This is not a rainbow table.  A rainbow table is a specific technique for precomputing a random walk over a space of, say, passwords, via, say, MD5 hashes, in a way that can find MD5 preimages for hashes that aren't necessarily in your table with fewer trial hash evaluations than a naive search.  (It can also be done in parallel with the search to not only speed it up but reduce the price/performance ratio.)  It is not simply a list of precomputed hashes on a dictionary of inputs.

(The blog post by tptacek in 2007 that you cited, and the blog post by Jeff Atwood that it was a response to, both misrepresent what rainbow tables are.  tptacek claims in 2019 that he DGAF about rainbow tables, perhaps because modern password hashes thwart them by the mere use of salts.  But password search under a fixed, unsalted hash function is only one application of the idea, for which the term was popularized.  Rainbow tables are relevant to any preimage search as noted in the original paper, such as AES keys given known plaintext/ciphertext pairs.  And it's not just a trivial time/memory tradeoff—a rainbow table preimage search can reduce price/performance ratio if parallelized.  This is why, for instance, AES-128 should not be construed to give ‘128-bit security’.)

  When the password scheme article states that "MD5 is fast", it clearly refers to the problem that hashing MD5 is too cheap when it comes to hashing a large amount of passwords to find the reverse of a hash.  But what does it mean when it says that "[MD5 is] too slow to use as a general purpose hash"?  Are there faster standardized hashes to compare files, that still have a reasonably low chance of collision?

I don't know what tptacek meant—you could email and ask—but if I had to guess, I would guess this meant it's awfully slow for things like hash tables, where you would truncate MD5 to a few bits to determine an index into an array of buckets or an open-addressing array.


what does differential privacy (in machine learning) promise or guarantee? I am recently reading some papers about privacy-preserving machine learning.

Some works incorporate the idea of differential privacy to protect the privacy of the training dataset when the model is published. The basic framework is as follows:

A trusted party (call it TP) possesses the training dataset in cleartext. TP then conducts some machine learning task and produces a prediction model. In the training process, TP will add some noise to the parameters (details omitted) such that the resulting model is noisy but is still accurate enough. It is then theoretically proved that some notion of differential privacy is achieved.

Meanwhile, I am aware of some "model inversion attacks" that can recover the training records given only a particular label and black-box access to the model.

So, what does differential privacy promise or guarantee in the context of privacy-preserving machine learning?

Specifically, suppose I am the owner of one record in the training dataset. The TP published a noisy model and tells me that it has $\epsilon$-privacy and the publication of the model will not violate my privacy. So what does it mean? Because I know that some model inversion attacks can recover my record. Does this violate the $\epsilon$-privacy?

Model inversion attacks are, by definition, impossible if the model generation process is $\epsilon$-differentially private for a sufficiently small $\epsilon$: differential privacy guarantees that if your original data was completely different, you would not be able to tell the difference just by looking at the model. Your data is effectively indiscernible from noise.

That said, the strength of the guarantee depends on the value of $\epsilon$, you can read a short explanation of that on this other question. If $\epsilon$ is very large, model inversion attacks might be successful in retrieving noisy or probabilistic information. I'm not aware of any attempt to experimentally verify for which parameters of $\epsilon$ it starts becoming a problem.


How is the keystream actually generated in AES CTR I've been trying to find out how the keystream in AES-CTR is generated, but I can't actually figure it out. Wikipedia and any other sites that "explain" it just say the nonce is padded with the counter and encrypted with the key...

So how does it actually work? (As nitty gritty as possible please)

How the counter and nonce are related is specified in e.g. NIST SP 800-38A: Recommendation for Block Cipher Modes of Operation Methods and Techniques, Appendix B: Generation of Counter Blocks.

I'll list the second approach, as the first approach - just concatenating all the messages - is stupid and really never used:

  A second approach to satisfying the uniqueness property across messages is to assign to each message a unique string of $b/2$ bits (rounding up, if $b$ is odd), in other words, a message nonce, and to incorporate the message nonce into every counter block for the message. The leading $b/2$ bits (rounding up, if $b$ is odd) of each counter block would be the message nonce, and the standard incrementing function would be applied to the remaining $m$ bits to provide an index to the counter blocks for the message. Thus, if $N$ is the message nonce for a given message, then the $j$-th counter block is given by $T_j = N \| [j]$ , for $j = 1...n$. The number of blocks, $n$, in any message must satisfy $n < 2m$. A procedure should be established to ensure the uniqueness of the message nonces.

So in bytes you would have NNNNNNNNCCCCCCCC where each character is one byte, with the most significant byte to the left and the least significant to the right. Here N is a byte or octet which is part of the nonce and C is part of the counter.

For AES this means a 8 byte (random, serial or otherwise unique) nonce and a 8 byte / 64 bit counter part, containing a statically sized, unsigned big endian encoding.

Most libraries simply allow any kind of scheme and will treat the 16 byte IV simply as initial counter value, and start counting as if it was an unsigned big endian 128 bit value (note that the increase operation is very lightweight and doesn't need any special big-number magic, you just increase the byte values right to left). So basically the counter is considered CCCCCCCCCCCCCCCC. This is kind of dangerous if you decide e.g. to have a larger nonce and smaller counter, as you may overflow the counter into the nonce at the left of it. So in that case you must make sure that the message size limitations are adhered to yourself.

Usually the counter part is initialized to all zero bits, so that the overflow happens only when the entire counter space is used up.

In principle NIST will allow any scheme that produces a unique counter for each block (for the same key). However, due to common usage, you'll likely not find many counter schemes that uses little endian. Sometimes the nonce consists of different fields though, and some implementations also accept smaller nonces as input variable, that are then placed at the leftmost side (and the counter starting at zero).


Is the XOR of PRGs sharing the same input a PRG? I have question in learning PRG. Given that $f$ and $f_1$ are PRGs, both $\{0,1\}^n \to \{0,1\}^{2n}$.

Is $g(x) = f(x)$ xor $f_1(x)$ a PRG?

Someone told me that in this case, $g(x)$ is not a PRG, but I don't know how to prove it.

Thank you everybody's help. I have known that if $f$ and $f_1$ have some relation, then $g$ can not be PRG.
e.g. $f = f_1$, then we can know, after $f ⊕ f_1$, it always return 0 for $g(x)$, in this case, $g(X)$ will never be a PRG.


How to generate Multiple Encryption Keys for use in RSA polymorphic multiplication I am a long time scroller, first time poster in the crypto stack. I've recently been finding myself leaving the realm of mainstream/standard crypto (imo that consists of symmetric/asymmetric encryption, some ciphers and one way hash functions ect). I am currently faced with a problem regarding using the RSA algorithm through multiparty computation. I am using RSA to conduct multiplicative homomorphic encryption using multiple keys. I am able to provably generate the encryption keys along with the final cipher text after multiplying all the values together. However I am not able to generate the correct decryption keys.
Process for encryption using RSA MPC
\begin{align}
C_1 &= a^{e_1} \pmod n \\
C_2 &= a^{e_2} \pmod n  \\
C_{final}&= C_1 \cdot C_2 = a^{e} \pmod n,\ \text{where} \ e=e_1 + e_2
\end{align}
The issue is that this only I can only really do this with a single encryption key (so if you consider $e_1=e_2$), whereas I would like to use multiple encryption keys ($e = e_1 + e_2$ or something equivalent), encrypt a value do some operation on that encrypted value then be able to decrypt it and receive some meaningful output.
Can someone help me with the problem of where to find details on using multiple encryption keys in RSA and working with the encrypted values directly ?
Research I based my working from: https://www.researchgate.net/publication/335743662_Enhanced_Homomorphic_Encryption_technique_using_RSA_ALGORITHM_with_multiple_keys

Besides the answer Dimitree gave to himself, I' like to add something even if I am not sure whether I understand the original problem he wanted to solve.
You used the same message a and encrypted it with different values for e, but used the same modulus N. And you added the different exponents e.
As far as I know, the homomorphic multiplicative feature of RSA is defined in a way, that the same e and N are used, and you either want to get a multiple of m by just manipulating c or you want to multiply two c values.
Simple encryption and decryption of numbers in RSA is straightforward: To encrypt a number m, one computes c = m^e mod N. To decrypt a ciphertext c, one only needs to compute m' = c^d mod N = m^(e*d) mod N = m.
To see that RSA is partially homomorphic, consider two numbers m1 and m2 and their respective ciphertexts c1 and c2. To compute the product m1 * m2 homomorphically, one computes the product of the ciphertexts, c1 * c2. This then decrypts to m1 * m2: (c1 * c2)^d mod N = (c1^d) * (c2^d) mod N = (m1^(e * d)) * (m2^(e * d)) mod N = m1 * m2.
The RSA scheme is only partially homomorphic because one is only able to perform multiplications.
In a similar way you may build an attack modifying c to c' such that the receiver gets m' = k*m.
However, I might not have understand the problem and you are talking of another kind of multiparty communication. If so could you explain the scenario a bit more detailled.


Understanding Key space I've looked at a few previous posts on this site but I'm still struggling with the concept of keyspace. Specifically I'm following a coursera course but I think it's probably too advanced for me as I'm failing to understand some numbers.

In the course it talks about a substitution cypher in an alphabet of 26 letters. There is then a question

  What is the size of key space in the substitution cipher
  assuming 26 letters?

The answer is 26! (I get this bit) but the instructor then says this is roughly equivalent to 2^88 which I don't get as the numbers don't seem close to me at all.

Furthermore it talks about the enigma machine and how a 4 rotor machine which would have the following

  keys = 26^4 = 2^18

  This is equating to 26^4 combinations (4 rotors with 26 keys - again I get this (though should it not be 26!^4?) but then I don't get how this gives a key space of 2^18 . I think it's the equality signs throwing me off as I'm thinking it's 'equal to' as opposed to it 'equates to or resolves to'.

I just don't get these numbers if I'm honest.

Can someone break it down in it's simplest terms for me? As I say, based on this evidence I think the course might be beyond me mathematically, but I really want to understand at least this part now I've gone through it!

I'm not sure exactly what you're not getting.

You understand that the keyspace for a simple substitution cipher is $26!$; do you understand that $26! = 1 \times 2 \times 3 \times 4 \times ... \times 24 \times 25 \times 26$, correct?

So, we have $26! = 403291461126605635584000000$, correct?

We also have $2^{88} = 309485009821345068724781056$, correct?

Would you agree that these are "roughly" the same (where roughly in this case means within 30%)?

  keys = 26^4 = 2^18

What might be confusing you is the equal sign; obviously $26^4 = 456976$ is not exactly $2^{18} = 262144$; I believe the idea the author is trying to convey is that they're close, well, at least close enough for his analysis.  I'd personally use $\approx$ here...

  (though should it not be 26!^4?)

Actually, for Engima, 26 is correct; each rotor can be set in one of 26 positions; hence each rotor can do one of 26 specific permutations; it can't do an arbitrary 26! permutation.


Key derivation with Curve25519 for data encryption I'm new when it comes to cryptography so this question might be a little bit stupid:

Can I derive a key with Curve25519 from a (let's say) root key and encrypt the file with a secret key algorithm? Or should I better use a key derivation function like PBKDF2?

What you actually want is called a key-based key derivation function (KBKDF).
The most prominent KBKDF (and really the standard solution here) is HKDF.

This is a function that takes a secret key (e.g. a KEK or a root key or something) and outputs (a set of) derived keys enjoying some nice properties.

You can customize the keys to get different keys for different purposes, e.g. you can add a purpose-string to them which ensure you won't accidently re-use some key material
You can salt the key material. This way you can store a (non-secret) salt with the object to be encrypted and this will ensure all files enjoy distinct encryption keys (and the customization ensure each key-based operation on an object has a different key)
Given a derived key it is impossible to find any other keys except for those derived from the leaked one.
The derivation process isn't computationally expensive (especially compared to PBKDF2 and Curve25519)

Now for a short clarification:

Curve25519 is an elliptic curve used to perform signature operations and derive keys between two distinct parties such that no passive attacker can obtain the negotiated key. This clearly doesn't apply to you as you already have the key material.
PBKDF2 is an (old) password based key derivation function which is used to process passwords such that the operation takes more time and thus it is more computationally expensive for an attacker to brute-force a password out of a given key. This one does not apply to you because your key material has such high entropy that an attacker doesn't have a chance at brute-forcing anyways.


RSA Key generation: How is multiplicative inverse computed? As per Wikipedia, RSA keygen goes like this:

Choose two distinct prime numbers p and q.
Compute $n = pq$.
Compute $\varphi(n) = (p − 1)(q − 1)$.
Choose an integer e such that $1 < e < \varphi(n)$ and $e$ and $\varphi(n)$ are coprime. $e$ is released as the public key exponent.
Determine $d$ as $d \equiv e^{−1} \bmod \varphi(n)$; i.e., $d$ is the multiplicative inverse of $e$ (modulo $\varphi(n)$). $d$ is kept as the private key exponent.

Thus the public key is $(e, n)$ and the private key is $(d, n)$.

According to this description, $d$ is determined directly from $e$ and $n$ (i.e. the private key is derived from the public key). I understand that finding the multiplicative inverse in that way is computationally difficult. If this weren't the case, then any attacker could determine the private key from the public key. What am I misunderstanding here? What does the key generator know that an attacker doesn't, and how is that used to determine the private key?

Modular inverse can be computed with Extended Euclidian Algorithm, as other answers suggest.

I will answer your second question - why an attacker can't get private key? The problem here is that the private exponent is the modular inverse of the public one, but modulo $\phi(n)$, not $n$:

$d \equiv e^{-1} \pmod{\phi(n)}$

Attacker does not know $\phi(n) = (p-1)(q-1)$ here and there's no known way to compute it without factorizing $n=pq$.

You can notice that these numbers differ only by $p + q - 1$ but this fact itself does not help much because $p+q=O(\sqrt{n})$ and the simplest trial division algorithm for factorization works with the same complexity (it is far from feasible). Of course there are much more advanced factorization methods but they are also far from factorizing large RSA modulus.


Implementing Inferno's ECIES: Creating a symmetric key from sender's public key I'm coding(in C#) an offline(no network or server), hybrid file encryption app, implementing Inferno's ECIES.  The user's private key is to be stored either on the pc drive or on a usb key, after being encrypted with a key(password) hashed with ~ 1 million Scrypt iterations. The user can load his key into protected memory once the app is started. Loading the key takes a huge 20 seconds but it would be a one-time/session delay if the following is acceptable:

For files meant to be kept by the user(some are sent, some are kept), is it secure to produce a "shared" symmetric key with the user's own public key? This would allow the user to have one password to remember(instead of one for each symmetric and asymmetric key) and since the symmetric key produced this way has a high entropy, hashing iterations are not necessary when saving/loading files, something that happens very often during a session.

The code itself is working but that does not tell me if the approach is secure. Just to make sure I'm clear, here is a shortened code example:

    internal static void SendText(string text, byte[] ephemeralPublicBlob, string file)
    {
        CngKey receiverKey = ephemeralPublicBlob.ToPublicKeyFromBlob();
        var ephemeralBundle = receiverKey.GetSharedEphemeralDhmSecret();
        var ephemeralPublic = ephemeralBundle.EphemeralDhmPublicKeyBlob;
        var ephemeralSymmetric = ephemeralBundle.SharedSecret;
        var textSegment = new ArraySegment<byte>(text.ToBytes());
        var ciphertext = SuiteB.Encrypt(ephemeralSymmetric, textSegment);

        using (FileStream fs = new FileStream(file, FileMode.Create, FileAccess.Write))
        {
            byte[] sent = Utils.Combine(ephemeralPublic, ciphertext);
            fs.Write(sent, 0, sent.Length);
        }
    }

    internal static string ReceiveText(string file, CngKey masterKey)
    {
        string decrypted = null;
        using (FileStream fs = new FileStream(file, FileMode.Open, FileAccess.Read))
        {
            byte[] received = new byte[fs.Length];
            fs.Read(received, 0, (int)fs.Length);
            var ephemeralPublic = new ArraySegment<byte>(received, 0, 104);
            var cipherText = new ArraySegment<byte>(received, 104, received.Length - 104);
            var sharedSecret = masterKey.GetSharedDhmSecret(ephemeralPublic.ToArray().ToPublicKeyFromBlob());
            decrypted = SuiteB.Decrypt(sharedSecret, cipherText).FromBytes();
        }
        return decrypted;
    }

So, in the first function(SendText), if I pass the sender's(instead of receiver's) public blob as the byte[] argument, the code works, but am I leaking/messing something?

You are not leaking anything, because ephemeralBundle will contain a new, unique public-private ephemeral key pair, and the encryption will occur with brand-new [ephemeral_public  sender_private == ephemeral_private  sender_public] secret key.

Using sender's pk as a receiver (ie. sending to yourself) is safe in your scenario above.


Correct integer input value for keccak 256 Assuming that we use k = sha3.keccak_256()(pysha3 package).

How should one convert integer input for a function k.update(myinteger) so that the output will be correct?

example:

import sha3

myinteger = 1064880000

k = sha3.keccak_256()
k.update(myinteger)
k.hexdigest()

Define 'correct'

That is less silly of an answer than you might think; SHA-3-256 is a function from bitstrings (or bytestrings) to 256 bit hashes; it has no predefined ideas about a mapping of an integer to those bitstrings; it'll work for any of them.

Now, the application which is using SHA-3 might have such a predefined idea, and hence might define a 'correct' way.  However, there is nothing in the code segment above would define it, and we have no idea what application you are attempting to be compatible with.

If you have no predefined application, and are just looking for a plausible way, might I suggest converting the integer into a little-endian 4 byte string (or 8 byte, if the integer value might be above 4 billion).  That's as good as any...


Why are primes important for encryption Why are primes so important? Why can't we just use a random number?
My guess is that it's because finding a random prime require more computing power, than finding a random number. Can anybody confirm this?

Primes are important because the security of many encryption algorithms are based on the fact that it is very fast to multiply two large prime numbers and get the result, while it is extremely computer-intensive to do the reverse. When you have a number which you know is the product of two primes, finding these two prime numbers is very hard. This problem is called prime factorization and finding an algorithm which does it fast is one of the unsolved problems of computer science.


Would It Be Technically Possible To Delete Old Blocks From A Blockchain Cryptocurrency? From what I understand, a cryptocurrency mine needs to store a copy of the entire blockchain in order to be able verify transactions, which is why most wallet owners are not miners. The more centralized a decentralized consensus is, the more likely it is that its participants will 'defect' and screw over other participants, as in 51% attacks. And since these mines are physical locations, they will be able to be blackmailed by defenders of the legacy fiat monetary system. Therefore, the goal should be to create a cryptocurrency that is radically decentralized. It should be mined on every smartphone, maybe even on every internet browser while the CPU capacity is not used. And this requires the blockchain to be radically small, small enough to fit on a few GB of flash memory, and with the potential to stay that small if there are millions of transactions per day due to worldwide adoption.
That's why one solution seems to be to simply not store transactions forever but delete old blocks.
[Q] Much like this Reddit user suggests, would it be technically feasible to delete old blocks from a blockchain in order to keep the data storage requirement for becoming a miner small? A cryptocurrency could, for instance, only keep the last year of transactions, and everything older gets deleted. The discussion seems to imply that this is technically possible, but maybe not desirable because funds are lost if they are not retransferred within the time window. So my question is: does a blockchain need to have all blocks down to the genesis block to verify transactions, or can it's participants agree to just use the oldest blocks available?
Private blockchains like Monero can't be pruned based on what coins are spendable, because that data is not available and every coin is potentially spendable. So it would just grow forever until mining becomes centralized in a few data centers. And that makes it vulnerable to attack. In order to stay honest, a blockchain needs to be radically decentralized. Then hash wars would not be a weapons race between the super computers of fraudulent actors and the super computers of honest participants, but between the super computers of fraudulent actors and the combined computing power of the entire world. Mining should be on by default in every wallet, and every browser should mine (for you) while you're not using the CPU power for something else! (It does not have to waste energy, the mining could only be applied when there is a dispute, but it has to be available in case there is a dispute.) But for this to happen, these devices have to be full nodes. In other words the entire blockchain can only be a few dozen GB or so.
I'm thinking maybe this blockchain would only be for short-term transactions, and people would not have large amounts of money on it. The spending blockchain with only a year of storage could be really small and fast, while the long-term blockchain that stores things forever would not have that many transactions because people only transfer large sums now and them. It's doesn't have to be all in the same cryptocurrency/chain. Specialize it! People usually have their pension funds on the same bank account as their beer money either. So when you go to prison and can't renew your wallet, only a relatively small amount of money is lost. Or automatic devices could be built that retransfer your holdings before the time limit.) Or would that lead to loss of value in one of these currencies?

For public cryptocurrencies, deleting old blocks has the potential to cause long-time inactive users to lose their ledger, thus unable to spend when older blocks are deleted.
Therefore, it would not be technically possible to delete old blocks.


Weakness in Pohlig-Hellman algorithm Let's try to solve a discrete logarithm:

  $\beta \equiv \alpha ^{x} \bmod \,\, p$

using the Pohlig-Hellman algorithm. Let's suppose that $p-1=tq$, where $q$ is a large prime number. This means that the resolution is probable infeasible, however, if $t$ is factorizable with small prime numbers the algorithm
can determine the discrete logs $\bmod t$ in an efficient way.
But at this point, what i do with the discrete logs $\bmod t$?

I am also having trouble understanding this passage:

  Note that even if $p - 1 = tq$ has a large prime factor $q$, the algorithm can determine discrete logs mod $t$ if $t$ is composed of small prime factors.  For this reason, often $\beta$ is chosen to be a power of $\alpha^t$.  Then the discrete log is automatically $0$ mod $t$, so the discrete log hides only mod $q$ information, which the algorithm cannot find.  If the discrete log $x$ represents a secret (or better, $t$ times a secret), this means that an attacker does not obtain partial information by determining $x \bmod t$, since there is no information hidden this way.  This idea is used in the Digital Signature Algorithm, which we discuss in Chapter 9.

The point is that even though $p - 1 = tq$ may be large, the discrete log security of $(\mathbb Z/p\mathbb Z)^\times$ against Pohlig–Hellman depends on the size of $q$, not on the (possibly much larger) size of $p$ or $tq$.  If $q$ is the largest prime factor, then the cost of computing discrete logs modulo $p$ is essentially at most the cost of computing order-$q$ discrete logs in Pohlig–Hellman.  This is why, e.g., Schnorr groups are chosen to have an order with a large prime factor.


MAC using a modified CBC mode of operation I'd like to know whether the following modified CBC-MAC is secure (given a fixed IV).

Source: an old course on Network Security

Are there some obvious attacks I can't see?

This scheme is not worth the name MAC; it is horribly weak.

First and foremost, the tag/MAC is unchanged when two blocks of plaintext are exchanged (because of the commutativity and associativity of the $\oplus$ operation). If follows that from any message with at least two different blocks, we can make a different message for which we know the tag/MAC. This conclusively proves that this MAC is not secure, for any modern definition of security (which must include that a new message crafted by an adversary ignoring the key from other messages+MAC will pass verification with odds marginally above $2^{-n}$, where $n$ is the width of the MAC in bits).

Further, if we happen to know the tag/MAC of a message with two identical blocks, we can change these blocks to anything, and that will leave the MAC unchanged.

If the message length is allowed to vary, things get worse: the tag/MAC for the concatenation of messages is the XOR of the tag/MAC of the originals; and we can insert two identical blocks in a message leaving the tag/MAC unchanged.


Establish Trust By Signing Random Seed I'm trying to get my server to establish trust with a client.  Neither is on the Internet, so there are no certificate authorities.  The typical way to establish trust in my domain is for a client to "request a seed", the server provides a seed, and the client "provides a key", and the server "verifies the key".  (In case you are curious:  ISO 14229-1,  Unified Diagnostic Services)  There is no required way to generate either the seed or the key, or to verify it.

Assuming I can properly generate an RSA asymmetric key pair and distribute it, the server holds the public key (n, e) and the client holds the private key K.  Assume good cryptographic hashes, strong random number generators, appropriate retry timeouts to prevent replay attacks, etc.

Is the private key vulnerable in the following scheme?

Server provides the seed:  A random number M.
Client signs said seed (S = RSASSA-PKCS1-V1_5-SIGN(K,M))  and sends the signature to the server.
The server verifies that signature (RSASSA-PKCS1-V1_5-VERIFY ((n, e), M, S)).
If the signature could be verified with the public key, then the client can be trusted.

I'm worried about a known-plaintext attack:  I see the private key getting mixed into the signature, unlike with encryption where only the public key is mixed into the output.

If you can recover the private key from a message and a signature (and the public key), then that signature method is broken, and broken quite bad.

We believe that RSA, with a decent signature padding method, is secure, and hence the specific failure mode you mentioned cannot happen.

There are two obvious ways to try to recover the private key for RSA; we believe that both are infeasible.

In the first one, we have the padded value of M (note: RSASSA-PKCS1_V1_5 has deterministic padding, so we always know that Pad(M) looks like, and we have the signature S; we could try to find the value $d$ where $Pad(M)^d = S \pmod{N}$, d would be the private key.  However, this is a discrete log problem; we believe that is difficult

In the second one, we could try to factor the public modulus $N$; if we could, then we could compute $d = e^{-1} \pmod{lcm(p-1,q-1)}$, and that would be the private key.  However, we believe that factoring a number the size of N is difficult.

One thing that might be an issue is a man-in-the-middle; if there is something between the client and the server; the server sends M to the man-in-the-middle, who forwards it to the client; the client returns the signature to the man-in-the-middle, who forwards it to the server.  The server thinks it has authenticated the client, but if the man-in-the-middle can then send its own requests to server, it hasn't really.

It might be that the larger protocol has protections against this sort of thing; however that's what I would be worried about.


Why would someone want a 20ns block encryption completion on a 1us bus? I was reading the NIST 8114 draft and there's an example of a profile, Sample Profile #2, that shows that 20ns (50MHz) for a block completion for encryption on a CANBUS.  The bus is serial and maxes out at 1us (1MHz).   Is there some standard somewhere that specifies a 20ns completion time for a block cipher?  I cannot figure out, from a hardware standpoint, where that 20ns came from.

The authors of the NIST 8114 draft said that the times were arbitrary for the purpose of generating discussion.  They did, indeed, generate discussion.


Randomness in Public Key Encryption For a scheme to be at least CPA secure, one has to randomize the scheme. In case of a secret key encryption scheme, the used randomness will typically become part of the cipher text as in the case of an IV and is "public" (This is not a necessary requirement but how most algorithms work).

Now, if I switch to public key encryption schemes, the randomness will typically not be "public". The decryption algorithm simply removes it without necessarily really knowing it, like for example in the case of LWE or McEliece.

Now my question is: Is this a necessary requirement for public key encryption schemes that at least some of the randomness is not explicitly given as part of the cipher text?

Moreover, might it even be the case that all randomness that effects security has to be non-public? To be more precise, does all randomness that I cannot replace with a public constant value, without harming the security of the scheme have to be private.

(As a motivating example of randomness that can not effect security: I can always add randomness by first XORing the plaintext with a random bit string and adding this bit string to the cipher text but the scheme would be as secure as if I XORed the all zero string instead. Hence, this randomness could be omitted without harming the security.)

A public-key encryption algorithm cannot rely exclusively on "public" randomness.  The reason comes down to the fact that encryption is a public algorithm that can be run by anyone. If the algorithm's output included all the random coins that it used, then an adversary could determine the message from the ciphertext, by running the encryption algorithm with the (given) coins and each of the two candidate messages from the IND-CPA experiment. The true message (and only that message) would yield the target ciphertext.

In some cryptosystems, the decryption algorithm recovers all of the encryption randomness. Examples include encryption schemes based on injective trapdoor functions like RSA. There's no contradiction with security here because one needs the secret key to recover the randomness.

For your second question, we can't go so far as to say that all publicly recoverable randomness is non-security influencing, i.e., replaceable by a fixed public constant (which is the contrapositive of your question).  For example, consider a PRG that uses some random public parameter along with a secret random seed (e.g., an LWE-based PRG).  Now consider an encryption algorithm that chooses both a public parameter and a seed for the generator, to produce a pseudorandom string for the "real" encryption, and outputs the parameter as part of the ciphertext. This would be secure, but might not be if we fixed the public parameter to be, say, all zeros.


Brute force against computational security One-time pad is secure under brute force with respect to either of the definitions
\begin{align}
\Pr[M = m] &= \Pr[M = m | C = c]\\
\Pr[C = c | M = m_0] &= \Pr[C = c | M = m_1]
\end{align}

basically because the key and message spaces are the same, and $\oplus$ is closed under these spaces.

Given the argument above, I don't understand precisely how computationally secure schemes are compromised under brute force. In particular, how would any of the two equations above be violated given the scheme $$\mathsf{Enc}(m, k) = m \oplus G(k),$$ where $G$ is a pseudorandom generator.

For a (fixed-length) cipher to meet your first condition, it needs to be the case that it's no easier to guess the plaintext if you have the ciphertext than it is to guess the plaintext without the ciphertext. Now, suppose I send a random 1024-bit string XORed with $G(k)$ for some 128-bit $k$ and computationally secure $G$. The probability that my message is $0\ldots0$ is exactly $2^{-1024}$. I encrypt my message with a 128-bit key selected uniformly at random from the space of 128-bit keys to get $c$. Now suppose you intercept $c$. You know it's encrypted with some key $k$; you know there are $2^{128}$ such keys. That means that there are only $2^{128}$ possible decryptions -- at most 1 per key. This is why the keyspace of a perfectly secure scheme must be at least as big as the message space: knowing the ciphertext means that the number of possible messages is reduced to the number of possible keys, and if there are fewer keys than messages we've eliminated a lot of messages. That means that knowing "this ciphertext can decrypt to $m$" tells us that it's much more likely to be $m$ than we had suspected beforehand.

If $K=k$, then $M=c\oplus G(k)$. So, $$\Pr[M=c \oplus G(k)|C=c] \ge \Pr[K=k]=2^{-128}\ne 2^{-1024}$$ for any $k$. Suppose, for instance, that you try $k=1\ldots1$ and find that $c\oplus G(k)=0\ldots0$. You now know that $$\Pr[M=0\ldots0|C=c]\ge\Pr[K=1\ldots1]=2^{-128}\ne 2^{-1024}=\Pr[M=0\ldots0]$$ after a very quick computation (just one evaluation of $G$). That means that even with a computationally secure cipher, given $c$ an attacker can easily find a message $m$ such that $\Pr[M=m|C=c]\ge 2^{|k|}$ -- specifically, $\mathsf{Dec}(c,0...0)$. And that violates $\Pr[M=m|C=c]=\Pr[M=m]$ in a single evaluation of $\mathsf{Dec}$.


Is the keystream transmitted with the ciphertext when a stream cipher is used? When a stream cipher is used and a keystream is generated to be XOR'ed with the plaintext, is the keystream sent with the ciphertext so that the receiver knows how to decrypt it? Or does the receiver(s) need to already know the keystream?

Absolute noobie to cryptography.

The keystream is as long as the message, so you don't want to send that to the receiver. The keystream is generated by a much shorter key (e.g., 128-bit private key). That is what the receiver needs in order to decrypt the message.

So, how do you get that to the receiver? Well, clearly you can't just send it in the clear or anyone watching the channel would have the key and could decrypt. Typically what we do in cryptography is run a key establishment protocol. This could be as simple as Alice and Bob meet up and exchange the key on a written piece of paper or as complex as using asymmetric crypto, with public/private key pairs, certification authorities, etc.


PBEWithMD5AndDES Cipher does not check for integrity first? I am running FindBugs with findsecbugs plugin to scan java code for security issues. I am getting "Cipher With No Integrity" error for a Cipher function implemented with "PBEWithMD5AndDES". The legend says "The ciphertext produced is susceptible to alteration by an adversary. This mean that the cipher provides no way to detect that the data has been tampered with. If the ciphertext can be controlled by an attacker, it could be altered without detection."

For the solution it suggests to "Use a cipher that includes a Hash based Message Authentication Code (HMAC) to sign the data. Combining a HMAC function to the existing cipher is prone to error. Specifically, it is always recommended that you be able to verify the HMAC first, and only if the data is unmodified, do you then perform any cryptographic functions on the data." Examples at http://find-sec-bugs.github.io/bugs.htm#CIPHER_INTEGRITY

My statement is like below

Cipher engine = Cipher.getInstance("PBEWithMD5AndDES");

Doesn't the "PBEWithMD5AndDES" option verify the HMAC first? Or should I use other cipher option like "AES/GCM/NoPadding" as suggested?

Password-based encryption uses a hash function to derive a key from a password and that is the only use of a hash function. PBEWithMD5AndDES itself doesn't provide any authentication (includes integrity) and only uses MD5 for key derivation.

If you want authentication, then you can still use PBEWithMD5AndDES, but you then would have to derive a MAC key from the password yourself and generate an authentication tag by running HMAC(ciphertext, macKey).

But it is not recommended to use DES or even MD5 nowadays, so you should change the encryption scheme nevertheless. If you do, then you can exchange it with AES-GCM which already provides authentication. You still would need to derive a key from a password that you provide. There are many key-derivation functions, but Java provides PBKDF2 in the standard library. Alternatives are scrypt, bcrypt and Argon2.


Using checksum instead of hash for authenticating ciphers Lets assume for a specific situation we cannot use authenticated encryption like GCM ...

If we were to use CTR, what would you think of using a checksum on the plaintext then encrypt the whole.

The reason I don't want to use a hash is because the checksum is already presented in the plaintext protocol, and the reason I don't want to use standard authenticated ciphers is because of the extra hash size, even though it is just 16 bytes.

Thanks in advance.

If we were to use CTR, what would you think of using a checksum on
  plain text then encrypt whole.

That's a really bad idea (from a security perspective).
Here are the reasons for this:

Depending on your checksum, there are immediate obvious attacks on the authenticity of messages. If your checksum is CRC for example then it is linear. This means that an attacker can just compute some $\Delta$ he wants to insert into the message and also computes $\operatorname{CRC}(\Delta)$ and he can just XOR this into your message and it will be accepted as a valid message, because $\operatorname{CRC}(P)\oplus\operatorname{CRC}(\Delta)=\operatorname{CRC}(P\oplus \Delta)$. This attack was already known to be
applicable to WEP.
A checksum is less "hardened" than a hash. A checksum doesn't even want to be a cryptographic hash and doesn't want to resist targeted attacks. They may thus expose linear behavior (see above) or other weaknesses which may allow for forgeries. Also see "Are checksums essentially non-secure versions of cryptographic hashes?" on this matter.
Hash-then-Encrypt is a bad idea as a composition. As you've already seen above Hash-then-Encrypt can be vulnerable if your "hash" is linear. However even if it is non-linear and the attacker can take a good guess at the message's contents, he can still compute $H(\text{oldMessage})\oplus H(\text{newMessage})$ and XOR that into your keystream (along with $\text{oldMessage}\oplus \text{newMessage}$) and he has easily achieved a message forgery. Also see "Why is plain-hash-then-encrypt not a secure MAC?" on this subject.
Authenticating and then encrypting is also highly discouraged. Even if your "hash" was an actual MAC, using it first on the message and then encrypting the result is less desirable. There are generic security proofs that assure that Encrypt-Then-MAC is secure and don't give the same guarantees for MAC-Then-Encrypt, so using the latter is discouraged. Also see Prof. Lindell's answer on the question "Should we MAC-then-encrypt or encrypt-then-MAC?".

OK, as asked for in the comments, let's dive a little into the attack I outlined in the first bullet point.
Let's call the ciphertext $C$, the (unknown) message $P$ and the (unknown) keystream $K$, which is internally used by the CTR mode. As you're using a stream cipher $C=M\oplus K$ (with $\oplus$ denoting bitwise XOR) is the encryption function. Note that for all choices of $A$ and $B$ you can come up with a $C$ such that $A=B\oplus C$. Now in the first step we manipulate the message $M$. So we first calculate the difference we want to see appear after decryption, let's call it $\delta$. Now we intercept $C$ and send $C'=C\oplus \delta$ onwards. Note how $C'\oplus K=M\oplus\delta$ will yield the manipulated message upon decryption. So now we split $M$ into the concatenation of the plaintext $P$ and its checksum $\operatorname{CRC}(P)$ as $P\parallel\operatorname{CRC}(P)$. Now also split $\delta=\Delta\parallel\operatorname{CRC}(\Delta)$. Now you see that you'll get $P\oplus\Delta$ upon decryption as the plaintext and $\operatorname{CRC}(P)\oplus\operatorname{CRC}(\Delta)$ as the checksum. Now as CRC is linear $\operatorname{CRC}(P)\oplus\operatorname{CRC}(\Delta)=\operatorname{CRC}(P\oplus\Delta)$ which is the valid checksum for the forged message.


Different ways for modular exponentiation $A^E$ with negative A's I was looking at a way for modular exponentiation $X=A^e \mod{n}$ with negative base $A$ in order to evaluate how it needs to be changed so I can use it with my hardware acceleration unit.

The crypto library I was looking at deals with negative base $A$ (MPI) as follows:

Check if A was negative and if it was, remember that it was negative and invert its sign (e.g. -5 --> 5)
Perform the actual modular exponentiation using a specific algorithm (e.g. sliding window method) with the positively signed $A$
If $A$ was positive at the beginning, you're done
If $A$ was negative at the beginning and the exponent $e$ was odd compensate by performing $ X = n-X$

This library can work with arbitrarily large (or small) values of $A$. However my crypto core which accelerates moudular exponentiation expects the input parameters $e$ and $A \in [0 \dots n-1]$ which is why I came up with following solution:

At the beginning always perform $A = A \mod{n}$. This would reduce $A$ if $A \ge n$. In case $A \lt 0$ this would make $A$'s sign positive.
Perform the actual modular exponentiation using a specific algorithm (e.g. sliding window method) with the positively signed $A$

I think that performing the reduction at the beginning to reduce A and make its sign positive should not change the final result as $A^e \mod{n} = (A \mod{n})^e \mod{n}$. However I wanted to make sure, that I did not forget anything.

For any integer $A$ we have the congruence $A \equiv A + kn \text{ mod } n$ for all integers k. This means a generic algorithm to get $A$ (where $A < 0$) into the range $[0, n)$ would be something like:

function(A):
    while(A < 0):
        A = A + n
    return A

Doing A = A % n will work in some languages as well (e.g. python) but not all languages (e.g. C).


Is predictable ciphertext/plaintext bad? I have a cryptosystem that I'm using for secure chat.

It is using AES 256 (with RSA 2048 for key exchange).

Would a predictable, and repetitively sent ciphertext plaintext compromise the cryptosystem?

For example, if Eve knows that the string "Username: testuser" is sent with each message (making it predictable), would that compromise the system?

Or something like an "html" tag at the very beginning?

Yes, if your ciphertext is repetitive, that's bad.

We can't really say how bad, since you haven't told us enough about your cryptosystem.  It could be because you're using AES in ECB mode, which is kind of bad.  Or it could be e.g. because you're using AES in CTR mode with a fixed IV, which would be worse.  Or, in principle, you might be using a deterministic authenticated encryption mode like SIV without a nonce, which would be almost OK (although, for a chat application, even the minimal information leakage of nonce-less SIV would seem undesirable).

But, in any case, a modern semantically secure encryption scheme should never produce repetitive ciphertext, not even if the plaintext repeats.  If yours does, it's a sign that you're using AES wrong somehow.

As a corollary, as long as the encryption method you're using is resistant to chosen-plaintext attacks (which turns out to be equivalent to semantic security), it does not matter what the plaintext is or how many times it's repeated, not even if the attacker gets to choose the plaintext.

Most standard AES modes of operation (with the exception of ECB) are provably secure against chosen-plaintext attacks, as long as the AES block cipher itself is not broken and as long as they're used correctly — i.e. the IV / nonce is chosen appropriately for the mode, and never reused, and the maximum amount of data encrypted with a single key is not exceeded (not that a typical chat application is likely to come anywhere close to doing that).

(However, if an attacker can intercept and manipulate the encrypted messages (and/or inject their own fake messages into the communication), they may be able to modify the messages in transit and to carry out chosen-ciphertext attacks, which the classical non-authenticated modes of operation like CBC, CFB, OFB and CTR are not resistant to.  To protect yourself against such attacks, you either need to combine them with a message authentication code, or use an authenticated encryption mode that, in effect, has the encryption  and authentication parts combined into a single standardized bundle.)


Link and end-to-end encryption What are the advantages of using end-to-end and link encryption together? In which situation we can use both?
If I understand correctly.
In link encryption, all data are encrypted, including headers, addresses, and routing information. So at each router it is decrypted to see the details and encrypted again and forwarded to next hop. Right?
In end-to-end encryption, Headers, addresses, and routing information are not encrypted, and therefore not protected.
So when we use both together at the end using link encryption all the data would be encrypted.

Link encryption isn't really a cryptographic concept, it's more a kind of networking protocol.

Link encryption protects the message only "on the wire" between routers. Looking at the OSI model, that would be on layer 2. And yes, it therefore is applied on all things regarding routing.

However, if you look at the Wikipedia article about link encryption, they list two advantages:

  encryption is automatic so there is less opportunity for human error.
  if the communications link operates continuously and carries an unvarying level of traffic, link encryption defeats traffic analysis.

And that's just nonsense.

Link encryption is useful in some scenarios, for example if you have to worry about wiretapping and you trust the routers. This does make sense, for example in a military communication network, or some other organization where routing stations are part of it. Additionally, you need some way to know or agree on cryptographic keys, and having a key exchange for every "layer 2"-package would be a performance nightmare.

However, if you don't trust the routers, then link encryption just adds extra effort for encryption and decryption and no benefit at all. If you consider something like man-in-the-middle attacks, then those attackers actually are usually routers (or can act as one). And in fact, you need to give routers the routing information (including adresses of senders and receivers) so that they can do their job.

So if you're thinking about Internet traffic, this doesn't make any sense, and it doesn't increase security. However, you could consider the wireless networking protocols (e.g. WPA2, UMTS, ...) as link encryption on that insecure communication channel, which is easy to monitor.

Other than that, I don't think the concept offers much more, and it really depends on the level of trust and the situation. I don't see any benefit in having link encryption between all routers - if you don't control the routers yourself.


Zero-knowledge voting with hidden weights Assume a voting with delegates, where each delegate's vote $v_i \in \{-1,1\}$ has a certain weight $w_i$ depending on the number of people who elected the delegate.

Is there a way to calculate the sum of votes $\sum_{i} v_i w_i$ without revealing $w_i$?

One approach might be the usage of a homomorphic cryptosystem like the Paillier cryptosystem, while the specific protocol properties depend on your use case.

For more detailed description of Paillier system,
 I refer to https://de.wikipedia.org/wiki/Paillier-Kryptosystem and limit my answer to a possible protocol application to achieve your goal.

Due to the homomorphic properties of the Paillier system, we are able to:

Add different plaintext by multiple their ciphertexts
$Dec_k(Enc_k(m_1,r_1) \cdot Enc_k(m_2, r_2))= m_1+m_2 \mod n$
Multiply an encrypted plaintext by raising the ciphertext to $k$:
$Dec_k(Enc_k(m_1,r_1)^k) = k \cdot m_1 \mod n$

As an example let us assume the following setup:

Common party $C_1$ knows all weights $w_i$ and calculates the result $\lambda=\sum_i v_i w_i$ without knowing the delegates votes
Common party $C_2$ generates the private and public keys for the Paillier encryption.
Each delegate shares an encrypted and authenticated channel with each common party.

In the interests of simplification, I neglect the method, how to achieve this secure channel. You can use a protocol for authenticated key exchange and an and for transport security of your choice to achieve the confidentiality and integrity of the messages.

Now we can define the protocol as follows:

$C_2$ generates one key pair for this election and sends the public key to all delegates.

$ C_2\xrightarrow{k_{pub}}Delegate_i$

$D_i$ Encrypts its vote with the public key and send it to $C_1$. Since $C_1$ does not know the secret key, it gains no knowledge over the delegates vote.

$ D_i\xrightarrow{\overline{v_i}=Enc_{k_{pub}}(v_i)}C_1$

$C_1$ can weight each vote by raise the encrypted vote to the power of $w_i$ and calculate the election result $\lambda$:

3.1 $Enc_{k_{pub}}(w_i \cdot v_i) ={\overline{v_i}}^{w_i}$ (2. homomorphic property mentioned above)

3.2 $\overline{\lambda}=\prod_{i} {\overline{v_i}}^{w_i} = \prod_i Enc_{k_{pub}}(w_i \cdot v_i) = Enc_{k_{pub}}(\sum_i w_i \cdot v_i)$ (1. homomorphic property mentioned above)

$C_1$ send the result to $C_2$

$ C_1\xrightarrow{\overline{\lambda}}C_2$

$C_2$ can decrypt it and publish the election result:

$\lambda = Dec_{k_{priv}}(\overline{\lambda})$

This approach is a common application of shared knowledge: The common party $C_1$ knows the weights and can compute the result without knowing the votes, while all other parties have no knowledge over the weights. There are, of course, many other ways to achieve your goal, e.g. encrypt the weights and raise them by the delegates vote, but I hope, the concept has become clear.


Pseudorandom number generation predictability Can you expect with certainty that any pseudo-random number generator will produce the same stream with a shared seed?

Take (hypothetical) seeded deterministic PRNG algorithm Gen1. If you use Gen1 to produce a stream, and I use Gen1 with the same seed, I will get an identical stream. As per Wikipedia's definition, a PRNG is deterministic.

Now consider another hypothetical seeded deterministic PRNG Gen2, which uses a different algorithm than Gen1. If I use Gen2 with the same seed as before, there is no reason to expect the same stream to result.


Is this distributed random oracle scheme safe? This question comes from an issue raised in another question: Non interactive threshold signature without bilinear pairing (is it possible)?

Is the proposed random oracle model safe when trying to output a distinct and random $m \times G = M$ value?

Doing the interpolation for $t$ compromised shares $m^{'}_i$ results in: $l_0 \times M_0 + \sum^t_{i=1} l_i \cdot m^{'}_i \times G = m \times G$ that reduces to $(m - \sum^{t}_{i=1} l_i \cdot m^{'}_i) \cdot l^{-1}_0 \times G = M_0$, where $M_0$ is always different for each signature. So, I suppose we can't reuse previous values to perform the attack.

How do you solve to a wanted $m$ value without resolving the DLP? Searching for $m^{'}_i$ and $m$ for some unknown $m_0$ is brute forcing the DLP, even in the k-sums context!

What I have seen in the k-sums/generalized birthday problem is a way to solve for $x_1 \oplus ... \oplus x_n = 0$. Mapping this approach to our problem, we should try to solve for $x_1 \oplus ... \oplus x_n = m_0$ equivalent to $x_1 \oplus ... \oplus x_n \oplus m_0 = 0$. The issue is, $m_0$ has a specific value but it is unknown to the solver due to DLP. How can we solve for something we don't know? If such solution were possible, won't this be solving the DLP?

I need a math clarification to explain exactly how this attack is performed?

Edited1: Expanded math proof:
Trying to follow @Aman Grewal logic, lets try to attack in a k-sum scenario.

All variables marked in the form $c^*$ are controlled by the attacker. The attacker's objective is to sign a random $B^*$ for a submitted $B$ such that $B^* \neq B$. The attacker has access to $M_0$ and $c=H(Y||M||B)$ for this or any previous messages. Assume the attacker has knowledge of $t$ shares of $y_i$.

We remove the Lagrange coefficients $l_i$ from the math, since they are public and doesn't affect the final proof. For a single signature we have:

For a set of randomly selected $m_i^* \times G = M_i^*$ one can derive $\sum_{i=1}^t M_i^* + M_0 = M^*$
Then $c^* = H(Y||M^*||B^*)$ and the output of a single signature is $(m_0 + c \cdot y_0) + \sum_{i=1}^t (m_i^* + c_i^* \cdot y_i) = m^* + c^* \cdot y$. Assuming $m_0 + \sum_{i=1}^t m_i^* = m^*$ and $c + \sum_{i=1}^t c_i^* = c^*$ (this last one is not totaly correct, since we removed the Lagrange coefficients, but this is even easier to attack)

One cannot solve for $c_i^*$ in $\sum_{i=1}^t (m_i^* + c_i^* \cdot y_i) = (m^* + c^* \cdot y) - (m_0 + c \cdot y_0)$. Even assuming that $m^*$ is equal to some previous result and that $c^*$ is directly dependent on $c_i^*$. There are $t + 3$ unknowns corresponding to $(c_i^*, y_0, y, m_0)$. So... lets expand it to $j$ signatures:

The real equation we need to solve is:
$\sum_{j=1}^n \sum_{i=1}^t (m_{ij}^* + c_{ij}^* \cdot y_i) = \sum_{j=1}^n [(m_j^* + c_j^* \cdot y) - (m_{0j} + c_j \cdot y_0)]$

Assuming somehow you can have a lot of equalities in this system of equations between signatures $j$, you are still left with $(t + 2) + j$ unknowns for $(c_i^*, y_0, y, m_{0j})$. For every new equation, you have a new unknown $m_{0j}$ that you can't catch up. $m_{0j}$ is distinct for every new signature by the definition of the threat model.

Edited2: Eq public version:
The public version of the equation is:
$\sum_{j=1}^n \sum_{i=1}^t (M_{ij}^* + c_{ij}^* \cdot Y_i) = \sum_{j=1}^n [(M_j^* + c_j^* \cdot Y) - (M_{0j} + c_j \cdot Y_0)]$

In this case there are only the $c_{ij}^*$ unknowns, but we have the DLP. If there is an efficient way to solve this, are we breaking the DLP?

If any one can contest this math logic to come up with a successful attack, I will accept your answer.

Attackers can choose their $M_0, m_0$ pair without solving DLP.

In particular, they generate multiple lists of $M, m$ pairs and try to solve for $l_1 \cdot M_1 + l_2 \cdot M_2 + ... + l_n \cdot M_n = M_0$.

In order to solve this, they no longer have $m_i$ for some $i$. The k-sums algorithm is effectively solving $l_1 \cdot M_1 + l_2 \cdot M_2 + ... + l_n \cdot (M_n - M_0) = 0$.

In this way, they can choose the final value ($M_0$), but are unable to recover anyone else's private values (an $m_i$ that the attacker doesn't own).

This shouldn't an issue for signatures (when computing the nonce) because the signature can never be computed without all the $m_i$. But it won't be secure for other applications.

However, there's another attack, presented in section 4 of https://eprint.iacr.org/2018/417.pdf. This attack relies on multiple parallel signature operations. Note that this attack still works with different messages even though it is only presented with the same message.

Suppose that $i$ indexes the participants and $j$ indexes the messages so that $M_j$ refers to the nonce of the jth message and $M_{ji}$ refers to ith participant's public value used to interpolate for $M_j$. In this attack, the attacker is searching for $M_{ji}$ and $a$ such that $a \cdot \Sigma H(Y||M_j||B) = H(Y||M||B^*)$, where $B^*$ is the message they want to sign.

The generalized birthday attack provides a somewhat efficient way to solve for these $j+1$ unknowns. For example, with a 256-bit hash and 127 parallel signatures, the equation can be solved in $O(2^{47})$, which is significantly less than the complexity of breaking the hash or solving the discrete log.


TDES (Triple DES) DUKPT decryption We have a POS (Ingenico) that uses DES3-CBC encryption using a derived key.
It sends encrypted data, and 10 bytes size Key Serial Number (KSN). I tried to use CKM_DES3_CBC_ENCRYPT_DATA to derive the key, and decrypted the data using DES3-CBC mech. However, I get some gibberish data something like this:

\ufffd\u001dl\ufffdP\ufffdl\ufffd\ufffd\ufffd+\ufffd\ufffd[\ufffd\ufffdl\u0017\ufffd\ufffd\ufffd\u001f?E\ufffd[*\ufffdmd\u0014\u0009ay\ufffd\ufffd3\ufffd\ufffd

I am not sure if I am using correct mechanism to derive the key, or even using the correct mechanism to decrypt the data.

Can someone please help me understand what could have been wrong? Some info says I need to pad the KSN.

Edit: I asked a similar question on Github/PKCS

I solved the problem.
So for people who are hunting for the answer, you need to consider what mechs your HSM supports.
Every logic I had in the code was correct. The only problem was the mechanism that I used to derive the key was wrong. There are several mechs that are available to derive the key with, which was the hard part to figure out since it did not specify. I started with CKM_DES3_CBC_ENCRYPT_DATA as stated in the question, but turns out, I had to use CKM_DES2_DUKPT_DATA. And this mech was not defined in any wrapper libraries such as c# interlop pkcs11 library or the one I use, golang. Because this is a vendor defined mechanisms, I had to define it myself, and use it accordingly.

I hope this helps anyone in the future!


What is the definition of "security beyond the birthday paradox"? I'm reading a paper about MACs and I would like to be sure about the meaning of a security beyond the birthday paradox.

Is there a definition?

For a MAC algorithm considered to be good, the best way to attack a MAC should be by collision (a birthday attack)

This means, that for MACs with $n$ bit tags an adversary will suceed with a forgery after having issued $q=O(2^{n/2})$ tag queries.

In the literature this bound is called the birthday barrier.

Now, if you are able to come up with a MAC construction for which you can prove that an adversary will require more queries, say $q=O(2^{2n/3})$ or $q=O(2^{5n/6})$ as for instance shown here, as given by the birthday bound, your MAC provides security beyond the birthday paradox.


Would finding a Merkle-Damgård preimage that doesn't change the initial state allow an attacker to prepend it to any hashed message? Suppose, a message M was found so that MD5(M) = S, where S is the initial state of the MD5 function (0x01234567, ...).

Given a hash MD5(m), would this allow computing MD5(M∥m∥padding), where padding is an empty block to get the length right?

Not quite. But it would allow computing ${\rm MD5}(M \,\|\, {\rm pad}_M \,\|\, m \,\|\, {\rm pad}_m \,\|\, {\rm whatever})$, where ${\rm pad}_M$ and ${\rm pad}_m$ are the extra length padding bytes appended to $M$ and $m$ respectively by the MD5 algorithm, as described in RFC 1321 sections 3.1 and 3.2.

To see why, it's worth looking at how the MD5 hash (like other similar hash functions based on the Merkle–Damgård construction) works.  Specifically, MD5 consists of a compression function $f: \{0,1\}^n \times \{0,1\}^b \to \{0,1\}^n$ (where, for MD5, $n = 128$ and $b = 512$), a fixed $n$-bit initial state vector $IV \in \{0,1\}^n$ and a padding scheme for extending an arbitrary input string to a multiple of $b$ bits (and also encoding its length into the padding).

For our purposes, it turns out to be useful to also define the iterated compression function $f^*$ that takes an $n$-bit IV $s_0$ and a sequence of $b$-bit input blocks $(m_1, m_2, m_3, \dots, m_k)$ as input, and returns the $n$-bit output $s_k$, where $s_i = f(s_{i-1}, m_i)$ for $1 \le i \le k$.  Then, for any given input message $m$, we have $${\rm MD5}(m) = f^*(IV, m \,\|\, {\rm pad}_m).$$

In particular, the usual MD5 length extension attack lets us, given $H_m = {\rm MD5}(m)$ and the length of some unknown message $m$, compute ${\rm MD5}(m \,\|\, {\rm pad}_m \,\|\, x)$ for any arbitrary suffix $x$ as $f^*(H_m, x \,\|\, {\rm pad}'_x)$, where the modified padding ${\rm pad}'_x$ is the same as the normal MD5 padding for the message $x$, except that the input length encoded in the padding is increased by the length of the prefix $m \,\|\, {\rm pad}_m$.

Now, in your scenario, we have a special message $M$ such that $${\rm MD5}(M) = f^*(IV, M \,\|\, {\rm pad}_M) = IV.$$  Thus, by the construction of the iterated compression function $f^*$, we also know that $$f^*(IV, M \,\|\, {\rm pad}_M \,\|\, m \,\|\, {\rm pad}_m) = f^*(IV, m \,\|\, {\rm pad}_m) = {\rm MD5}(m).$$

Thus, given ${\rm MD5}(m)$ and the lengths of $M$ and $m$, we can compute ${\rm MD5}(M \,\|\, {\rm pad}_M \,\|\, m \,\|\, {\rm pad}_m \,\|\, x)$ as $f^*({\rm MD5}(m), x \,\|\, {\rm pad}''_x)$, where the modified padding ${\rm pad}''_x$ now encodes the combined length of $M$, ${\rm pad}_M$, $m$, ${\rm pad}_m$ and $x$.