What challenge should I use in a challenge-response proof-of-work? In order to guard against denial-of-service attacks, I want to require clients to do some work (more work than the server does fulfilling the request) before talking to them.

Client connects
Server sends a challenge, including a piece of data

"Find bytes x such that hash(challengeData + x) has n zeros at the beginning"
Client finds x, sends it to the server
Server verifies that hash(challengeData + recv()) has n zeros at the beginning
The actual request is handled

I found a few different methods to generate this "challengeData" thing, and some problems with each of them:

Random bytes

Here, the client can just exhaust the server's PRNG by repeatedly connecting to it. Which brings us back to square one (denial of service).
Current time of day

This seems like a good idea to me, but I'd like to know what attacks you could have against it.
A string involving something dependent on this particular request (like hashcash)

In order to make sure evil connections are dropped as soon as possible, I'd like to avoid handing anything about the request before making sure the client has done some work. The idea is that the client should always do much more work than the server before it starts handling the request.

I have some constraints: firstly I'd like the server to be completely stateless. I don't want to save "hashcash" and make sure it isn't spent twice, instead I want to challenge the client to do work that, inherently, can't be pre-computed. Secondly I don't want to know anything about the request itself at this stage (such as authentication). This is so the server sends and recieves as little data as possible. For instance, the current time (nanosecond or millisecond precision, depending on the OS, hardware and implementation) is 8 bytes (a double), and 2^64-1 tries (i.e. an 8-byte response) should be more than enough before resetting the connection (for the foreseeable future).

In short:

What properties does this challenge need to have?
What easily generated data has all of these properties? Is the current time any good?

As usual when I ask something about protocol-design, this may well be reinventing the wheel. If there are any existing protocols that do this, I don't know about them yet.

A good PRNG can't be exhausted, so your argument against random bytes doesn't matter.

  firstly I'd like the server to be completely stateless.

Sounds impossible to me.

a PRNG needs state. A clock needs state.
An open connection is state too
You probably want to store open challenges too. This part isn't strictly necessary, but very convenient.

You might also want to include something unique to the server in the challenge(for example its domain or IP address) so clients can't be tricked by one server into solving the challenge for another.

I'd go with the server sending 16 random bytes as challenge, and the client responding with something like ServerIP || HMAC(proof, Challenge || ServerID)


Rotating password with PBKDF2 Crypto is hard. Thank you for helping me learn.

My encryption scheme currently looks like this:

Salt is stored out in the open
Secret is the user's password, known only to them
EncKey||AuthKey = PBKDF2(Secret, Salt, n) where n = lots
My encrypted payload consists of IV||Ciphertext||HMAC

IV = secure random bytes, unique to each payload
Ciphertext = AES-256 CBC(EncKey, IV, Plaintext)
HMAC = HMAC-SHA1(AuthKey, IV||Ciphertext)

Now, I want to change Secret.  As it stands, this will make all of my already encrypted data unreadable.  So, I want to keep the same EncKey.

Will the following be a secure scheme?

EncKey||AuthKey = secure random bytes, chosen once ever
PwdEncKey||PwdAuthKey = PBKDF2(Secret, Salt, n)
EncKey and AuthKey are encrypted as above, but using the PwdEncKey and PwdAuthKey
Everything else is encrypted and signed with EncKey and AuthKey

To rotate my password, I can then decrypt the payload which has EncKey and AuthKey (which now never change) and re-encrypt it with the newly derived PwdEncKey and PwdAuthKey.

Does it weaken my security having EncKey and AuthKey stored in an encrypted blob alongside the data which they are encrypting?  Is there a smarter way to do this?

No, wrapping the data key set seems a good idea to me. It's pretty standard and should even work with e.g. hardware modules.

Note that your old ciphertext would still rely on the security of your old secret (password) when you choose this scheme! If $Enckey$ is ever guessed it can be confirmed by decrypting (the first part of) your ciphertext.

There is a more efficient way: you can simply calculate the difference on bit level using XOR between the keys calculated from your old and new secret. Then store that difference with the ciphertext. So retrieve the old key simply XOR with your newly created key to retrieve the older key.

This is more efficient CPU-wise and may require fewer bits (if CBC padding is used). I'd still go for your current scheme though. The XOR method is less flexible and will expose your new master key if any of the data keys is ever leaked.

Notes:

I would not request too much output from PBKDF2, rather use another KBKDF such as HKDF to split off multiple keys from the derived key;
PBKDF2 requires an iteration count (work factor) as configuration parameter, which seems to be missing;
HMAC can be configured to use SHA-1, but it isn't SHA-1 and SHA-1 doesn't take two input parameters;
you could consider using SIV to encrypt your keys, in that case you don't need a second authentication key or IV;
you might consider storing a random salt with the ciphertext;
a fully random data key set for each separate encryption is more secure;
addition 1: if you do not use an IV when encrypting the keys then it is easy to spot which ciphertext was encrypted with the old keys.


Derive cipher IV and cipher Key using PBKDF2 with random salt? It is said that cipher IV does not have to be secret and the only secret component of the encryption scheme should be a cipher key.

Question: is it safe to generate IV using PBKDF2 function, which takes password and randomly generated salt as input (Scheme 2)? Or do I have to use only completely random IV which has no relationship to password whatsoever (Scheme 1)? In other words, is Scheme 2 less secure, equally secure or more secure than Scheme 1?

NOTE: To generate entropy based on password/salt I use a hybrid PBKDF2/HKDF approach described here, where PBKDF2 generates PRK which has the same length as used hash function (SHA-2) and then expands PRK to obtain sufficient entropy to populate KEY (Scheme 1) or IV + KEY (Scheme 2).

Example of Encryption Scheme 1 - traditional approach:

Input data: Password and Message (e.g. plaintext to encrypt).
Generate completely random SALT (using system entropy provider).
Generate completely random IV (using system entropy provider).
Use Password and SALT as input for PBKDF2/HKDF function, which generates and expands entropy based on input data.
Use obtained entropy to set cipher KEY, use IV that was generated in step 3.
Encrypt Message, send SALT + IV + cipher text to the receiver.

Example of Encryption Scheme 2 - generating IV with PBKDF2:

Input data: Password and Message (e.g. plaintext to encrypt)
Generate completely random SALT (using system entropy provider).
Use Password and SALT as input for PBKDF2/HKDF function, which generates and expands entropy based on input data.
Use obtained entropy to set cipher IV and KEY.
Encrypt Message, send SALT + cipher text to the receiver.

For decrypting, we use received SALT (and possibly, IV - if Scheme 2 is used), setup cipher according to the used scheme and decrypt message.

So, is Scheme 2 less secure, equally secure or more secure than Scheme 1? In my opinion, it should not be less secure, since for every message SALT, IV and KEY are going to be completely different. Besides, IV is unpredictable, since to generate it, we use SALT - which is unpredictable, since it is considered to be completely random. It is probably more secure, since in Scheme 1, SALT and IV are known to an attacker, and in Scheme 2 an attacker knows only SALT. Even if it is said that IV does not have to be secret, is it not better to try to reveal to an attacker as little information as possible?

Can Scheme 2 help an attacker to determine password more easily than in Scheme 1?

It is secure. The IV only needs to be indistinguishable from random to an attacker, and it is as long as the salt is random.

There is one remark: if you extract more key + iv bytes than the hash function in PBKDF2 returns then the PBKDF2 function is executed twice. An attacker however only has to find the key, not the IV, so an attacker doesn't have to do this, halving the security provided by the number of iterations.

You could use a KBKDF (Key Based Key Derivation Function) rather than direct extraction to get the key and IV. So you would have:

S = PBKDF2(salt, password, iterations)
K = KBKDF(S, 'enc')
IV = KBKDF(S, 'iv')

A good KBKDF is HKDF-expand.


Is there a way to compress multiple signatures of the same data? So, I'm working with a system that allows individual users to each have their own private-public key pair.

I would like to allow multiple users to use their private key to sign the same piece of information to confirm they agree with something.  By signature, I mean the public key can be used to check the signature is valid.

However, space is at a premium.  So is there a way to compress those multiple signatures of the same data?

Using Curve25519, but other algorithms might be acceptable.

You can use multi-signatures.

One example is the BN06 scheme described in the paper:
Bellare, Neven - Multi-signatures in the plain public-Key model and a general forking lemma


Huffman encoding of hashes I have a huge list of MD5 hashes, which takes up quite some space. I wonder whether I would achieve (some) compression by encoding the characters (which are A-F 0-9), with Huffman coding. I made a quick script, and seem to notice that almost every character in the strings (A-F 0-9) has the same frequency in the file of hashes.

So my questions is: will hashes always produce strings with an almost equal letter frequency?

A cryptographic hash function will produce an output with pseudorandom properties, therefore when expressed in hexadecimal, a list of hash values will have an almost equal number of each character. Pseudorandom data will not compress, as compression looks for patterns. If you had duplicates, compression could reduce the data size.

If you want to compress the list, take your hexadecimal string of 32 characters, and convert it back to ASCII character values, taking up 16 characters. If you need it to be text readable, that can be encoded using Base64 or a variant, which will take 22 to 24 characters.


Why is it OK for secretbox to leak the message length? Most block cipher implementations expect users to pad so that the message matches the cipher block size. I understand the purpose of the padding is to make the input match the cipher block size. It also has a the possibly beneficial effect of hiding the actual message length from the observer.

With NaCl secretbox, the documentation is explicit in stating "Note that the length is not hidden.". What exactly does that mean?

It is usually assumed that the length of the message is not secret. Even with padding the approximate length is leaked, and necessarily any encryption reveals a maximum length – or at least information content if compression is used – because the ciphertext cannot in general be shorter than the message.

NaCl's secretbox does not use a block cipher, but a stream cipher – XSalsa20 (pdf) – so it requires no padding and the exact message length is revealed.

If you have a situation where the message length should remain secret, you must ensure that yourself, e.g. by padding the message to a fixed maximum length. Doing that automatically would be wasteful and would limit the message size the algorithm could be used with, which is why it is left for the user.


is this useful to help break RSA? So, I'm kinda newbie in this cryptography stuff, I just like to understand complex things.A couple of months ago I was learning and I maybe found a pattern in prime numbers and their multiplications, lets check out.
So, it's high demanding to multiplicate random prime numbers, correct? I thought this: Instead of multiplicate the numbers, you can just isolate the last number of each one and sum them up, for example: 23518 and 619741, we can just take the last digit of both and get 2, right? I found out that, if the sum result equals to 2, the ending number in the multiplication it will ALWAYS be 1 (tested with 20k prime numbers)

This also holds true for all sums (2, 4, 6, 8, 10, 12, 14, 16 and 18)
Table:
1 [(1, 1), (3, 7), (9, 9)]
3 [(1, 3), (7, 9)]
5 [(1, 5), (3, 5), (5, 5), (5, 7), (5, 9)]
7 [(1, 7), (3, 9)]
9 [(1, 9), (3, 3), (7, 7)]
So in the RSA-260 challenge number
( 2211282552952966643528108525502623092761208950247001539441374831912882294140
2001986512729726569746599085900330031400051170742204560859276357953757185954
2988389587092292384910067030341246205457845664136645406842143612930176940208
46391065875914794251435144458199) we know that the last digit sum MUST BE, 6, 10 or 14, right? reducing our possibilities by a lot.
Can anyone confirm this for me? I'm really dumb in programming but I think this is a start. Check out the spreadsheet I did. https://docs.google.com/spreadsheets/d/1rcAIz5094WGqVZLGgCiTZotzrHg8TeQ2kQSB6lhAEaU/edit?usp=sharing

