Can multiple hashing weaken the password? Problem. I want a longer key out of password than my hashing function provide.

Idea.  I want to hash password multiple times rotating chars one position each time and use composite key.

Question. Do I really weaken the password?

Example:

Password=carphagen

Key1= BCrypt("carphagen")=OZrxJo..IAwipd8hHm69IGFiPz/Y/veK
Key2= BCrypt("ncarphage")=PiG1Qndv8kOHDFoEwhbM.rqtM4O5XNR2
Key3= BCrypt("encarphag")=Hbrz35n4pwOLsWnMdyuQ7Ze1XMH/QnmC
. . .
KeyN= BCrypt("rphagenca")=OapAj6P0OS5P0m20f5oAKY482hEvfLhy

N < less password length

Key = Key1 + Key2 + . . . + KeyN

Question. The attacker knows Key, does he get help with password?

Small Update: BCrypt Salt is the same and is known. It is removed from the hash and not used as a part of the Key

Do I really weaken the password?

To some degree, yes.

The function is considered public, and the attacker can test random passwords with it and check the output and compare it to your key. Then he finds the correct password, even if he actually just guessed one of those permutations you defined. In your example:

Actual password is carphagen
The key is: key is $Key = Key1 + Key2 + . . . + KeyN$
The attacker tries the password ncarphage, which is the passwords permutation to generate $Key2$.
The attacker gets as output: $Key2+\dots$.
He still can easily detect that the partial key is the same as in the given output, even if it's not at the same location.

One more thing to consider: Your idea takes $N$ times the computation time of a single BCrypt call. But an attacker can actually check one password with a single call to BCrypt (if he's not interested in checking the permutated passwords). And that's quite bad - testing a password for the attacker surely should not be less than regular usage.

Here's an alternative idea:

Use BCrypt to generate $k_0$ from your password - with enough iterations that it fits your requirements.
Use a different key derivation function to generate values $k_1,k_2,k_3,\dots$, by using $k_0$ and a counter as input. If the function utilizes iterations, just use one.
If you want to increase the computation time, increase the number of iterations to generate $k_0$, don't apply them to the computation of $k_1,k_2,\dots$ .

For the second step, there are various possibilities for a KDF. For example you could use a keyed hash function (also called MAC), a CSPRNG seeded with $k_0$, a PRF, ...

A second alternative: Use another password-based KDF, which supports variable length output. BCrypt is quite old and there are more recent alternatives, two examples would be Argon2 or scrypt.


How much time to generate a proof in ZK-snark? I know that zk-SNARK takes in range of milliseconds to verify statements. But what about the time to generate the proof. For example, if I have a circuit that tests the There is key s.t H(key)=s

Thanks for anyone offers help in this question since I need an answer to it urgently in my thesis.

I just run example code from ZoKrates manual and measured time and memory usage.

Here is how "proof of preimage" problem defined in ZoKrates:

def main(field a, field b, field c, field d) -> (field):
    h0, h1 = sha256packed(a, b, c, d)
    h0 == 263561599766550617289250058199814760685
    h1 == 65303172752238645975888084098459749904
    return 1

For such a simple program:

setup takes ~20 seconds and ~350 Mb memory;
generating witness and proof takes <5 seconds and ~150 Mb memory.

For something more complex like proving UTXO in ZCash proving may take tens of seconds and couple of gigabytes (see here).

Following steps are required to run the proving protocol.

1. Compile human readable code into arithmetic circuits (~7 seconds, ~240 Mb):

$ time zokrates compile -i hashexample.code
2.08user 5.14system 0:07.24elapsed 99%CPU (0avgtext+0avgdata 238044maxresident)k
0inputs+21641416outputs (0major+70866minor)pagefaults 0swaps

Generated arithmetic circuit is 15Mb.

2. Trusted setup (~15 seconds, 350 Mb)

$ time zokrates setup
13.73user 0.94system 0:14.68elapsed 99%CPU (0avgtext+0avgdata 354912maxresident)k
0inputs+66248outputs (0major+90965minor)pagefaults 0swaps

On this step proving key (32Mb) and verifying key (2.6Kb) are generated.

3. Computing witness from known arguments (~1 second, ~150 Mb)

$ time zokrates compute-witness -a 0 0 0 5
0.82user 0.92system 0:01.75elapsed 99%CPU (0avgtext+0avgdata 148620maxresident)k
0inputs+1440outputs (0major+39469minor)pagefaults 0swaps

Witness is 458 Kb in size.

4. Generating the proof (~3 seconds, ~106 Mb)

$ time zokrates generate-proof
2.71user 0.06system 0:02.78elapsed 99%CPU (0avgtext+0avgdata 106188maxresident)k
0inputs+40outputs (0major+36676minor)pagefaults 0swaps

The proof is 1.4 Kb in size.


KDF based on HMAC-SHA-256 Is KDF based on HMAC-SHA-256(Hashed Message Authentication Code, Secure Hash Algorithm) algorithm a suitable option to generate symmetric key from the secret key?

What is the basic funda, behind using KDF after getting the secret key. Can the secret key itself be used as the symmetric key.

Yes, according to NIST SP 800-56A revision 2, a KDF based on HMAC-SHA-256 is a suitable option.

The basic idea behind using a Key Based Key Derivation Function KBKDF is that the output of the the primitive within the key agreement protocol (DH, ECDH) returns enough entropy for a key to be created. However that entropy may still be distinguishable from random. For instance, the first bit of the secret after a Diffie-Hellman key agreement will certainly be biased. Hence it is required that a KDF extracts the entropy into a key that is indistinguishable from random.

Besides the extraction of the entropy, the KDF may also be used to expand the amount of key material. This key material can be generated by supplying different otherInfo or counter to the KDF (preferred) or by requesting a larger output from the KDF. Note that the entropy within the keys is still bounded by the entropy in the output of the extraction phase or the internal state of the KDF.

The question if the secret can be used as symmetric key directly depends on the key agreement used. I've asked a specific question for Diffie-Hellman here. Note that the KDF calculation should take a small amount of processor time and memory, especially compared to for instance DH or ECDH.


Cracking a hash when you know the result? If I know that the algorithm used is SHA1 constructed as salt+key, and I have the result, is it possible to find the salt?

Example:

sha1(saltExamplealturkovic) => 4e6a306ff65e252571f36972949f45e513b79ba7

In this example, I know that the input value is alturkovic, the result is 4e6a306ff65e252571f36972949f45e513b79ba7, how it is constructed and that SHA1 is used as the hashing algorithm. I would like to find out what salt was used (with some common sense limits of course, such as length).

I tried using hashcat but I can't figure out if this can even be done using such a tool...

TL;DR: Salts are too long to try and brute force them.

In theory
You can create a mask attack using hashcat, specifically a hybrid attack.
Let's assume you know that the salt used is (only) 4 numbers.
-a 7 ?d?d?d?d myKnownKey.txt

myKnownKey.txt contains the key alturkovic.
This setup would then try out these combinations:

0000alturkovic
0001alturkovic
0002alturkovic
$\ldots$
9999alturkovic

This is one example of how to create hybrid attacks using hashcat.

In practice
In practice salts are (as SEJPM commented) of course not only just 4 digits long but they are very long random alphanumerical characters and thus renders any brute force attacks impractical.


Hashes as mutually independent keys For cascading encryption (ie. AES-Twofish-Serpent), the most secure implementation is with mutually independent keys. My question is if it is secure to hash the previous key for each layer of encryption. In my case, Serpent will be the innermost cipher and AES the outermost.
password = "my_hopefully_secure_password"
masterKey = argon2(password,...)
serpentKey = sha3_256(masterKey)
twofishKey = sha3_256(serpentKey)
aesKey = sha3_256(twofishKey)

ciphertext = aes(twofish(serpent(plaintext,serpentKey),twofishKey),aesKey)

In this case, an attacker would have to attack AES first, since it's the outer shell. Suppose that the attacker successfully found the key to AES and decrypted it. Now the attacker is left with Twofish and Serpent, but the AES key doesn't reveal anything because it's a hash of the Twofish key (hashes are one-way). If the attacker broke Twofish, they still wouldn't know Serpent's key because the Twofish key is only a hash of the Serpent key.
Is this secure?
Edit: Is this secure and does it provide 256-bit security? Would this scheme correctly implement cascading encryption and provide three layers of protection?

The security is considered to be proportional to the size of the keyspace. In your proposal, the keyspace is not increased by adding encryption layers since all keys are derived from a single password.
In the proposed case Hashes are not mutually independent keys since they are derived from a single password. If they are derived from separate password then the algorithm provides three-layered security
Based on the proposal, it can be inferred that the sequence of encryption and the key derivation has to be kept secret for improving security. This is Security through obscurity and is not considered as any stronger. Wiki
If the algorithm is not hidden then cascading encryption with keys derived from the same source is not adding any layers (additional time penalty to brute-force keys at each stage) therefore no better than one layer of encryption, that is the outermost layer.
It provides one layer of encryption with a strength depending on password complexity.


Can you help me understand Pollard's rho example? I'm studying the Pollard's rho algorithm to solve discrete logaritms on the Handbook of applied cryptografy but I didn't understand one part of the theory and looking at the example gets me more confused.
This is the example

The first thing that I don't understand is how do you know that an element is on $S_1$ or $S_2$ or $S_3$ (in general not in in this example because is explained)and the second thing is: where did he get mod 3?

The algorithm is clear about all your questions. The partitions of $G=\mathbb{Z}^{*}_{383}$ are the sets
$$S_1=\{x \in G: x \bmod 3=1\}$$
$$S_2=\{x \in G: x \bmod 3=0\}$$
$$S_3=\{x \in G: x \bmod 3=2\}$$
Here are the left parts ($x_i$) of the computation slightly more detailed with $x_i \bmod 3$ and the corresponding sets $S_k$

i    x_i    x_i mod 3  S_k          x_(i+1)
1    228        0       2       228^2 mod 383 = 279
2    279        0       2       279^2 mod 383 = 92
3     92        2       3       2*92  mod 383 = 184
4    184        1       1     228*184 mod 383 = 205
5    205        1       1     228*205 mod 383 = 14
6     14        ...


In an A5/1 stream cipher, why do the registers have a stepping probability of 3/4 I know that the probability of each register to step is 3/4 but I have yet to find an explanation of why. Can anyone explain this to me?

In A5/1, there are three shift registers (about 20 bits each), each with a certain bit (about in the middle) controlling clocking. At each cycle, a register is shifted when its clock bit agrees with one or both of the other two clock bits.

Under the fair approximation that the clock bits are random, independent, and evenly distributed, a given register is thus shifted with odds $3\over4$ (derivation: as the odds of a coin toss matching either of two other coin tosses).


How does Bluetooth pairing (SSP with numeric comparison) work? I have a question concerning the pairing of two Bluetooth devices using Simple Secure Pairing with numeric comparison.
The NIST document I am looking at states on page 14:

  Numeric Comparison was designed for the situation where both Bluetooth devices are capable of displaying a six-digit number and allowing a user to enter a “yes” or “no” response. During pairing, a user is shown a six-digit number on each display and provides a “yes” response on each device if the
  numbers match. Otherwise, the user responds “no” and pairing fails. A key difference between this operation and the use of PINs in legacy pairing is that the displayed number is not used as input for link key generation. Therefore, an eavesdropper who is able to view (or otherwise capture) the
  displayed value could not use it to determine the resulting link or encryption key.

And on page 15, there is a graphic that illustrates the “Link Key Establishment for Simple Secure Pairing”:

Now…

To check on things, I've used a Bluetooth packet capture to sniff the traffic on my phone to see the pairing details. I expected the Bluetooth packet capture to log the details about the $PK$ that was sent and received by the controller. I do see the User Confirmation Request containing the number for the numeric comparison, but I am not able to detect any infos about a $PK$ exchange – as if such an exchange never happened. Therefore, it would be nice to get a confirmation if Simple Secure Pairing indeed uses a $PK$ – and at what point it actually exchanges it.

TL;DR:

I don't understand how the “Link Key Establishment for Simple Secure Pairing” prevents a MITM attack. It seems as if attackers could send a false $PK_2$ nevertheless… or did I miss something?

I think that you miss the point of this method. You can think of this SSP as a key-exchange protocol between two devices which have nothing shared between them a priori and also the entire communication is inspectable and even temperable, that is, the adversary can modify/send messages as it wishes. The big advantage of this SSP method over a usual key-exchange protocols (i.e. between computers over the Internet) is that the devices have a human linking between them, or abstractly, authenticated communication channel that cannot be tampered with by the
adversary and can be used to send a short message.

Regarding the MITM attack, I'm not very familiar with the spec but looking at this makes it more clear: Assume that as an attacker you execute this key-exchange protocol with both devices A and B. Let $pk_A, pk_B$ be the public keys of A and B resp. and let $pk_A',pk_B'$ be the keys that you (the adversary) choose in the execution between you and A and between you and B resp. Now the number that appears on the screen is a function $H$ (truncated as needed) applied to the keys of the parties (and some more random strings but let's skip it for simplicity), that is, the number on A's device would be $c_A=H(pk_A,pk_A')$ (where the adversary behaves as device B) and the number on B's device would be $c_B=H(pk_B',pk_B)$ (where the adversary behaves as device A). The goal of the adversary is to make $c_A=c_B$ in order for the device to be "paired". The randomness of $pk_A$ dictates that $c_A$ is random as well, which means that in order to make $c_B=c_A$ the adversary has to find a $pk_B'$ such that $c_A=H(pk_B',pk_B)$. This is a hard problem (as finding a preimage for a hash function) and thus the MITM attack could not be held successfully.


