Computationally expensive key derivation whose difficulty is asymmetric I am looking for a primitive or a construction that meets the following requirements. Is such a construction (a) theoretically possible, and (b) in existence right now?

Given are:

a long secret $X$
a authenticated cipher that takes a key $K$ with encryption function $\mathcal{E}_K$ and decryption function $\mathcal{D}_K$
a trusted server $S$
a set of trusted clients $C$
an attacker

Every client has a copy of $X$ in the encrypted form of $\mathcal{E}_K(X)$, where the decryption key $K$ is the same across all clients. I am trying to find a pair of functions $\mathcal{F}_S$ (on the server) and $\mathcal{F}_C$ (on the clients) such that $\mathcal{F}_C(Y, e) = \mathcal{F}_S(Y) = K$, where $e$ is a cost factor and $Y$ is a secret value that varies between each client.

I need $\mathcal{F}_S$ to be computationally inexpensive so that the server can generate many different values of $Y$ (to provision many different clients) quickly, yet all clients arrive at the same value $K$ with which to decrypt secret $X$. On the other hand, I need $\mathcal{F}_C$ to be computationally expensive so that it is prohibitively computationally expensive to the point of infeasibility for an attacker to (a) guess a valid $Y$ given only $\mathcal{F}_C$ and $e$ (i.e. Kerckhoff's principle applies for $\mathcal{F}_C$ with respect to $Y$), and (b) derive a new tuple of $(Y_1, e_1)$ given an existing tuple $(Y_0, e_0)$ that is known to the attacker to generate $K$.

Similar issues have already been solved in other contexts.

Key derivation functions such as HKDF per se are not news. However, they do not seem to allow fixing the output value to generate a series of input values that all generate the same output value.

Computationally difficult functions exist in the context of passwords (such as Argon2, scrypt, bcrypt, PBKDF2). However, not only do these suffer the same issue as key derivation functions in general, but these are symmetrically expensive, which means that the load on the server is immense when provisioning clients.

I've also thought about approaching this issue by making the client perform a brute-force computation of varying missing parts of $K$, but this gives attackers an undue advantage if the missing parts must be chosen such that computationally weak clients can finish the brute force search in less than a minute, but an attacker (a) is able to parallelize and very quickly run the brute force search to recover $K$, and (b) having determined $K$ is able to trivially generate their own $K$ with missing bits.

Another attempt involved a Diffie–Hellman protocol, but it seems infeasibly difficult to fix the shared secret and generate two inputs that then yield the fixed shared secret.

The immediately obvious way to do this is to use RSA in a large-public-exponent format.

That is, the server selects an RSA modulus, and a large public exponent (say, $e = 2^{2^{30}}+1$) [1]; if the RSA primes are safe primes, this practically eliminates the possibility that $e$ is not relative prime to either $p-1$ or $q-1$.  The server would internally compute the CRT parameters (which are the same size as for normal RSA with the same modulus size, and the large $e$ value does not complicate this computation), and publish the public parameters (the modulus and the large $e$ in some compressed format; e.g. if it's always in the form $2^{2^x}+1$, we might just denote $x$).  We would also select a good RSA encryption padding method, such as OEAP.

Then, we have $\mathcal{F}_C(Y) = \text{Depad}( Y^e )$ (where $\text{Depad}$ is the procedure for removing the RSA padding); to compute $Y$, the server would take $K$, randomly pad it, and then perform the RSA private transform.

The client would need to perform $O( \log e )$ modular multiplications to compute $\mathcal{F}_C$; by selecting $e$ sufficiently large, we can make this as expensive as we like.  And, while the inverse computation of $\mathcal{F}_S$ isn't exceptionally cheap (it's about as expensive as generating an RSA signature or doing an RSA public key decryption), it isn't that bad (and we could reduce the cost somewhat if we used multiprime RSA).  And, if the server had some RSA acceleration hardware (which is not rare), this can be even cheaper.

Obviously, this is not the normal use of RSA, either as a public key encryption method, or as a signature method.  It is still a valid use of the concept.

[1]: Note: I'm using $e$ to describe the public exponent we give to the client, not the cost factor (as the question used it).


Why does Carter-Wegman (and AES-GCM) use different keys for PRF and keyed-hash So. As I understand, Carter-Wegman transforms a one-time MAC (which must be a difference unpredictable function (DUF)) by encrypting it with a PRF.

The DUF and the PRF use two different keys, which can be understandable if:

you're just being precautious and not mixing keys
the PRF and the DUF might take keys of different sizes/format

Now, AES-GCM uses AES and GHASH which both take keys of size 128-bit. So why don't they use the same key?

Let's consider a degenerate case. Suppose you're authenticating 16-byte messages, your DUF (better known as (almost) xor-universal hash) is $\text{AES}_k$, and your PRF is also $\text{AES}_k$. Then you have
$$
\text{WC}(m, n) = \text{AES}_k(m) \oplus \text{AES}_k(n)\,,
$$
where $m$ is your 16-byte message, and $n$ is a 16-byte nonce. This is obviously forgeable by simply switching the nonce and the message! Yet, it would be perfectly secure if we used independent keys for each primitive.

In less degenerate cases, such as GCM, you could possibly use the same key for both. But you would have no easy way of arguing the security of the scheme, since the hash and the PRF would not be independent.


Parameterizing adversaries with security parameters In many cryptographic games, the adversary doesn't seem to be parameterized by the security parameter.‡ Are such games equivalent to variants in which the adversary is parameterized by the security parameter?‡‡

‡ E.g., Bellare et al.'s IND-CPA (Crypto'98) defines: $(pk,sk) \leftarrow K(1^k)$; $(x_0,x_1,s) \leftarrow A_1(pk); ...$, i.e., $A_1$ isn't taking $1^k$.

‡‡ E.g., is the game above equivalent to: $(pk,sk) \leftarrow K(1^k)$; $(x_0,x_1,s) \leftarrow A_1(pk,1^k); ...$.

The adversary should definitely always be "allowed to know" the security parameter. In other words, a security definition should allow the adversary's behavior to depend on the security parameter. This can be accomplished either by quantifying the adversary after the security parameter is chosen, or by letting the security parameter be an explicit input to the adversary.

The alternative would fly in the face of Kerckhoff's principle -- since the adversary is not allowed to "know" the security parameter, it would mean that the scheme is (apparently) deriving some important property from the secrecy of the security parameter.

Nonetheless, here are some valid reasons why this dependence on security parameter might be omitted in the notation:

Authors are lazy, the extra parameter to the adversary is cumbersome to write, and the intended audience probably knows the standard conventions about security parameters.
In an earlier section, authors have said "all algorithms are assumed to take a global security parameter as common input" or something along those lines.
The adversary already gets to see certain things from which it could infer the security parameter anyway. So it is redundant to give the security parameter explicitly. For example, the adversary sees a public key in some security game, and the length of the public key is the security parameter. Especially in things like public-key crypto, it is without loss of generality that you include the security parameter in the public key.


Avoid decrypting every password in a password manager The Setup

I'm making a password manager for fun. It stores a random encryption key, encrypted with a key derived from the master password, and then it stores the data, which is a list of (site, username, password) triples, encrypted with the encryption key. Here, encryption means calling libsodium's secretbox, which is authenticated encryption.

The Problem

I wanted to avoid decrypting every single password just to get a single one. Since the database still needs to be searchable, all the metadata still needs to be unencrypted in one go. So I came up with two different strategies:

Keep the passwords in a separate dictionary, indexed by hash(encryption_key ++ data).
Encrypt the password before storing it in the triple, which is then encrypted again. This idea sounds terrible, because double encryption scares me.

My questions are:

Is my setup secure?
Is it reasonable to avoid decrypting every password?
Which of the two aforementioned strategies are secure, and is there a simpler way to encrypt passwords only as necessary?

Sorry if this question is too specific, I'd be happy to try to make it more general.

I understand your design goal, but I see an issue in that you propose to encrypt the metadata alongside the passwords.  Searching is made more complicated because you have to decrypt the database to expose the metadata to search for the associated password.

Instead, consider storing only encrypted, unique passwords in your database, indexed by a secure hash of the site/username metadata.  For any new site that requires a password, locate a slot indexed by $H(meta)$. Generate a unique password for that site, encrypt it with the master, and store it at the hash slot. Give the plaintext to the website.

To access the password later, reverse the steps.  This lets you encrypt only the passwords, and uses a strong hash function to protect the mapping between the site and the password even in the event of a disclosure of the master password.

[A few edits later,] Here is a protocol that might work.  It assumes you have a secure hash function $H$, a wallet $W$ indexable as a dictionary with no entries to start, and a secure master password $m$.  Assume $E_p(data)$ means to encrypt data with key $p$, and $D_p(data)$ means to decrypt.  Let $meta$ be a tuple representing the site name, user name, cookie, or anything else that makes sense to include for retrieving a password.

When visiting a site $s$:

Let $i \leftarrow H(meta)$.
If $i \not \in W$, then this is the first visit to the site (with this meta tuple); generate unique password $p_s$ (conforming to the policy at $s$) and encrypt with $E_m(p_s)$ and store at $W[i]$.
If $i \in W$, then site has been visited before, therefore retrieve site password $p_s \leftarrow D_m(W[i])$.

The benefits are that you decrypt only a single password for each site $s$.  The master password $m$ is used only for site password protection, not for the metadata.  The identity of the sites and meta information are protected with a hash function.  With a fast implementation of $W$, lookup can be as fast as $O(1)$.  A dictionary indexed by a hash can grow dynamically, better than my previous edit.

On the downside, if the adversary has access to $W$ and meta information on $s$, he can tell that you have an account on that site.  By encrypting the entire database including metadata, your original design is secure against this threat.

I haven't thought more than a day on this, so there may be a weakness - hopefully someone will comment and I'll continue to revise it.


How can I resolve this basic MAC paradox I’m stumbling upon in my proof? Suppose $S: K \times M \to T$ is a secure MAC. ($K$ = key space, $M$ = message space, $T = \{0,1\}^n$ = tag space.)

$S$ being secure means that no matter what messages $m_1,...,m_q$ we throw at $S$ to get back tags $t_1,...,t_q$:

$\{ (m_1,t_1),...,(m_q,t_q) \}$

we cannot subsequently find another message-tag pair $(m,t)$ that is not in the above set. In other words, we cannot find a forgery $(m,t)$.

Let's create a new MAC $S'$ based on $S$:

$S'(k,m) = (S(k,m), S(k,0^n))$

It is clear by example that $S'$ is not secure. The attack is simple: Throw at $S'$ some $m \neq 0^n$, and extract the value $s = S(k,0^n)$ out of the tag. Then, the message $0^n$ and tag $(s,s)$ is our forgery.

Here is the paradox. I believe I can prove that if $S'$ can be forged, than so can $S$. This would prove that if $S$ is secure (as we assumed), $S'$ is secure! There must be something wrong with my proof, so my question is, what is wrong with the following proof?