Yes, this stems from elementary school arithmetic:
If you multiply two numbers ending in 1 the resulting least decimal digit or result will always be 1. Primality not required.
This does not however mean that if the resulting decimal digit is 1 both original primes end in one: e.g 7*3 or any primes ending in 7 and 3 respectively.
The best way to break RSA (excluding rubber hose cryptography) is to factorize the composite n. This is typically done using: https://en.wikipedia.org/wiki/General_number_field_sieve
Your observational on the behavior of the least significant digits though correct, does not obviously lead to any superior attack.
I use 2048 bit RSA and feel secure, and sometimes 4096 bits for extra safety margin. I expect this to remain this way for many years to come.


Reveal all information up to n-th message Is there a way to generate a sequence of keys that have the property that exposing any of those keys will reveal all previous keys, but no future key?

I'm thinking about an application that sends an encrypted message every day, and sometimes I want to disclose to some other party the content of all past messages at any point in time, but without revealing any future message.

A possible way would be to hash some data x times, and than use the final hash for the first message, the x-1th hash as key for the second message, x-2th hash as key for the second message and so on. Revealing to any party the x-n key allows them to just hash it many times to obtain all the keys between x and x-n with no access to any later keys. But that limits the application in the total number of messages and requires a lot of work to be done beforehand. Maybe there is a much better way?

Is there a way to generate a sequence of keys that have the property that exposing any of those keys will reveal all previous keys, but no future key?