Is there any way to have a coded string such that it can be decoded in multiple ways? This is more out of curiosity than anything, having no knowledge of cryptography.

But say I have strings "test1" and "test2", is there any way/algorithm to encode the two strings to an encoded string "string" such that when "string" is decoded with "key1", it returns "test1", and likewise for "key2" and "test2"?

Thanks!

Maybe this example is only remotely related to the question, but anyway:

VeraCrypt application for encrypting computer's disks has an ability to offer part of the disk capacity to reach the plausible deniability with the help of 2 different passwords:

the first one unlocks so called outer volume with a non-important content,
the second one unlocks inner, hidden volume with the important content.

So both passwords are used in the same manner (in a command or a dialog box) and only by choosing between them decides which content will be accessible.


Is jacobian to projective conversion unique? I am doing a small project in ECC. I have used the following equation for converting Projective to Jacobian coordinates:

$$D = AC\\
E = BC^{2}\\
F = C$$

and also the following equation to convert Jacobian to Projective coordinates:

$$A = DF\\
B = E\\
C = F^{3}$$

where $(A,B,C)$ represents a point in Projective coordinates and $(D,E,F)$ represents a point in Jacobian coordinates.

What I’m having doubts about: if I convert a point from Projective to Jacobian coordinates using the first equation and also use the second equation to convert back to projective, then how will the first and last point be related? Or will it be the same?

You'll get back the same point; however it may be a different representation of the same point.

Remember, an elliptic curve point is a solution to a cubic equation in two variables (or the point at infinity); one commonly used equation is $y^2 = x^3 + ax + b$ modulo a large prime $p$.

What projective coordinates do is encode the $x$ and $y$ coordinates of the solution; the projective coordinates $(A,B,C)$ are considered equivalent to the solution with $x = AC^{-1}$ and $y = BC^{-1}$.

Notice what we have here; if we take an arbitrary nonzero value $t$, and replace $(A,B,C)$ with $(tA,tB,tC)$, it turns out that it is equivalent to the exact same solution $(x,y)$, and so it is the exact same point; it is just a different representation of that same point.

If you go through what happens when you use the algorithm to map from projective coordianates to Jacobian, and then back again, it turns out the process multiplies $A$, $B$ and $C$ by the value $C^2$; $C^2 \neq 0$, and so after this process, the new projective coordinates refer to the same elliptic curve point.


Security concern with TOTP I am pretty new to cryptography and I have been studying up on TOTP (Time Based OTP) and while I have learnt how the computation works, I'm unable to figure out why using TOTP makes a system more secure.

Here's what I have understood. TOTP is used for 2FA, so the first factor would be your username and password. This as we know is not very secure in itself and hence we use the second factor, here the OTP.

So with TOTP, there is a secret key that both the server and the client have. So my question is that if an attacker has gained access to this secret, would he not be able to generate the OTP just as easily as the client software on my system because HOTP(key,counter) will remain the same for all? So to ensure TOTP is helpful, I have to make sure that the secret key with the client is safe? Let's say I'm making a software that is to be used by the public which uses TOTP based authentication. So will I be attaching a different secret to each of the clients and maintaining a database on the server end to match the secret server side?

If not, what's a safe way to have the same secret on both client and the server in this case?

So my question is that if an attacker has gained access to this secret, would he not be able to generate the OTP just as easily as the client software on my system because HOTP(key,counter) will remain the same for all?

Yes, if an attacker learns your shared secret, he can calculate OTPs whenever she wants. But this is very unlikely, since every secret is unique (no reuse, like with a password) and never transmitted (apart from the initial agreement) a direct hack of the server or the client's token is the only possibility of obtaining it.

  So to ensure TOTP is helpful, I have to make sure that the secret key with the client is safe?

Correct.

  Let's say I'm making a software that is to be used by the public which
  uses TOTP based authentication. So will I be attaching a different
  secret to each of the clients and maintaining a database on the server
  end to match the secret server side?

Yes. Every user has a different key on your service. If you store it in a database or obtain via some deterministic calculation from a master secret is up to your implementation.


Zero-knowledge-proofs on committed value Assume user $A$ with corresponding public-private keys $(pk,sk)$ and a public information $r_1$ and $r_2$.

Let $r_{1s} = Sign(sk, r_1)$ be the signature on $r_1$ generated using $sk$ and $c = Hash(r_2 || r_{1s})$.

Now given $r_1, r_2$ and $c$ are publicly available can user $A$ produce a zero-knowledge proof that $c$ is generated correctly without revealing $r_{1s}$ and $sk$ ? If so how?

Thanks in advance.

Yes, user $A$ can produce such a proof - indeed, any statement in NP (i.e., for which it is possible to verify that a given solution is valid, which is obviously the case here) can be proven in zero-knowledge.

In general though, proving non-algebraic statements of this kind (involving evaluations of hash functions, rather than algebraic manipulations such as exponentiation) is more costly and less easy than proving algebraic statements. Yet, this kind of questions have been considered at length. There are currently three main approaches:

Using garbled-circuit-based techniques, see e.g. this paper and some follow-ups
Using MPC-in-the-head techniques, introduced in this seminal paper and subsequently improved in Zkboo, ZKB++, and this recent paper.
A slightly different approach was taken in Ligero, using error-correcting codes, achieving a cost that scales only with the square root of the size of the circuit representing the statement (all previous solutions are linear).

Other techniques can also apply here, depending on your other constraints: should the prover be efficient? The verifier? Do you need the proof to be non-interactive? As short as possible? For each case, different solutions exist and provide various tradeoffs.


Cryptanalysis and weaknesses of SEED cipher I've discovered that a client has SEED enabled in their SSL ciphers, and would like to know a bit more about it from a security perspective. The Wikipedia article doesn't mention any flaws, yet I've found two papers that demonstrate attacks - a differential fault analysis, which is fast but has infeasible requirements, and another differential attack that breaks 8 rounds.

For example, this paper says you can do key recovery by injecting faults into the input registers of the G function. What does that entail at a practical level?

Am I missing anything else? Is there anything I should warn them of?

A fault injection attack is based on the fact that you have a healthy black box on which you can do queries, but you can mess with the black box, for example flipping random bits.

In real life this could for example be a RFID chip which can be messed with using strong electronic fields. Attacks like these are generally:

Very sophisticated in theory and equipment.
Only apply to "black box models"; you have a side channel into the crypto device, but can't actually access the key.

Other than that, I'm not aware of any successful cryptanalysis against full-round SEED. So my suggestion is to warn your client of the hardware side-channel attacks (but since the question is about SSL I don't think it's applicable), but also make sure their software implementation is side-channel free.


Is SSL getting faster because it's getting less secure? There has been some discussion about it being more practical to use SSL due to advances in hardware. From my understanding, stronger public-key encryption means that both encrypting/decrypting and breaking it (via brute-force or vulnerabilities) take longer.

Is the return (in security) for the performance loss of using SSL increasing, or has today's hardware simply outgrown the strength of encryption used?

There are several effects coming into play. But the most important property is that with increasing keylengths, the attacker's work becomes exponentially expensive, whereas the defenders work only becomes slightly more expensive.

Looking at the different kinds of cryptography in use:

Symmetric cryptography

Originally we used DES and 3DES. DES had a dangerously small key and decent performance. 3DES had a secure keysize, but bad performance (3 times as slow as DES).

So AES was developed which has very good performance and secure key sizes. AES-128 is secure against brute-force for a long time and AES-256 is secure against brute-force using conventional and quantum computers forever.

So unless there are major advances in crypto-analysis, there is no reason to use symmetric cryptography slower than AES-256, no matter how fast the attacker's computers get. AES performance becomes significantly better on the current generation of processors, which offer specialized instructions.
RSA used in the key-exchange

The defender's cost grows with the key-size to the third power. The attacker's cost growth much faster, but doesn't double with each bit. So we need to increase key-sizes somewhat to compensate for the increased computational power of attackers. For example 1024 bit RSA keys are currently being replaced by 2048 bit keys, because cracking them will become possible soon.