Assume $S'$ can be forged. In other words, we have thrown at $S'$ messages $m_1,...,m_q$ and gotten back the tags $t_1 = S'(k,m_1), ..., t_q = S'(k,m_q)$ and subsequently obtained a forgery message-tag pair $(m, t = S'(k,m))$ such that

$(m, S'(k,m)) \notin$ $\{ (m_1,S'(k,m_1)),...,(m_q,S'(k,m_q)) \} $

In other words,

$(m, (S(k,m),S(k,0^n))) \notin$ $\{ (m_1,(S(k,m_1),S(k,0^n))),...,(m_q,(S(k,m_q),S(k,0^n)))\}$ (*)

Then it seems obvious that the following is our forgery on $S$:

$(m, S(k,m)) \notin$ $\{ (m_1,S(k,m_1)),...,(m_q,S(k,m_q)) \} $

because $(m, S(k,m))$ being an element in that set would contradict (*).

That's the end of my proof. There must be something wrong with it. The question is, what?

Your attack on $S$ involves computing $S'(k,m_i)$ for arbitrary messages $m_1,\dots,m_q$. In order to do that, you must compute $S(k,m_i)$ and $S(k,0^n)$, and thus you have obtained $S(k,0^n)$. This means that $0^n$ must be added to the list of invalid forgeries, and so in order to present a valid forgery for $S$, you must have
$$(m,S(k,m)) \notin \{(0^n,S(k,0^n),(m_1,S(k,m_1)),\dots,(m_q,S(k,m_q))\}.$$

But you do not know how to do that: the only known attack on $S'$ precisely involves computing $S(k,0^n)$. More precisely, the attack goes like this:

Compute $S'(k,m)$ for some $m \ne 0^n$.
Output $(0^n, (s,s))$ as a forgery for $S'$ (where $s = S(k,0^n)$).

Then, you present $(0^n, s)$ as a forgery for $S$, but this is not a valid one.

The exact point where this error manifests itself in your proof is when you write

  because $(m,S(k,m))$ being an element in that set would contradict (*).

This assumes that if $(m,S(k,m))$ is in the second set, that necessarily means that $(m,S'(k,m))$ is in the first one. In other words, that if a "request" for $S(k,m)$ was made, it necessarily means that a request for $S'(k,m)$ was made as well. This is, again, not correct: it is possible to make a request for $S(k,0^n)$ without making one for $S'(k,0^n)$.


What is the correct format for a CRLF in a SSL certificate's pem Currently I am working with SSL certificates inside a Ruby on Rails application.

I am storing the certificates in a database along with the corresponding  dhparam, and chain. At some point I want to render these fields into real files and publish them to a server.

Although the published certificates work in the client's browser we got in massive trouble with a couple of other apps (including golang services, amazon cloudfront, ...) telling us that the certificate is not correct (e.g. x509: certificate signed by unknown authority).

So I had a look at the certificates that were rendered. The only difference I was able to find is that Ruby's OpenSSL library returns the certificate with a different carriage return than I was used to:

-----BEGIN CERTIFICATE-----\n
MIIDhDCCBWygAwIBAgIQDyh/z7hUIji7pFcz+75NWTANBgkqhkiG9w0BAQsFADCB\n
kDER ...

but the original, raw string looks like this:

-----BEGIN CERTIFICATE-----\r\n
MIIDhDCCBWygAwIBAgIQDyh/z7hUIji7pFcz+75NWTANBgkqhkiG9w0BAQsFADCB\r\n
kDER ...

And here's how I rendered the certificate:

certificate = OpenSSL::X509::Certificate.new '<raw certificate>'
certificate.to_pem # => This returns the \n formatted certificate

Could the different format of the CRLF be the root of the problem? Are both formats valid?

No, x509: certificate signed by unknown authority shows that the certificate of the Certificate Authority or one of the intermediate certificates issued by it is not present at the other party. It could be that the certificate is very new and it hasn't yet been taken into account, or that the certificate was not received or accepted by the parties you mention. Even more likely is that an intermediate certificate is missing so that the chain to a trusted certificate cannot be made.

To look up the certificates above it the certificates look up the issuer certificate which is referenced by the certificate you send them. Then using that certificate the next certificate is looked up. Finally the signatures within the certificates are verified and the other information (validity period etc.) are validated. This is called chain validation. This ends with a trusted certificate, often the self signed root certificate of the CA.

Obviously to even try to look up the "parent" certificate the certificate must first be parsed. You'd expect another error if the certificate could not be parsed at all.

As for the carriage return: openssl returns only a line-feed character - as most unix utilities probably will. But any implementation that doesn't accept CRLF or even just CR (for Apple) will be in serious trouble, so I don't think you'll find many libraries / applications that won't accept any kind of line ending (and certainly not Amazon etc.).


Padding in Keccak SHA3 hashing algorithm In FIPS-202 specification, the padding required for SHA3 were not clearly mentioned. so we have analyzed the NIST test vectors for SHA3, which states that append "0x06" (never used 1 followed by 'j'zeros and then 1 specified in FIPS-202) to the message digest, which is a contradiction to the specification.

The link for NIST test vector is :-

http://csrc.nist.gov/groups/ST/toolkit/examples.html#aHashing

http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/SHA3-224_Msg0.pdf

could you clarify padding mechanism  for SHA3?

In FIPS-202 specification, the padding required for SHA3 were not clearly mentioned.

I beg to differ. From the FIPS 202. section B2.:

  For most applications, the message is byte-aligned, i.e., $len(M)
= 8m$ for a nonnegative integer $m$.

  In  this  case,  the  total  number  of bytes,  denoted  by $q$,
  that  are  appended  to  the  message is determined as follows by
  $m$ and the rate $r$:
  $$q = \frac{r}{8} – (m \bmod{\frac{r}{8}})$$

  The  value  of $q$ determines  the  hexadecimal  form  of these  bytes
  in  this  case according  to  the conversion  functions specified in  Sec.  B.1.  The  padded  messages  that  result  are  summarized  in
  Table 6:

+-------------------------+--------------------------------+
|                         |                                |
| Number of padding bytes |       Padded message           |
|                         |                                |
+----------------------------------------------------------+
|                         |                                |
|         q = 1           |  M || 0x86                     |
|                         |                                |
|         q = 2           |  M || 0x0680                   |
|                         |                                |
|         q > 2           |  M || 0x06 || 0x00... || 0x80  |
|                         |                                |
+-------------------------+--------------------------------+

  the notation 0x00... indicates the string that consists of $q – 2 $ “zero” bytes.

If you look at your test vector, for $\operatorname{SHA3-224}$. $224$ means $224$ bits of security. So we have $c = 224 \times 2 = 448$ and $r = 1600 - c = 1152$.

Because message is empty, $len(M) = 0$, therefore $m = 0$. Hence $$q = \frac{1152}{8} - 0 \bmod \frac{1152}{8} = 144$$

Therefore we are in the third case: ($q > 2$).

The padding will be : 0x06 || 144 - 2 zeros || 0x80.Therefore we find back the data to be absorbed :

06 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 80

06 followed by 284 0 (or 142 00) then followed by 80. The followings 00 are provided to show that the capacity won't change during the absorption.


Plaintext with 'T' and 'E' alphabets missing and encrypted with Vigenere Cipher I wrote the normal code to decrypt a Vigenere cipher encrypted text without knowing the key. But that won't work for this are two of the alphabets are missing and that would mess up the frequency analysis. Any idea on how to go about decrypting it?

frequency analysis works just fine even without a few common letters. In fact you don't even need to know the frequency in the underlying alphabet it is sufficient that it is far from uniform. You can rotate the columns so as to make the frequencies in each match.
Alternatively using an English bi-gram frequency table you can break this quickly even without two letters.

Do you know if the letters were removed from plain text in preprocessing or is this a clever text without these? it makes no difference for first method but some if you bring in external frequency tables.


How is a block-chain stored? Background of the problem: I am undertaking a blockchain course at University and I have taken up a case study for blockchain that relates to logistics. The requirements are simple, yet I am confused with the storage segment of blockchain. Given that we have a table of deliveries to be made, I incorporate certain fields of the table into the blockchain.

Problems Faced:

Would the data (payload of the block) be stored as plaintext?
And how would I verify that the table hasn't been tampered with and it satisfies the blockchain?

It depends on what blockchains are you talking about and what you considered as plaintext.
For example, in Bitcoin, the transaction includes the signature, public keys, amount etc., and the amount being transferred is in plaintext. For Monero, the transaction includes more elements (i.e. a list of public keys, a signature, commitment to the amount), amounts are encrypted in a way that the only recipient can open.
The hash of the current block is the hash of the data in the current block and the hash of the previous block (i.e. $B_i = h(B_{i-1}, \{tx| tx \in B_i\})$). So what happened when you modified the data in block $B_{i-1}$? $B_{i}$ will change.
If you understand how $\mathsf{git}$ works? it's very similar. It's more interesting to see how the network agrees on a single chain.


Strange notation using dollar sign In the paper Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma, the authors Bellare and Neven use notation which looks like left arrow with dollar sign above it.

Authors provide an explanation for one variable:

  $s \overset{{\scriptstyle \$}}{\longleftarrow S}$ denotes the
  operation of assigning to $s$ an element of $S$ chosen at random

However, in this paper they use it with multiple variables like this:

  $s_1, \ldots, s_N \overset{{\scriptstyle \$}}{\longleftarrow S}$

What is the definition of this notation? Can we chose dependent random variables for $s_i$? Do we must choose all variables $(s_1, \ldots, s_N)$ at once from the set $S^N$ with uniform distribution?

$s_1, ..., s_N \stackrel{\$}{\leftarrow} S$

means coordinate-wise sampling:

$s_1 \stackrel{\$}{\leftarrow} S$

$s_2 \stackrel{\$}{\leftarrow} S$

...

$s_N \stackrel{\$}{\leftarrow} S$


PBKDF2 without salt on 16 digit password How secure would be to use PBKDF2 without salt (or with the same salt for all) with a 16 digits passwords that are unique and randomly generated (there can't be two identical)?

Assuming an adversary with large resources and technical know how, How fast someone would be able to identify password using 10000 or 50000 iterations?

TL;DR: If an attacker can gain less than 50k-100k USD from breaking all the "passwords" you're fine, else you could be screwed. (for 10k iterations, using SHA-1 for PBKDF-2)

  How secure would be to use PBKDF2 without salt (or with the same salt
  for all) with a 16 digits passwords that are unique (there can't be
  two identical)?

It would keep medium-scale companies and smaller attackers from getting the passwords, but would fail to do so for larger scale attackers.
The exception being of course an attacker that already has the right scale of infrastructure ready-to-use (first noted by Maarten Bodewes)

The reason for this is documented in the answer to the next (sub-)question.

  How fast someone would be able to identify password using 10000 or
  50000 iterations?

Let's assume you'd use 10,000 iterations (multiply everything with $5$ for 50k). This would mean to search the entire password space you'd have to do 10k SHA-1 iterations per entry. There are $10^{16}$ entries, so that's $10^{20}$ SHA-1 hashes in total.

Now let's have a look at how many SHA-1 hashes a modern GPU (a Nvidia GTX 1070) can calculate per second: 6.3GHashes/s which is $6.3\times 10^9$ hashes per second. Now multiply this with $60^2\times 24$ to get the number of hashes per day: $5.4\times 10^{14}$. So you'd need $10^{20} / (5.4\times 10^{14})\approx 180,000$ days with a single GPU. Now - just for fun -  let's calculate how much 400 GTX 1070 (roughly 500€ a piece) would cost (they'd take roughly 450 days to search the entire key space): $400\times 500\approx 20k$ euro. This is the hardware cost. Additionally you'd need to pay for electricity and other stuff and if you want to be faster you need either FPGAs, better GPUs, ASICs or more GPUs. Now I think with the additional infrastructure, the deployment and the electricity you may end up at 50k-100k USD (and maybe you've bought a few more GPUs ;). So if an attacker can gain this amount of money by breaking your system, you should adapt and if not you're probably fine.

Note that this is an example calculation. An attacker could also very well try and rent high-end GPUs in the cloud, possibly reducing cost and management overhead (first noted by Maarten Bodewes).


Is there a 3-D alternative for elliptic curves? As I understand the most widely used method to exchange encrypted data over untrusted network is Diffie-Hellman protocol. Protocol itself doesn't define how to encrypt data, but it defines a usage pattern of public/private keys and implementation can vary.

So, original idea was to use big prime numbers (1 number, 1-D) and their combinations as public/private keys. After a while elliptic curves (x and y coordinates, 2-D) was discovered, so now everyone using them.

Do elliptic curves have more cryptographic strength than classical approach because of 2 dimensions? Is there any research related to 3rd (or even more) order polynomial that potentially can provide even more cryptographic strength than elliptic curves?

So, i've just started to figure out how encryption works.

From what you've said, I fear that's not true.

  As i understand the most widely used method to exchange encrypted data over untrusted network is Diffie-Hellman protocol.

Partially true, as DH is used as key agreement protocol to further derive session encryption & MAC key. DH is asymmetric, where as encryption and MAC (message authentication code) are symmetric.

  So, original idea was to use big prime numbers (1 number, 1-D) ... After a while elliptic curves (x and y coordinates, 2-D) was discovered, so now everyone using them.

The original realization of the idea was to use a big prime number, but those numbers that can be represented in binary system have a exploitable structure make possible attacks faster than brutal-force search.

DH is still realized using scalars, except this time, the scalars are points on elliptic curves over finite fields.

  Question is - do elliptic curves have more cryptographic strength than classical approach because of 2 dimensions?

No, they are stronger because they don't have the same exploitable structure as (big) integers.

  Is there researches related to 3-rd (or even more) order polynomes that potentially can provide even more cryptographic strength than elliptic curves?

Yes, one of my questions here attracted this comment, but I haven't thoroughly comprehended it, I advise you read it with care if you have time.


Cryptanalysis of MD4 (Wang et al) -- how did the authors come up with the collision differential? Edit:
ok, after I re-read the paper a couple of times it is clear that Table 6 is  easily derived from Table 5, which describes the collision differential. So the real question is: how did the authors come up with the collision differential?

Original question:

The paper Cryptanalysis of the Hash Functions
MD4 and RIPEMD describes a set of sufficient conditions for collisions of MD4 (Table 6 in the paper). The authors explain how to verify these conditions, but there is no info about how they got them in the first place. I'm curious, what could be a possible procedure?

I've found the following tweet:

  [...] all the papers I've read say that she found the right difference patterns by "intuition"

(https://twitter.com/ghostly_gray/status/906009834755055617)

I'll happily accept another, more specific answer!


Standard symbol / notation for "x knows y", or the inverse What's the standard way to express "$x$ knows about $y$", or "$x$ has no knowledge of $y$" in cryptographic notation?

Example (PRNG predictor):

$\exists f : P(f(G(k)|_{0..n}) = G(k)|_{n+1}) \geq 0.5 + \epsilon$, for non negligable $\epsilon$, where $f$ has no knowledge of $k$.

The notation is "", i.e., the empty string. $\;\;$ Since $k$ is not an input of $f$, $f$ has no knowledge of $k$.


RSA hybrid decryption via PKCS#11 - unwrap or decrypt? I have an application that does RSA hybrid encryption/decryption – i.e., messages are encrypted with a fresh AES key, which is then itself encrypted with RSA-OAEP and sent with the message. Decryption then does the reverse.

I want to now provide support for hardware security modules (HSMs) via PKCS#11. (The application is written in Java, so this will actually be via some wrapper such as the default SunPKCS11 library). I can see two options for implementing decryption:

Use the HSM to decrypt the temporary AES key and return the raw bytes of that key to my application, which then does the AES decryption in-memory.
Use the HSM to “unwrap” the AES key as a (sensitive) session object and then use the HSM to perform the AES decryption.

My instinct is that option 1 will generally be faster than option 2 on a server with AES-NI instructions. As the AES keys are unique to each message, it also doesn’t seem less secure - the AES key is therefore no more sensitive than the message itself.

Are there any reasons to prefer option 2? My only thought is that if a customer has spent a lot of money on a FIPS-compliant HSM then they may want all crypto to be performed on the device for compliance reasons. Is that a likely scenario?

The AES is just used to protect the data. And although keeping the AES key in the HSM is more secure, you need to remember that there is little reason to protect it any better than the data itself.

However, if you don't need the speed, why not go for the HSM option? At least you'd be reasonably sure that the key is secure, that there are no side channel attacks and that the algorithm will operate as designed (e.g. with regards to random generation of the IV, self tests, destruction of the key etc.).

So use AES in software if you require the speed, HSM resources or low latency. Otherwise use the AES key in the HSM if you don't require it.


How is asymmetric cryptography safe if one of the keys is public? Let's suppose $A$ is sending a message $m$ to $B$ using asymmetric cryptography.

To guarantee the authenticity of a message, $A$ encrypts $m$ with $A$'s private key: $E(m, k_A) = m_A$.

Then, $A$ sends $m_A$ to $B$.

$B$ can check that $m_A$ was sent by $A$ using $A$'s public key $p_A$, by doing $D(m, p_A) = m$.

If the public key $p_A$ is, by definition, public, if an attacker intercepts the communication and get $m_A$, he could easily find $m$.

How is asymmetric cryptography safe under these conditions?

How is asymmetric cryptography safe under these conditions?

Well, you sort of outlined (but see kelalaka's corrections) how you would use asymmetric crypto to do authentication; that is, to make sure that the message was actually sent from $A$.

You ask "how does that provide privacy?".  The answer, of course, is "if that's all you do, it doesn't".

If we want to do privacy, that is, generate an encrypted message that only $B$ can read is that $A$ encrypts $m$ with $B$'s public key, that is, $E(m, p_B) = m_A$.  We then send $m_A$ to $B$.  $B$ can then take his private key and compute $D(m_A, k_B) = m$, recovering the original message.  No one else can read the message, because only $B$ knows $k_B$, and that's needed to decrypt the message.

Two notes:

If we need to provide both authentication (only $A$ could have generated the message) and privacy (only $B$ could read the message), we do both; $A$ might generate the ciphertext $E(m, p_B) = m_A$, and then sign it with his private key $Sign( m_A, k_A ) = s_A$ and then send both $m_A$ and $s_A$.  $B$ can then verify the signature (with $A$'s public key), and then decrypt the message (with $B$'s private key).
In practice, if we need to encrypt a long message, what we generally do is pick a random symmetric key (which is short), and use the public key encryption to encrypt the key, and then use the symmetric key to encrypt the message.  Symmetric encryption is far more efficient than public key crypto, and so this is a significant performance gain over using the public key encryption method multiple times to encrypt the message.


Possible problems in using a hash algorithm to construct a stream cipher I'll define an example hash-based stream cipher as such:

$H: \{0,1\}^* \rightarrow \{0,1\}^{256}$ is the hash function.
$K=\{0,1\}^{256}$ is the secret key.
$N=\{0,1\}^{128}$ is the nonce.
$C=\{0,1\}^{128}$ is the counter.
$X=H(K||N||C)$ is the keystream output.

I've read several of the questions posed on this site about basing a stream cipher on hash functions. One of the replies said that the properties that make a hash function "secure" might not be enough to make a secure stream cipher. Would having the outputs of many similar inputs make it possible to calculate $K$?

It would be good to define what you require for the cipher to be secure before trying to determine it's security properties. Take the example of CPA security - Katz and Lindell (Introduction to Modern Cryptography 2nd ed.) state that a symmetric scheme has indistinguishable multiple encryptions under chosen plaintext attack (i.e. the scheme is CPA secure for multi-encryptions) if the following relation holds in the so called "Left - Right Oracle" Game:

$ \textbf{Pr}[\textbf{PrivK}_{\mathcal{A},\pi}^{LR-cpa}(n) = 1] \leq 1/2 +  \textbf{negl(n)}$

where $\textbf{K}$ is an encryption key of length $n$ and $\textbf{negl}(n)$ is a "negligible'' function in $n$ (this relation is a re-statement of definition 3.23 in the above text by Katz and Lindell)

Given the above definition of CPA security, it can be shown that CTR modes are CPA secure so long as the underlying "block cipher" is a pseudo-random function and you are dealing with a "q-query" adversary, i.e., you are limiting the number of oracle queries by the adversary to $q$ such that $q^{2}<< 2^{n}$ where $n$ is the size of the block (cf. so called "CTR Mode Theorem" over here:
http://spark-university.s3.amazonaws.com/stanford-crypto/slides/04.5-using-block-annotated.pdf)

If your underlying "block" is a PRF and you have constructed a proper randomized counter mode, then your scheme would be "CPA secure" by the results stated above.

If you require CCA security, on the other hand, your scheme would need to be non-malleable in the manner of authenticated encryption schemes. So the answer to your question on security depends partly on what you require or what you wish to achieve from a security definition standpoint.


Inside attack (attack from participants) in secret sharing I have considered a $(t,n)$ secret sharing scheme with $n$ secret, say $a1,a2....an$. It's third party secure, but it has inside adversaries. While reconstructing secrets, a group of $t$ qualified participants upload their data to a public server.
If $t-1$ participants are cheaters, they can fool the remaining participants by changing the secrets.
How I could make this attack scheme such that the $t1$ participant can assign a chosen polynomial (i.e., chosen secrets) to fool the remaining participants.
I am aware that the number of secrets is one (i.e., constant term in the polynomial), which M.Tompa & H. Woll proved.

I think you are mis-understanding secret sharing and what it can and cannot do. In a $(t,n)$ secret sharing scheme, the server/trusted party creates $n$ shares of the secret. At least $t$ shares must be present in order to recreate the secret from the shares. Now, if after reconstruction, the secret itself is revealed to the $t$ share holders requesting re-construction, then they each know the secret, and it is possible that the secret will be revealed milliseconds after the shares have been distributed when at least $t$ shareholders promptly send their shares back with a request for reconstruction! "Don't given me a share of the secret, just tell me the secret!" would be the rallying cry. Whether the reconstructed secret is also provided to the other $n-t$ shareholders and not just the $t$ requesters is an open question.

The way secret sharing is meant to operate is that reconstruction of the secret enables some further action (e.g. making a payment) that can be authorized by any $t$ shareholders but doesn't require approval of all $n$ shareholders. The secret is the password that is used to authorize the action. Thus, setting $t > \frac n2$ would mean a majority of the shareholders approve taking the further action and so authorize it. The secret itself is not revealed to those requesting re-construction; doing so would mean that any of the shareholders who now know the secret can carry out the further action all by themselves without the knowledge or approval of anybody else.

With this as an introduction, let us consider what the OP wants. There are $t$ shareholders who wish to reconstruct the secret, but $t-1$ of them are "cheaters" who want to "cheat" the honest participant. Well, regardless of whether valid shares are presented or are sheer gobbledygook, the trusted party will reconstruct something. For example, as I described in this answer, with Shamir secret-sharing, the secret is
$$s_0 = (-1)^t (x_1x_2x_3\cdots x_t) \sum_{i=1}^t \frac{y_i}{x_i\cdot c_i}$$
where $y_1, y_2, \ldots, y_t$ are the share values as submitted by the share holders, $x_1, x_2, \ldots, x_t$ are the corresponding "locations" used in computing the shares, and
$$c_i = (x_i-x_1)(x_i-x_2)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_t).$$
There is no checking as to whether the submitted "shares" are valid or not; we get $s_0$ which is the correct secret if the shares are valid as submitted, or is gobbledygook if any of them are not. So, when the trusted party who reconstructs the secret tries to use the reconstructed gobbledygook as the password for taking the requested action, that login fails! Thus, the only question is how, if at all, the honest shareholder is cheated in all this. Well, presumably the honest shareholder wants the action to be taken, and that action will not be taken if the $t-1$ cheaters (or even just one cheater!) have submitted invalid shares. So the honest shareholder has been cheated of his desire by fickle friends who pretended to support him in in his desire but thwarted him by choosing to submit invalid shares.

Is it possible that $t-1$ cheaters can prevent reconstruction of the secret?  Yes, if there are only $t$ shares available. With more shares available for reconstruction, things might be  done. But we are too far afield already.


Secure AES Key Generation via Salsa20? I am not rolling my own crypto or anything - just trying to learn about
the Dos and Don'ts of cryptography: specifically about AES encryption and
ways to generate keys for that.

As far as I've understand, one of the options when creating
cryptographically secure keys would be to gather entropy from
/dev/urandom and then feed that data through the Salsa20 cipher.

However I am not quite sure about the next steps, because that’s where search engines stop being useful to me.
From what I understand, using the output Salsa20 generates doesn’t seem to be secure enough to be used as key material as-is.
If that's correct, what would be the "cryptographically" correct next step after getting the Salsa20 output?

Also, if you know of any relevant papers and are happy to share, they would be very welcome!

As stated in the comments, dev/random already produces cryptographically secure random bytes which are perfectly adequate for use in encryption keys.  Running these bytes through another CSPRNG is completely redundant.

  As far as I've understood, one of the options to create cryptographically secure keys would be to gather entropy from /dev/urandom/ and then feed that data through the Salsa20 cipher.

A symmetric cipher such as Salsa20 by itself is not the correct cryptographic primitive.  You need a CSPRNG (such as /dev/random).

  But I am unsure about the next step, because that’s where search engines stop being useful to me. From what I understand, using the output Salsa20 generates doesn’t seem to be secure enough to be used as key material as-is. Am I correct? If, what would be the cryptographically correct next step after I've retrieved the Salsa20 output?

If you have some reason not to use dev/random (convenience, mistrust, etc), and you have some other strong (and I do mean strong, not just mouse-movements ala mega) source of entropy, then you should refer to one of the CSPRNGs defined in NIST Special Publication 800-90A.  You might be particularly interested in CTR_DRBG, which uses a block cipher internally (running in CTR mode, which is essentially a stream cipher like Salsa20).  You can find implementations of this in many languages.

Pro-tip: avoid Dual_EC_DRBG


KCV and compatibility with block cipher modes of operation There has been lately a question on KCV (key check value), value provided by many CRYPTOKI (PKCS#11) implementations. I don't particularly like KCV, but I decided to ask about proper use of KCV.

This "KCV" (also known as CKA_CHECK_VALUE object attribute) value is derived as follows:

For most objects: first three bytes of SHA-1 hash of the object.
For cryptographic keys for block ciphers, it is the first three octets of ciphertext produced by ECB mode encryption of a block full of zeros.

Sending KCV (key check value) with cipher text is done rarely, because the check does not ensure correctness of the key very well. The excellent answer from poncho to this question Sending KCV (key check value) with cipher text illustrates a few reasons.

My concern is that KCV could jeopardize confidentiality or authenticity of proper usage of some modes of operation:

CMAC mode uses $k_{0} = E_{k}(0^{128})$ for deriving sub-keys.
If CTR mode is used starting with counter value 0, that would obviously allow revealing three first bytes.

Is it good idea to avoid using KCV in above situations?

Are there some other modes of operation, where revealing the first octets of encryption of zero block is bad?

I've thought quite a lot about this, and I think in general the answer is no, it would not be a good idea to use a KCV for those kind of situations. Using a hash or even better a MAC (using the key as MAC Key) would be a much better idea when a KCV is required. Instead of zero's, it would be much better to use a previously random (block of) bytes that is not likely to be of use to an attacker.

You could of course wonder if all zero input should be used for CMAC and counter mode. For CMAC is would be very easy to use another constant value. For CTR mode it is probably best to always increase the counter before it is used; one way would be to simply start with value 1. It would be easy to define a protocol that specifies the nonce / IV / counter that way.

Using a KCV for keys can be very useful for key management - it certainly saved the company I worked for a lot of time.

For CMAC mode it is easy to show that the KCV returns part or all of the keys...

Calculate a temporary value $k_0$ = $\operatorname{E}(k,0)$.
If $\operatorname{msb}(k_0) = 0$, then $k_1 = k_0 \ll 1$, else $k_1 = (k_0 \ll 1) \oplus C$.
If $\operatorname{msb}(k_1) = 0$, then $k_2 = k_1 \ll 1$, else $k_2 = (k1 \ll 1) \oplus C$.
Return keys $k_1$ and $k_2$ for the MAC generation process.

These keys in turn are used for the last block of the CBC mode encryption that underlies CBC-MAC, which is used to build up CMAC. Now it seems that this would reveal the last block to an attacker before it is encrypted.

Now comes the tricky part, I'm not sure if this negates the security added to CBC-MAC to create CMAC, but it doesn't look good.

As for CTR mode, it is clear that you can directly decrypt (part of) the first block of the ciphertext if you have a nonce (and counter) set to all zeros. You cannot get a more direct attack than that.


How long brute force AES-128 at 24 bits of key I have 1 block of encrypted data with AES-128, but I know 104 bits of 128 bits the key.
How long it will take to brute force 24 bits of a key at Intel I 7 CPU? How can I calculate that?

I have an Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz. Intel I7 has around 10 generations to speak of. The result cannot be accurate without providing the actual referenced Intel I7.
Here is the method;
Run openssl speed -evp aes-128-cbc command. That will give you the metric.
My CPUs output:
aes-128-cbc for 3s on 16 size blocks: 144516288 aes-128-cbc's in 3.00s,
that is $144516288 = 2^{27.1066568628459}$. Therefore 1 seconds is more than enough.
\begin{array}{|c|r|r|} \hline
2^i & \text{seconds} & \text{years} \\ \hline
2^{30} & 22.29 & 0.0000007\\ \hline
2^{40} & 22824.65 & 0.0007\\ \hline
2^{50} & 23372450.03 & 0.74\\ \hline
2^{60} & 23933388835.87 & 758.92\\ \hline
\vdots & \vdots & \vdots \\ \hline
2^{128} & 7.06388957874987e30 & 2.23994469138441e23\\ \hline
\end{array}
The below code ( tested in SageMath )
SecondsInADay = 86400
SecondsInAYear = 31536000
TotalCBCin3Sec = 144516288 #your CPU time from openssl speed -evp aes-128-cbc
power = (30,40,50,60,128)

for i in power:
    print('seconds for 2^{%d} =' % (i),end="")
    print(((2^i *3.0)/TotalCBCin3Sec).str(no_sci=2))
for i in power:
    print('years for 2^{%d}   =' % (i),end="")
    print(((2^i *3.0)/TotalCBCin3Sec/SecondsInAYear).str(no_sci=2))


Digital Signature with Encryption Hope it will be clear.

I need to digitally sign pieces of information.
What I'm currently doing is the following (for each piece of information):

Run SHA1 on the information
Encrypt the result with RSA
Store both of them together
Now, I can say for sure if someone altered the information.

My problem is that I don't want to run the RSA encryption on each one of the pieces since it has some performance hit on my system.

I thought of doing the following:

Generate a seed for the SHA1
Encrypt the seed with RSA
Store the encrypted seed.
Now I can only run the SHA1 (+seed) on each piece of information.

I don't find any reason for why it should be less safe than what I'm doing today.
Is it true? any thoughts about it?

Thanks

Your scheme doesn't appear to provide any authentication whatsoever.

For a normal RSA digital signature the intended recipient can calculate the hash of the message, decrypt the signature using the public key to get the original hash, and compare them to authenticate the message. If an attacker is to tamper with the message, then in order to change the signature so that it matches the tampered message they would require access to the private key (which we assume they do not have).

In your scheme, an attacker can simply modify the message and update the "signature" by recalculating the hash of [tampered message + seed]. The attacker must have access to the (unencrypted) seed because it was encrypted with the private key, and so can be decrypted with the public key which we assume the attacker has. If the seed was instead encrypted with the public key, then the attacker would not be able to decrypt it to get the original seed in order to calculate a new hash, but nobody else would be able to either so it would be impossible for the intended recipient to verify the signature is correct.


SRP man-in-the-middle This site suggests that Secure Remote Password protocol is secure when "Attackers can intercept, modify, and forge arbitrary messages between client and server."

However, from a quick reading of the Wikipedia page on SRP [1], it seems that an obvious shortcoming of the method is that the server cannot, in general, be trusted.  Since organization-hacking and stealing of credentials is the problem that is being addressed by not storing passwords in plain-text, the client's password verifier and salt ($v$ and $s$ in the notation of [1]) cannot be assumed to be known only to the server.  Therefore an attacker with knowledge of $v$ and $s$ (stolen from the server) could perform a man-in-the-middle on an SRP authentication, obtaining the symmetric key using the same procedure as the server.  Using the known symmetric key, it seems that the attacker can now issue arbitrary requests to the server masquerading as the client.

I'm not a security expert, so I'm almost certainly missing something here.  What's the catch?

The attack outlined in the question does not work, at least as is. Still, SRP6a is very vulnerable to leak of server data, which is not part of the threat model that it addresses.

An attacker Mallory with knowledge of $v$ and $s$ (stolen from the server) can indeed masquerade as the server to the client and establish a shared key with the client. However, without the password, Mallory can not masquerade as the client to the server and get to the point where the server uses a private key. Further, if Mallory attempts to hijack a connection previously established with the server by the legitimate client, that will fail because that connection uses another private key than the one shared between client and Mallory.

However, with $v$ and $s$ stolen from the server, and pure SRP6a, an adversary can find a weak password by a dictionary attack (trying likely passwords sequentially starting from most likely), and then impersonate the legitimate client to the server. Technological progress ("Moore's law") tends to make SRP6a proportionally less secure from that standpoint. The only way around (beside not letting $v$ and $s$ leak, or hoping users will magically start using strong passwords) is that SRP6a is modified yet again by using a slow key derivation function for passwords (also known as password hash, password-based key derivation function) such as PBKDF2, Bcrypt, Scrypt, Argon2, Balloon instead of a fast hash.

Bottom line: when using SRP6a, if $v$ and $s$ being stolen from the server is considered possible, then the client software must implement a properly parametrized slow key derivation function for passwords; with the choice of that function, parametrization, and where the salt comes from not defined by any standard that I am aware of, including RFC5054 or ISO/IEC 11770-4:2006 (did not check the latest version). Correspondingly, practice is overwhelmingly to ignore SRP and send the password as keyed-in within an https tunnel (with the problem that a bogus certificate or a variation of the correct domain name that pass user scrutiny glance will reveal the user's login/password to a competent attacker). That practice also solves the problem that typical browsers have no built-in SRP client support, and that bringing one thru https as Javascript is vulnerable to the aforementioned attacks of https.


Linkable ring signature scheme I need an implementation of linkable ring signature, a ring signature which allows identifying whether two signatures belong to the same signer. It has important privacy-related applications, like e-voting, but unfortunately there seems to be no public implementation. So I'm going to roll my own.

The simplest method seems to me is described in this highly cited paper: http://eprint.iacr.org/2004/027.pdf . Is it a sane scheme? Are there any known vulnerabilities in it? Are there any standards for linkable ring signatures which describe a good way of doing it?

After looking through some papers, I feel qualified to answer my question, for the record.
The scheme works and I've found no evidence that it has been broken. A good review is given in "A survey of ring signature" by L. Wang, which contains a section on linkable signatures.

The technique used in Liu's 2004 paper from the question makes O(n)-long signatures, where n is the number of public keys. There are more recent schemes commonly called "short LRS", which produce O(1) signatures. However, all schemes that I saw require some kind of trusted party to be involved in the generation of key pairs. This defeats the purpose of LRS I think, and anyway is unsuitable for my applications. From my superficial understanding, in O(1) schemes the danger of chosen key attack is somehow greater, and has to be compensated by including this key managing authority.

As for real applications, I found one (unfinished?) implementation of the 2004 scheme, and that's it.

So I've implemented the 2004 scheme and a similar, but more efficient scheme by the same authors. It's here: https://github.com/sorrge/LSAG . Public domain. Not reviewed by anyone yet, so no promises of its security.


AES - which cipher is the safest one out there and what are the best practices for creating and storing the key I just started to learn cryptography. I've read a ton of articles but couldn't find a book or a course that is based on this subject (and also is not outdated).

Therefore I have a few questions (some of them were asked before but there's no specific answer).

Also i must specify that all my questions are related to aes in PHP:

First question is what is the best way to create a completely random and unique key? So far I've made this little code that is (in my opinion) an overkill (and I guess it ads no extra security and randomness to the key since it is only 32 bytes in the end anyways) but still here it is:

$length = 32;
$hash = hash('sha512', microtime(true) . random_bytes(2) . chr(rand(0, 255)) . openssl_random_pseudo_bytes($length));
if((strlen($hash) / 2) > $length){
    $x = rand($length / rand(1, $length), strlen($hash) - $length);
    $key = substr($hash, $x, $length);
} else{
    $key = substr($hash, 0, $length);
}

The cipher that I'm using is: aes-256-gcm. Is there a better cipher that I could use (a more secure one that has a longer key maybe)?

Also why does aes-256-gcm accept a longer than 32 bytes key but on decryption it just ignores anything above the first 32 bytes of that key?

Finally what is the best way to store the key for later usage (keeping in mind that I'm using php/mysql - I am aware of the fact that storing the key in the same database where you store the ciphertext/iv/tag is purely insane).

PS: I do NOT use any of these lines in any project, those are just me trying to learn.

First question is what is the best way to create a completely random and unique key?

Simply generate an appropriately sized array of cryptographically random bytes from something like /dev/urandom, CryptGenRandom, or apparently openssl_random_pseudo_bytes.

The rest of your derivation process appears to serve no function; Even if it did, the entropy content of time and three random bytes is very low, so low that it can be guessed in practice.

So

$length = 32;
$hash = hash('sha512', microtime(true) . random_bytes(2) . chr(rand(0, 255)) . openssl_random_pseudo_bytes($length));
if((strlen($hash) / 2) > $length){
    $x = rand($length / rand(1, $length), strlen($hash) - $length);
    $key = substr($hash, $x, $length);
} else{
    $key = substr($hash, 0, $length);

Would become:

$length = 32;
$key = openssl_random_pseudo_bytes($length);

And that really is all that you need, assuming that openssl_random_pseudo_bytes provides cryptographically secure random bytes.

  The cipher that I'm using is: aes-256-gcm. Is there a better cipher that I could use (a more secure one that has a longer key maybe)?

There is no benefit to using a key that is larger than 256 bits. One of the only reasonable alternatives to AES-256-gcm would be a Salsa/ChaCha-poly1305 based construction. If you're concerned about side channel attacks, then it might be wise to switch. However, if the library you're using doesn't happen to support Salsa/ChaCha-poly1305 out of the box, then don't worry about it.

  Also why does aes-256-gcm accept a longer than 32 bytes key but on decryption it just ignores anything above the first 32 bytes of that key?

The algorithm is only defined to use key sizes of 128, 192, and 256 bits; You cannot simply supply more and expect them to be used.

It is possible that the key length not being checked might lead to a bug somehow.

  Finally what is the best way to store the key for later usage

Here are some options:

Derive the key from a password on application startup
Split the key into $n$ secret shares and distribute them to a bunch of distinct servers

Retrieve the shares and recover the key on application startup

Store the key on a hardware device such as a flash drive
Make use of some kind of HSM (hardware security module) device.

The last option should easily be the most secure, but it will cost money.

If you go with any option other than the HSM, do your best to ensure the key only stays in memory in one location and isn't copied all over the place. With an HSM this isn't a concern, as the key never leaves the HSM.


How to convert roots of Weber polynomial to Hilbert class polynomial over modulo prime? Using any non square root discriminant $D$, we should be able to find the Weber class polynomial. How can I convert the roots of a Weber polynomial to a Hilbert class polynomial over modulo prime?

Let $j_w$ be the root of Weber polynomial $W_D(X)$ over $F_p$, then the root $(j_h)$ of Hilbert polynomial $H_D(X)$ over $F_p$ is given by

$$j_h=\frac{{(j_w^{24}-16)}^3}{{j_w}^{24}}$$


Has the distributed project "Number Fields @ Home" project benefited cryptography in any meaningful way? Is there any new understanding, property, or knowledge that has come from the Number Fields @Home distributed computing project?  Has any outcome advanced the study of cryptography, or altered previous recommendations?

If nothing in particular has come from the project as of yet, are there some outcomes a cryptographer would find intriguing? If so, what are they, and in what way?

TL;DR: The NumberFields@home Project has not benefited cryptography.

Background
Number fields play an important role in cryptography, especially when talking about the RSA cryptosystem.
The security of RSA is based on the presumtion that factoring a large semi-prime (the product of two prime numbers) is very hard to achieve, this problem is known as the integer factorization problem.
Quadratic sieve
The Quadratic sieve is an algorithm for factorization. It's the fastest known algorithm for factoring a number $n$, where $n < 10^{100}$.
Number fields
General number field sieve
The General number field sieve is the fastest known algorithm for factoring a number $n$, where $n > 10^{100}$.
It currently holds the record for factoring the RSA-number RSA-768, meaning it has factored a 768-bit semi-prime. A detailed describtion about how this was achieved can be found in this published paper.
Are 1024-bit numbers considered safe if 768-bit numbers can be factored?
Well... Less so. Factoring a 1024-bit RSA modulus would be about a thousand times harder than a 768-bit. They have achieved factoring this number by a collection of parallel computers and the total time amounted approximately to the equivalent of almost 2000 years of computing on a single-core 2.2 GHz AMD Opteron-based computer.
Quoting the previously mentioned paper from February 18, 2010:

Because the first factorization of a 512-bit RSA modulus was reported only a decade ago it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within
the next decade by an academic effort such as ours or the one in. Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.

But you can rest assured that the current standard (2048-bit RSA modulus) is safe.
NumberFields@home Project
Number Fields @ home has yet to reveal some "breakthrough" for cryptography. You can see a list of there achievements here, so strictly speaking the answer is No.
But it might reveal something someday, even though the purpose of this project is "backwards", since the goal of this project is not to prove anything directly, but rather to gather information that might answer a question we maybe haven't asked yet.
To quote the project:

The project as a whole is basic research, in effect, charting unknown territory. In the future, this may have a bearing on a number of questions.

And quoting directly the impact on cryptography:

Number fields are used in some modern factoring algorithms which are relevant to attacks on RSA. Other researchers have investigated using properties of number fields as the basis of new cryptosystems. It is not clear what number fields will be useful in this research, but the more we know about the general landscape of number fields, the better.


On CPA & KPA security of $\boxplus$-Feistel I am interested to identify the effect of replacing $\oplus$ with $\boxplus$ on basic balanced Feistel structures over $r$-rounds. Given:
$F_\boxplus[L,R]= [S,T] = [R,L \boxplus f(R)]$ where $f$ is a PRF
$[L,R] \in \left\{0,1\right\} ^{n} $
Q1 . In terms of CPA and KPA security, does $\boxplus$ replacement add security over 3 rounds, with proof?
Q2 . If   $\boxplus$-Feistel structures have better security bounds than  $\oplus$-Feistel, why are they not commonly used?

In term of CPA and KPA security, does $\boxplus$ replacement add security over 3 rounds, with proof?

No. There's nothing special about $\oplus$ in the Feistel struture. In fact any group operation $\boxplus$ over $\{0,1\}^n$ will do just fine. The main point of these random functions is to "blind" the previous rounds' other halves and for that a group operation is sufficient.

In fact Maurer and Pietrzak proved the more general security bounds for the Feistel construction beyond 4 rounds using an arbitrary group operation $\oplus$.

  If   $\boxplus$-Feistel structure have better security bounds that  $\oplus$-Feistel, why do not we see it common?

Well, as any group operation is sufficient, we usually choose the operation which can be computed fastest on most hardware. In particular you can evaluate XOR on your whole arbitrary-width block without having to consider carries and the like on any word-size. Also it's way easier to construct XOR in hardware than it is to construct any other group operation I can imagine right now. Also it's hard to beat 1 cycle / word with no inter-bit dependencies.


Sharing an encrypted file between a group of people Is there any way to share an encrypted file with a group?
In the other words, can I encrypt a file with a public key so that each person in a group decrypt it with his/her private key?

Is there any way that I have a public key and some different private key for it?

I want to find a way to encrypt a file with a public key, and then produce some private keys from this public key, so that whenever I wanted to share that file with some person, I gave him/her a private key from this set to decrypt my file.

Yes, you encrypt the file with a symmetric key, then encrypt that symmetric key with each of the recipients public keys. gpg can do this by adding multiple --recipient options.


LFSR get output from characteristic polynomial? Say you have a characteristic polynomial of an LFSR:

$$f(X) = X^4 + X^3 + 1$$

How can I use this function f to get the output of the LFSR, given some initial state?

Obviously I can create the LFSR diagram based on the function, since this function describes where the "taps" are (see .e.g the Wikipedia article http://en.wikipedia.org/wiki/LFSR):

|----+--------+
|    |        |
+-->[0][1][1][0]-->

Then calculate it iteratively like this: 0, 1, 1, 0, 0, ... (here the initial state is as in the diagram, 0,1,1,0).

I know you can also get this output from the equation:

$$s_j \equiv c_1s_{j-1} + c_2s_{j-2} + \dots + c_2s_{j-2} \pmod 2$$

Which gives the same result as calculating it from the diagram "by hand".

However my question is how to get this from the characteristic polynomial. Also what purpose does the characteristic polynomial have, beyond describe the taps in this way? If you give f some arbitrary argument, what are you really doing? What is the argument X?

I have a feeling this should be covered pretty well in some readily accessible online guide or tutorial that I cannot find, however I have read several such texts and searched through several more, and this is still not clear to me.

The variable of a polynomial is traditionally noted $x$, not $X$; and, when dealing with LFSRs, the polynomial is seldom considered a function. Thus I'll rewrite the polynomial as $P(x)=x^4+x^3+1$, a polynomial of degree $n=4$.

This is a polynomial with coefficients in the field $\operatorname{GF}(2)$, also noted $\mathbb Z_2$ or $(\{0,1\},+,\cdot)$ [note: in $\operatorname{GF}(2)$, $1+1=0$, and $-$ is the same as $+$]. The polynomial's coefficients are all either $0$ or $1$, and not shown: a term $x^j$ is present when its coefficient is $1$, and absent when its coefficient is $0$. When performing polynomial arithmetic, we are manipulating polynomials irrespective of the value and domain of their variable and result, unless otherwise stated.

The state of the LFSR is a polynomial $S(x)$ with coefficients in $\operatorname{GF}(2)$ of degree at most $n-1$, but can also be thought as:

A vector of $n$ bits $(s_0,s_1,\dots,s_{n-1})$ that are the coefficients of $S$ starting from the constant term going up to higher order terms, that is with $S(x)=\sum_{j=0}^{n-1}s_j\cdot x^j$ with the convention that $x^0=1$;
The integer $\hat S=\sum_{j=0}^{n-1}s_j\cdot 2^j$; addition of polynomials becomes bitwise eXclusive-OR, and multiplication of polynomials becomes carry-less multiplication [performed as binary multiplication, but replacing additions with bitwise eXclusive-OR]; the same integer can be defined as $\hat S=S(2)$ [note: here we are considering $S$ as a polynomial function over $\mathbb Z$].

The next state of the LFSR is, by definition, the remainder of the polynomial division of the polynomial $x\cdot S(x)$ by the polynomial $P(x)$, noted $\big(x\cdot S(x)\big)\bmod P(x)$.
By definition of polynomial division, the remainder of the division of polynomial $T(x)$ by non-zero polynomial $P(x)$ is the polynomial $R(x)$ of degree less than $P(x)$ such that there exists a polynomial $Q(x)$ with $T(x)=P(x)\cdot Q(x)+R(x)$.
In the context of moving to the next step of a LFSR, $Q(x)$ is either $Q(x)=1$ [when $S$ is of degree $n-1$] or $Q(x)=0$ [otherwise]; thus the next state $\big(x\cdot S(x)\big)\bmod P(x)$ is either $x\cdot S(x)+P(x)$ [when $S$ is of degree $n-1$] or $x\cdot S(x)$ [otherwise].

For example, if the initial state of the LFSR is $S_0(x)=x^2$,

the first non-initial state is $S_1(x)=\big(x\cdot S_0(x)\big)\bmod P(x)=\big(x\cdot x^2\big)\bmod P(x)=x^3\bmod P(x)=x^3$.
the second non-initial state is $S_2(x)=\big(x\cdot S_1(x)\big)\bmod P(x)$ that is $\big(x\cdot x^3\big)\bmod P(x)=x^4\bmod P(x)=x^3+1$, with the last step because $x^4=P(x)\cdot Q(x)+x^3+1$ with $Q(x)=1$, and we can obtain $x^3+1$ as $x^4+P(x)=x^4+x^4+x^3+1=x^3+1$.
$S_3(x)=\big(x\cdot S_2(x)\big)\bmod P(x)=\Big(x\cdot\big(x^3+1\big)\Big)\bmod P(x)$ that is $\big(x^4+x\big)\bmod P(x)=x^4+x+P(x)=x^3+x+1$.
$S_4(x)=\big(x\cdot S_3(x)\big)\bmod P(x)=\Big(x\cdot\big(x^3+x+1\big)\Big)\bmod P(x)$ that is $\big(x^4+x^2+x\big)\bmod P(x)=x^4+x^2+x+P(x)=x^3+x^2+x+1$.
$S_5(x)=\big(x\cdot S_4(x)\big)\bmod P(x)=\Big(x\cdot\big(x^3+x^2+x+1\big)\Big)\bmod P(x)$ that is $\big(x^4+x^3+x^2+x\big)\bmod P(x)=x^4+x^3+x^2+x+P(x)=x^2+x+1$.
$S_6(x)=\big(x\cdot S_5(x)\big)\bmod P(x)=\Big(x\cdot\big(x^2+x+1\big)\Big)\bmod P(x)$ that is $\big(x^3+x^2+x\big)\bmod P(x)=x^3+x^2+x$.

It is easy to perform the same calculation using either bit vectors, or integers, and that's practice in most computer programs. With integers, we define $\hat P=P(2)$ [that is $\hat P=\text{0x19}$ with our $P(x)$], and the state following $\hat S$ with $0\le \hat S<2^n$ is whichever of $(2\cdot\hat S)\oplus \hat P$ or $2\cdot\hat S$ is less [or, equivalently, less than $2^n$], where $\oplus$ is bitwise eXclusive-OR [operator ^ in C].

One common definition of the output of the LFSR is the coefficient of the term of degree $n-1$ in the states of the LFSR. The constant term is also popular when the reduction polynomial $P(x)$ has a constant term, which is the case in practice. Sometime [especially with the later convention], the initial state is not taken in consideration.

In the above example, the output of the LFSR [including the initial state $S_0(x)=x^2$] is thus
$0$, $1$, $1$, $1$, $1$, $0$, $1$...

Sometime it is used a reflected representation, where state $S(x)$ is represented by the integer $\check S=\sum_{j=0}^{n-1}s_j\cdot 2^{n-1-j}=2^{n-1}\cdot S(1/2)$ [note: here we are considering $S$ as a polynomial function over $\mathbb Q$].
This allows obtaining the output as the low-order bit of the integer representing the state [rather than its bit of rank $n-1$, which might be less easy to isolate]; and makes it possible to compute the next state without any test, using only common operators on unsigned words of size at least $n$ bits, using the C expression
S = (S>>1) ^ (P & -(S&1))
where P is $\check P=\lfloor2^{n-1}\cdot\big(P(1/2)\big)\rfloor$ [that is P of $9$ with our $P(x)$] and fits an unsigned word; >> is unsigned right shift [that's >>> in Java]; & is bitwise AND; and by definition of unary operator - over unsigned words, -U is the unsigned word such that the sum of U and -U is divisible by the smallest power of two that is not representable as an unsigned word [that's the definition of unary operator - using Two's-complement].

For example, starting from the same $S_0(x)=x^2$ and P of $9$, we have S taking the values $2$, $1$, $9$, $13$, $15$, $14$, $7$.. when applying S = (S>>1) ^ (P & -(S&1)) repeatedly, and the same output $0$, $1$, $1$, $1$, $1$, $0$, $1$.. obtained as S&1.

If we are able to do with bit vectors or integers rather than with polynomials, why are we using polynomials, even in theory?

One important reason is that $S_{i+1}=\big(x\cdot S_i(x)\big)\bmod P(x)$ gives $S_i=\big(x^i\cdot S_i(x)\big)\bmod P(x)=\Big(\big(x^i\bmod P(x)\big)\cdot S_i(x)\Big)\bmod P(x)$, and that's key to computing the $i^\text{th}$ state in time $\mathcal O(\log i)$ rather than $\mathcal O(i)$, and linking the period of the generator to properties of $P(x)$.

The schematic in the question (where the first + in reading order is a XOR gate with output on the left, and any other + is just a wire) at first does not seem to be matching what's above in this answer, which applies to the so-called Galois construction of a LFSR. That drawing uses the Fibonacci construction of a LFSR.

The two constructions give the same output, but starting from a different state. The state of a Fibonacci LFSR of degree $n$ [with polynomial $P(x)$ having a constant term] is the first $n$ bits output by the Galois LFSR with the the same polynomial [or that polynomial reflected, depending on definition of a Fibonacci LFSR].

For nice schematics of gate realizations of the two kinds of LFSR, see here.


How to prove membership of a list without disclosing the list members? I'm designing a messaging system where the sender A sends a message m with a signature s to n Receivers.

A Receiver Ri should then be able to prove to a Verifier V that he is one of the receivers of the message without disclosing m and the identity of the other receivers. He will however disclose A and Ri.

Question: how could this be done ? What must A store along with m and sign with s for this to be possible ?

The solution I have now is that A would computes hash(m) and hash(A || Ri || hash(m)) for each receiver Ri. The signature s uses a hash computed over all hash values and nothing else. All these hash values are then send along with m and the signature s to all receivers.

To prove that a receiver Ri is member of the list the receiver sends to the verifier A, all the hash values, s and Ri. The verifier can then verify the signature s and that hash(A || Ri || hash(m)) is in the list of hashes of the receivers.

This solution uses hashes to obfuscate the identity of the receivers and the message.

Is there another solution which would not need to generate and send the list of hashes ?

Is there a risk that something could be deduced about R2 knowing A, R1, hash(m), hash(A || R1 || hash(m)) and hash(A || R2 || hash(m)) ?  I guess no if the hash is secure.

Edit : As signaled by poncho this proposed solution is not optimal because the Verifier could easily test if R2 is member of the list. Prior knowledge of potential members of the list would then expose their presence.

Another solution I found that solves this problem, but is unfortunately very inefficient, is for A to generate random numbers and encrypt them with the public key of each receiver Ri. A would then sign the list of encrypted random numbers and sent both with the message to each receiver.

With its secret key, a receiver can decrypt the random number and pass it to the verifier. The verifier can then encrypt the random number and check that the encryption matches the one found in the list and signed by A.

This algorithm is very bad in term of computation complexity for A and in size for the message m. But this proves at least that one solution exist.

Apparently the principle of accumulators would be the way to go. Here is a reference article on this subject: http://www.cs.stevens.edu/~nicolosi/tech-reports/FaNi00.pdf which could be of interest.

Edit 2: Following David Cary's which is technically valid, I must make clear that A (Alice) can't interact with the verifier V. The reason is because the verification process is very infrequent compared to the sending process. Also the verifier's role is strictly limited to verification. It doesn't relay the message. Thus Ri must be able to prove that it is one of the receivers as stated by A by only using information sent along with m.

The only viable solution I found so far is for A to send a list of random numbers, each one encrypted by the public key of one of the Ri. A would sign the list of encrypted random numbers. Each Ri can decrypt its random number and can use this knowledge to prove its identity. Because the numbers are random and encrypted with public key, the identity of the other receivers is perfectly sealed.

Unfortunately it requires one public key encryption for each receiver of each message. This is expensive in processing time and in amount of data to transmit along with the message m.

Have a look at Zero Knowledge sets and paragraph 4.3 from here


Guessing the Secret in RLWE Search-to-Decision In On Ideal Lattices and Learning with Errors over Rings, the authors prove a search-to-decision reduction by guessing the RLWE secret $s$, and using the guess to transform a sample from $\mathfrak{q}_{i}$-$\mathrm{LWE}_{q, \Psi} \text { to } \mathrm{DecLWE}_{q, \Psi}^{i}$ (Lemma 5.9). They say nothing about the properties of the guess, $g$, although they do go on to consider whether $g\equiv s$ mod $\mathfrak{q}_{i}$ or $g \not\equiv s$ mod $\mathfrak{q}_{i}$. My question is: what can we assume to be true about $g$? What can we say about its distribution? about other behaviour modulo $\mathfrak{q}_{i}$, or in the ring? Or can it have no more structure than merely being a ring element?

The "guesses" are part of the enumeration of all possible values of $s\bmod \mathfrak{q}_iR^\vee$. The reduction has two parts essentially:

A way of telling if the guess was correct (the $\mathsf{WDLWE}_{q, \Psi}^i$ oracle)
A small space of values to try (as values $s\bmod \mathfrak{q}_i R^\vee$ are within $R_q^\vee/\mathfrak{q}_iR_q^\vee$, which from context in the paper appears to have size $N(\mathfrak{q}_i) = q = \mathsf{poly}(n)$).

You then enumerate all possible guesses, and return the one which verifies to be correct.
This is a deterministic process (although you're free to choose the particular order to enumerate things in).


Using the same secret key for encryption and authentication in a Encrypt-then-MAC scheme Is it a weakness to use a single shared secret for protecting messages using a Encrypt-then-MAC scheme?

Assuming a system is using AES-256-CBC and a SHA1-HMAC and the same secret key for both operations.  Upon intercepting one of these messages and attacker could brute force this secret key by trying to solve the HMAC or by successfully decrypting the first block of the ciphertext.

Performing  a decryption on a single block of AES-256 should be a lighter operation than performing a SHA1-HMAC on a potentially large message.  Therefore AES-256 is ideal for a massively parallel brute-force attack and the use of the SHA1-HMAC doesn't hurt the system.

Is this approach sound, or is there an attack that has not been taken into consideration?

Brute forcing the key would hardly be an issue: 128-bit keys (assuming they have been properly generated) are in a space which is way too large to be successfully explored by brute force; and 256-bit keys (the kind you put in AES-256) are even more larger. Whether AES is "faster" than HMAC or not does not make such brute force more feasible: even if each key try was as simple as a simple bit flip, 128-bit keys would still be too large for any practical attacker.

Said otherwise, if "massively parallel brute-force attacks" are relevant, then your key is not properly generated (bad PRNG, bad key exchange algorithm, bad password-to-key derivation...), and that is your problem, not the reuse of the same key for both AES and HMAC. If you reach the point where the relative slowness of AES vs HMAC/SHA-1 is how you envision protection, then things have gone sour upstream.

Potential problems with using the same key for encryption and MAC would be structural; @Henrick's example is CBC-MAC, which is indeed identical to CBC encryption, except that you only use the last encrypted block as MAC. CBC-MAC works fine as long as you do not give to the attacker access to pairs (p,c): p is a plaintext block, c is the corresponding ciphertext block, for the key k which you use for CBC-MAC. But if you use the same key k for encrypting the data, then you are giving to the attacker a lot of such blocks.

With HMAC vs AES, no such interference is known. The general feeling of cryptographers is that AES and SHA-1 (or SHA-256) are "sufficiently different" that there should be no practical issue with using the same key for AES and HMAC/SHA-1. However, simply defining that "difference" with any kind of scientific rigor would be hard, and it is not a much explored security feature. So that's one of these constructions which can be qualified as "no urgency to fix it, but don't do it if you can avoid it". A much "safer" way (in the sense of: "we know what characteristics of the involved algorithms we are exercising") is to take your master key K, and derive from it, with a good one-way Key-Derivation Function, a sub-key for encryption and another sub-key for the MAC. This can be as simple as applying SHA-256 on K and splitting the 256-bit result into two 128-bit keys.

There are some MAC and encryption algorithms which intrinsically support sharing the same key. This is exactly what happens in GCM.


Deterministic Encryption using AES I am in need of a deterministic encryption algorithm I can use on social security numbers (9 character string, numbers only) that I will store encrypted in a MongoDB and need to be able to search for them and recall them (ruling out one way hashes).

For example, 11122333 is encrypted and then stored in the db.  The user then wants to know if 111223333 is in the db so i encrypt it and then search for the cipher text in the db.

db.patient.find({"PatientDemographics.SocialSecurityNumber" : "N9DF63vmf0fedH/YW5Et6g=="})

What I came up with is to use AES (in CBC-Mode) but purposefully gimp it using a un-changing IV.  I have it working with this change. I just want to make sure I am not completely ruining the encryption and only doing what I need to do to enable searching.

To summarize, If you got a dump of the db with the SSNs encrypted as described above, would you able to get the cleartext via some sort of attack without knowing the IV and Key? Would it help if i passed in the IV (instead of hard coding it) which would act as a second key?

Another option (that I havn't tried yet), suggested here, says to hash the ssn and use that as a IV.  I would then have to prepend the IV to the ciphertext and store it in the db.  Is this cryptographicly better?  My approach is having a secret static IV (requires key and IV to decrypt) vs this one having a deterministic IV prepended to the ciphertext (requires only key to decrypt).

If this is the wrong approach, can you recommend another that fulfills the searching requirement (implemented in C#)?

Hoping to get more constructive feedback than i got from the main site

First, you should specify:

what you need to be able to do in your database to get your job done;
what capabilities an adversary may have; and
what you want to ensure the adversary can't do.

Here's some generic guesses, but you should fill these in with specialized knowledge of your application's needs.

For (1): If all you need to do is search by a known SSN, as in SELECT * FROM users WHERE ssn = '123-45-6789' if there were no cryptography—in particular, if you never need to SELECT ssn FROM users WHERE ... and get back an SSN—then it is sufficient to hash the SSN irreversibly; there is no need for reversible encryption.

For (2): The standard threat model here is database disclosure.  But you might have a separate application server and database server, which have different attack surfaces and different risk of compromise, so you might consider compromise of the application server separately from compromise of the database server.

For (3): Obviously, one might hope that if your database is compromised, then the adversary nevertheless can't the SSN of anyone indexed by other information in the database.  But beware here: there's a lot that can be learned from the structure of databases even if individual records or identifiers are concealed.

Once you've read about leakage from databases even if encrypted, let's suppose for the moment that you just want to search by SSN, not look up SSN.  Here are some approaches.

You could store $\operatorname{SHA-256}(\mathit{ssn})$.

However, anyone who can read the database and find a hash $h$ in it can quickly enumerate all SSNs to find which one $h$ corresponds to by testing whether $h = \operatorname{SHA-256}(\text{000-00-0000})$, $h = \operatorname{SHA-256}(\text{000-00-0001})$, etc.  The problem here is that SHA-256 is a public function that anyone can evaluate, including the adversary, to test a guess, and the space of SSNs is very small.
You could store $\operatorname{Argon2}(\mathit{salt}, \mathit{ssn})$, with a per-row unique salt, and the largest time and space parameters for Argon2 that fit in your budget.

This raises the adversary's cost of testing a guess.  However, Argon2 is still a public function, so an adversary can still just test guesses—in parallel to get answers sooner, at the same total cost—and using Argon2, or any other sequential memory-hard hash, increases the cost for you to run your application too.
If there is a meaningful separation between the application server and the database server, so that an adversary could plausibly compromise one without the other, then you could store a secret key $k$ on the application server, and store $\operatorname{HMAC-SHA256}_k(\mathit{ssn})$.

Then, if only the database server is compromised, the adversary learns essentially nothing about the SSNs themselves: since they don't know $k$, they can't evaluate the secret function $\operatorname{HMAC-SHA256}_k$ to even test a guess.  Of course, once they break into the application server and recover $k$, the security is essentially as if you had used SHA-256.

The specific criterion here is that HMAC-SHA256 is a pseudorandom function family, or PRF.  Other PRFs would work too: keyed BLAKE2, SHA-3 KMAC, AES-CMAC, etc.

If you do need to store and retrieve the SSNs, you should use a deterministic authenticated cipher, such as a nonce-misuse-resistant authenticated cipher like AES-SIV or AES-GCM-SIV with a fixed nonce.  As it happens, authenticated ciphers like these also serve as pseudorandom function families, so you get essentially the same security as HMAC-SHA256 as long as the key $k$ is not compromised.  Be careful to check on the scaling limits of AES-SIV or AES-GCM-SIV in comparison to the potential volume of your database.


What's the preferable encryption for large data and files in terms of speed and security other than AES? First of all, I'm relatively new to encryption so please bear with me.
I'm looking for a way to encrypt large amounts of data only on my device, no need to transfer my encrypted files/data (10-20GB or less), I don't really care about speed as long as the encryption is really strong. I have tried encryption with AES-GCM and using RSA for encrypting the AES Keys, but AES doesn't really give me that safety feeling like it's only 256bits maximum.

Based on your comments I have a feeling that may be you don't really understand what a huge number of combinations a 256-bit key means. At the first glance 256 bit is "just" 16 bytes. But look at it closer. With 256 bits we can encode $2^{256} = 10^{77}$ numbers. It is 100 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 numbers.
Still too theoretical? You may get better feeling if you run a simple Python script:
i = 0
while i < 100000000000000000000000000000000000000000000000000000000000000000000000000000: # 2^256 ~= 10^77
    if (i % 100000000 == 0):
        print i
    i = i + 1

Every second, on weaker CPUs may be every 10 seconds, you will see a 9-digit number. In 1 day you will see the numbers are 10-digits. In 100 days you will see 12-digit numbers. In 3 years you will see 13-digit numbers. If you pay for 1 000 computers for 30 years, then you will get 16-digit numbers. Still extremely far from 77-digit numbers.
This script is very simple and fast. But brute-forcing of AES will be much slower. For every key candidate one would need to decrypt some considerable peace of data, then analyze if decrypted data mean anything like document, image, video.
Be realistic. Estimate how much money would an attacker obtain if your files are brute-forced and if they can sell your files to somebody. Will they get \$1 000, \$1 000 000? Nobody will brute-force your AES password (except checking against dictionary with typical weak passwords and their variations, which is very quick). If your secrets are worth \$1 000 000, then it may be much cheaper to pay hackers $500 000 to break into your system, read your passwords or install key loggers; or install spy cameras in your home, your car etc. and thus get your passwords; or steal your key if you have hardware token.
TLDR: AES with 256-bit key is more than sufficient.


TLS 1.3 Security against PKCS#1v1.5 This paper explains an attack on TLS 1.3. This was published way back in 2015 when TLS RFC was in draft stage.
My question is now TLS 1.3 RFC is finalized, is this attack got addressed?

There is an encryption scheme called RSAES-PKCS1-v1_5, or PKCS#1v1.5 for short. There is a signature scheme called RSASSA-PKCS1-v1_5, or PKCS#1v1.5 for short. These two schemes have different security postures.

The signature scheme has no particular weakness as long as the implementation is functionally correct and the use of the private key has no exploitable side channel leak. There is a class of attacks against PKCS#1v1.5 due to Bleichenbacher, but it's due to implementations of signature verification that don't verify everything they should. Vulnerable implementations still existed in 2019, but major implementations of PKCS#1v1.5 have been safe for ages.

The encryption scheme is extremely difficult to implement correctly because decryption is vulnerable to padding oracle attacks. Some ciphertexts are invalid, and merely revealing whether a ciphertexts is valid or not, even through a very small timing difference, is enough to allow attackers to decrypt arbitrary ciphertexts. To make matters worse, revealing partial information about a plaintext after a successful decryption can also allow the attack. This class of attacks is also due to Bleichenbacher (there's also a similar class of attacks known as Manger's attack). There was a big wave of disclosures in late 2018 nicknamed “the 9 lives of Bleichenbacher's CAT”, and it's probably not the last one. PKCS#1v1.5 encryption is extremely hard to implement and use correctly and many voices are calling to stop using it altogether.

TLS up to 1.2 has cipher suites that use RSA encryption: the client encrypts a master secret, the server decrypts it, this master secret becomes a shared key for the subsequent communication, and the client knows that it's talking to the correct server because only the correct server can decrypt the master secret. TLS also has cipher suites that use RSA signatures: the two parties perform an unauthenticated key agreement to establish a master secret, the server signs the handshake data, and the client verifies the signature to ensure that it's talking to the correct server.

If a server is willing to use a cipher suite that uses RSA decryption, and there is a vulnerability that allows attackers to use the server as a decryption oracle, this vulnerability may also allow attackers to use the server as a signature oracle. If this is the case, then attackers can impersonate the server even against clients who refuse to use RSA decryption. The attack goes like this:

The client starts a handshake. The attacker is a man-in-the-middle and intercepts the handshake packets. The client and the attacker agrees to use a TLS cipher suite based on RSA signature.
The attacker needs to sign the handshake data. It contacts the server, which is willing to perform RSA decryption. The attacker uses the server as an oracle to construct a signature of the handshake.
The attacker sends the valid signature to the client, so the client believes that it is talking to the correct server.

This attack is possible even if the client uses TLS 1.3, which only has cipher suites based on RSA signature (as well as cipher suites using other signature schemes), not RSA encryption. The root of the problem is that the server is willing to do RSA decryption and RSA signature with the same key.

This is an illustration of the fact that it's bad practice to use the same key for two different purposes. A protocol definition cannot protect against this (other than to say “don't do it”, but it's not something that the other side can detect).


On-the-fly computation of AES Round Keys for decryption? The usual implementation of AES first computes all the Round Keys sequentially starting from the key, and stores them in RAM for later uses. However, when enciphering a single block with a key that will be used for that purpose only, or when RAM is very sparse, or perhaps in hardware, it is advantageous to use the Round Keys a they are being generated, rather than store them. Quoting the Rijndael submission to NIST:

  The key schedule can be implemented without explicit use of the array W[Nb*(Nr+1)]. For implementations where RAM is scarce, the Round Keys can be computed on-the-fly using a buffer of Nk words with almost no computational overhead.

It is said this also works for deciphering:

  The key expansion operation that generates W is defined in such a way that we can also start with the last Nk words of Round Key information and roll back to the original Cipher Key. So, calculation ’on-the-fly' of the Round Keys, starting from an “Inverse Cipher Key”, is still possible.

However, the how-to is left as an exercise to the reader. In particular: Can the last Round Key (the first used when deciphering) be computed directly, rather than sequentially?

This self-answer is heavily based on comments by Paŭlo Ebermann.

When performing AES decryption with on-the-fly computation of AES Round Keys, there is no choice beyond running the key schedule forward to the last Round Key (the first used when deciphering). The structure of the key schedule creates enough non-linearity and diffusion at each of the 10 steps that no shortcut is practicable. One step comprises 4 SubBytes transformations, 16 XORs of 8-bit quantities, some rotations of all the 16 bytes of the Round Keys, and the doubling of the byte Rcon in $\operatorname{GF}(2^8)$, in a manner such that what's produced by a byte XOR goes thru SubBytes on the next step, and non-linearly influence all the 16 bytes after 4 steps. Even halving the number of steps to reach the last Round Key would be extremely hairy, to the point of being counterproductive.

There are however two implementation variants:

If about 160 bytes of additional temporary RAM are available, the Round Keys can be stored as they are computed, and re-used during the decryption.
Otherwise (and memory is often tight in a small micro-controller, or unavailable in hardware), each of the 10 steps can easily be reversed. The only remote difficulty is the un-doubling of the Rcon; it can be implemented using a small ROM table, or as Rcon=((0x00-(Rcon&0x01))&0x8D)^(Rcon>>1). As pointed by Craig McQueen in comment, the reversal of the key schedule uses the direct AES SBox.

Hardware implementations typically do 2; both options are justifiable in software.


Why does the DES crypto algorithm NOT use 2 rounds? Now, if we were to go round by round, you could give a distinct reason for not using a single round since after just one round, the right half of the text comes directly, as-is, to form the left half of the new text after the one round. In this way, if an observer were to notice this, he/she could deduce that DES may be the algorithm being implemented. But is there a way of figuring out that DES is being used after performing TWO rounds?

DES with 2 rounds is broken. It is trivial to find a way to get the key with much less work than for the full DES (and even that is broken).

DES is a Feistel cipher, so we have two halves, the left and the right half. For every round, we do something with the one half and a subkey, and then XOR it with the other half. After that we switch both halves, repeating the whole algorithm until we have done all rounds.

Let's say we begin with both halves before the first round, $l_0$ and $r_0$. The calculated values for the next round are, with $DES()$ as the encryption function, this:

$$ l_1 = r_0 $$
$$ r_1 = DES(r_0) \oplus l_0 $$

If we continue this for another round, we have two "randomly mixed" halves. It's not easy to get the ciphertext from this, especially if the round function is really good. The one of DES is not so good, and that's the reason why we use 16 and not 4 rounds. (4 is the minimum of rounds needed, but explaining that would be beyond the scope of this answer.)

But there's another way to solve this. We can use the chosen-plaintext attack. If we encrypt an arbitrary plaintext, and then the same plaintext with one bit in the left side inverted, we will see some interesting things in the ciphertext: The right half has changed pretty much, but in the left half only the one bit you inverted earlier did change. This works with every Feistel cipher, not just DES. If you have to determine if DES was used, then you have a bit more work to do. I can't tell you how, but searching for something like "breaking DES reduced rounds" would be a good way to find a solution.


How to attack this authentication protocol from "Cryptography: An introduction" Consider the following protocol (from the book "Cryptography: An introduction", by Nigel Smart):

A → B: A, Na
B → S: B, {A, Na, Tb}Kbs, Nb
S → A: {B, Na, Kab, Tb}Kas, {A, Kab, Tb}Kbs, Nb
A → B: {A, Kab, Tb}Kbs, {Nb}Kab

where the smaller letters are the suffix so example Kab means the Key shared by A and B.  Tb represents the timestamp for the message and Nb represents a nonce.

My question is: If an external attacker is impersonating A and S at the same time, how the attacker can manage to trick B into believing A is authenticated?  I'm told I should be able to describe how to do this in exactly 3 messages (omitting one of the messages in the protocol).

My attempted solution is: If A and S are impersonated then when B is sending a message to S, the external attacker will know what is being sent and therefore the attacker can forward the message as normal to A but can corrupt the message. I'm not able to write a protocol as it's a bit confusing.

See also What does this Authentication protocol achieve and what information is shared? for a related question about the same protocol.

If the attacker M is impersonating both A and S, then he obviously doesn't have to bother sending the third message in the protocol to himself.  Thus, the protocol reduces to:

M(A) → B: A, Na
B → M(S): B, {A, Na, Tb}Kbs, Nb
M(A) → B: {A, Kab, Tb}Kbs, {Nb}Kab

where M(A) and M(S) denote M impersonating A and S respectively.

By itself, this is not a successful attack: while M can pick any valid Kab he wants, he generally cannot obtain the corresponding ciphertext {A, Kab, Tb}Kbs to send to B.  However, if the formats for Kab and Na are compatible, such that M can choose Kab equal to Na, and if B does not check for this possibility, then M can simply replay the ciphertext {A, Na, Tb}Kbs he received from B in the second step, leading to the attack:

M(A) → B: A, Na=Kab
B → M(S): B, {A, Na=Kab, Tb}Kbs, Nb
M(A) → B: {A, Na=Kab, Tb}Kbs, {Nb}Na=Kab

Other attack methods may exist if the encryption scheme denoted by the curly braces is malleable, but the attack described above will work even if it's not.