One possibility: select a hard to factor value $n = pq$; publish the value $n$ (or include it with each day's "key"), and keep the factorization secret.  It'll make things easier if you select $p \equiv q \equiv 3 \pmod 4$

Then, select a random quadratic residue $r_0$ (which you can do by selecting a random value $t$ and computing $r_0 = t^2 \bmod n$)

Then, for each day's secret $r_i$, you can compute the next day's secret $r_{i+1} = \sqrt{r_i} \bmod n$ (that is, a modular square root); there are four such square roots; you'll want the one which is a quadratic residue.

That's actually easier than it sounds; if you took my advice about about $p \equiv q \equiv 3 \pmod 4$, then all you need to do is compute:

$$r_{i+1} \mod p = r_i^{(p+1)/4} \mod p$$

$$r_{i+1} \mod q = r_i^{(q+1)/4} \mod q$$

And combine $r_{i+1} \mod p$ and $r_{i+1} \mod q$ using CRT to reconstruct $r_{i+1}$

This addresses your problem, as:

Computing next keys is as difficult as factoring $n$
Computing previous keys is easy, as $r_{i-1} = r_i^2 \bmod n$
You can compute next keys as long as you want


Attack mode for DES + ECB Given that the plain text(P) and the ciphertext is known, and there's a random string(8 bytes)(S) concatenated to the plain text(P || S), how to go about figuring out the random string. Querying of black box is unlimited.

Suppose you've let the box encrypt 'AAAAAAAx' for all byte values of x. (It will be the first block of the total output). Then send AAAAAAA and see what the first block is. You know now what last byte is and it's the first one of S. Now you know one byte. Think and iterate.


Size of Parameters in Polynomial Key-Splitting Algorithm I've seen the elegant way of splitting a key among different people so that only a certain number need to be present to re-compute the key, yet nobody has enough information to re-compute the key on their own. For example, if I want to split $K$ between 4 people, such that any 3 can re-compute the key, I first form a polynomial $y(x)=ax^2+bx+K$.
Then I compute and distribute 4 pairs of the form $(x_i, f(x_i))$, one to each of the people.

It seems like $a, b, x$ should certainly be chosen with a cryptographically secure RNG, but is there any advice on how big they should be? Should they be as big as $K$? Big enough so that the term is about the same size as $K$ (which would make $a\approx K/x_i^2$, where $\approx$ means of the same order of magnitude)? As big as I can make them to the point that time to re-compute the key becomes an issue?

All of this arithmetic must be done modulo $p$ (for some prime $p$ that is large enough so that it'll be larger than any conceivable $K$ you might ever want to use).  You need to pick $p$ in advance.

Once you've picked $p$, then you choose $a$ and $b$ uniformly at random from the set of integers modulo $p$, i.e., uniformly at random from the set $\{0,1,2,\dots,p-1\}$.

The values $x_i$ can be, so long as they are distinct.  A simple choice is to set $x_i=i$, i.e., $x_1=1$, $x_2=2$, $x_3=3$, $x_4=4$.  That suffices.

(Working modulo $2^n$ is not secure.  You need to work modulo a prime $p$.)

(Technically, you can work in any finite field; working modulo $p$ is just one way to get a finite field.  However, if you don't know what a finite field is, you can ignore this remark.  I'm adding this remark only to keep my fellow cryptographers happy.)


Curve25519's Y coordinate of Basepoint origin The paper High-speed high-security signatures by Bernstein et al. introduces the Edwards curve Ed25519.

Concerning the base point $B$, it says that

  $B$ is the unique point $(x,4/5)∈E$ for which $x$ is positive

and $B$ corresponds to the basepoint used on the birationally equivalent curve Curve25519.

So I haven't found on any site information about how do they get that $4/5$ value of the $y$ coordinate in order to get a small basepoint generator.

Is there any reason or origin of that $4/5$? How they determined that $4/5$ was part of the group $2^{255} -19$?

Over the field $\mathbb Z/(2^{255} - 19)\mathbb Z$, Curve25519 is the Montgomery curve $$v^2 = u^3 + 486662 u^2 + u,$$ and edwards25519 is the twisted Edwards curve $$-x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2.$$  The curves correspond by the birational map

\begin{gather}
  x = \sqrt{-486664} \frac{u}{v}, \quad
  y = \frac{u - 1}{u + 1}; \\
  u = \frac{y + 1}{y - 1}, \quad
  v = \sqrt{-486664} \frac{u}{x}.
\end{gather}

The standard base point $P$ for the X25519 Diffie–Hellman function has $u(P) = 9$; the $v$ coordinate is not significant because X25519 works exclusively with $u$ coordinates, so there are two possible points, $P = (9, \pm \sqrt{9^3 + 486662\cdot 9^2 + 9})$.  The choice of $u(P)$ is arbitrary as long as it corresponds to a point of large prime order—it can't affect security—but was made to be the smallest such integer.  The standard base point $Q$ for Ed25519 signature was chosen to correspond to one of the possible choices for $P$, so $$y(Q) = \frac{u(P) - 1}{u(P) + 1} = \frac{9 - 1}{9 + 1} = 4/5;$$ then the $x$ coordinate of $Q$ was chosen arbitrarily from the two options.


Why Static RSA and Diffie-Hellman cipher suites have been removed in TLS 1.3? Why Static RSA and Diffie-Hellman cipher suites have been removed in TLS 1.3?

How keys can be exchanged then?

https://tools.ietf.org/html/draft-ietf-tls-tls13-28

TLS 1.3 has a huge clean up as having 5 cipher suites. As stated in the RFC document RFC 8446 section 1.2 :

  Static RSA and Diffie-Hellman cipher suites have been removed; all public-key based key exchange mechanisms now provide forward secrecy.

With forward secrecy (also called PFS for Perfect Forward Secrecy), even if one of the site's key is compromised, the previously generated keys are safe since there is no method that can regenerate them. The keys are called ephemeral keys.

You can still use ECDH in TLS 1.3 for key establishment but not statically. This version also named ECDHE where the last E is Ephemeral.

There is one drawback, that is; even if you use FPS, the other side can not only store the keys but can also store all the decrypted messages. You don't/can't know that. Storing is not recommended but you cannot prevent that.

When one side stores the keys, it is the opposite of the forward secrecy. Once the attackers breached into the site that will access all the stored keys, but the system was perfect secrecy! Actually, the keys must be erased after the decryption.

See also, misuse of forward-secrecy on Squeamish Ossifrage's answer.


What's the state of the attack to get the first pre-image on MD4? What's the state of the attack to get the first pre-image on MD4?

Is it still $2^{102}$ as described by
Gaëtan Leurent in "MD4 is Not One-Way" ?

The latest I know about is indeed "MD4 is Not One-Way." by Gaëtan Leurent (PDF) FSE 2008. Some of the more interesting and more recent publications to check on are "Advanced Meet-in-the-Middle Preimage Attacks: First Results on Full Tiger, and Improved Results on MD4 and SHA-2", Jian Guo/San Ling/Christian Rechberger/Huaxiong Wang, 2010 (PDF) and the paper Henrick Hellström mentioned in his comment. I don't think you'll find any more recent and/or note-worthy discoveries.

In 2011 there was RFC 6150 (http://tools.ietf.org/html/rfc6150) which stated that MD4 aka RFC 1320 (http://tools.ietf.org/html/rfc1320) is "historic"; meaning: "obsolete". I guess, due to the now "historic" status of MD4, there won't be too much interest to expand further on the issue.


IV in Galois Counter Mode I am looking at Wikepedia Galois Counter Mode article. I see this diagram

I am trying to figure out where the IV works its way in. Is it used to initialize the counter? If so, how does a sequence of 12 bytes (96 bits)initialize a counter on a 32 bit machine?

The diagram shows the gist of the algorithm, but not everything in it.

The bulk of the encryption in GCM uses AES in CTR mode. "CTR mode" means that "successive" values of a counter are encrypted with the block function (the AES properly said) in order to yield a key-dependent pseudorandom stream which is combined (bitwise XOR) with the data to encrypt or decrypt. Each counter value thus has the size of a full block, which is 128 bits. Note that there is no requirement for the notion of "successive values" to match any given arithmetic model, in order to achieve security; we only need that the "successive values" are distinct. Of course, for encryption and decryption to work, sender and recipient must agree on the initial value and how to "increment" it in order to obtain the successive values, and that is defined in GCM.

The specification for GCM is NIST SP800-38D. In that document, we see the following:

While the counter value has the size of a block (16 bytes), only the last (rightmost) 4 bytes are modified to step into the "next value". The last 4 bytes are interpreted as a 32-bit integer (with big-endian convention), which is incremented. Note that the value conceptually "wraps around" (if the last 4 bytes have value FF FF FF FF, the increment yields 00 00 00 00, and the first 12 bytes of the block are kept untouched).
If the IV for GCM has size exactly 12 bytes, then the value "counter 0" in the Wikipedia schema is the concatenation of the IV, and 00 00 00 01. The value "counter 1" will be identical, except that the last byte will be 02 instead of 01. Note that the AES-encrypted value "counter 0" is used as post-processing for the authentication tag; the first counter value used to encrypt actual data is "counter 1".
If the IV for GCM has any other size, then it is first processed with GHASH, in order to yield a full 16-byte initial value for "counter 0". Note that, in that case, the GHASH output is also used for the last 4 bytes, so the starting value for the 32-bit integer is not necessarily 1 (and the "wrapping around" behaviour may actually happen, if we start close enough to FF FF FF FF).

In GCM, the AES block function is used for exactly three things:

To encrypt an all-zero block, to yield the h value (used in GHASH, for the authentication tag).
To encrypt the value "counter 0", used to mask the authentication tag.
To encrypt values "counter 1", "counter 2"... to produce the pseudorandom stream that is combined (with XOR) with the plaintext or ciphertext.

The details of GCM have been made such that, if the IV has length exactly 12 bytes, then all these values are guaranteed to be distinct to each other; the security of GCM depends on it. An important consequence is that if you use the AES/GCM key for anything else, then all security guarantees evaporate like dew in the morning sun.

It shall be noted that the use of the last four bytes as wrapping counter is not a universal convention. That is, it is defined that way in GCM and all GCM implementation follow it (otherwise they would not interoperate). However, other schemes that use CTR mode may have different conventions. In EAX and CCM, the full 16-byte block is considered to be the encoding of a complete 128-bit integer.

Computers are not limited to what can fit in a register, in exactly the same way that you have only ten fingers, but can still perform operations on numbers that contain several digits. On a 32-bit computer, you would use four 32-bit registers to hold the complete 128-bit value. See for instance how it is done in BearSSL implementation; the gist of the increment operation is as follows:

            cc0 ++;
            carry = (~(cc0 | -cc0)) >> 31;
            cc1 += carry;
            carry &= (~(cc1 | -cc1)) >> 31;
            cc2 += carry;
            carry &= (~(cc2 | -cc2)) >> 31;
            cc3 += carry;

The four 32-bit words are cc0, cc1, cc2 and cc3 (of type uint32_t, i.e. exactly 32 bits each). These weird expressions compute the carry propagation with branchless, constant-time code; a simpler (but not constant-time) implementation would look like this:

            cc0 ++;
            if (cc0 == 0) {
                cc1 ++;
                if (cc1 == 0) {
                    cc2 ++;
                    if (cc2 == 0) {
                        cc3 ++;
                    }
                }
            }

To be clear, I repeat that the code snippets above handle the EAX/CCM case, where the counter is incremented as a 128-bit value, not the GCM case, where only the last 4 bytes are incremented arithmetically.


Question about proof of pseudo-random random generators being one way functions I've been looking over this proposition and proof in the book "Introduction to modern cryptography" and am a little confused. Picture is attached at the bottom).

Why is it that we do not multiply the $2^{-n}$ by $\varepsilon$.

It is true that the probability of being in the generator range is $2^{-n}$ but even once we're there the chances of A giving the correct inverse are not $1$.

Should the equation not be $\leq  \varepsilon ~ 2^{-n}$ instead?

It's analyzed in this way because it is tricky to correctly conclude much more than what's written here.  The issue is that a uniformly random string $w$ in the image of $G$ is not necessarily distributed like $G(x)$ for a uniformly random $x$. We know that $\mathcal{A}(y)$ succeeds with $\varepsilon$ probability for a random input $y=G(x)$ of the latter form, but that doesn't tell us much about how it behaves in the former case.

More precisely, conditioned on $w$ being in the image of $G$, it is uniformly random in that image.  This does not necessarily imply that $\mathcal{A}(w)$ ouputs an element of the preimage set $G^{-1}(w) = \{x : G(x)=w\}$ with probability $\varepsilon$.  For example, $G$ could be highly "irregular," meaning that some preimage sets are much larger than others.  But $\mathcal{A}$ might only successfully invert on, say, those $y$ that have very large preimage sets.  This would give it good inverting probability on $y=G(x)$ for uniformly random $x$, but its probability of inverting on a uniform $w$ in the image of $G$ would be much less than $\varepsilon$.


Partial hash code protocol for security tokens providing signatures I've read the following two sentences within a beta protocol specification, which references ISO/IEC 7816-8 for PSO:HASH which already contains notions of a "partial hash".

  The off-card entity is responsible of computing the intermediate hash over the first part of the data to be signed. The intermediate hash-code is transferred to the token by the PSO:HASH command together with the remaining part of the data, the token performs the last round hash computation.

As far as I know, there is no standard that describes how a "partial hash-code" or "intermediate hash-code" values can be transferred. Does anybody know of a standard way to represent a partial hash code as octet string?

Note that in the protocol specification a "bit counter" is also send after the "intermediate hash-code", plus some last bytes of the message itself.

The answer is in the CEN-EN 14890-1:2009, 7.3 General Aspects, and in the SHA-1 and SHA-2 specifications. The output of the hash algorithm for both SHA-1 and SHA-2 is the state of the hash algorithm (specified by $H^{(0..N)}_x$), after the last block is processed. So the output size is identical to the running state, possibly truncated to the leftmost bits.

The following calculations are for SHA-1 and SHA-224/256, for the other SHA-2 hash algorithms the block size is 128 bytes and the length encoding takes 16 bytes. To understand the calculations it is necessary to have read FIPS-180-4.

So first the message is split up into 64 byte message blocks, where the final block consists of 1 to 64 bytes. All the blocks are processed outside the token, up to - but not including - the last message block. The internal state and the amount of bits encoded so far is send to the token, together with the last bytes. Then one or two blocks of padded data - see 5.1 of FIPS 180-4 - have yet to be hashed by the card (expressed as a kind of regular expression on bytes represented as hexadecimals):

MM{r} 80 00{x} LL{8}

where $x = 53 - r$ for $r$ between $1$ and $53$ inclusive (one block) or $x = 117 - r$ for $r$ between $54$ and $64$ (two blocks) where $r$ is the amount of remaining bytes to be hashed.

Then the hash function calculates the final running state and truncates it to calculate the hash output, which in turn is used as input for signature generation.


How does order-preserving encryption work on string? I have read “How does order-preserving encryption work?”. After that, I completed order-preserving encryption on integer data.

Now, I have four questions in this subject:

Is it possible to apply sum operation on encrypted integer data.
Is it available for string data?
Can i make string operations like finding an encrypted string in a ciphertext, order encrypted strings ... ?
If order-preserving encryption is not suitable for these operations, Does any algrotihm make the job ?

Paillier cryptosystem has the property that the product of 2 ciphertexts decrypt to the sum of the plaintexts.

Strings are integers. Only that they are usually large. So this algorithm is also available for strings.

This algorithm doesn't allow you to find encrypted string in a ciphertext.

If you want an encryption scheme in which you can do any operation with the ciphertext, see homomorphic encryption.


Forgery against signature using RSAES-PKCS1-v1_5 padding I wonder what is the security of RSAES-PKCS1-v1_5 under chosen-plaintext attack, in the context of signature verification.

Notations. Let $(N,d)$ be an RSA signing key, and $(N,e)$ the corresponding verification key, with no assumption on $e$ (in particular, I don't assume $e=3$ and consider the general case $e=2^{16}+1$). Let $n$ be the bit-size of $N$.

More specifically, assume that one produces a signature $s$ for a short message $m$ using RSAES-PKCS1-v1_5 padding (bad practice):
$$
s = pad(m)^d \bmod{N},
$$
where

pad(m) = 00 || 02 || R || 00 || m

and R contains 8 or more nonzero bytes to make $pad(m)$ as long as the byte-length of $N$. (Note: unlike RSASSA-PKCS1-v1_5, the bytes in R are not fixed to FF.) Also here, the message is not hashed.

I wonder whether universal forgery is possible with only oracle access to the verification oracle $O(s)$, which returns $m$ if $s^e \bmod{N}$ corresponds to a valid padded message, and returns an error otherwise.

In an answer, Thomas Pornin writes that this "type 2" padding yields a weak signature scheme due to malleability of modular exponentiation. I understand that "type 1" (RSASSA-PKCS1-v1_5) is for digital signatures and "type 2" (RSAES-PKCS1-v1_5) for encryption, yet I don't see how malleability can be applied here to break the security.

Side question. In another answer poncho wrote that if $x^3 = h \bmod{2^{k}}$, then $y^3 = h \bmod{2^{k+1}}$ for $y=x$ or $y=x+2^k$. Hence here, given a target message $m$, is it easy to construct $s'$ such that $s'^e = m \bmod{2^{n+1}}$ for $n$-bit $N$. Which means that there exists $t$ such that $s'^e = m + t\cdot 2^{n+1}$. The integers $s'$ and $t$ are easily, but can they be leveraged to deduce $s$ such that $s^e = m \bmod{N}$?

Less than satisfactory partial answer, which no longer fits a comment.

With $N$ of $k$ bytes and message of $l$ bytes, a (signature, message) pair with random signature is accepted by the most stringent verification oracle with probability $$2^{-8l-24}\;(2^{8k}/N)\;\left(1-2^{-8}\right)^{k-l-3}$$

For 2048-bit $N$ and small $l$, that's about $2^{-8l-25}$. Probability is higher for an oracle comparing messages as C strings, stopping with the first zero encountered.

That's enough for universal forgery of short messages with about $2^{8l+25}$ queries to the verification oracle or modular exponentiations to the $e$, and existential forgery with about $2^{24}$ modular exponentiations to the $e$. No signing oracle is used.

Malleability allows a small speedup: we pick some $a$ (e.g. $a=2$), compute $b=a^e\bmod N$, then $b^i\bmod N$ for incremental $i$, which we check for acceptable padding (and match with the message for universal forgery). If $b^i$ is accepted, $a^i\bmod N$ is a signature of the message embedded in $b^i$. Each new candidate $b^i$ is obtained with a single modular multiplication by $b$, rather than 16 sqrmod and 1 mulmod for modular exponentiation with $e=2^{16}+1$. Further, modular multiplication by a constant can be appreciably optimized by precomputations.

Independently, malleability allows to obtain $f$ existential forgeries from $f+2$ queries to a textbook-RSA signature oracle. We can efficiently prepare $2f+2$ values $c_i$ with acceptable padding such that $c_0 c_{2j}=c_1 c_{2j+1}$, submit $c_0$, $c_1$, and the $c_{2j}$ for $1\le j\le f$ to the oracle, then compute what it would return for the $c_{2j+1}$. There is a lot of freedom for the messages which forged signature is obtained. The attack still works if the signature oracle checks that what it is asked to sign has correct padding format, but fails if the oracle supplies the R part of the padding.

It remains unclear what The Bear had in mind with the following in his answer:

  If you use (this) padding for signatures, then you obtain a very weak signature scheme (because of the malleability inherent to modular exponentiations)


Why is the private key generated first in public key crypto? I'm still new to public key crypto. I'm trying to understand how it is that the private key is generated first in public key crypto? I would have expected the private and public key to be generated at the same time, as they would depend on each other.

For example, in a Bitcoin wallet, I can choose a private key (brain wallet), which will then be used to derive my public key (then my BTC address).

In general, the public and private keys are computed together.

For some schemes, the public key is computed from the private key. ElGamal is an example. (The system parameters include a suitable cyclic group $G$ with a generator $g$. Choose a random exponent $a$. Compute $y=g^a$. The public key is $y$, the private key is $a$.)

For other schemes, this is not the case. Some variants of RSA are examples. (Choose primes $p$ and $q$. Compute $n=pq$. Choose (somehow) $e$ relatively prime to $(p-1)(q-1)$. Compute an inverse $d$ of $e$ modulo $(p-1)(q-1)$. The public key is $(n,e)$, the private key is $(n,d)$ (or something equivalent). Notice (a) how the public key is completed before the private key, and (b) it is not in general possible to quickly compute the public key $(n,e)$ from the private key $(n,d)$.)

(For completeness: Note that of course, the private key cannot be quickly computed from the public key. If it could, any adversary could.)


How should I check the received ephemeral Diffie-Hellman public keys? In my application I'm doing a DH key exchange, where both sides generate their
own ephemeral  key. No static keys are used. I am trying to make my
application resistant against an active attack and therefore need to validate
the public key that my counterpart is sending me.

Below I'm using standard DH variable names: DH parameters $g$ and $p$. Party $A$ has
a private key $x_a$ and public key $y_a = g^{x_a} \bmod p$. Party $B$ has a private key $x_b$
and public key $y_b = g^{x_b} \bmod p$. The calculated secret is then $z = g^{x_ax_b} \bmod p$. Also $p$
is a safe prime $p = 2q+1$.

In my application I will authenticate the shared secret $z$ via an out of bounds
way (basically a user verifying a fingerprint).

OpenSSL has a function to validate a DH public key (DH_check_pub_key()) which
does the following check:

$$2 \leq y_b \leq p-2$$

I believe this always excludes the generators that generate the order-2
subgroup. Because $p$ is a safe prime, I think these generators are always $1$
and $p-1$. Is this correct? Is it also correct that all integers in $[2, p-2]$
either generate an order-$q$ or an order-$2q$ subgroup?

Secondly, in NIST SP800-56, section 5.6.2.4, it is mentioned that I should
also check:

$$y_b^q \bmod p = 1$$

I don't understand the background of this check. Is it needed when $p$ is a
safe prime? OpenSSL does not implement this.

The check $y_b^q = 1 \mod p$ is there to prevent two possible weaknesses:

Suppose someone gave us (either because of a programmer error or deliberate attack) gave us a $y_b$ value of small order.  If so, then someone listening in can guess the shared secret you derive.
Suppose an attacker gave us a $y_b$ value with an order with a small factor $r$.  Then, by seeing the shared secret value $z$ you derived (which will be one of $r$ possibilities), then the attacker could rederive the value $x_a \bmod r$; whether that is interesting would depend on whether you reuse $x_a$ elsewhere.

Now, for a "safe prime" (one where $q=(p-1)/2$ is prime), neither of these attackers are of much concern; there are no small subgroups other than the trivial order-1 and order-2 subgroups (and yes, you are correct, all group members in $[2, p-2]$ are either of order $q$ or $2q$).  In addition, which the attacker could give us a $y_b$ value with order 2q (and potentially learn $x_a \bmod 2$, that just gives him one bit of your private exponent; as he can't learn anything else, this is not much of a concern (even if you reused $x_a$ in other DH exchanges).

On the other hand, NIST SP800-56 doesn't assume a safe prime.  In fact, a strict reading of NIST SP800-56 would appear to forbid it; if you look at Table A, it specifies the size of $q$ to be either 160, 224 or 256 bits (and not "at least so many bits", precisely that size).

As for your question as to whether the check $2 \le y_b \le p-2$ will always exclude all members of an order-2 subgroup, that is actually true for any prime $p$, not just "safe primes".  For any prime $p$, the only group member with order 2 will be $p-1$.

Also, if you think you want to perform the $y_b^q = 1 \mod q$ check (even though it doesn't appear to be strictly necessary), one optimization that a safe prime allows is that you can compute the Lagrange symbol; that's a short cut for computing $x^q \bmod p$ for $q = (p-1)/2$ (which is a lot faster than computing $x^q \bmod p$ directly)


How to optimise a finite field multiplication? I'm currently trying to optimise the finite field multiplication in $ \operatorname{GF}(2)[x]/(p)$, where $p = x^8 ⊕ x^7 ⊕ x^6 ⊕ x ⊕1 ∈ \operatorname{GF}(2)[x] $.

The thing is that I have to multiply by $ 16,32,133,148,192,194 \ \ and \ \ 251 $. Actually, what I do is that I declare 7 arrays (one for each multiplication; length 256) which contains every result. for example, when i want to multiply $ i = 145 $ by 32, i just assign $ array_{16}[i] $ to the result.

Is there an other way to do the multiplication, in order to reduce the memory used by my algorithm for example?

a better way to optimize the code is to use multiplication by 2 concept(xtime).

xtime(x) is multiplication by 2 which is left-shift modulo irreducible polynomial ($x^8\oplus x^7\oplus x^6\oplus x\oplus1$ = 0x1C3)

xtime is implemented in c code with irreducible polynomial (0x1c3) as following

#define xtime(x)   ((x<<1) ^ (((x>>7) & 1) * 0xc3))

= addition modulo 2(xor in code)

The binary representation of your values is as following:

16  : 00010000

32  : 00100000

133: 10000101

148: 10010100

192: 11000000

194: 11000010

251: 11111011

16*x (mul16) is as following
16 is $2^4$ (4 times left shift)-> mul16(x)=xtime(xtime(xtime(xtime(x)))). it can be rewritten as of mul8 as following xtime(mul8(x)). mul8 is defined as nested triple time

32*x (mul32) is as following
32 is $2^5$-> mul32(x)=xtime(xtime(xtime(xtime(xtime (x)))))= xtime(mul16(x)).

133*x = (128+4+1)x = 128*x+ 4*x + x;
= ($2^7 + 2^2 +1$)x = (mul128(x)^xtime(xtime(x))^x) = (mul128(x)^mul4(x))^x)

192= (128+64)x = mul128(x)^mul64(x)
194= (192+2)x =  mul192(x)^xtime(x)

I will let you do the 148 and 251 multiplication, you can use the following code for assistance:

#include <stdio.h>
#include <stdint.h>

#define xtime(x)   ((x<<1) ^ (((x>>7) & 1) * 0xc3)) //P: x8⊕x7⊕x6⊕x⊕1
#define mul4(x)    (xtime(xtime(x)))
#define mul8(x)    (xtime(mul4(x)))
#define mul16(x)   (xtime(mul8(x)))

#define mul32(x)      (xtime(mul16(x)))
#define mul64(x)      (xtime(mul32(x)))
#define mul128(x)     (xtime(mul64(x)))&0xFF
#define mul133(x)  (mul128(x)^xtime(xtime(x))^x)&0xFF
#define mul192(x)  mul128(x)^mul64(x)&0xFF
#define mul194(x)  mul192(x)^xtime(x)&0xFF

uint8_t gmul(uint8_t a, uint8_t b) {
    uint8_t p = 0; /* the product of the multiplication */
    while (a && b) {
            if (b & 1) /* if b is odd, then add the corresponding a to p (final product = sum of all a's corresponding to odd b's) */
                p ^= a; /* since we're in GF(2^m), addition is an XOR */

            if (a & 0x80) /* GF modulo: if a >= 128, then it will overflow when shifted left, so reduce */
                a = (a << 1) ^ 0x1c3; /* XOR with the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible */
            else
                a <<= 1; /* equivalent to a*2 */
            b >>= 1; /* equivalent to b // 2 */
    }
    return p;
}

int main(){
    // printf("%x\n",mul16(0x06)&0xFF);
    // printf("%x\n",mul32(0x06)&0xFF);

    // printf("%x\n",mul32(0x22)&0xFF);
    // printf("%x\n",gmul(0x22,32)&0xFF);

    printf("---------\n");
    printf("%x\n",mul128(0xf5)&0xFF);
    printf("%x\n",gmul(0xf5,128)&0xFF);

        printf("---------\n");
    printf("%x\n",mul64(0xf5)&0xFF);
    printf("%x\n",gmul(64,0xf5)&0xFF);

        printf("---------\n");
    printf("%x\n",mul192(0x35)&0xFF);
    printf("%x\n",gmul(192,0x35)&0xFF);

        printf("---------\n");
    printf("%x\n",mul133(0x35)&0xFF);
    printf("%x\n",gmul(133,0x35)&0xFF);

            printf("---------\n");
    printf("%x\n",mul194(0xe5)&0xFF);
    printf("%x\n",gmul(194,0xe5)&0xFF);

    return 0;
}


Why/how is libsodium/nacl's cryptobox repudiable? https://nacl.cr.yp.to/box.html see "security model".

As far as I can see, Alice encrypts a message using her private key, Bob's public key and a nonce.  Bob decrypts the message using Alice's public key, his private key and the nonce.

The documentation says "The crypto_box function is not meant to provide non-repudiation."

How can Alice says she didn't encrypt a ciphertext, if Bob can verify its origin and authenticity using her public key?

(Assuming that the message must be in a known language or format to be 'real'.)

To take SEJPM's answer and be more explicit: Bob can also generate that ciphertext.

One of the conditions on nonrepudiation is that no one (other than Alice, assuming her private key wasn't leaked) could possible generate that message.  This doesn't hold here.  If Bob can decrypt the ciphertext, he knows Alice must have generated it (as Bob knows he didn't), however he can't prove it to anyone else.


Is there any existing analysis for this construction to turn a tweakable blockcipher into a PRF? I'm basically looking at this construction to turn a tweakable blockcipher $E_c(x)$ taking a key $k$, nonce $n$, counter $c$ (forming tweak $t = c||n$) and an input $x$ into a PRF on an arbitrary-length message $M$ that has $m$ blocks. Without further ado:

$$tag = E_0(E_1(M_1) \oplus \dots \oplus E_{m-1}(M_{m-1})  \oplus M_{m} \oplus E_{\ell + |M_m|}(0) \oplus E_{\lambda + |M_m|}(0))$$

$l$ is a constant larger than any legal value for $m$. $\lambda$ is larger than any legal value for $l + |M_m|$. $|M_m|$ is the length of the final block, and the XOR of the last two elements $M_{m} \oplus E_{\ell + |M_m|}(0)$ is truncated to $|M_m|$ bytes. $E_{\lambda + |M_m|}(0)$ is not truncated.

The closest to this construction what I found is the authentication part of OCB3 mode defined in terms of the tweakable blockcipher. How the last block is handled however is quite different.

I don't have a proof myself, but here's how you could analyze this / prove it secure yourself, if you want to have a go.

Your construction is basically $F(M) = E_0(G(M))$, where $G(M) = E_1(M_1) \oplus \dots \oplus E_{\lambda+|M_m|}(0)$ (that long thing defined in the question).  To prove this secure, it suffices to prove the following:

The tweak values used in computing $G(M)$ are never $0$.
It is highly unlikely that the attacker can find a "collision".  In other words, say that two messages $M,M'$ form a "collision" if $G(M)=G(M')$.  Consider an (adaptive) attacker with an oracle for $F$, and let $M^1,\dots,M^q$ denote the $q$ messages that the attacker queries its oracle on.  Let $\mathsf{BAD}$ denote the event that there exists some $i,j$ with $i\ne j$ and $G(M^i)=G(M^j)$.  If you can prove that $\Pr[\mathsf{BAD}]$ is negligible, then you are home-free.  That's because $E_0(Y^1),\dots,E_0(Y^q)$ will be pseudorandom if $Y^1,\dots,Y^q$ are all distinct.

The first condition should be easy to establish, as long as you put appropriate bounds on the length of the message to ensure that $l+|M_m|$ and $\lambda+|M_m|$ never wrap around to become equal to $0$.

You will have to analyze the second condition carefully.  It looks like you might be able to establish that the second condition holds through some sort of case analysis, but that looks too tedious for me to do it -- so I'm going to leave that to you to establish.

Other comments.  I don't understand why you have $E_{l+|M_m|}(0)$ in the xor; that looks pointless to me.  I don't understand why you treat $M_m$ differently (premature optimization?).  I don't understand why you don't just use some existing construction, like PMAC.

If you're going to invent something new, the following seems cleaner and easier to analyze:

$$F(M) = E_0(E_1(M_1) \oplus E_2(M_2) \oplus \cdots \oplus E_m(M_m) \oplus E_\lambda(\text{length}(M))),$$

where $\lambda$ is a constant chosen to be larger than any possible value of $m$, and where $M_m$ is padded with zeros (say) deterministically.

Related work. I suggest you make sure ythat you read the following papers:

http://cseweb.ucsd.edu/~mihir/papers/xormacs.html - Describes a similar but not identical construction, and offers a proof of security.
A Block-Cipher Mode of Operation for Parallelizable Message Authentication - PMAC is also very similar, so make sure you take a look at it.  It's not clear to me why you have invented something new, rather than just using PMAC.  I don't see any advantage of your scheme over PMAC.
Improved Security Analyses for CBC MACs - I recommend you read their proof of security for ECBC.  It is the framework I outlined above (show that the input to a final PRF/PRP is free of collisions across all queries, then it follows that the output is pseudorandom).


Crypto implementations bits and bytes Reading many papers in the homomorphic encryption domain and in cryptography, a lot of schemes operate on bits as 1 and 0.

If I wanted to implement a scheme, for example, Gentry's FHE, would I have to encode inputs as "bits" or just use bytes (C & C++ (char), Golang(byte), etc)?

That issue is not really relevant when one implements such schemes, because the plaintexts are typically used only in the encryption, where they are combined with big values that need to be encoded as big integers anyway.

All the homomorphic operations should not depend on the plaintext, so, the chosen encoding is irrelevant here.

And even if the decryption outputs a single bit, all the operations done in the decryption function are performed also over big integers.

As an example, the scheme implemented by Leo Ducas uses a regular C integer to encode input bits, as you can see in lines 29 and 30 of file LWE.h from his Github repository.


iterated discrete log problem Consider the following problem: given  $g_1 \ldots g_i,h_1 \ldots h_i  \in G$, $\forall i$ find  $x_i$ such that $g_i^{x_i}=h_i$

For $i=1$ this is the discrete log problem and  is assumed to to have some level of security based on the order of $G$ for certain groups. Let's call this security level $\lambda$.

What happens to $\lambda$ as $i$ increases? Best case, it scales linearly with $i$. That is, its twice as hard to solve two DL instances in the same group $G$ as it is to solve one. Worse case, its no harder.

Im particularly curious with what happens when $G$ is a Schnorr group, though composite groups might work too.

At least on a nieve quick glance, neither Pohlig–Hellman nor Baby-step Giant-step seem to benefit much from being run multiple times in the same group. I'm worried, however, that there are overlapping sub problems that if properly leveraged, perhaps using dynamic programing, would lead to a sub-linear scale up. The question is, how effective these techniques are.

I'd imagine someone has examined this before and I just need to find a paper on it, but as of yet I haven't found one.

UPDATE
The Pollard Rho algorithm can apparently solve $i$ dl instances in the same group in $O{\sqrt{Ni}}$ where $N$ is the order of the group. So $\frac{1}{2}\lambda\sqrt{i}$.[1]

The real question appears to be  how index calculus methods handle it.

I don't know the general answer, however, it appears that Baby-step Giant-step is able to give you the solution in $O(\sqrt{in})$ time (where $n$ is the size of $G$); this is $O(\sqrt{i})$ times longer than it takes the same algorithm to solve a single discrete-log problem.

The first observation is that if you know the group order $n$ and a group generator $g$, that this problem can be reduced to $2i$ discrete log problems with the same base; if we find the values $y_a, z_a$ such that $g^{y_a} = g_a$, $g^{z_a} = h_a$, then we know $x_a = y_a^{-1} z_a \bmod n$.

So, here is how we can use Baby-Step/Giant-Step to solve all $2i$ discrete log problems in $O(\sqrt{in})$ time:

Let $t$ be the integer closest to $\sqrt{2in}$
Compute the $t$ values $g^j$, for $0 \le j < t$, and store those values in a hash table.
For each $g_a, h_a$ value, compute the $n/t$ values $g_ag^{-tk}$ for $0 \le k < n/t$.  Look up each value in the hash table; when we find $g_ag^{-tk} = g^j$, we know $g_a = g^{tk + j}$

The first step involves computing $t = O(\sqrt{in})$ values, and hence takes $O(\sqrt{in})$ time.  The second step involves iterating over $2i = O(i)$ variables, each iteration involving $n/t = O(\sqrt{n/i})$ time, for a total of $O(\sqrt{in})$ time.

Now, this gives an answer to the question from a theoretical standpoint ("yes, there do exist ways where we can take advantage of multiple subproblems"), however, it's not very interesting from a practical basis -- groups small enough for Baby-step/Giant-step to be a threat are too small to give real security.


Envelope Encryption with asymmetric keys vs KMS In Envelope encryption a symmetric secret key is used to sign the data and then another key is used to encrypt the secret to produce an encrypted secret key. The encrypted messages is packaged with the encrypted secret key and sent to the client/consumer which then decrypted the encrypted secret key to get the secret key, which in turn is used to decrypt the message

There are 2 ways to implement it:

Asymmetric encryption: The producer encrypts the secret key(s) with the consumers public key. The consumer uses a private key to decrypted the encrypted secret
KMS (such as AWS KMS): The secret key is encrypted by the KMS, and client that needs access to the secret key has to ask the KMS to decrypt it

The advantage of the KMS approach is that key management is centralized, and revoking permissions from a client can be done by removing the client from the KMS and rotating the key.

Are there any good reasons to use asymmetric keys instead of KMS?

It's all about where you store the secret and who has access to it.

First a clarification: You are confused. KMS does not use asymmetric encryption (also called Public-Key encryption).  It uses private key encryption to enable envelope encryption.  They are two different things.

In asymmetric encryption the producer of the encryption never has to access the secret, they just need the public key.  The producer uses the public key to encrypt, the consumer uses the corresponding private key to decrypt.  In order to facilitate key rotation the producer sometimes appends the public key that was used to encrypt so that the consumer knows what private key to use to decrypt.
No matter how much data is encrypted there are no hints at the private key.  The algorithm for decryption is usually more compute intensive than private key encryption.

In envelope encryption the producer and the consumer must be the same (or both have access to the master key). You use a master key to generate a secondary key called a data key.  You then encrypt the data key using the master key and the data itself using the data key, then you append the encrypted data key to the encrypted data.  When you decrypt you use the master key to decrypt the appended data key, then use the decrypted data key to decrypt the data.

The advantage of this is that you can cost effectively store your master key in purpose build Hardware Security Module and never expose it to anything else without having to pass all the data you encrypt into the HSM.  You can even generate the key inside the HSM and not take it out so that there's no chance that it has ever been exposed to anything externally.  KMS provides you with a cloud based HSM and it's backed by physical HSMs at Amazon.

If you don't care about keeping your master key in an HSM, then you can do the same kind of encryption using your own key that you try to keep safe by putting in on a jump server or something like that.  Also as long as you aren't encrypting more than 250 million TB you can skip the envelope.

If you're looking for some example code you can snatch up to implement either simple AES encryption or envelope encryption you might want to check our open-source project.  It's got an implementation for each you can leverage...

https://github.com/kunai-consulting/KeyStor


ECDSA vs ECIES vs ECDH Recently I started studying Elliptic Curve Cryptography and I just loved it. I want to transfer some big data (like 3KB), What is the best method, ECDSA, ECIES, or ECDH (and why)?

I am confused, how should I choose between ECDSA, ECIES and ECDH?

ECDSA is a digital signature algorithm
ECIES is an Integrated Encryption scheme
ECDH is a key secure key exchange algorithm

First you should understand the purpose of these algorithms.

Digital signature algorithms are used to authenticate a digital content. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, such that the sender cannot deny having sent the message (authentication and non-repudiation) and that the message was not altered in transit (integrity).

Integrated Encryption scheme is a hybrid encryption scheme which provides semantic security against chosen plain text and chosen cipher text attacks. ECIES uses different types of functions:

Key Agreement function
Key Derivation Function
Symmetric Encryption scheme
Hash function

Secure key exchange algorithms are used to exchange our keys securely via a non secure channel.

Here you are interested in Elliptic Curve variants of those algorithms. Your requirement is to exchange some data. So you can use ECDH to share the secret key and ECDSA to sign the content. Because ECDH does not provide authentication we can use ECDSA for that purpose. Once the secret key is shared, you can securely exchange your data through a non secure channel. Strength of the secret key can be defined by considering the level of security you need and amount of computation power you got.


Is RSA encryption without padding secure with NIST Key Establishment schemes? NIST SP800-56B standard (addressing IFC-based Key Establishment schemes) defines some key establishment (KE) schemes using the RSASVE primitive in which the common secret $Z$ is encrypted with RSA-EP  (basic RSA encryption without padding).

I understood that RSA encryption should mandate one of the two padded schemes (PKCS#1 v1.5 or OAEP) as defined in the PKCS#1 standard.

I've got two related questions about this:

Is such basic RSA encryption of common secret $Z$ without any padding - of which all security obviously relies) secure?
If yes, for what use cases is RSA encryption without padding secure? In which use case is padding required?

Yes, RSA encryption without padding as used by RSASVE in NIST SP800-56B is secure.

The RSASVE Generate Operation in NIST SP800-56B §7.2.1.2

is given on input an RSA public key $(n,e)$;
generates a random secret bitstring $Z$ uniformly distributed on range $[2,n-2]$;
computes $C=Z^e\bmod n$ (as in textbook RSA encryption);
outputs the secret $Z$ and the public $C$ (as bitstrings).

and the RSASVE Recovery Operation

is given as input $C$ and the private key $(n,d)$ (or some equivalent);
computes $Z=C^d\bmod n$  (as in textbook RSA decryption);
outputs the secret $Z$.

It is used to generate a secret bitstring $Z$, then share it with the legitimate holder of the private key $(n,d)$.

This is safe (in the sense that an adversary intercepting $C$ gains no knowledge about $Z$ chosen in RSASVE Generate), despite the lack of padding, because what's passed to textbook RSA is random. Breaking RSASVE is, quite precisely, the RSA problem, defined as gaining information about random plaintext randomly chosen on $[2,n-2]$ (give or take $0$, $1$, $n-1$) and encrypted using textbook RSA encryption. Padding is unnecessary here. One way to see that is that the aim of RSA padding is to transform plaintext (or message to sign) into something close enough to random that the RSA problem is safe, and here we have something assumed random in the first place.

Update: as rightly pointed by SEJPM in comments, the above is not enough to show that the uses of RSASVE in NIST SP800-56B are safe. According to a cursory review, that's indeed the case, for I only see that $Z$ is

optionally, first concatenated with another similarly shared secret, to form a wider one;
used as the input of some KDF, where it is subject to $H(\text{counter}\|Z\|\text{OtherInfo})$

and this prevents any exploitation of the homomorphic property of RSA.

We can safely use RSA encryption without padding when

The plaintext enciphered is guaranteed to be about uniformly random (from the adversary's standpoint) over $[0,n-1]$ (or a large-enough subset of that, say with more than $n^{2/3}$ elements); this is enough to insure that the adversary can not gain knowledge of what's enciphered.
And it does not matter that the alleged plaintext obtained by deciphering unauthenticated ciphertext can have special relations to some true plaintext.

Two common applications of that are

Encryption of a freshly generated secret, for secret sharing, when that secret is then hashed (as in NIST SP800-56B) or otherwise used in a manner matching 2.
Encryption of a freshly generated RSA signature, when the modulus used for encryption is different form the one used for signature (and not with much more bits); in this application, deciphered plaintext is then naturally submitted to signature verification using a different modulus than in encryption, which insures 2 is met. In the common case of moduli of the same bit size, there is a standard trick to shorten the signature by one bit so that it is always less than the encryption modulus: replacing signature $S$ by $\min(S,n_s-S)$ where $n_s$ is the signature modulus. Enciphering a signature is useful to insure confidentiality of some of what's signed.

Note: I have silently assimilated bitstrings to integers using big-endian convention.


Using the floor of sines of integers is to show that there is nothing sinister, like a backdoor in the choice of the constants.

The answers to the following
question shows how the choices for the shifts help with diffusion, I.e., a fast avalanche effect.


Is direct RSA encryption of AES keys secure? I am wondering: If we take this scheme/procedure and each of it seems very secure (to me at least), is it truly secure or is there a vulnerability hidden in the process?

This is the scheme:

Bob has an RSA key with modulo $N$ with a size that is considered safe, 2048 and a public power of $e=3$ (should assure efficient encryption).

Alice wants to send Bob a big file, and chooses symmetric encryption: She uses a random $k$ for AES and sends it encrypted using RSA using $C=k^e \bmod N$, and then sends the file encrypted by AES using key $k$.

To decrypt the file, Bob recovers $k$ using $k=C^d \bmod N$ and then decrypts the encrypted file using AES with $k$ is the key.

Is this procedure really secure?

On the paper, it uses secure parameters and seems secure, but I am not sure because $k$ is used too much here. Is there some hidden vulnerability I am missing here?

EDIT: what i am asking is in regards to attacking it, so could you please put an emphasize on attacking it rather than suggesting an alternative? i don't fully understand it, i understand that because of AES, $k^3$ cannot be more than 768 bits, so it does not pass the modulo (that is 2048). but i don't understand the technical details very well and would appreciate if you could elaborate on it instead of on possible mitigations.

thank you very much

This scheme suffers from a classic problem of textbook RSA which is mitigated e.g. by RSA-KEM (as outlined by kelalaka) or RSA-OAEP.

When you compute $k^3\bmod N$, you'll experience that $$c=k^3\stackrel{k< 2^{256}}{\leq}\left(2^{256}\right)^3=2^{768}\ll 2^{2000}<N$$

Now remember how $x\bmod N$ works: If $x\geq N$, then you recursively compute and return $(x-N)\bmod N$ and else you return $x$.

Given that $c\bmod N$ fits the "else" case, $c$ is simply returned. Now an adversary can just compute $\sqrt[3]c$ as your calculator does for real numbers (with a bit more precision), you get $k$ back.

Note that the above weakness doesn't violate the RSA assumption because the assumption explicitly states that $x$ is uniformly randomly sampled from $\mathbb Z^*_N$ 1 in $c=x^e\bmod N$.

1: $\mathbb Z^*_N$ is the set $\{1,\ldots, N-1\}$ without any $x$ such that $\gcd$$(x,N)>1$


Cut through mode for TLS AES-CBC / SHA ciphersuite I am looking at RFC5246 and it seems that AES-CBC/SHA cipher suites cannot be implemented in a cut-through mode.

Let's suppose that received record spans two segments.
As i understood HMAC calculation can be started only after the last byte (pad_length) of second record is decrypted, that requires to buffer both segments comprising a record.

Am I missing something ?

Am I missing something ?

Well, the first obvious question to ask, even before "can I?" is "should I?".

It would appear, from a security standpoint, doing TLS in a cut-through mode would have security issues, and so it's not clear that it should be attempted, even if you could.

Suppose you did; you implemented a way to receive a partial TLS record, and send the partial decrypted plaintext record to the receiver.

Then, what an attacker could do is send a TLS record claiming to be a 16k byte encrypted record, and then send segments containing the first 15k of ciphertext of his choosing; if won't be able to come up with a matching HMAC; he might decide not to send that at all.

Your implementation will decrypt the 15k of ciphertext and forward it along.  It'll then either receive an HMAC that doesn't match, or time out; it doesn't matter, as the receiver has received his 15k of bogus plaintext.

And, if you say "the attacker has no control over what his ciphertext will decrypt to, and so it's not that critical of an attack", well, that's wrong.  By pasting in ciphertexts from previous records, and/or flipping well chosen bits (which will garble one plaintext block, but flip the corresponding bits of another plaintext block), the attacker has quite a bit of flexibility.

This isn't a concern with TLS as it was designed, as the entire decrypted record is never forwarded to the application until the HMAC validates; you're breaking that assumption.


Extracting modulus from hidden function I have a hidden function $f(x) = x \pmod{n}$ and would like to solve for $n$ based on a set of input and output pairs which can be chosen freely.

I would like to do this without brute force (i.e. start at $x_0=1$ and iterate $x_{i+1}=x_i+1$ until $f(x_i)=0$).

So far I have observed that if I expand $x=an+b$, then by subtracting $f(x)=b$ from the input, I am left with $x-f(x)=an$.

I can repeat this operation for various inputs and obtain a list of different multiples of $n$, but I cannot work out how to use them to solve for $n$ itself.

If I use the above procedure to obtain distinct $a_0n$ and $a_1n$, I could compute $gcd(a_0n,\,a_1n) = kn$, but there is no guarantee that $k=1$, and the situation remains the same no matter how many $a_in$ are processed in this way.

Is this even a solvable problem or do I need to include extra constraints on the function, like being explicit about the domain, perhaps $f := \mathbb{F_2}[x] \to \mathbb{F_2}[x]$ (polynomials with binary coefficients)?

This smells like a HW question, so the OP should try it with more hints.

By querying this function at $x$, it is easy to tell whether $x\geq n$ or $x<n$. Let $k$ be a natural number such that $2^k<n\leq 2^{k+1}$, how many queries do you need to find this $k$? Knowing this $k$, how can you figure out $n$?

If the modulo operation is part of polynomial division with remainder, you could find the degree of $n$ using binary search. Once you know the degree, you can query another polynomial to find $n$.


Breaking ElGammal encryption of two different mesagges I'm stuck with the following problem on ElGammal encryption.

  We work on $\mathbb{Z}_{p}^*$ where $p$ is prime and we are given $p$,
  the generator $g$ of $\mathbb{Z}_{p}^*$ , the public key used $y$ and
  five encryptions $(u_1,v_1), \cdots, (u_5,v_5)$ where each of them is
  a encryption of a message $m$ that can be $1$ or $-1$.

Please refer to the second scheme of this question if you need more details on the ElGammal cryptosystem I'm using.

As a hint I'm told to look for a subgroup of index two. I tried to solve the discrete logarithm problem in that subgroup with sage but as this post discusses the complexity is only reduced by a constant so that it is still intractable.

I give you the code I was using in case you have some comments.

F = Integers(p)
gmod = F(g)
q = p // 2
F2 = Integers(q)
gmod2 = F2(g)
ymod2 = F2(y)
gmod2 = F2(g)
ymod2 = F2(y)

Can you figure out how this could be solved?

Edit:

In my case $\frac{p-1}{2}$ is already prime.

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


Key generation on rebalanced RSA-CRT Key Generation Method: Take $s \le n/2$ bits.

Generate two distinct random $n / 2$-bit prime numbers $p$ and $q$ with $\operatorname{gcd}(p-1, q-1)=2$ and
calculate $N= p*q$;
Generate two $s$-bits random numbers $d_p$ and $d_q$,
such that $\gcd(d_p, p-1)=1$, $\gcd(d_q, q-1)=1$
and $d_p= d_q \bmod p-1$.
Calculate one $d$ such that $d= d_p \bmod p-1$ and $d= d_q
\bmod q-1$.
Calculate $e=d^{-1} \bmod \varphi(N)$,
Public key= $(N, e)$,
Private key= $(p, q, d_p, d_q)$.

On the 3rd step of key generation, do I need to select between $d= d_p \bmod p-1$ and $d= d_q \bmod q-1$ or do I make the $d_p$ and $d_q$ to make same $d$ result?

It is okay to use small prime because I use $p = 41$ and $q = 59$ for study purposes.

Please help me to find the $d$.

The paper on which the question is based describes Rebalanced RSA-CRT with $d_p=d_q\bmod(p-1)$ as stated in the question's step 2, but is wrong in doing so. Notice that when $s<n/2$, that condition implies $d_p=d_q$, and that goes squarely against generate two $s$-bits random numbers $d_p$ and $d_q$ also in step 2 (further step 3 can become $d=d_p$, ans $d$ is $s$-bit only).

That's confirmed by looking at the paper's source: M. J. Wiener's Cryptanalysis of RSA with short secret exponents (IEEE ToIT, 1990), which section 8 open problems states [emphasis added]:

  A useful technique for reducing the secret key exponentiation time is
  to take advantage of the knowledge of $p$ and $q$ (rather than just the product $pq$). Using this technique, two half-sized exponentiations are performed. The first exponentiation gives the result modulo $p$ using exponent $d_p=d\bmod(p-1)$, and the second gives the result modulo $q$ using exponent $d_q=d\bmod(q-1)$. These two results can be combined easily using the Chinese Remainder Theorem to obtain the final result modulo $pq$. One could reduce the secret key exponentiation time further by choosing $d$ so that $d_p$ and $d_q$ are short. An interesting open problem is whether there is an attack on RSA when $d_p$ and $d_q$ are short, but not equal.

Wiener clearly knew that short $d_p=d_q$ would be unsafe (his paper conclusively proves it when $s\le 0.125n$).

I thus suggest that the key generation procedure for Rebalanced RSA-CRT should be:

Generate two random $n/2$-bit primes $p$ and $q$ (that are nearly certainly distinct for sensible choice of $n$), optionally such that $\gcd(p-1,q-1)=2$ ;
calculate $N=p\cdot q$ (which will be $n$-bit or one bit less).
Generate two $s$-bits random integers $d_p$ and $d_q$ (that are nearly certainly distinct for sensible choice of $s$), such that $\gcd(d_p, p-1)=1$ and $\gcd(d_q, q-1)=1$.
Calculate (using the CRT) one $e$ (possibly: the lowest) such that $e\equiv d_p^{-1}\pmod{p-1}$, $e\equiv d_q^{-1}\pmod{q-1}$, and $0<e<(p-1)(q-1)$.
[or we could explicitly compute $d$ then deduce $e$ as in the question]
Public key = $(N,e)$,
Private key = $(p,q,d_p,d_q)$.

but I caution against using it:

We know that it would be insecure to use $s<0.146n$, thanks to D. Boneh and G. Durfee's Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$ (first version in proceedings of Eurocrypt 1999)
These authors caution the bound could further be improved to $d<N^{0.5}$, thus $s<0.25n$; so we should probably stick to prudently larger $s$, and a conservative Rebalanced RSA-CRT is thus bound to a speed improvement smaller than a factor of two.
Further, when using RSA-CRT (rebalanced or not) to compute $x\to x^d\bmod N=y$ , it is customary and useful to check that $y^e\bmod N=x$ in order to guard against fault injection; in which case having a large $e$ (as in Rebalanced RSA-CRT) much more than offsets any speed gain achievable by lowering $d_p$ and $d_q$.

Example with $n=40$, $s=13$ (which are too small to be sensible choices)

$p=768941$, $q=825443$, $N=634716965863$
$d_p=4231$, $d_q=6779$
$d_p^{-1}\bmod(p-1)=634271$, $d_q^{-1}\bmod(q-1)=670801$
$e=303057573891$.


Zero-knowledge proof for the product of additive Paillier ciphers Suppose that Alice received the cipher values: $E(x_1), E(x_2), ..., E(x_n)$ that are encrypted using Paillier cryptosystem by $n$ entities with Bob's public key.

Alice computes $E(\sum x_i)$ from the product of the cipher values she received.
Alice sends $E(\sum x_i)$ to Bob for decryption, but she needs to prove that she used all the cipher values she received to form the product $E(\sum x_i)$ for Bob to return the plain text $\sum x_i$.

What should each entity: $i$ send along with their share $E(x_i)$ for Bob to be able to do such verification, and how could he do it?

Note: $x_i$ values are not merely $0$ or $1$. They can take any integer value.

Assuming entities do want Bob to decrypt the sum, but not be able to decrypt individual ciphertexts: enitites would send commitments to plaintext to Bob while sending ciphertexts to Alice. Commitment scheme should be additively homomorphic such that Bob could open the result (over commitments collected) with plaintex decrypted as verification. This would prevent Alice from manipulating ciphertexts collected (assuming honest entities).

Please note plaintext is not an integer in Paillier scheme modulo $n^2$, but a ring element modulo $n$.


What's wrong with XOR encryption with hash and an iterated salt Suppose you'd use the following algorithm to encrypt a message

Let $k$ be the key to encrypt with
Let $m$ be the message to encrypt
Split $m$ into groups of 512 bytes

Given a hash function with a 512 bit output.
For each 512 bit group in the message:

let $s$ starts at 0

let $l = hash(k + s)$
XOR the current group of the message with $l$
Append the result from above to the final result.
Increase $s$ by 1.
Repeat until there are no more groups in the message

How would one go about breaking such an encryption?
If the hash function is well designed then each bit in the input should have a 50% chance of being flipped in the output.

The only predictable relationship between the input and output should be the length of the message. In this case the length of the input and output would always be the same. But is that a security problem? If so, how would one go about exploiting it?

Edit:
This question was marked as a possible duplicate.
In contrast to the linked question, this question is not concerned with the specifics of the hash function used.
This question assumes that the $hash(m) \rightarrow m'$ function is perfect, and given that, if it is a secure method of encryption.

Assuming that:

the functions $F_k(s) = {\rm hash}(k + s)$ form a pseudorandom function family (PRF) indexed by the key $k$, and
each key is only used to encrypt one message,

then this construction is provably1 secure against chosen-plaintext attacks.

Being a PRF is not a standard property of a cryptographic hash function, so one cannot just assume that any given secure hash function will satisfy it.  A "perfect hash" (i.e. a random oracle) would indeed yield a PRF when used in this manner, but some real-world hash functions might have weaknesses that using them in this way could expose.

Fortunately, however, there's a standard way of converting a hash function into a PRF, called HMAC.2  Thus, you could fix this part of your scheme by using ${\rm HMAC}_{\rm hash}(k; s)$ instead of ${\rm hash}(k + s)$.  Or just use a hash function that does claim to be a PRF when used this way.3

As for encrypting multiple messages, the problem is that, as cygnusv notes, XORing two ciphertexts encrypted with the same key would cancel out the hash outputs, yielding the XOR of the corresponding plaintexts.  If one of the plaintexts is known to the attacker, they can then trivially recover the other.

This limitation would be easily fixed by picking a unique nonce string $n$ for each message and including it in the hash input, e.g. as ${\rm hash}(k + n + s)$ or ${\rm HMAC}_{\rm hash}(k; n + s)$.  Of course, the nonce would have to be stored / transmitted alongside the ciphertext, so that it can be decrypted.

(Also, to avoid attacks due to the ambiguity of concatenation, at least two of $k$, $n$ and $s$ should have a a fixed length; otherwise, it would be possible for e.g. $k = \text{"xyz"}$, $n = \text{"123"}$, $s = \text{"4"}$ to yield the same hash input as $k = \text{"xyz"}$, $n = \text{"12"}$, $s = \text{"34"}$ or $k = \text{"xyz1"}$, $n = \text{"23"}$, $s = \text{"4"}$.  Or you could simply replace the concatenation with some less ambiguous encoding.)

1) The proof is essentially the same as that used to prove the IND-CPA security of CTR mode encryption, except that we don't need the PRP/PRF switching lemma since we already have a PRF, and the requirement that only a single message can be encrypted obviously requires some modification to the IND-CPA game to keep it non-trivial.  A natural choice would be to allow the adversary online access to the encryption oracle, i.e. the ability to submit individual blocks of plaintext, which the oracle will encrypt as successive parts of a single message stream and immediately return to the adversary.

2) Strictly speaking, the standard security proof of HMAC only applies to certain types of hash functions, known as Merkle-Damgård hashes, and only with certain specific assumptions on their internal operation.  That said, most traditional hashes (including SHA-1 and SHA-2) are of the Merkle-Damgård type, and most newer hashes like SHA-3 are explicitly claimed to be secure when used in HMAC, even if they don't use the Merkle-Damgård construction.

3) Off the top of my head, I believe SHA-3 / Keccak effectively makes this claim, via its "flat sponge claim"; of course, if you're using Keccak anyway, it would be even easier to just use its variable-length output, standardized as SHAKE128/256, to generate enough bits to encrypt the whole message from a single hash input.


Can schnorr-signatures be used to ensure public keys are of the correct form (namely $Y= x \cdot G$)? Assume a Schnorr-signature scheme in an elliptic curve setting with a publicly known generator base point $G$ where the the discrete logarithm is hard. That is, given $x \cdot G$, it is hard to find $x$.  I am curious to know if this signature scheme can be used to perform public key validation in the following sense:

Alice provides Bob with a signature $(e,s)$ for some message $m$ and a public key $Y$.
Bob verifies that the signature $(e,s)$ like so:

Calculate $R = (s \cdot G) -  (e \cdot Y)$
Set $e_v = H(R_x || m)$
Accept signature iff $e_v = e$

Can this scheme be used to ensure the public key provided by Alice is indeed of the form $Y = n \cdot G$ (and not say of another form $Y = n \cdot G + n' \cdot G'$?). Assume Alice is computationally bounded and in particular cannot solve the discrete logarithm problem. Or is there a way for Alice to carefully choose the values $(e,s)$ such that Bob accepts the signature even if $Y$ is of them form $Y = x \cdot G + x' \cdot G'$?

As long as the public key is in the elliptic curve group, there is no such thing as being "of the correct form" or not. For any point $P$ in the group, there exists a value $x$ such that $P=x\cdot G$. Thus, all that is necessary is to check that $P$ is indeed in the group. This is carried out by checking (1) that $P=(x,y)$ is on the elliptic curve itself (i.e., it fulfills the equation), (2) that $P$ is not the identity (i.e., the point at infinity, or zero), and (3) that $q \cdot P = 1$, where $q$ is the order of the Elliptic curve group that you are working in. (The third check is needed when the number of points on the Elliptic curve is greater than the size of the subgroup you are working in.)
A completely separate question is whether or not the public-key owner can prove that he knows the associated private-key. That is, do they actually know $x$ such that $P=x\cdot G$. This can be done using a zero-knowledge proof, but actually a Schnorr signature is exactly a zero-knowledge proof of this fact. Indeed, providing an ECDSA signature would also work. However, you need to make sure that this can't be used to extract a meaningful signature that they never meant to sign...


Why are computations (isogeny) in SIDH done in an extended prime field? While reading the SIDH key exchange protocol, I noticed that all the isogeny computations and curves are defined over the extended prime field $\mathbb{F}_{p^2}$. Does it make the problem computationally hard for the attacker or what is the reasoning?

I am an inventor of SIDH. The computations take place in $\operatorname{GF}(p^2)$ just because all supersingular elliptic curves are defined over $\operatorname{GF}(p^2)$, up to isomorphism. It's just the way the mathematics works out. For general mathematical background, see any standard reference, such as Silverman "The Arithmetic of Elliptic Curves."


Pronounceable encrypted text I want to "translate" a text so that its encrypted form should be pronounceable text. Is there any crypto technique that can make encrypted text look as another language? (yet, difficult to decrypt).

The best solution is out of scope for this website. Just apply an algorithm that converts binary data to human-readable pronounceable text.

A simple solution, much like base-64 or diceware, would be to download a dictionary, split binary ciphertext into chunk, and replace each chunk by selecting the nth word in the dictionary. Join the words together using spaces as separators. Punctuation can be added randomly.

The process would be reversed by removing punctuation, splitting on spaces, looking up the index of each word, then joining the binary format of the indices together.

Format preserving encryption is undesirable in this case. English prose is not a simple data format. It would be hard to convert one message to another without leaking some information about the content and/or format of the text.

Chances are also pretty good that readers wanting to implement the same kind of thing as you would roll their own format-preserving encryption algorithm which is little more than a substitution cipher. (Replacing plaintext words with pseudorandom dictionary words, for example.)

Substitution ciphers can be broken with paper and pencil. They put puzzles in newspapers next to Sudoku and comics where people are challenged to do exactly that.

The primary reason I suggest looking at reversible methods of encoding binary data as English text is because I think it's best to work to work on the process of encrypting and of formatting data as two totally independent problems.

When you use normal strong encryption (don't forget authentication), the ciphertext will be indistinguishable from a randomly generated bit sequence. It won't matter if the binary-to-text conversion reveals something about the input because the input is ciphertext. Even side channels in the conversion algorithm wouldn't be a problem if the encryption implementation isn't vulnerable to side-channel attacks.

Therefore, I think you would have better luck if you took that half of the question to StackOverflow.

You should not have high hopes for the results. Procedural generation of text is a difficult problem. It's of interest to AI researchers, spammers, news media, anyone with customer support chat, and artists. Even the most successful algorithms produce text that seems unnatural

It's really hard to generate text which can pass for something written by a real person. Luckily (or not, if you use a spam filter) it's also somewhat hard for computers to tell the difference between human-generated and computer-generated text.

As for what kind of suggestion I would give if you asked on StackOverflow...

I would take word frequency and n-gram frequency into account if the purpose of the algorithm was steganography. "To" is more likely to appear in a normal sentence than "meteorite" is. "Go to" is more likely than "jump bread".

Think of using the auto-complete function on a phone. You could write a random sentence that might look legitimate at first glance pretty easily. You could randomly select the first one or two letters of each word and select from the options given to you. An n-gram based data encoding algorithm might produce pretty similar results.

If steganography is not required (say the purpose of making ciphertext human readable was so that you could send a message over an audio channel or less-than-reliable text channel) then the simple word list encoding method is what I would try. I would make sure the word list doesn't contain homophones or even words with similar or confusing spellings.

(See one of EFF's short diceware word lists. There is one where the first three letters of a word uniquely determines which number it corresponds to and no two words have spellings which are too close to make spellcheck hard. Something like this would be more resilient to typos and misunderstandings.)


Fermats Little Theorem, primitive root So I am studying for finals and I am not able to solve the problem:

Let $ p = 3 * 2^{11484018}- 1 $ be a prime with 3457035 digits. Find a positive integer $x$ so that $2^x\equiv 3\pmod p$

Any guidance or tips would be great. I assumed it dealt with Fermat's Little theorem.

Hint: modular inverses are unique, therefore the following holds:

$$2^x \equiv 3 \pmod{p} ~ ~ \iff ~ ~ 2^{-x} \equiv 3^{-1} \pmod{p}$$

Now what is the inverse of $3$ modulo this particular $p$? Can you express it as a power of two modulo $p$? Solve for $x$. If you end up with a negative $x$, use Fermat's little theorem to derive a positive exponent.


NIST DRBG algorithms' optional parameter As I'm going through NIST-SP-800-90Ar1 spec for DRBG, I found the mention of security_strength in all of the 3 specified construct in the document: Hash_DRBG, HMAC_DRBG, CTR_DRBG. However, they're all noted as optional:

  security_strength: The security strength for the instantiation. This parameter is optional for Hash_DRBG, since it is not used.

and

  security_strength: The security strength for the instantiation. This parameter is optional for HMAC_DRBG, since it is not used.

and

  {3 no df, 4 with df}. security_strength: The security strength for the instantiation. This parameter is optional for CTR_DRBG.

And in the disgraced previous version, there wasn't even mention of this parameter.

What is, or what can we infer as, the rationale for its inclusion?

A partial answer is that the 2012 version of SP 800-90A included a fourth DRBG construction, Dual_EC_DRBG (§10.3.1.2), for which the security_strength parameter was required. Since one DRBG flavor required this parameter, to have a common interface, all DRBG flavors had to take this parameter. In Dual_EC_DRBG, security_strength is used only for one thing: to select the curve.

  Using the security_strength and Table 4 in Section 10.3.1, select the smallest
  available curve that has a security strength security_strength. The values for
  seedlen, p, a, b, n, P, Q are determined by the curve.

Dual_EC_DRBG was retired after it became public that is was probably backdoored by NSA, but its legacy survives in this minor way.

What escapes me is why Dual_EC_DRBG chooses the curve based on the security strength, whereas Hash_DRBG and HMAC_DRBG are parametrized by a choice of hash algorithm and CTR_DRBG is parametrized by a choice of block cipher.


Probability for collisions of a one-way compression function Given a one-way compression function $h:\{0,1\}^n \rightarrow \{0,1\}^m$ and an attacker that picks $x_1 \ldots x_t \in \{0,1\}^n$ (uniformly distributed), I have to show that the probability to find a collision in the picked elements is smaller than $\epsilon$ if $m > log(\frac{t^2}{2 \epsilon})$.
Assumption: $h$ is surjective and has the same number of inverse images for each image.

What I found out already:
Because a binary alphabet is used, I have to show that the probability is smaller than $\epsilon$ if there are at least $\frac{t^2}{2 \epsilon}$ elements that the compression function can map to. And because I want to find a collision between two elements, there are ${t \choose 2} \le \frac{t^2}{2}$ possible combinations for a collision pair in the set of picked elements.

Question:
How can I go on from here and how do I handle the $\epsilon$?

$\left|\hspace{.01 in}\operatorname{Range}(h)\hspace{.01 in}\right| \:$ is the number of elements that the compression function can map to.

If $\: m > \operatorname{log}_{\hspace{.01 in}2}\left(\hspace{-0.03 in}\frac{t^2}{2\cdot \epsilon}\hspace{-0.04 in}\right) \:$ then $\;\; \left|\hspace{.01 in}\operatorname{Range}(h)\hspace{.01 in}\right| \: = \: 2^m \: > \: 2^\left(\operatorname{log}_{\hspace{.01 in}2}\left(\hspace{-0.03 in}\frac{t^2}{2\cdot \epsilon}\hspace{-0.04 in}\right)\right) \: = \: \frac{t^2}{2\cdot \epsilon} \;\;\;\;$.


Security of 64-bit truncated HMAC of Matrix protocol I have seen other questions like this one, but I am asking this specifically in the context of Riot messaging and the underlying Matrix protocol.

A basic summary of their message encryption (using keys derived from the key ratcheting Olm primitive, details in the section "Olm authenticated encryption" in the Olm spec) is that messages are encrypted with AES-256-CBC, then authenticated with truncated HMAC-SHA256. Only the first 8 bytes of the HMAC code are sent with the message.

Doesn't this provide only 64-bit protection against MAC forgery? Wouldn't it make more sense to include at least 128 bits so as to match the security of the Curve25519 identity keys underlying the ratchet?

While the 2012 NIST document linked in this answer states that at least 64 bits of HMAC is recommended, is a higher security margin called-for nowadays?

I once had a similar question, and the answer is that: MAC forgery attack targets interacting parties, where as other types of attack such as key-guessing and message decryption targets static messages.

To attack interacting parties with MAC forgery, you can only know if you succeed after they've replied decryption success/failure indication, by which time they would probably have terminated the communication or re-keyed.

On the other hand, if you've enough money to spend on a supercomputer to crack a 64-bit key to decrypt a ciphertext, you can wait as long as you want, and each failure doesn't cause you to start all over again - you can continue where you left.


Is this hash function almost XOR universal? Consider this hash function:

The key $K$ is $2^n$ bits.  The message $M$ is divided into $2^n$ bit blocks.  Arithmetic is performed modulo $2^{n+1}$. The hash is defined by:

$ H_0 = 1 $.
$H_{i+1} = (2M_i + H_i)\times (2K + 1)$ where K is a (secret) hash key.
Output $H' = \frac{H_{|M|/2^n}}2$

Is this hash (the iterative one) almost-XOR-universal?

Is this hash almost-XOR-universal?

No.

Consider the two 1 block messages $M = \{0\}$ and $M' = \{2^{n-1}\}$.

We have:

$$H(M) = ((2\cdot 0 + 1)(2K+1) \bmod 2^{n+1}) /2 = K$$

and

$$H(M') = ((2\cdot 2^{n-1} + 1)(2K+1) \bmod 2^{n+1})/ 2 = K + 2^{n-1} \bmod 2^n$$

As $H(M) \oplus H(M') = 2^{n-1}$ has a nontrivial probability of being true, $H$ is not almost-XOR-universal.

Similar logic (using the two messages $\{0, 2^{n-1}\}$ and $\{2^{n-1}, 0\}$) will show that $H$ isn't even almost-universal.


What salt should be used when generating TLS 1.3 CertificateVerify message? When signing handshake messages digest, the MGF1 function takes some salt value with same length as the digest has. But what content must be in salt's buffer?
I explored the source code of libnettle, especially method rsa_pss_sha256_verify_digest and found that salt which is used inside is 32 similar bytes - 0x22. Using this value I was able to generate a valid signature myself. But I found no information about the salt in any documentation. How is it actually generated for TLS 1.3 CertificateVerify message? Is this value fixed or depends on certificate or key...?

The salt should be generated randomly. This is how PSS encoding is defined: the salt length is an input, and the encoding process generates a random salt of the specified length. The PSS verification process treats the salt read from the signature as an input which can be an arbitrary string of the expected length.
The TLS 1.3 specification states that the salt length must be equal to the length of the hash. (That's the same algorithm used to hash the input and for the MGF — PSS recommends using the same hash, and TLS 1.3 mandates this.) PSS itself allows longer and shorter salts, but using the hash length is very common, even in contexts other than TLS 1.3 where the salt length is not mandated. The security proof of PSS is based on this common choice, but as far as I know there are no known weaknesses for using a shorter, even empty salt, or a non-random salt.
Choosing a non-random (or too short) salt for PSS can reveal the message, since it makes the message guessable from the signature. This is not a concern for a TLS handshake since the message itself contains a random input (ClientHello.random and ServerHello.random).


Can you help me to understand the mode XCBC of authenticated-encryption? I read: "$Z_0$ serves as an initial vector for CBC-like encryption, R is used to post-whitening each ciphertext block $C_i$ by $i ∗ R$".

but I don't understand what is the "post-whitening". Can you help me to solve this problem?

Wikipedia states that key whitening increases security:

In cryptography, key whitening is a technique intended to increase the security of an iterated block cipher. It consists of steps that combine the data with portions of the key.
The most common form of key whitening is xor-encrypt-xor -- using a simple XOR before the first round and after the last round of encryption.
The first block cipher to use a form of key whitening is DES-X, which simply uses two extra 64-bit keys for whitening, beyond the normal 56-bit key of DES. This is intended to increase the complexity of a brute force attack, increasing the effective size of the key without major changes in the algorithm. DES-X's inventor, Ron Rivest, named the technique whitening.
In cryptography, key whitening is a technique intended to increase the security of an iterated block cipher. It consists of steps that combine the data with portions of the key (most commonly using a simple XOR) before the first round and after the last round of encryption.

The "post-whitening" consists into applying the whitening after the encryption function: encrypt-xor.


I want forgery ECDSA when prime p is form of 2*n+1, n is order of Elliptic curve I have parameters of an elliptic curve s.t $p=2n+1$ , when $n$ = order of elliptic curve over finite field of order prime p.

If I want to forge any message for such ECDSA, What can I do? Maybe the condition $p=2n+1$ will be helpful, but I have no idea for this.

Hasse's theorem on elliptic curves tells us that, using your notation:
$|n-p+1|\le2\sqrt{p} \Rightarrow |n-(2n+1)+1)|\le2\sqrt{2n+1}\Rightarrow n\le2\sqrt{2n+1}$ which doesn't hold for $n>8$.

So either your curve is so small you can solve the ECDLP by hand or you are not defining an elliptic curve.

Could it be that the order of the curve is $2n$ but you are just working in the large prime order group (of order $n$)?
Because in that case $n$ divides $p-1=2n$ and you can mount a MOV attack.


Chosen Plaintext Attack on DES/AES PERSON A sends messages to  PERSON B using AES, CBC, PKCS5Padding with an IV that is incremented by one after each message. If PERSON Z knows that the first block of the plain-text of any message is either "Yes" or "No", can she launch an attack that decrypts the first block of a given message?
  Hint: Chosen Plaintext Attack

My answer is I do not think it is possible to mount an attack that decrypts the first block because of the avalanche effect. Any changes, whether if it is the size or the content, atleast 50% of the content in CT changes.

Is there anything missing or totally wrong in my answer??

Let's say we have a message (sent by Person A) encrypted with CBC using the IV $x$, and the first block of the message is either "Yes" or "No".  We also assume the attacker has the capability of requesting the encryption of arbitrary chosen plaintexts (though he doesn't control the IV - it is always incremented after each encryption request).  Let us also say the IV is predictable by the attacker (an incremented IV is predictable so long as the attacker always knows and/or can control when the encryption function is used).  In other words, the attacker knows that if he requests the encryption of some plaintext then the IV used to encrypt it will be $x \oplus k$ for some value $k$.  Let's denote the IV the attacker predicts will be used if he makes a request by $IV_z$ ("z" for Person Z), i.e. $IV_z = x \oplus k$.

In which case the attack is simple: Request the encryption of a plaintext where the first block is "Yes" $\oplus$ $k$.  Because of how CBC works, the first block of ciphertext, $C_z$, will be: $C_z = E(Yes \oplus k \oplus IV_z) = E(Yes \oplus k \oplus x \oplus k) = E(Yes \oplus x)$.

Now the attacker compares $C_z$ to the first block of the encrypted message sent by Person A, which we will denote as $C_a$.  If the message sent by Person A started with a "Yes" then $C_a = E(Yes \oplus IV_a) = E(Yes \oplus x)$.  So if the message started with "Yes" then $C_z = C_a$.  Conversely, if the message started with "No" then $C_z \neq C_a$.  So simply by comparing $C_z$ with $C_a$ the attacker can easily determine the first block of the message.