Still the defender's advantage grows as computers get faster.
Better asymmetric algorithms

Elliptic curve cryptography is much faster than RSA. Currently it doesn't get used much for authentication in SSL, only for the ephemeral key-exchange using ECDHE suites. But in principle they allow a 128 bit security level with better performance than 1024 bit RSA keys.

In general modern cryptography is at a level where brute-force is no longer a threat for most schemes. The main trade-off is performance vs. how resilient to crypto-analysis the ciphers are. But even there we're only talking about a small constant factor that doesn't scale with computational power.

Unless there are major advances in crypto-analysis or computer science in general, I expect the processor cycle cost of cryptography to remain approximately constant. This means that effectively it'll get faster at the same rate as our processors.

In particular that means that the hand-shake costs effectively becomes much cheaper as computers get faster, whereas encrypting the connection itself will stay at a constant cost, assuming bandwidth (and thus the amount of data) and processor speed increase at the same rate. Luckily symmetric encryption is already very fast, especially on processors supporting specialized AES instructions (more than 1GB/s on a single core). Generating dynamic webpages is typically more expensive than encrypting them afterwards.


Hardness assumptions on composite order bilinear groups I am not at all knowledgeable in elliptic curve cryptography. So, here lies a couple of questions that I failed to find answers for to my satisfaction.

Is there any known Type-III bilinear pairing defined over composite order groups?
Do DLIN/SXDH assumptions hold in composite order groups?

The BGN (Boneh Goh Nissam) cryptosystem uses a Type-III bilinear pairing defined over composite order groups to have 1 homomorphic multiplication along with unlimited homomorphic additions.
You may want to have a look at their paper: Evaluating 2-DNF Formulas on Ciphertexts, or any lecture on this cryptosystem.

I hope this will help you.


Is the openssl implementation of ECDH missing something? From the OpenSSL Wiki:

  Also note that the derived shared secret is not suitable for use directly as a shared key. Typically the shared secret is passed through some hash function first in order to generate a key.

My understanding of ECDH is that it generates a very secure shared secret. Why does it have to be hashed too?

There are two reasons:

Reason one is that the ECDH shared secret is not equidistributed; not all values are possible.  In particular, and $x$ that is not a possible solution to the elliptic curve equation cannot happen at all.

Things that use the shared secret (such as AES) are generally assumed to have uniform keys; that is, all keys are possible (and are equiprobable); this isn't possible when using the ECDH shared secret directly.

In practice, it probably doesn't matter; it's hard to conceive of an attack that becomes practical because half of the possible $x$ coordinates are impossible.

Reason two is that not all bits of the ECDH shared secret are actually independent.  If the part of the shared secret bits start going into the $y$ coordinate, then if the attacker somehow gets the $x$ coordinate bits, he gets the $y$ coordinate bits for free (well, one of two possibilities).

We try to avoid revealing some of the bits of the key; however having some bits imply others isn't what we want.  A proper KDF (key derivation function) avoids this possibility.

Note: reason two doesn't apply to all elliptic curves; for example, with Curve25519, we don't explicitly compute the $y$ value, hence that's not available as part of the shared secret.  However, it is present for other curves.


Homomorphic Modular Reduction for Secure Storage My question is quite similar to Homomorphic modulo, but I want to give a context where the operation is carried in an outsourced environment.

Are there any specific homomorphic cryptographic schemes that could do the modular reduction and subtraction operations at the same time.

Suppose $Enc(x)$ a ciphertext of $x$ after homomorphic encryption, and $mod$ is modular reduction operation.
$$(Enc(x)-Enc(a))\ mod\ Enc(N) == (x-a)\ mod\ N$$
While $x$, $a$ and $N$ are all natural numbers. And $N$ are bigger than $x$ and $a$.

I know that $mod$ can be transformod into additional ($+$) and multiplicative ($*$) operations, which are operations supported by HE. But I don't want the factors exposed to someone who carry such operations, like $Server$.

For example

$(6-5)\ mod\ 10 = 1+(0*10)=1$, $(4-5)\ mod\ 10 = -1+(1*10)=9$

But when a $Server$ is assigned do this, the factors like $0$ and $1$ here are exposed.

So I'm wondering, are there any specific HE schemes that can do modular reduction operation directly, or are there any solutions that can keep $Server$ from knowing the factors?

Your modulo operation does not require a real division, because you are not far from your modulus.

Represent your numbers with 2's complement by using TFHE, or HELib libraries. In this case, your numbers use bit arithmetic in FHE, i.e. you will have a cyphertext $\{c_0,c_1,\ldots,c_{k-1}\}$ for $k$-bit numbers.

What operation do you need?

$Add(A,B)$ : homomorphic addition
$Sub(A,B) = Add(A,-B)$ : homomorphic substraction by using $Add$.
$MSB(A)$ : return the most significant bit of the ciphertext
Comparison $Comp(A,B) = MSB(Sub(A,B)) = MSN(Add(A,-B)) $
If : for singe if else case with single encrypted bit $S$, $$I = S \cdot A + S' \cdot B$$ where $\cdot$ is the $\text{AND}$ operation. According to value of $S$, $I$ is either $A$ or $B$.

More details on these operations can be found in a previous answer about common circuits in FHE.

Let $A = Enc_{pk}(A)$, $B=Enc_{pk}(b)$, and $N = Enc_{pk}(n)$ be encryption of plaintexs $a,b,\text{and } n$ under a semantically secure Fully homomoerphic Encryption with public key $pk$, where $n$ is the modulus.

$S = Sub(A,B) = Add(A,-B)$
$C = MSB(S)\quad\quad\quad\;$          //one bit comparison the result.
$F = S + N\quad\quad\quad\quad\;$      // adding modulus if needed
$R = C * F + C' * S\quad$  // If condition on $C$ selects either $F$ or $S$.
Return $R$

The circuit is not complete because the answer can still be negative. In this case, compare with encryption of zero $E_0 =Enc_{pk}(0)$and add $N$ again.


Is PRG On Concatenation of Input a PRG This is a homework assignment, so I'm not expecting full solutions, just general guidance.

  Let a PRG $G:\left\{ 0,1\right\} ^{n}\to\left\{ 0,1\right\} ^{l\left(n\right)}$ (where $l\left(n\right)$ is a polynomial and
  $l\left(n\right)>n$).

  Is $G':x\mapsto G\left(x\|x\right)$ a PRG? (where $\|$ is the concatenation operator).

My intuition (that is probably wrong) says it is not, since $\left|Im\left(G'\right)\right|\leq2^{n}$ whereas $\left|Im\left(U_{l\left(2n\right)}\right)\right|=2^{l\left(2n\right)}>2^{2n}$.

I'm not sure however how to show this.

I want to show a distinguisher between $U_{l\left(2n\right)}$ and $G'\left(U_{n}\right)$ with a non-negligible advantage, so I get input $z\in\left\{ 0,1\right\} ^{2n}$ and need to decide from which distribution it came from.

I thought about just checking whether $z\in Im\left(G'\right)$, but that can take $2^{n}$ to compute.

I would love some direction. Thanks!

I think I figured out the solution.

Assume such G exists (a PRG).

Then G' as described here is a PRG as well.

But applying it on $x\|x$ results in $G'':x\mapsto G\left(x\right)\circ G\left(x\right)$, which is not a PRG (easy to construct a distinguisher that checks if its input $z=z'\|z'$).

It is also possible to use $G′:\left(x\|y\right)↦x\|G\left(y\right)$ instead.


What impact could general quantum computing have on BCrypt? While discussing the 72 character limit of BCrypt, the question of resilience to quantum cryptanalysis came up. A search online didn't give me much of a lead as to what research has been done in this area.

So my question is, are there any candidates for algorithms that would decrease the security of Blowfish, and by extention of BCrypt? If so, by how much?

I'm not aware of any quantum-based cryptanalysis results of symmetric ciphers that would perform better than Grover's algorithm on any symmetric cipher.

Now here's the interesting part: Grover's algorithm. It allows you to search in an unsorted set of size $n$ in time $\sqrt n$. Now for Blowfish the implication is clear: It effectively halves the keysize from 448-bit to 224-bit which is still extremely strong. However you shouldn't use Blowfish because of its blocksize and the fact that it's nearly broken by cryptanalysis.

Now for bcrypt we need the following statement:

  Grover's algorithm is a quantum algorithm that finds with high
  probability the unique input to a black box function that produces a
  particular output value, using just $\mathcal O(\sqrt n)$ evaluations of the function, where N is the size of the function's domain.

Now Grover's algorithm allows you to find passwords much faster, but won't evaluate bcrypt faster but probably much slower. So suppose you have a password hash that has a strength of 80-bit, ie one would need $2^{80}$ operations to find the password. Chance are bcrypt takes 20-bits from that leaving you with 60-bits provided by the entropy of the password. Grover's algorithm can now half this value so you end up at $2^{30}$ bcrypt evaluations and thus $2^{50}$ operations overall.

TL;DR: Quantum computers will weaken password hashing but "as bad" as they weaken standard encryption.


Can RSA signing be implemented on top of RSA encryption/decryption? I need to use RSA-SHA256 signing. Unfortunately not all Microsoft CryptoAPI providers support that. It's possible that I might get a handle to a CryptoAPI provider that can just encrypt/decrypt with RSA, and maybe sign with SHA1, but not SHA256. Also, the private key might be unavailable (say, it could be in a smart card or some such device).

Is it then possible for me to "fill the gaps" myself? I can, after all, calculate the SHA256 hash of the data myself. Can I then somehow encrypt it with the provider and get a valid signature? Simply encrypting the hash doesn't seem to work (it produces the wrong result).

Or is the signing algorithm a modification of the encryption algorithm, and if the provider doesn't support it, then there's physically nothing that I can do?

Yes, you can, but you would need access to raw or textbook RSA encryption and you would have to implement the PKCS#1 v1.5 or PSS padding primitives yourself. Beware that PKCS#1 v1.5 compatible padding is different for encryption signature generation.

If you only have PKCS#1 v1.5 encryption or OAEP encryption available then the encryption routine will already pad your data, and in that case you cannot use the encryption API to sign.

The padding methods in common use are found in RFC 3447 which basically is a copy of RSA/EMC's PKCS#1 v2.1 specification.


Scalar product of vectors over polynomial rings I have been studying about homomorphic encryption (HE) lately, and I am trying to perform simple computations over encrypted data. Specifically, I am interested in the scalar product between two vectors.
I came across this presentation about HElib (an implementation of HE) and on slide 32 there's this particular way of encoding vectors that gives use the scalar product after we multiply the polynomials that represent them:

Given $v=[1, 2, 3]$, $u=[4,5,6]$
If we make two polynomials such as $V(x) = 1 + 2x + 3x^2$, $U(x)=4 + 5x + 6x^2$
But $V(x)U(x) = 4 + 13x + 28x^2 + 27x^3 + 18x^4$
Change a little bit $Û(x) = 6 + 5x + 4x^2$
$V(x)Û(x) = 6 + 17x + 32x^2 + 23x^3 + 12x^4$
$32 = \langle v, u \rangle$

So my question is: How to choose the polynomial encoding of the vectors in order to obtain the scalar product value from a particular coefficient after multiplication? In other words, why inverting the representation of $U(x)$ to $Û(x)$ gave us the scalar product in the third coefficient?

To encode vectors following that technique, you just have to generalize it.

For any two $(d+1)$-dimensional vectors $a = (a_0, a_1, ..., a_d)$ and $b = (b_0, b_1, ..., b_d)$, define the polynomials $a(x) = a_0 + a_1x + ... + a_dx^d$ and $b(x) = b_d + b_{d-1}x + b_{d-2}x^2 + ... + b_0x^d$.

Then, when multiplying $a(x)$ by $b(x)$, among all the coefficients that we multiply, we will multiply $a_0$ by $b_0x^d$, also $a_1x$ by $b_1x^{d-1}$, $a_2x^2$ by $b_2x^{d-2}$, and so on... Notice that all that multiplications are of the form $a_kx^k \cdot b_kx^{d-k}$, which result in $a_kb_kx^d$. Therefore, if we look to the $d$-th coefficient of the product polynomial we will see

$$\left( \sum_{k=0}^d a_kb_k \right) x^d$$

and that summation is exactly the inner product between the vectors $a$ and $b$.

It is worth noting that if this summation is greater than the module of the plaintext ring (usually a parameter $t$ or $p$), than the decoding will not work. Also, that representation is only possible if that value $d$ is smaller than the degree of the polynomial used to define the quotient ring (usually a cyclotomic polynomial).


Is sharing the RSA public key secure? I am trying to understand how RSA public key cryptography works. I have the following questions:

Are any attacks / compromises possible if a server sends its public key $(n,e)$ in the clear to a client?
Suppose a server is using the same public key $(n,e)$ for all the clients in a LAN. Does this pose a threat?

Are any attacks / compromises possible if a server sends its public key $(n,e)$ in the clear to a client?

Nope, it's a public key; it's designed to be public. Shout it out loud, tell the world, there's no risk.

That said, you want to be sure that a Man In The Middle attacker can't intercept the message and replace your public key with their own and then pretend to be you. The only real way to prevent this in to get your public key embedded into a Public Key Certificate tying that public key to your server in some unique way (IP, or domain name, or email address, etc) by a Certificate Authority that both you and the other person have in their trust store. (I'll leave out further details from this post.)

  Suppose a server is using the same public key $(n,e)$ for all the clients in a LAN. Does this pose a threat?

Yup, that's fine.


Complexity of Discrete Logarithms in binary fields without special exponents or special structure There has been recent work, due to Joux, Gologlu, Zumbragel and others which has developed efficient algorithms for discrete logarithms in small (and specifically binary) characteristics, where the exponents have some special form. See the discussion in the questions

how-robust-is-discrete-logarithm-in-GF(2^n)

and

do-recent-announcements-about-solving-the-dlp-in-gf26120-apply-to-schemes?noredirect=1&lq=1

My understanding is that discrete logarithms in $\operatorname{GF}(2^n)$ where $n$ is large and has no special for is still relatively robust to attacks.

Here is the question, say I pick $n$ large enough such that the multiplicative group $\operatorname{GF}(2^n)^{\ast}$ has no small subgroups. So either $2^n-1$ is prime, or $n$ is so large and well chosen that the largest subgroup is large enough.

Would the best algorithm in this case still be baby-step-giant-step for the discrete logarithm? Or something else of still exponential (in $n$) time and memory complexity?

Edit: My hunch that the best complexity is exponential was incorrect. It is actually quasi-polynomial (thanks to Samuel Neves for his comment).

Recall that  Coppersmith's algorithm has complexity
$$
L_{2^n}(1/3,c)
$$
for a small constant $c,$ while even for $n$ prime, which is the hardest case,  discrete logarithms over $GF(2^n)$ using Barbulescu et. al.'s method   have quasi polynomial complexity
$$
O(2^{c(\log n)^2})\asymp c' n^{c \log n}.
$$

Note that the authors state "The crossing point between the (best knoen before) L(1/4) algorithm and our quasi-polynomial one is not determined yet".


Mac-sforge motivation for storing pairs I don't understand why Q keeping pairs of  instead of m like mac-forge solves the problem of generating a new tag on a previously authenticated message. Say, a previously authenticated message for "Cat" is tag 90, Adversary can retrieve (Cat, 90) from the query. However, if Adversary is able to successfully forge a new tag (Cat, 138), I almost feel as if sforge weakens the definition. Q has Cat, but it doesn't have 138 as the tag, so this will pass mac-sforge, but not pass mac-forge. Could someone clarify my confusion?

Relevant passage From Katz and Lindell:

"As defined, a secure MAC ensures that an adversary cannot generate a valid tag on a new message that was never previously authenticated. But it does not rule out the possibility that an attacker might be able to generate a new tag on a previously authenticated message. That is, a MAC guarantees that if an attacker learns tags t1, . . . on messages m1, . . ., then it will not be able to forge a valid tag t on any message m ̸∈ {m1, . . .}. However, it may be possible for an adversary to ”forge” a different valid tag t′1 ̸= t1 on the message m1. In general, this type of adversarial behavior is not a concern. Nevertheless, in some settings it is useful to consider a stronger definition of security for MACs where such behavior is ruled out.

Formally, we consider a modified experiment Mac-sforge that is defined in exactly the same way as Mac-forge, except that now the set Q contains pairs of oracle queries and their associated responses. (That is, (m, t) ∈ Q if A queried Mack(m) and received in response the tag t.) The adversary A succeeds (and experiment Mac-sforge evaluates to 1) if and only if A outputs (m,t) such that Vrfyk(m, t) = 1 and (m, t) ∈/ Q.

DEFINITION 4.3 A message authentication code Π = (Gen,Mac,Vrfy) is strongly secure, or a strong MAC, if for all probabilistic polynomial-time adversaries A, there is a negligible function negl such that:
Pr[Mac-sforgeA,Π(n) = 1] ≤ negl(n)."

A security definition is stronger if we make it easier for the attacker to win. The point being that the stronger definition rules out even this easier way of winning

In the specific case noted in the question, you are indeed correct.
The scenario you describe is the following:

An attacker queries "Cat" and receives the tag "90". It then computes the tag "138" such that $\mathsf{Vrfy}_k(\text{Cat},138)=1$ and outputs the pair $(\text{Cat},138)$.

The regular $\mathsf{MAC\text{-}forge}$ experiment will reject this output. I.e., the attacker does not win, and therefore this security definition does not rule out the existence of said attacker.

The stronger $\mathsf{MAC\text{-}sforge}$ experiment will accept this output. I.e., the attacker wins, and therefore this security definition rules out the existence of said attacker.


What is the advantage of Encrypt-then-MAC over Encrypt & MAC separately the plaintext For secrecy, authentication & integrity, you can either use

CipherText = Encrypt(PlainText)
Signature  = Hash(PlainText)

CipherText = Encrypt(PlainText)
Signature  = Hash(CipherText)

Either case, you send both CipherText & Signature to the receiver.
What is the advantage of one method over the other? Does it differ in case of Symmetric vs Asymmetric Encryption?

I'll be assuming the question means Message Authentication Code (MAC) where it uses "Signature" and "Hash". MAC, signature and hash are three different things: MAC uses a secret for generation and verification, signature uses a secret for generation only, hash uses no secret.

Following comment, and most important: sending in clear a MAC of the plaintext, as in "encrypt and MAC separately" sending $\operatorname{ENC}(M)\mathbin\|\operatorname{MAC}(M)\,$, without any further specification about the MAC, would be very poor practice: depending on the MAC, that can leak some information about the message $M$. In particular, for any deterministic MAC (as HMAC is) and a fixed key, identical messages will lead to identical MACs, and are thus trivially detected, breaking IND-CPA security.

The other historically used argument for encrypt-then-MAC (against MAC-then-encrypt) is that the seemingly natural corresponding procedure on the receive side is verify-MAC-then-decrypt, implying that decryption will only be carried on ciphertext that passed an integrity test. The adversary thus can not observe use of the decryption key on ciphertext that it chooses arbitrarily, since that ciphertext won't pass the MAC test and won't be decrypted. This in turn blocks a number of attacks that submit artificial or altered ciphertext to a decryption device, and use it's observed behavior to deduce useful information, or induce some desired behavior.
One example of vulnerable decrypt-then-verify-MAC would be an implementation where decryption is followed by a padding check, insuring that the last 16-byte block of ciphertext ends with 0 to 15 byte(s) at 0x00, then (walking back) a byte at 0x80; and if not aborts the use of the received ciphertext, only performing the MAC check if it does. By observing the timing of the decryption device, an adversary could then determine if the padding check fails or succeeds. For block encryption in CBC mode, iterating that apparently minor information leak allows decryption.
Other examples can be made, including side-channel attacks by differential power analysis of the decryption, when limited valid ciphertext is available to the attacker.

One serious problem with this historical argument for encrypt-then-MAC is that it is technically valid only if there is verify-MAC-then-decrypt on the receiver side. However, it is entirely possible to run decryption and MAC verification concurrently even for ciphertext produced with encrypt-then-MAC. And such concurrency is highly desirable, for it avoids scanning the ciphertext twice, which typically would have an impact on performance, at worse would make using crypto impractical.
Also, by integrating integrity check with encryption, it is possible to get the integrity part at sizably lower computational cost than that of a MAC. For these reasons, state of the art is authenticated encryption, such as AES-GCM-SIV. Thus in modern practice we do not encrypt-then-MAC, and even more seldom verify-MAC-then-decrypt, making this historical argument pointless. Authenticated encryption does secrecy, authentication & integrity in one primitive, no necessarily with a separate generic MAC.


"Strict" software for playing and learning with private and public key my question is just for teaching/learning practice and I think it's not meaningful for the real world.

I've played with openssl a lot but from my understanding it's somehow not strict in the format of the input because it's capable of understanding different format or doing some operations not transparently to the user.

Getting to the question: is there way by using openssl to get just the private key from the key pair and from that private one to compute the public key? An example:

When I do openssl rsa -in private.key -pubout I know that openssl does not compute the public key from the private but it just extracts the information that is alredy stored in the keypair (private.key is indeed a store for the pair).

Also openssl pkey -in private.key -text claims to extract the private key but how I can be sure that it's not another keypair storage? Ideally I would use another software than openssl that IS stricter with the input it receives and feed it with the private key and that would complain if as input it's given the keypair.

It might be that the confusion I'm trying to clear comes from the fact that maybe I'm missing some details of the cryptography but I'd like to check that by playing with different softwares (i.e. encrypting data with one software and decrypting it with another), again a software that is strict about what it gets as input, in another terms not-user-friendly but learner-friendly :-)

For software I prefer to have something at hand and not to compile anything.

Thanks for reading till here :-)

Alex

I'd suggest to get OpenSSL source, build it, and run it under debugger,
watching exactly what "-text" is doing to private key.
One could verify exponentiation operations with a calculator having big numbers capability.
ASN.1/DER parser could be handy to see private key file.


MD5 - Chosen Prefix Collision Attack Given 2 messages $m_1$ and $m_2$, in a chosen prefix attack, we want to find $s_1$ and $s_2$ such that:

$\text{MD5}(m_1 || s_1) = \text{MD5}(m_2 || s_2)$

Are $s_1$ and $s_2$ found by brute force or are there some rule(s) to construct $s_1$ and $s_2$ based on $m_1$ and $m_2$?

The answer is due to the Stevens et. al's work ;

Chosen-prefix collisions for MD5 and applications,  2012.

They showed that, with an approximately $2^{39}$ calls to the MD5 compression function, it is possible, for any chosen $m_1$ and $m_2$, to construct $s_1$ and $s_2$ such that $$\text{MD5} (m_1\mathbin\|s_1) = \text{MD5} (m_2\mathbin\|s_2)$$
They also gave examples for colliding documents, software integrity checking, etc ...


Security of SWIFFT Hash Function Is the SWIFFT hash function described in:

https://en.wikipedia.org/wiki/SWIFFT

still considered a provably secure one way function?  Is it also considered secure against attacks by a quantum computer?  Would it be a good candidate for a post-quantum (quantum safe) hash?

You have to be a bit careful here, I think.

The SWIFFT hash function is linear and does not behave like a random oracle. It is second pre-image resistant in an asymptotic sense. The fact that this property seems to depend on "a relatively mild assumption about the worst-case difficulty of finding short vectors in cyclic/ideal lattices" would seem to suggest (subject to verification) it might be post quantum secure (like NTRU which is also based on cyclic/ideal lattices).

However, the SWIFFT function is defined for fixed input length. Hence it cannot be directly used as a one way hash function for arbitrary length inputs, maybe it could be a building block for a post quantum secure one way hash function, I am not sure.


How does using salt reduce rainbow table attack? I could create a rainbow table for a particular salt value and still create a successful attack similar to one without salt value.

The point of a rainbow table for password cracking is to allow attacking multiple password hashes with only a little less work than for cracking a single password hash.

Building a rainbow table takes about as much time as worst time for cracking a single password hash (just calculating the crypto operations, not the table overhead). This is about double the time of the average cracking time, assuming an equal distribution.

This means for attacking a single password, a rainbow table only has the advantage that it can be build before we actually know the hash that is searched. A rainbow table only really pays when attacking multiple passwords, since the lookup is quite faster than building the table (the actual lookup time depends on the space used for the table).

When we build a new table for each single salt, we lose both advantages – we can't build the table before knowing the salt, and we can't use it for more than one password (assuming the salt is unique).
So you still can attack a salted password with a rainbow table, but this is more costly than attacking it directly – in other words, a rainbow table is useless.


a doubt in Rijndael's key expansion sizes I've often heard/read that AES key sizes 256 & 192 would be weaker than 128 or not stronger as expected from the size increase, but I've never seen a proof. How does one proof the strength of a Rijndael key size?

If I understand correctly, the main effect of having the key size different from the block size is on the key expansion. The iterative algorithm is moving along the columns, but the key size determines the number of columns. Later, this expansion is used in the addRoundKey() by taking sets that fit with the number of columns due to the block size.

I've been trying to understand, assuming this issue would be correct, from where this would come from.

AES-128 takes a 128-bit key, produces 11 128-bit subkeys out of it with a cryptographically weak function, and uses them in 10 internal rounds. It can be said that the full key is reused 10 times.

AES-192 takes a 192-bit key, produces 13 128-bit subkeys out of it (or, equivalently, 9 192-bit subkeys), and uses them in 12 rounds. The full key is reused 8 times.

AES-256 takes a 256-bit key, produces 15 128-bit subkeys (or 8 256-bit ones) and uses them in 14 rounds. The full key is reused 7 times.

Therefore, AES-128 uses its key more intensively, and AES-192 and AES-256 -- less intensively.  However, only very specific cryptanalytic attacks may exploit this property. For example, related-key attack can break the entire AES-256, but can not break the full AES-128. By ''break'' we mean that it is possible to produce ``similar'' ciphertexts from ''similar'' plaintexts on some particular key pairs. However, the related keys are rarely seen in practice, so this property is not much relevant to the actual security of AES.

To conclude, AES-256 can be considered weaker than AES-128 in a very specific setting only, and this setting is unlikely to occur in practice.


Does hashing PII in logs provide any real security? I have PII in my logs that I would like to replace with hashes (e.g. sha3-256(salt + email)). The idea is that I can always go back to my logs and find all the log lines with that email address, by searching on the hash result of sha3-256(salt + email).
How hard would it be for folks to retrieve the original email address? I'm assuming the salt is fixed, and kept secret and the salt is >= 32 bytes.
Will this setup provide any real security if the logs are leaked?
/W

Will this setup provide any real security if the logs are leaked?

One issue is the fixed salt.  With that, the translation of email to hash is fixed; that is, if the attacker sees two identical hashes, he knows that they were the same email address; he might not know what the email address is, but he knows that the two emails were to/from the same person.  And conversely, if the hashes were different, then they referred to two different email addresses.
One possibility would be to include a 'per-hash' salt (salt1), which is randomly selected each time you generate a hash [1], and so the email address would be replaced by salt1 + sha3-256( salt + salt1 + email ) (where + is string concatenation).

[1]: You could generate the per-hash salt sequentially if the order you generated the hashes didn't need to be secret; this would allow the per-hash salt to be shorter without worrying about duplications.


Entropy in natural language texts I have a couple of related questions:

I read about an estimate, ascribed to Shannon, of the entropy of English text to be between 0.6 and 1.3 bits per letter. The modern day corpus, including the huge and exponentially ever expanding volume of materials accessible via the Internet, is different from the one available a century back. Is there a revised estimate?

If one simply takes two books from one's small private library (that contains e.g. only very common novels) and arbitrarily select two starting points to combine with xor the letters, then the resulting pseudo-random sequence presumably could be argued to have a non-negligible risk of being attacked through brute-force by a knowledgeable opponent. But the actual choice of materials (including especially those via the Internet) to be combined is nowadays virtually unlimited. If one could thus appropriately choose a sufficiently large number of text sources to be combined, wouldn't the result be practically secure for crypto usages in view of the combinatorial explosion of the complexity that the attacker has to deal with? One could certainly also employ some more complex operations than xor and even a couple of different operations either simultaneously or in variations. Are some good schemes in this direction already being used in non-trivial practical applications?

[Added on edit:] A later work of Cover and King give an estimate of 1.34 bit per letter, which implies that appropriately combining 4 text files should lead to sequences of full entropy. Several weeks ago I wrote a software for that but unfortunately, due to a bug in codes used in its design, it had to be retracted for not being satisfactory. I have just released a carefully tested replacement, named TEXTCOMBINE-REV, in which I wrote in Prologue:

What has been achieved by the present software can be tersely summarized as follows, assuming the general case where the text files are sufficiently large:

(1) The generated byte sequences pass, via design specifications of the software, Maurer's universal test and the autocorrelation test for all d in the range [1, 16] as well as the ENT test with an entropy value according to it of at least 7.99 bits per byte. The software is namely coded such that it would give up, reporting failure, after a certain specified maximum amount of processing has been done without finding a solution.

(2) An extensive expermiment of the present author done on all different combinations, totalling 3060 in number, of 4 source materials (of size 600 KB each) taken from 18 different books of English literature downloaded from Project Gutenberg resulted in the following:

(a) No case of failure was ever encountered. On the contrary, the above mentioned processing limit, which is in terms of rounds of certain preprocessing of source materials before they are xor-ed together, was by far not being approached in the experiment. For details, see Epilogue.

(b) The worst case of entropy according to ENT in the experiment was higher than 7.995 bits per byte and the average CPU-time was less than 15 sec on author's PC.

The software (new version 1.1) is available at http://mok-kong-shen.de

Shannon's paper Prediction and Entropy of Printed English details  the experiment to determine the entropy of English.
Without getting into too much detail, it's only really proper to talk about the entropy of a source of information. You can estimate the entropy given a sample of the source's output and it's fair to say that Shannon's method gives an estimate for the upper bound. A more sophisticated experiment would give a lower estimate for the upper bound.
Another way to arrive at an upper bound would be to look at the results of a competition to compress a portion of wikipedia which shows that 100M of English can be compressed into 16M.

I'm reminded of a similar scheme I read about which relied on a long stream of publicly available bits derived in this case from digitizing a picture of the surface of the moon. I can't find the reference but I'm sure it would be relevant, although of purely academic interest.

There are no practical schemes that I am aware of which use your idea or anything similar. You would have to ask yourself what security guarantees you're trying to achieve and whether this really is the best way of obtaining them. I believe that it should always be preferable to implement your system using established cryptographic primitives in the prescribed fashion.


Does XOR have diffusion properties? Does the XOR operator provide diffusion if the right side of plain text is XORed against a round key which is then XORed against the left side to produce that side of cipher text, for example in a Feistel cipher.

Let's take the definition from Wikipedia:

  Diffusion means that if we change a single bit of the plaintext, then (statistically) half of the bits in the ciphertext should change, and similarly, if we change one bit of the ciphertext, then approximately one half of the plaintext bits should change.

Now, what ever the XOR operation does, it works on 2 bits, 1 bit of the key and one bit of the plaintext. So no, XOR cannot provide diffusion by itself.

In your example, if you change a single bit of plaintext then then the output will only change with a single bit as well. If you applied the output to another bit then you'd still have the same situation (as the two bits flip at the same time).

If the Feistel function itself provides diffusion used with XOR in the steps is a different matter, of course. But XOR won't have provided the diffusion.


Calculating G for a give cyclic group mod P For DH key agreement, one must begin with a generator of a cyclic group g.

However, intuitively to me at least, it seems that g may be expensive to calculate for a random cyclic group mod some large prime p.

How is this done efficiently on the fly for Diffie Hellman?

Probably this is naive, however it would seem one must check each element of the group to test it's generative properties...

How is this done efficiently on the fly for Diffie Hellman?

For Finite-Field Diffie-Hellman, you usually pick $p$ such that $q=(p-1)/2$ is also prime. Now Lagrange's theorem tells us that every element's order must divide the group order which is $p-1=2q$. This leaves us with four divisors: $1,2,q,2q$. Once you know that, you can simply test that your chosen candidate $g$ doesn't have order $1$ nor $2$ which you can test by checking that $g^2\neq 1\pmod p$. If you now explicitly want either of the other two orders you can test whether $g^q=1\pmod p$ and if yes you have a generator of order $q$ and if not then it has order $2q$. As to whether we can actually find the two interesting cases, Sylow's theorems guarantee this and usually you would start with $g=2$ and count up until you have a suitable candidate.


Implement AES-CTR on top of AES-ECB I using a microcontroller which only support AES-ECB encryption i.e. no decryption-mode, CBC, GCM or similar modes.

However, I'm wondering if it's possible to implement AES-CTR or similar on top of AES-ECB?

I'm grateful for help, tips, similar implementations etc.

Cheers

Yes, you can do this.  In fact, implementing other cipher modes is precisely what ECB mode is good for (and, indeed, just about all it is good for).

To implement AES-CTR, simply fill an array of 128-bit blocks with increasing counter values, encrypt it with AES-ECB and XOR the resulting keystream with the plaintext (for encryption) or ciphertext (for decryption).


Why is garbled circuit a randomized encoding? In Garbled Circuit, a circuit C is encoded to C' and input x is encoded to x' such that only C(x) can be computed given C' and x'.

Randomized encoding of a function f is another randomized function f' such that output distribution of f' encodes f.

I heard that garbled circuit is a randomized encoding but couldn't figure out how. Can anyone please explain it?

First of all, having a precise definition of garbled circuit is a bit cumbersome - if you want to see a clear and nice (formal) definition, I suggest looking at page 2 of this article.

The purpose of a randomized encoding is to create, from a function $f$ and an input $x$, an encoding $\phantom{i}\hat{f}(x;r)$ such that:

Correctness: there is an algorithm $D$ such that, for any input $x$ and any random coin $r$, $D(\hat{f}(x;r)) = f(x)$
Security: $\phantom{i}\hat{f}(x;r)$ reveals nothing about $x$ except $f(x)$. Formally, there is a simulator that, given only $f(x)$, can sample from a distribution indistinguishable from $$\{\phantom{i}\hat{f}(x;r) | r \text{ random}\}$$

The level of indistinguishability (perfect, statistical, or computational) gives the corresponding flavor of the randomized encoding.

For a randomized encoding to be be useful, computing $\phantom{i}\hat{f}(x;r)$ must be simpler than directly computing $f(x)$ for a definition of "simpler" that depends on the application in mind. An example: suppose you want someone to learn $xy$ and nothing more, but you cannot directly compute $xy$ because all you know are, say, additively homomorphic encryptions of $x$ and $y$ - so you can compute any function of the form $ax+by+c$, but not $xy$. Here, you can pick two random coins $(r_x,r_y)$ and send (encryptions of) $(u,v,w) = (x+r_x,y+r_y, xr_y+yr_x+r_xr_y)$: your opponent (who has the secret key of the scheme) can compute $xy = uv-w$, and one can easily prove that he can only learn $xy$.

So, why are garbled circuits randomized encodings? Well, given a function $f$ represented by a circuit $C$, the randomized encoding of $C(x)$ is just Garble$(x;r) = (C',K)$ ($K$ is the list of keys for every input bit, $r$ is a random coin) together with Encode$(K,x) = E$: given $(E,C')$, one can recover $C(x)$ by evaluating the garbling $C'$ with the keys $E$ associated to $x$ (this is the correctness of the encoding), and it reveals nothing more than $C(x)$ (this is the security of the randomized encoding). Therefore, this does indeed correspond to a computational randomized encoding of a function.

But why is it useful? Because with known constructions of garbled circuits, computing $(C',E)$ is simpler than computing $C(x)$ in the following sense:

Garble$(C;r)$ can be computed by a constant depth circuit, independently of the depth of the function computed by $C$. Indeed, one can garble all the gates in parallel. This has many applications in cryptography and led to a fruitful line of work that started with the article Cryptography in $NC_0$.
Garbling the circuit and encoding the input are two separated algorithm, and Encode$(x,K)$ is usually a very simple algorithm (a table lookup).


Is using a predictable IV with CFB mode safe or not? While writing this answer, I noted that NIST SP 800-38A says that (emphasis mine):

  "For the CBC and CFB modes, the IVs must be unpredictable. In particular, for any given plaintext, it must not be possible to predict the IV that will be associated to the plaintext in advance of the generation of the IV."

For CBC mode, using a predictable IV allows a well known chosen plaintext attack exploiting the way in which the IV is combined with the first block.  However, I don't see how a similar attack could apply to CFB mode; indeed, as I observed in an earlier answer, the CFB, OFB and CTR modes are equivalent for the first block.

Indeed, in this answer, Thomas Pornin writes that (emphasis again mine):

  "CFB and OFB require only uniqueness: for a given key, each IV value shall be used at most once. The is no need for unpredictability or uniformness because the IV is first encrypted "as is" (before any operation with the plaintext) and encryption of a sequence of values with a good block cipher, using a key that the attacker does not know, is a good PRNG."

So, is Thomas wrong, or is NIST mistaken or merely excessively cautious?  And if there is an attack enabled by using predictable IVs with CFB mode, how does it work?

Thomas is correct; there's no attack on CFB mode if you can predict the IV; NIST is just being cautious.

With CBC, the value of the first encrypted block $C_0 = E_k( IV \oplus P_0)$, where $IV$ is the IV used for that packet, $P_0$ is the value of the first plaintext block, and $E_k$ is the evaluation of the block cipher.

If an attacker can predict the value of the $IV$ in advance, and can influence the value $P_0$, then he can get the value $E_k(Q)$, for any value $Q$.  Here is how; he learns the value of $IV$, and then injects a message whose first plaintext value $P_0 = IV \oplus Q$.  The encryptor will generate an encrypted message whose first block is $C_o = E_k( IV \oplus P_0 ) = E_k( Q )$.

Using this encryption oracle, the attacker can verify guesses on the possible decryption of previous messages.

In contrast, with CFB mode, the first encrypted block is $C_0 = E_k(IV) \oplus P_0$.  While this looks similar, there is no similar opportunity to an attacker to select the block that is presented to the block cipher.  If the attacker knows the IV in advance, all he knows the value of the first block that will be presented to the block cipher; he cannot influence it by selecting any specific value for the first plaintext block.  Now, if the attacker can control the value of the IV, then yes, he can use that directly to create an encryption oracle; he generally don't allow the attacker to do that.

In addition, if we use the same IV repeatedly, then there is also a weakness (beyond the rather obvious leaking of the first block); the second ciphertext block is $C_1 = E_k( E_k(IV) \oplus P_0 ) \oplus P_1$; if $IV$ is constant, so is $E_k(IV)$, and so the attacker can select messages with $P_0 = E_k(IV) \oplus Q$, also creating an encryption oracle.

The bottom line: predictable IVs are safe in CFB mode, as long as they don't repeat, and you don't allow the attacker to pick them.


How can I hash an input into an arbitrary domain point? I am trying to implement a signature scheme involving RSA signing of a message digest generated by SHA-$256$. I want to hash the input into an RSA domain point instead of the fixed $256$ bit digest generated by SHA.

Apparently, this can be achieved using a Full Domain HashingFrom the Wikipedia definition of Full Domain Hashing

  In cryptography, the Full Domain Hash (FDH) is an RSA-based signature scheme that follows the hash-and-sign paradigm. It is provably secure (i.e., is existentially unforgeable under adaptive chosen-message attacks) in the random oracle model. FDH involves hashing a message using a function whose image size equals the size of the RSA modulus, and then raising the result to the secret RSA exponent.

How would one go about practically implementing the following part of the FDH process:

  hashing a message using a function whose image size equals the size of the RSA modulus

I have tried randomly padding the $256$ bit digest, however, it requires sending extra values to remove the padding before verification.
I also looked at some papers on Random Oracles and FDH by Bellare and Rogaway(Paper 1,Paper 2) which are a little to esoteric for me and as  such, I'm looking for simplified explanation of the process.

Hash functions we use, e.g. Sha-1, Sha-256, Sha-512, usually don’t have a sufficiently large range. But we can construct full domain hash via repeated application of a hash function $h$: $FDH(m) = h(m||0)||h(m||1)||\cdots  $, then take the leading n-bit. This way the hash value is deterministic and the size is arbitrary.

This is something like MGF1 defined in PKCS #1 v2.2, B.2.1.


Can we use non-adaptive zero-knowledge proof in group signatures Group Signature schemes are used to provide anonymity of the signers. During signature generation, signers provide a NIZK proof to prove that they are certified group members. Verifiers check whether the proof is valid during verification of signature.
Can we use non-adaptive NIZK proof to prove signer is a certified group member?

This question is hard to answer in general, without specifying a concrete group signature scheme and a security model in which you want the group signature scheme to be secure.

However, we may observe some things: first you will need a non-interactive proof/argument system as signatures are non-interactive by definition. Second, you will most likely be required to include the common reference string (CRS) of the proof/argument system in the group public key. Third, you will probably (in any reasonably strong model I can currently think of) have to simulate proofs (resp. signatures) after handing the group signing key over to the adversary. In these cases you will definitely require adaptive zero-knowledge proofs/arguments, i.e., ones that allow the adversary to choose the targeted statements after seeing the CRS.

Nevertheless, it can not be excluded that one can define a (weaker, maybe also non-adaptive) security model as well as a construction in this security model which does not have this requirement. The question is whether such a model would still provide the security guarantees one would hope for.


Difficulty of a congruence problem The problem is described as follows. Let $c_1=p_1q_1+r$, $c_2=p_2q_2+r$, $\cdots$, $c_n=p_nq_n+r$, where $p_i$'s, $q_i$'s, $r$ are all large positive integers, and $p_i$'s and $q_i$'s are randomly chosen. Notice that $p_i$'s and $q_i$'s are different while $r$ is the same. Now one knows $c_1,\cdots,c_n$, and he knows the above structure of $c_1,\cdots,c_n$, but he does not know $p_i$'s or $q_i$'s. He aims to extract the value of $r$ from $c_1,\cdots,c_n$. Is this problem hard (either proven to be hard, or no polynomial solving algorithm found yet)? Does this problem have a name?

A similar (but easier) problem is solving the system of linear congruences: by knowing $c_1,\cdots,c_n$ and $p_1,\cdots,p_n$, solve $r$ from the equations $r\equiv c_1\mod p_1$, $r\equiv c_2\mod p_2$, $\cdots$, $r\equiv c_n\mod p_n$. This problem is related to the Chinese remainder theorem and I know that it has polynomial-time solving algorithms. However, in my question in the first paragraph above, one only knows $c_1,\cdots,c_n$, but does not know the moduli $p_1,\cdots,p_n$ (or $q_1,\cdots,q_n$), the problem of my question might be harder. I can only find works on linear congruences but cannot find related works on my question. Is anyone familiar with this question? I just wonder is this a problem that has been ever studied.

Combining fgrieu's and my observation, it appears that a large $r$ can be recovered given enough $p_iq_i + r$ values.

In particular, we will assume that both $p_i$ and $q_i$ are selected uniformly.

Then, $(p_iq_i + r) = r \pmod s$ will hold will probability at least $(2s-1)/s^2 \approx 2/s$ (as it will hold if either $p_i$ or $q_i$ is 0 modulo $s$, $(p_iq_i + r) \bmod s$ will be any other specific values with probability circa $1/s$.  Actually, the bias is even stronger if $s$ is a power of a smaller prime, we'll ignore that for now.

Hence, what we can do is, for various small prime-power $s$, take our $p_iq_i + r$ values, and compute $p_iq_i + r \bmod s$, and see what value happens the most often.  That'll give us the likely value of $r \bmod s$.  Then, we take all our likely values, and use the Chinese Remainder Theorem to reconstruct $r$.

If we have 10,000 such values, we can use the prime-power's up to 710; for each value of $s$, the correct value of $r \bmod s$ will be at least 3 standard deviations over the rest (and hence the most common value is likely to be the correct one), and that'll give us enough relations to recover a 1024 bit $r$.

We can then use fgrieu's observation to validate the $r$ we recovered.


Boolean circuit: can the output wire of a gate be used by many different gates in the next layer? There are two typical secure multiparty computation paradigms using boolean circuits, namely garbled circuit and secret-sharing-based boolean computation. It is well-known that garbled circuits can be constructed layer by layer, in which each garbled gate has a fan-in of two and a fan-out of one (i.e., two input wires and one output wire). We have a similar construction in the secret-sharing-based boolean circuits. However, I failed to find any explicit comment whether an output wire of a gate can be used simultaneously by several gates in the next layer. In some available implementations of boolean circuits (e.g., this), no output wire is used more than once.
In my opinion, the reuse of an output wire does not undermine the security of the whole circuit since no information seems to be leaked by observing either the garbled gates or the secret-shared outputs. Am I wrong?

However, I failed to find any explicit comment whether an output wire of a gate can be used simultaneously by several gates in the next layer.

Of course you can do that.
In fact there are examples in the very repository you linked to, e.g. wire 3488 of the AES-128 implementation is used twice.


Should I add randomness at the end before AES? Seen AES, changing a character drastically affects the encrypted text. I want to make it harder to decrypt AES I send. So, it seems this can be done by adding some special code and some random bytes RNDBYTES at the end of plaintext, and when decrypting removing the ramdomness after the special code. This way encrypting the same text will look different, which is what I need. But is this secure? Should I use a special algorithm for this or a CSPRNG is enough? How long should it be?

I'm using it in CBC mode, but the implementation doesn't add the randomness I want, the same message when encrypted looks the same. But the receiver of the encrypted code should be able to decrypt knowing the key without the need to know the RNDBYTES. This is just to prevent someone smart outside the connection to observer the repetition pattern.

Edit: A hacker might know other ciphertext AND some parts of the plaintext.

I want to make it harder to decrypt AES I send.

Fundamentally, the thing you are trying to do is completely unnecessary. If AES does ever become broken, the scenarios in which this makes any measurable difference are exceedingly unlikely. If AES isn't broken, then doing this was wasted effort in the first place.

There is zero plausible reason why your idea would make AES harder to decrypt in any scenario.

Virtually any other use of your time would be better spent. AES, when used correctly (e.g., a well-regarded mode like GCM, non-repeating nonces, and a cryptographically random key or strong password with suitable PBKDF), is going to be the strongest part of your cryptosystem by multiple orders of magnitude. Focusing extra time on this part of the problem is, to paraphrase Bruce Schneier, like protecting your house by planting a single stake into the ground and hoping the attacker runs into it, instead of building the rest of the fence.

Edit: Upon rereading your question, it appears you're gravely misusing CBC mode by using a static (or no) initialization vector (IV). An initialization vector should never be reused between encryptions with the same key. Additionally, CBC IVs have the requirement of being unpredictable to an adversary. Your encryption library should have a function to set the initialization vector before encrypting any plaintext, and before decrypting any ciphertext. Generate one with a cryptographically secure random number generator, pass it to your encryption library, and then send the IV alongside the ciphertext so the receiver can decrypt it.


How to multiply two Public Keys in Elliptic Curve in Go I am working on a messaging client similar to Signal. I am  stuck on
implementing Tripartite Diffie-Hellman handshake in which three DH exchanges are combined to authenticate both parties and produce a session.
Alice starts with identity key $g^A$ and ephemeral key $g^a$ (her secrets are $A$ and $a$). Similarly Bob has identity key $g^B$ and ephemeral key $g^b$ (his secrets are $B$ and $b$). Alice send Bob $g^A$ and $g^a$ and he sends back $g^B$  and $g^b$. Their initial shared secret is:

Now my question is to how to implement $g^{a*B}$ which are both public keys?
Also the code to calculate DH share for private with public key is working which is as follow:

Thanks.

Now my question is to how to implement $g^{a*B}$ which are both public keys?

Just given $g^a$ and $g^B$, this is a hard problem (or so we hope); if that is feasible, the strength of the entire system falls apart.

However, both Alice and Bob can compute: for Alice, she computes $(g^B)^a$ (given the value $g^B$ from Bob and her secret $a$).  Similarly, Bob computes $(g^a)^B$ (given the value $g^a$ from Alice and his secret $B$)

Both computations yield the common value $g^{a\cdot B}$


Using weak hash functions to construct a stream cipher I am in the awkward position of developing a secure encryption scheme that provides data-at-rest security for a very limited embedded system. The system is only guaranteed to have 4 MiB of memory (some systems have an extra 32 MiB), and they do not even have an MMU. They are running an old version of μClinux. While the resources are not that big an issue (even a cheap 8051 could run a secure cipher), the real issue is that I can only use the utilities that are present on the system. Unfortunately, there are no scripting languages other than a rather limited ash shell, so implementing a real stream cipher is out of the question. However, the md5sum utility is present, as is od which is necessary to combine the keystream with the plaintext of a binary stream.

Because implementing a stream cipher in ash shell would be too slow, I thought of using MD5, where the keystream $H$ at position $i$ is the hash of key $K$, nonce $N$, and counter $i$ concatenated. Encryption of plaintext $P$ and decryption of ciphertext $C$ is done as in any stream cipher.

\begin{align*}
  C_i &= P_i \oplus \operatorname{MD5}(K \mathbin\| N \mathbin\| i) \\
  P_i &= C_i \oplus \operatorname{MD5}(K \mathbin\| N \mathbin\| i)
\end{align*}

I understand that it is possible to design a stream cipher from a hash function, but I would like to know specifically if MD5 is an acceptable hash function in this particular scenario. As far as I am aware, collision attacks are irrelevant for use in a stream cipher, but I want to make sure I missed nothing. Is this scheme appropriate for my unfortunate hardware / software limitations?

I am also aware that designing a cryptographic scheme as an amateur is very bad. Unfortunately, I have little choice as I can't load my own executables onto the device, and thankfully I do not need authentication or any security properties other than data-at-rest security (i.e. it is a situation where unauthenticated AES-CTR would suffice).

As long as your encoding of $K$, $N$, and $i$ is injective (i.e., for each encoded string you can uniquely derive $K$, $N$, and $i$) and fixed-length, this is almost certainly a decent stream cipher.

It won't break any speed records, obviously!  But collision resistance is not relevant here, and I have no reason to suspect that the distribution of $x \mapsto \operatorname{MD5}(k \mathbin\Vert x)$ for fixed-length $x$ is distinguishable from uniform under a uniform choice of $k$.  Any distinguisher would probably suggest a better than generic partial preimage attack on MD5, and in spite of some papers claiming the contrary in nonsensical cost models, so far there's no evidence of preimage attacks on MD5.

That said: Consider carefully whether you also need to do authentication!  Unauthenticated encryption is seldom useful in real-world applications.  Using the tools you have, you can probably compute HMAC-MD5 too without too much trouble.  Encrypt-then-MAC with MD5-CTR and HMAC-MD5 may be goofy, but it probably makes a reasonably secure authenticated encryption scheme.

Do make sure, though, to limit yourself to ${\lll}2^{64}$ messages under any one key because the 128-bit state of HMAC-MD5 admits a birthday forger, and make sure to use at least a 256-bit key in case there is any danger of multi-target attacks.


what is the relationship between epsilon and sensitivity in the Differential-Privacy? In some Differential-Privacy(DP) papers, they use epsilon as the x-axis in the figures of the experiments' result while other papers use the sensitivity.

What is the relationship between epsilon and sensitivity in the DP?
How can I compare the results of different papers?

I'll answer the second question first. The two are distinct concepts — there's no way directly compare graphs or results without more info or context.

Differential privacy is usually obtained by 1. computing a function $F$ of the data and 2. adding some noise to the result. The noise must be large enough to hide an individual contribution, and "how well an individual contribution is hidden" is captured by the parameter $\varepsilon$.

But for some functions $F$, an individual contribution can change the true result more than for others functions. For example:

The answer to "how many employees of this company have blue eyes?" can only change by one if you add or remove an employee.
The answer to "what's the average salary of people in this company?" can change by a lot if you remove the CEO's salary.

That concept is captured by sensitivity: the higher the possible change, the higher the sensitivity. And typically, to get $\varepsilon$-differential privacy with a fixed $\varepsilon$, you have to add more noise when the sensitivity is larger (to compensate). That's the typical relationship between the two concepts.


Misuse-resistant authenticated encryption based on SHA-3/Blake2b and AES-CTR/ChaCha20 I am wondering if the following is a useful misuse-resistant authenticated encryption scheme:

Parameters (shared by many users):

Choose a hash function $H$, such as Blake2 or Keccak.  SHA2 could also be used.
Choose a stream cipher $E$, such as ChaCha20 and AES in CTR mode.

Inputs

Up to a large amount of associated data $A$.
Up to $2^{64}$ bytes of plaintext $m$.
Secret key $K$, which must have at least $k$ bits of entropy but can be much longer.

Outputs

Ciphertext $C$, of the same length as the plaintext.
An auth tag $t$, of 256 or 512 bits depending on the choice of $H$.

Decryption takes $A$, $C$, $t$, and $K$ as inputs and returns either $m$ or the symbol $\text{FAIL}$ if the message was forged.

All lengths are 64 bit, little-endian encoded.

Encryption algorithm:

Calculate the auth tag $t$ as $H(len(K)||K||len(A)||A||len(P)||P)$.
Calculate the shared secret $S$ as $H(len(K)||K||t)$.
Use $S$ as the key for stream cipher encryption. Any extra bits can be use for the nonce.  Bits beyond that are discarded.

Decryption algorithm:

Calculate shared secret (same as step 2 of encryption).
Perform stream cipher decryption (same as encryption step, since encryption = decryption for a stream cipher).
Recompute auth tag $t'$ from plaintext, AAD and key (same as encryption step 1).
The message is rejected unless $t=t'$.

Claim

256-bit confidentiality.
256-bit integrity when used with a 256-bit hash.
512-bit integrity when used with a 512-bit hash and $K$ has at least 512 bits of entropy.
IND-CCA2 security provided that the AAD is never repeated with the same key.
If the AAD repeats the only leak is whether a message repeated.

I would definitely like to know if this cryptosystem lives up to my claims.  I doubt it, since I am not a cryptographer -- but I would be glad if I was proven wrong.

256-bit confidentiality

Let's assume that we're using AES256-CTR and a 256-bit hash.  A new 256-bit key $S$ is derived for each message.  Since AES256 requires a 256-bit key, there are no extra bits in $S$ available for use in the nonce, suggesting that a constant nonce is used.  I believe this is vulnerable to a multi-target attack.

The first block of ciphertext $C_0 = \text{AES256}(S, 0^{128}) \oplus P_0$, where $P_0$ is the first block of plaintext.  Suppose that this block is predictable to the attacker (think of SMTP for example: it's not unusual for the first 16 bytes to be predictable) or attacker-controlled.  The attacker can compute $K_0 = C_0 \oplus P_0 = \text{AES256}(S, 0^{128})$ to get the direct output of the block cipher.

Suppose that the attacker can observe (and maybe encourage the sending of) lots of encrypted messages.  The attacker can compute $\text{AES256}(x, 0^{128})$ for many values of $x$, and check to see if any of those values match any of the $K_0$s the attacker observed.  With $2^{20}$ messages (and therefore $2^{20}$ $K_0$s), the attacker should find an $x$ that works after about $2^{256-20} = 2^{236}$ tries, allowing the attacker to decrypt a single message.  I believe this violates the claim of 256-bit confidentiality.

A similar attack can be applied to ChaCha20 when it is used with a constant nonce.  In the case of a 512-bit hash, this seems to leave enough bits of $S$ for a complete nonce, which should mitigate this attack.

  The message is rejected unless $t=t'$.

This is an implementation issue, but this is vulnerable to timing attacks unless a constant-time comparison is used.


Are ECDSA keys and RSA keys interchangeable? Is it possible to use an ES512 key pair for RS512 signatures?
Is it possible to use an RS512 key pair for ES512 signatures?
I've also posted an issue in the NodeJS jwa package.

I created a key pair for EC512 with the following commands:

openssl ecparam -genkey -name secp521r1 -noout -out ecdsa-p521-private.pem
openssl ec -in ecdsa-p521-private.pem -pubout -out ecdsa-p521-public.pem

Then, instead of using ECDSA as I should, I used RSA:

jwa = require('jwa');
rsa = jwa('RS512');
signature = rsa.sign('hello', fs.readFileSync('ecdsa-p521-private.pem').toString());
result = rsa.verify('hello', signature, fs.readFileSync('ecdsa-p521-public.pem').toString());

And the result was true!

Is this an expected behaviour? Is it possible to use ECDSA keys for RSA and vice versa?

Thanks

--- EDIT ---

Here's a list of possible algorithms to choose from (for my json-web-token implementation), so we will have common terminology:

HS256:   HMAC using SHA-256 hash algorithm
HS384:   HMAC using SHA-384 hash algorithm
HS512:   HMAC using SHA-512 hash algorithm
RS256:   RSASSA using SHA-256 hash algorithm
RS384:   RSASSA using SHA-384 hash algorithm
RS512:   RSASSA using SHA-512 hash algorithm
ES256:   ECDSA using P-256 curve and SHA-256 hash algorithm
ES384:   ECDSA using P-384 curve and SHA-384 hash algorithm
ES512:   ECDSA using P-521 curve and SHA-512 hash algorithm

--- EDIT ---

Following Squeamish Ossifrage's suggestion to use ed25519, here is my Node.JS code for signing and verifying "nonstandard ed25519 json-web-tokens".

const jwt = require('jsonwebtoken');
const base64url = require('base64url');
const ed25519 = require('ed25519');

const ed25519Header1 = base64url.encode(Buffer.from('{"alg":"Ed25519","typ":"JWT"}'));
const ed25519Header2 = base64url.encode(Buffer.from('{"typ":"JWT","alg":"Ed25519"}'));
const noneHeader = base64url.encode(Buffer.from('{"alg":"none","typ":"JWT"}'));

function sign(obj, privateKey, options) {
  const noneToken = jwt.sign(obj, '', { ...options, algorithm: "none" });
  if (jwt.decode(noneToken, {complete: true}).header.typ !== 'JWT') {
    throw new Error("Invalid object to sign");
  }
  const [, payload] = noneToken.split('.');
  const signature = base64url.encode(ed25519.Sign(
    Buffer.from(`${ed25519Header1}.${payload}`),
    { privateKey } // passing an object makes sure we want to sign with private-key, not seed.
  ));
  return `${ed25519Header1}.${payload}.${signature}`;
}

function verify(token, publicKey, options) {
  const [tokenHeader, payload, signature, ...leftover] = token.split('.');
  if ((tokenHeader !== ed25519Header1) && (tokenHeader !== ed25519Header2)) {
    throw new Error("ed25519 jwt malformed - unexpected header");
  }
  const signatureBuffer = base64url.toBuffer(signature || '');
  if (base64url.encode(signatureBuffer) !== signature) {
    throw new Error("ed25519 jwt malformed - invalid signature format");
  }
  // signature is a string, therefore payload is a string (not undefined)
  if (!ed25519.Verify(
    Buffer.from(`${tokenHeader}.${payload}`),
    base64url.toBuffer(signature),
    publicKey
  )) {
    throw new Error("Invalid signature");
  }
  return jwt.verify([noneHeader, payload, '', ...leftover].join('.'), '', {
    ...options,
    algorithms: ['none']
  });
}

a pair of publicKey and privateKey can be generate with the MakeKeyPair(...) function of the ed25519 package (privateKey should be 64 bytes long and publicKey should be 32 bytes long).

The code allows to enjoy both ed25519 signing, and the features of the jsonwebtoken package.

For example:

var token = sign({hello:"world"}, privateKey, {expiresIn:'1 minute'})
console.log(verify(t, publicKey)); // prints { hello: 'world', iat: 1526078738, exp: 1526078798 }
// After 1 minute:
verify(t, publicKey); // Throws "TokenExpiredError: jwt expired"

From the source code:

function createKeySigner(bits) {
 return function sign(thing, privateKey) {
    if (!bufferOrString(privateKey) && !(typeof privateKey === 'object'))
      throw typeError(MSG_INVALID_SIGNER_KEY);
    thing = normalizeInput(thing);
    // Even though we are specifying "RSA" here, this works with ECDSA
    // keys as well.
    var signer = crypto.createSign('RSA-SHA' + bits);
    var sig = (signer.update(thing), signer.sign(privateKey, 'base64'));
    return base64url.fromBase64(sig);
  }
}

See in particular the comment. What happens here is that even though you specified "RSA with SHA-512" as signature algorithm (the 'RS512' parameter, in that library's weird terminology), the code perfectly knows that the private key is for ECDSA, not RSA (look at the contents of the private key file, it starts with "BEGIN EC PRIVATE KEY"), and so it "helpfully" uses ECDSA instead of RSA, transparently.

No mystery here then, just some Node.js code doing Node.js stuff (i.e. doing what it can instead of what you asked for, and hoping for the best -- a rather dubious methodology for all things related to security, in particular cryptography).


Can the HMAC of a pre-hash be considered equivalent to an HMAC of the message? Assume:

size of m = 1kB
HMAC hashing function = SHA256
H hashing function = SHA256

It seems reasonable to think that there would be no difference in authenticating a message if either HMAC(k, m) or HMAC(k, H(m)) are used as this other post indicates.  Am I missing something or are there other potential security risks in doing this?

Pre-hashing is preferred due to the reduction in HMAC validation time on large messages as only the 32byte pre-hash would need to be run through HMAC validation (vs. the entire 1kB message).

TLDR: Such pre-hashing is weaker, and slower on a standard computer.

Most serious security problem: in order to break the MAC with pre-hasing, it is enough to find two different messages with the same SHA-256 hash, and that's an offline attack (it requires a single query to a MAC oracle/device knowing the key). Such breaking of SHA-256's collision resistance could become possible¹ due to some combination of cryptanalytical and technological progress, like that happened for SHA-1. Absent cryptanalytical breakthrough and discounting quantum computers useful for cryptanalysis, that costs $\approx2^{129}$ compression functions (using distributed Pollard's rho with distinguished points). Contrast with the best known attacks against HMAC, which require a much less realistic $\approx2^{128}$ online queries (performing $\approx2^{129}$ compression functions), or a whopping $>2^{256}$ offline compression functions (for 256-bit key).

For just that reason, HMAC-MD5 remains practically secure when MD5 collision is totally broken (collision with chosen prefix is easy), and HMAC-SHA-1 remains practically secure when SHA-1 collision is very broken (collision is easy, collision with chosen prefix is feasible).

Another explanation of these facts: we have argument that HMAC is secure for weaker properties of the hash's compression functions than required for argument of collision-resistance of the hash: Mihir Bellare, New Proofs for NMAC and HMAC: Security Without Collision-Resistance, originally in proceedings of Crypto 2006, republished in Journal of Cryptology, 2015.

  Pre-hashing is preferred due to the reduction in HMAC validation time on large messages as only the 32byte pre-hash would need to be run through HMAC validation (vs. the entire 1kB message).

No, the opposite, pre-hashing is slower on a standard computer. For a 1024-byte $m$ an $k$ at most 512-bit, $\operatorname{HMAC-SHA-256}(k,M)$ first hashes 512+8192 bits (18 blocks after padding), then 512+256 bits (2 blocks). Whereas $\operatorname{HMAC-SHA-256}(k,\operatorname{SHA-256}(M))$ first hashes 8192 bytes (17 blocks), then 512+256 bytes (2 blocks), then 512+256 bytes (2 blocks). That 2 blocks more, and one more each of hash initialization and finalization. Optimizations for repeated use of the key apply equally to both variants.

The one situation when pre-hashing would result in a speedup is when HMAC itself is implemented in a relatively slow secure device (like a Smart Card or HSM) in order to keep the key protected. In that case, pre-hashing is reasonable, and using SHA-256 for that is not unreasonable. But if performance matters, SHA-512/256 or SHA-384 is probably as better choice for the pre-hash: these hashes are faster on modern CPUs, the secure device won't make more SHA-256 compression functions, and (for SHA-384 pre-hasing, which arguably is more secure than either SHA-256 or SHA-512/256) performance overhead of transmitting 128 extra bytes to the security device is low.

¹ I'm not saying that's likely in next two decades; rather, the contrary.