Can Blake2 be a replacement for double SHA-256? My previous question was closed because it was too open-ended, so let me simplify the question:
Is it a good choice to drop double SHA-256 and use straight Blake2 in a Bitcoin-like blockchain (more POS oriented so it's not a mining problem)?
I'm talking about Blake2 because I've read more about it than Blake3, so this question may even consider Blake3.
I don't want to clone Bitcoin but experiment with variations to see what can be improved at low level, so I want to keep it as simple as possible while maintaining at least the bitcoin security level.
Based on my research, it seems Blake2 hash computation is as secure as double hashing SHA-256, correct?
If I've understood correctly, double hashing SHA-256 is done to prevent length extension attack, as one can read here. That's prevented by default on Blake2. Read about it here.
Is this correct?
I'd like to see the performance difference between using Blake2 instead of double SHA-256, but I don't want to upend security.

BLAKE2 can be used as a drop-in replacement for SHA-256d, yes. It is not vulnerable to the length extension attack. Whether or not you should use it in cryptocurrency is a more complex question, but it suffices to say that it will not be any less secure than using SHA-256d for your purposes.
Regarding the speed comparison, this will be more complex to answer as you'd need to specify if you want to encourage CPU mining, GPU mining, or ASIC mining for the cryptocurrency. The raw speed of the hash on a modern CPU will also vary, but BLAKE2 will be faster than SHA-256d. Exactly how much faster depends on the CPU's capabilities, such as SIMD features supported.


Can we quantify strength of encryption scheme ? Was wondering if we have any (or can we come up with) "units" for strength of encryption like in Physics. Most of our comparative analysis of encryption schemes are based on number of S boxes or number of rounds or proofs in a particular model or some times even performance of algorithms.

Is it possible at all for quantifying the security of encryption schemes objectively ? irrespective of the scheme's internal workings ?  Say AES provides "X" units of Strength (under a particular attack, say IND-CCA2) Similar to how we quantify in Physics for temperature, pressure, weights etc.

I would imagine such metric should consider the encryption algorithm as black box

Usually cryptographic strength is given as the effective strength in bits of a security primitive. This is related to the amount of tries necessary to break a primitive. So for AES-128 the effective strength is about 126 bits. The number of bits is of course directly related to the number of tries required to perform an attack. This is often given as a power of two as well (e.g. $2^{126}$ for above). This of course directly relates to the number of bits. The time it costs for a single try of course depends on the runtime and is usually not considered significant.

For attacks it is often necessary as well to keep some kind of state. In that case the memory requirements are described as well. Often the memory requirements are particular to a specific primitive (e.g. the amount of encrypted blocks to store in memory), but usually those are easily converted to bits or bytes.

If the strength is related to an algorithm then of course the order $\mathcal{O}$ is most often used. If an attack has a specific order $\mathcal{O}$ then filling in the parameters of the function should return an approximation of the amount of tries.

Background

Cryptographic strength can be tricky to calculate and is highly dependent on the known attacks. It very much depends on the use of the primitive within a protocol or setting if attacks are applicable at all. Because of this the cryptographic strength shown is just the cryptographic strength of the primitive within its mathematical context. So that would be 128 bit effective for AES-128 and SHA-256 (because of the birthday paradox).

Even then it may be hard to clearly identify cryptographic strength. For instance for DH there is no clearly defined key size. Both the size of the modulus as well as the size of the subgroup should be taken into account. Key size and cryptographic strength do not have to be directly related (and key size may not be that well defined in the first place).

To get a clear idea about cryptographic strength there are organizations such as NIST and ECRYPT (II) take a look at keylength.com and the documents linked from that site.


Establish more secure symmetric crypto system given A and B have small initial secret Alice and Bob have a secret number X that is known only to them. However, the number is only 14 bits, and Trudy knows they share such a secret and can intercept messages between them. Instead of using X right of the bat for their symmetric key, Alice and Bob want a more secure system because Trudy can brute force X. How can Alice and Bob have establish a more secure system?

My textbook points at Diffe-Hellman as a hint.

I am not sure how to go about this, this is something I came up with:

Alice and Bob enact DH as normal. After Alice receives $g^b$ mod $p$ and Bob receives $g^a$ mod $p$ instead of just computing $g^{ab}$ mod $p$ as their shared key, they add X as well, for $g^{abX}$ mod $p$.

Since $p$ will be much larger than $X$ the whole key can't be brute forced easily. A MiM attack Trudy can try in normal DH is to establish $g^{at}$ mod $p$ with Alice and $g^{bt}$ mod $p$ with Bob. My understanding is $x$ or $g^{atx}$ mod or $g^{btx}$ mod $p$ would be expensive to find for Trudy, thus Alice and Bob retain confidentiality.

I'm not sure if I'm overthinking the problem or if what I came up with adds that much more security that couldn't be achieved in a simpler way. Is my method OK? What could a more secure system be?

My understanding is $x$ or $g^{atx} \bmod p$ or $g^{btx} \bmod p$ would be expensive to find for Trudy, thus Alice and Bob retain confidentiality.

Not really.  Trudy knows $g^a$ (Alice sent that) and $t$ (Trudy picked that); let us assume that Alice uses the value $g^{atx} \bmod p$ for something, such as deriving symmetric keys, and then uses that to encrypt a message.  What Trudy could do it compute $(g^a)^{tx} \bmod p$, for all possible values of $x$, and derive keys from all of them; that's 16384 possible keys.  Trudy can then try to decrypt Alice's message using each key; the one that works will tell her the correct value of $x$ (and then she can either continue with a MITM attack, or impersonate Bob).

There are protocols that don't have this weakness, examples include EKE and SRP; these don't prevent Trudy from taking a random guess of $x$, attempting a MITM attack (and learning whether that was the $x$ that Alice and Bob shared); what they do is make sure that Trudy can't do any better; to test 1000 possible $x$ values, she'll need to perform the MITM attack 1000 times.


Same certificate for server authentication and authorizatoin in other system I have a program which acts as a node in a larger system. Those nodes can be connected to form a tree. TLS with mutual authentication is required, which means that each node has it's own certificate. Is it safe to use the same certification for both server authentication (when someone connects to the node) and client authentication plus authorization (when node connects to someone else)?

Also all my nodes require unique IDs within the system. This ID is similar to URI, but in "reverse notation" (so top most element is at the beginning). Should I put this value into subjAltName (and if so, as what value?) and put node's domain name into CN in DN, or should I put this ID into CN in DN and node's domain name into subjAltName?

What I did in the end was to use DN/UID (OID: 0.9.2342.19200300.100.1.1) to store this value, exactly as it is suggested in an answer to this question.


Would $\mathrm{LLL}$ give us a hint to solve the $\mathrm{SIS}$ problem? I know that the $\mathrm{LLL}$ algorithm can find a short, not necessarily the shortest, basis in polynomial time.
My question is: if we construct a lattice from $\textbf{A}$ and then run $\mathrm{LLL}$ on the lattice, would it help in finding the solution or clue to find the solution to the $\mathrm{SIS}$ problem (especially for small dimension matrices)?

$\mathbb{Z}^{n}_{q} = n$ dimensional vectors modulo $q$ (for
simplicity say, $q$ is prime and $n = m$)
$\textbf{Goal}$: find nontrivial short vector $z \in \mathbb{Z}^m$
such that:
$\begin{pmatrix}\\ \dots \text{A} \dots \\ \\\end{pmatrix} \times
 \begin{pmatrix}\\z\\\\\end{pmatrix} = 0 \in \mathbb{Z}^{n}_{q}$
Note that $\textbf{A}$ is a $n\times m$ matrix and $z$ is a $m \times
 1$ matrix or vector.

I understand that $\mathrm{LLL}$ solves Merkle–Hellman knapsack cryptosystem. But it is different from $\mathrm{SIS}$ problem.

As mentioned by 111 in the comments, solving SIS comes down to finding a short vector in the underlying lattice of some prescribed norm $\beta$ or less. Lattice basis reduction methods like LLL help in the sense that they can reduce a basis with long lattice vectors to a basis with shorter, more orthogonal lattice vectors.

If the reduction is strong enough (LLL, or BKZ with large enough block size) then you expect that the first basis vector of the reduced basis is a solution to SIS. (How strong your basis reduction should be to find a solution depends on $n, m, q$ and on the required length of the short lattice vector, $\beta$.)

So to answer your overall question: LLL can solve the easiest SIS instances (with large $\beta$), and can assist in solving harder SIS instances (with small $\beta$) by finding a shorter basis, which makes finding even shorter lattice vectors a bit easier.


Bleichenbacher 1998 "Million message attack" on RSA I have been reading Bleichenbacher's 1998 paper on a forged message attack on RSA. The paper assumes access to an Oracle that takes a ciphertext $c$ and will check the decrypted text for valid PKCS #1 padding and returns the validity of the padding. This side-channel can be used for an attack since we can send a forged ciphertext by selecting random integers $s$ and compute:

$c' = cs^{e}\, \mbox{mod}\, n$

If $c'$ is PKCS conforming we know that the two most significant bytes of $ ms = c'^{d} \mbox{mod}\,n$ were equal to 0x00 0x02.
If we define

$B=2^{8(k-2)}$

where $k$ is the length of $n$ in bytes, then we know

$2B\leq ms\,\mbox{mod}\,n<3B $

Now we have a range $M_{0}$ in which we know $ms$ to lie:

$M_{0} = {[2B, 3B-1]}$

The attack now proceeds by iteratively generating more valid forged ciphertexts for integers $s_{i}$ and with the gained knowledge reduce the range of $M_{i}$

I am having trouble understanding Step 3 in the paper which deals with narrowing the set of solutions:

$M_{i} \leftarrow \cup_{a, b, r} \lbrace [\mbox{max}(a, [\frac{2B+rn}{s_{i}}]), \mbox{min}(b, [\frac{3B-1+rn}{s_{i}}])]\rbrace$

for all $[a,b] \in M_{i-1}$ and $\frac{as_{i}-3B+1}{n}\leq r< \frac{bs_{i}-2B}{n}$

How would this be implemented in code? It looks to me that we would need to compute each range for every $r$ within the specified bounds e.g.:

for (r=r_min; r<r_max; ++r)
    max(a, x);
    min(b, y);

However this seems to be intractable to me and I think I am making an error in trying to convert the math to code. Anyone maybe see where I am going wrong?

I implemented this padding oracle attack some time ago in Python and remember this part being a bit confusing to wrap my head around, my code is as follows:

newM = []
for (a, b) in M:
    # util.ceiling rounds arg1 / arg2 to the next highest integer
    rlow = util.ceiling((a*s - 3*B + 1), n)
    rhigh = (b*s - 2*B) / n

    for r in range(rlow, rhigh + 1):
        newa = max(a, util.ceiling(2*B + r*n, s))
        newb = min(b, (3*B - 1 + r*n) / s)
        newM.append((newa, newb))

M = list(set(newM))

So basically for each (a, b) pair in the set M you have to calculate the range of possible r values and create a new pair for each r. Since the pairs (a, b) are such that a <= b, calling max for the first element and min for the second element ensures that for any (a, b) the new value of a can only increase and b can only decrease. Said another way, you never increase the range, you are always narrowing it down. So while the amount of pairs in M does increase for a while it eventually does decrease back down to one pair (a, b) where a = b.

Hope that is somewhat helpful. :)


Key management in Java + Remembering passwords I'm new within the area of crypto so I apologise if I am bad at explaining this, or have misunderstood certain areas.

I'm currently developing a Java Fx application which includes the use of a 'remember password' option.

The password needs to be reversible. So in this case I need to use encryption (I know hash + salt (e.g. using Bcrypt) is better but I cannot do that without the user having to enter their password every login).

I'm just wondering what the best way to achieve this is.

For example, I could create a Java KeyStore to store a key pair and then store the password encrypted elsewhere in a configuration file. But I'm not sure how to go about storing the password for the KeyStore. Also, I'd need to encrypt the private key right? And would need to secure the passphrase for the private key? (Again, I'm a nooby so correct me if I've misunderstood anything)

Does anyone have any advise on a good, secure method to handle this? It doesn't have to be the way I have explained (using JKS) - I'm open to alternative approaches.

There is no way you can make this secure without using some kind of DRM or additional devices. If an attacker has access to the running program then the attacker is able to retrieve the password. You can of course try to hide and / or scramble the password in memory, but that's about anything you can do. It then comes down to obfuscation.

Sometimes the operating system has access to additional resources to secure passwords. You need to provide your password to the operating system almost by default. So for instance Windows has a Credential Manager that you can access from your applications. I looked around and I found some way to make use of it here (warning: I've never used or viewed this solution). Obviously such code won't be portable across operating systems.

In the end, you're probably better off trying to protect your application itself. Make sure your input is sanitized and that the debug port isn't left wide open. Make sure you limit access to the application. Once an attacker has full access to a user account - or worse, a system account - then your application security is probably the least of the user's worries.


Does "Shattered" actually show SHA-1-signed certificates are "unsafe"? Note: I am not advocating anyone continues using SHA1-signed certificates: they are dead as far as security is concerned and should no longer be used. I'm just trying to clarify my understanding of the theoretical implications of Shattered as they might apply to such certificates.

Prompted by this recent question: After Google's collision attack, is RSA-SHA1 signature still safe?, to which the overwhelming response is "no", I want to ask to what degree does the Shattered result actually show that SHA1-signed certificates are "in danger"?

The existence of the Shattered result is not, I think, in itself a surprise: everyone knows that in theory you can create two streams of bytes that hash to the same value. Google's achievements (which I don't wish to downplay) are (a) that they mustered enough resources to actually do this, and (b) they did so while keeping the colliding file a valid PDF (that also matched the format of the original very closely, and included the "obvious" difference in background colour).

As the accepted answer to Does “SHAttered” only work for PDF files? explains, Google had the "luxury" of an effectively "free-form" block of data that they could alter at will to achieve the collision. As I understand it, the "collision blocks" embedded in the JPG data (itself embedded in the PDF) have no (visible) effect on either the image itself nor on the PDF. Therefore (to grossly simplify things), "all" they had to do was vary this block until a collision was achieved1.

However, in the case of a SHA1-signed certificate, there is nothing like the same freedom to inject unconstrained data: the amount of data that is signed is much smaller; and far less of it is free to be varied without consequence – you might find a collision, but the result is likely not to be usable as a certificate.

So: is it correct to say that while Shattered was a significant event, it does not in itself show that the chances of creating a usable, collided, SHA1-signed certificate are increased, and, in fact, the chances of doing so are still small?

1 As per parts of Maarten Bodewes's answer, I realise that Google's attack wasn't completely random: the "magic" was in their tailoring of the attack and an "academic level knowledge to construct such an attack". While the targeting was important to being able to find a collision, so too was the ability to put arbitrary data into the file without compromising the file's validity. It is the latter aspect I'm asking about, and whether the same freedom extends to X.509 certificates.

Yes, SHA1-signed certificates are unsafe.

The SHAttered paper is instructive.  From the introduction:

  The MD-SHA family of hash functions is the most well-known hash function family, which includes MD5, SHA-1, and SHA-2 that have all found widespread use.  This family originally started with MD4 in 1990, which was quickly replaced by MD5 in 1992 due to serious security weaknesses.  Despite early known weaknesses of its underlying compression function, MD5 was widely deployed in the software industry for over a decade.  A project MD5CRK that attempted to find a collision by brute force was halted in early 2004, when a team of researchers led by Xiaoyun Wang demonstrated collisions in MD5 found by a groundbreaking cryptanalytic attack that pioneered new techniques.  In a major development, Stevens et al. later showed that a more powerful type of attack (the so-called chosen-prefix collision attack) could be performed against MD5.  This eventually led to the forgery of a Rogue Certification Authority that in principle completely undermined HTTPS security in 2008.  Despite this, even in 2017 there are still issues in deprecating MD5 for signatures.

Let me draw out the timeline here:

MD4 published.
-
MD5 published.
-
-
SHA-1 published.  Hans Dobbertin reports collisions in MD4 within seconds.
Hans Dobbertin reports collisions in the MD5 compression function.  Cryptographers advise against the use of MD5.  SHA-1 is available as an unbroken alternative.
-
-
-
-
-
NIST publishes SHA-2 in FIPS 180-2.
-
Xiaoyun Wang's team reports collisions in MD5 in a few hours.  It is sheer idiocy to use MD5 at this point.  SHA-2 is available as an unbroken alternative.
Xiaoyun Wang's team reports a $2^{69}$-cost collision attack on SHA-1, later lowered to $2^{63}$.  Cryptographers advise against the use of SHA-1, and even go out of their way to tell engineers to use SHA-2 instead of MD5 or SHA-1.  Cryptographers realize there are sheer idiots out there and try to persuade them to stop using MD5 by making colliding pairs of x.509 certificates, albeit only sharing the same names.
-
Stevens et al. demonstrate chosen-prefix collision attacks on MD5, enabling potential forgery of certificates with different names.
Cryptographers realize that even the operators of certification authorities are sheer idiots and try to persuade them to stop using MD5 by forging x.509 certificates in real time on a real CA.  Some HTTPS CA operators grudgingly acknowledge that there might be a problem.
-
-
CA/Browser Forum writes down first draft of Basic Requirements so web browsers can formalize justification for kicking out incompetent HTTPS CAs.
BLAKE2 is published based on a SHA-3 finalist.  The governments of the United States and Israel are documented to forge code-signing certificates using an independently developed chosen-prefix collision attack on MD5 in the Flame malware deployed in an international incident of industrial sabotage attacking Iran's nuclear program.  This attack was presumably developed before 2007—otherwise, why not use the published attack?
-
CAB Forum votes to sunset SHA-1 next year.
HTTPS CAs whine and demand to push SHA-1 sunset back a year.  NIST publishes SHA-3 in FIPS 202.
HTTPS CAs whine and demand to push SHA-1 sunset back another year.  CAB Forum votes to require random ≥64-bit serial numbers, the first mitigation for chosen-prefix collision attacks on certificates (but not on signatures in general) in eight years since MD5 certificate forgery was demonstrated in practice.
Stevens et al. report collisions in SHA-1.  It is sheer idiocy to use SHA-1 at this point.  SHA-2, SHA-3, and BLAKE2 are available as unbroken alternatives with high confidence from years of analysis.
-
[Update, 2019-05-10: Gaëtan Leurent and Thomas Peyrin report chosen-prefix collisions in SHA-1 at only a few times the cost of SHAttered, a major step toward certificate forgery.]

The technique demonstrated in the SHAttered paper is an identical-prefix collision attack.  Specifically, the attack takes a prefix $p$ and finds two pairs of message blocks $(m_0, m_1) \ne (m'_0, m'_1)$ such that $$\operatorname{SHA-1}(p \mathbin\Vert m_0 \mathbin\Vert m_1 \mathbin\Vert s) = \operatorname{SHA-1}(p \mathbin\Vert m'_0 \mathbin\Vert m'_1 \mathbin\Vert s)$$ for any suffix $s$.  In contrast, the MD5 certificate forgery used a chosen-prefix collision attack, which takes two prefixes $p \ne p'$ and finds middle parts $m \ne m'$ such that for any suffix $s$, $$\operatorname{MD5}(p \mathbin\Vert m \mathbin\Vert s) = \operatorname{MD5}(p' \mathbin\Vert m' \mathbin\Vert s).$$

Can this specific attack on SHA-1 be used to forge x.509 certificates?  Probably not.  Can someone find a chosen-prefix collision attack on SHA-1?  It took one year from first collision to identical-prefix collision attacks on MD5.  It took two more years from identical-prefix to chosen-prefix collision attacks on MD5.  We already have identical-prefix collision attacks on SHA-1.  I hope that we don't need to demonstrate another CA forgery in practice before people will listen to advice to stop using SHA-1.  [Update, 2019-05-10: We now have chosen-prefix collision attacks on SHA-1 at only a few times the cost of the identical-prefix attacks of SHAttered.]

There are mitigations like randomized serial numbers, so maybe for public HTTPS certificates—which by CA/Browser Forum Baseline Requirements 1.5.9 §7.1 must use randomized ≥64-bit serial numbers for all certificates issued after 2016-09-30—it is sufficient that SHA-1 be eTCR, enhanced-target-collision-resistant, which is a much weaker property than collision resistance.

Of course, the CAB Forum requirements also (§7.1.3, p. 44) forbid new certificates signed using SHA-1 starting 2016-01-01 anyway—as is sensible!  Do all HTTPS CAs respect that rule?  I hope so, but if they don't respect it, maybe they won't respect the rule for random serial numbers either.

But there are many other kinds of certificate out there, like the code-signing certificates that were forged for Flame.  Even if you restrict your question to x.509 certificates, e.g., the openssl ca command-line tool—which many people build private CAs out of—suggests and makes it easy to use sequential serial numbers and doesn't advertise a built-in way to randomly generate serial numbers.

P.S.  No matter how many caveats you put on them, questions like this are frustrating to cryptographers because they provide fodder for self-important Hacker News readers to disregard all the context around the specific individual scientific result and instead conclude that the specific individual scientific result does not tattoo a collision on their foreheads and that therefore there's no need to replace SHA-1 yet.


MiTM on RSA public key encryption a) Alice just generated a new pair of public and private RSA keys (pkA , skA ) = ((N, e), d) and would like to start a private conversation with Bob. How can Alice interact with Bob and exchange a symmetric key? Describe a key exchange protocol between them which is secure against an eavesdropper adversary.
b) Fully specify a Man-in-The-Middle (MiTM) attack attack against the key exchange protocol you described above.
c) Assume now that Alice and Bob are very old friends and that Bob already knows a public key pkA owned by Alice.  How can you improve the above protocol in such a way that Bob can detect the presence of a MiTM? Can Alice also detect the presence of a MiTM?

In part a) I defined a protocol using the idea behind D Hellman, so this is vulnerable to MiTM.
However, I dont know how to work out part c

You need an authentic channel from Alice to Bob to get a secret channel from Bob to Alice. This assumption is missing in a), so anyone in control of the communication channel can play man in the middle on any protocol.

As long you don't have a secret channel from Alice to Bob or an authentic channel from Bob to Alice, Alice will never (= for any protocol) be sure who is sending her the secret messages.

See U. Maurer, P. Schmid, A calculus for secure channel establishment in open networks, ESORICS' 94, LNCS 875, pp 175-192.


What are these fields in ASN.1 encoding of RSA Nice resource for ASN.1 structured RSA keys https://etherhack.co.uk/asymmetric/docs/rsa_key_breakdown.html in private key section shows following RSA private key related fields:

modulus
public exp
private expo
prime 1
prime 2
exponent 1
exponent 2
coefficient

I understand the majority of these fields as per https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation.

But what are the bolded exponent 1, exponent 2 and coefficient? I cannot find their use in RSA in the linked wiki article.

The are the $d_P$, $d_Q$ and of course $q_{inv}$ - in that order - in the Wikipedia article. As you can see in the formulas relating to the Chinese Remainder Theorem the primes are also used but $d$, the private exponent, isn't.

The CRT calculations can be used to speed up RSA private key operations, which are the slowest part of the RSA cryptosystem after the prime generation. The calculations also have different side channel attacks linked to them compared to "plain" RSA.


How to choose parameters for Argon2 for password vault I'm creating a password vault and I'm planning on using Argon2id to derive the master key from the master password. For encryption I'm planning on using XChaCha20 with Poly1305.
To be clear: a set of multiple passwords and usernames will be encrypted using XChaCha20 and authenticated using Poly1305, using (a random 192-bit IV and) a 256-bit key derived from a master password using Argon2id (the version that tries to both resist GPU cracking attacks and side-channel attacks) (using 256-bit secure random salt; although I might actually just use 128-bit salt because that should also be plenty). (If there's any issues with this setup, such as with using the id version of Argon2 or using XChaCha20, also tell me, but I think these should be suitable.)
Eventually, I'd like to make the password vault usable on both desktop(/laptop) and mobile devices.
Now I want to determine good secure-but-not-overkill default parameters to use for Argon2id, that are both suited for modern mobile phones and normal computers. The parameters to choose are the following:

Time cost (number of iterations)
Memory cost (number of KiBs to use)
Parallelism (number of threads to use; also influences the output)

The Argon2 draft RFC just tells us to first choose the maximum memory cost and parallelism you can afford and increase the time cost until the function takes longer than you can afford.
Another page references multiple sources, such as the libsodium documentation, which has multiple recommendations:

"For interactive, online operations, crypto_pwhash_OPSLIMIT_INTERACTIVE and crypto_pwhash_MEMLIMIT_INTERACTIVE provide base line for these two parameters"

Currently this means 2 iterations and 64 MiB RAM (see crypto_pwhash_argon2id.h)

"Alternatively, crypto_pwhash_OPSLIMIT_MODERATE and crypto_pwhash_MEMLIMIT_MODERATE can be used"

Currently 3 iterations and 256 MiB RAM

"For highly sensitive data and non-interactive operations, crypto_pwhash_OPSLIMIT_SENSITIVE and crypto_pwhash_MEMLIMIT_SENSITIVE can be used"

Currently 4 iterations and 1 GiB RAM

(In all cases just one thread is used.)
A quick benchmark on my laptop tells me that the function just takes 3.9 seconds with the last set of parameters (using the original Argon2id implementation), which I think is more than acceptable because I prefer having a secure system. However, on my phone this takes 8 seconds (using argon2kt), which is a bit longer than I'd prefer, not to mention that 1 GiB is quite a lot of memory.
For reference I took a look at the source code of password vault KeePass, and it seems they use Argon2d (so less side-channel protection) with 2 iterations with just 1 MiB of memory (but 2 threads) by default: [excerpt from KeePassLib.Cryptography.KeyDerivation.Argon2Kdf:]
internal const ulong DefaultIterations = 2;
internal const ulong DefaultMemory = 1024 * 1024; // 1 MB
internal const uint DefaultParallelism = 2;

It it just me, or is that a bit on the insecure side??
Also, what role does the parallelism parameter play in countering attacks? Is this not as important, as libsodium just keeps it at 1?
Concluding, I think this all is a bit vague and I'd like to have some minimum secure values for the 3 parameters, because what if I take small parameters because I just have a slow phone, while the attacker has a bunch of fast GPUs? Then my vault would be utterly useless.
Also, I imagine one can also go overboard and choose values way larger than necessary; is there some limit after which directly cracking the symmetric key is faster than guessing passwords?

The parallelism was probably one reason why Argon2 won the Password Hashing Competition.
The use of processor cores allows for greater memory hardness (security)
without increasing the execution time accordingly.
The drawback is that developers have since then been wondering what value they take for their application.
Paralellisms depends on the number of available cores.
If you want your application to run on different devices,
the execution time will vary greatly with higher parallelism factor.
As of that time, about 50 percent have quad-core processors in their computer.
This would suggest to increase the parallelism factor to 8 (twice the number of cores),
but for smartphones with a single core this would roughly quadruple the execution time.
There is no clear solution for this.
I personally find the choice of libsodium too extreme, even though it is most likely to be cross-device.
But you are thus missing out on a major advantage of Argon2.
If you assume that the vast majority of your users have at least two processor cores,
you can set the parallelism factor to 4, if you are more careful, to 2.
Then you can set the assumed available memory (there is no clear solution for this too, at least 64 MiB?)
and at the end set the time-factor that the execution time is maybe one second.


One-way function and uninvertible function How can I prove the following:

  If $f$ is a one-way function, then it is an uninvertible function?

One-way in the context of cryptography is usually defined to mean that, given an element from the range of a function (or even a series of elements from the range), it is not possible in time polynomial in the input (or maybe output) size to identify the element(s) in the domain that yields the range element(s).  This is purely a bound on computational complexity.  I can absolutely identify every input for any deterministic encryption algorithm by simply exhaustively searching all possible inputs until the desired output is found.  It's only that that will take time($O(2^n))$) for $n$-bit inputs.

Uninvertible is usually defined as a mathematical property of a function which says that an inverse for each element of the range is not guaranteed to exist, or at least to uniquely exist.  For example, let $f(a,b)=a\wedge b$, and let $x$ be an output of $f$.  What are the values of $a,b$ that produced it?  They could be any of $(0,0), (0,1), (1,0)$  if $x=0$, so $f$ is not uniquely invertible.

My guess is that what you really want to show is something like this:  Let $f$ be some computable function and let $x=f(a)$ be the output of $f$ at some unique $a\in dom(f)$.  If $f$ is one-way (as defined above), then $a$ cannot be computed in time poly($|a|$) given only $x$.

This re-statement assumes definitions for what you mean by one-way and uninvertible.  But with that assumption, the proof is simple--just apply the definitions.  Intuitively, if you could compute $a$ from $x$ in polynomial time, then $f$ is not one-way by the definition.  More formally, suppose there exists a deterministic, polynomial-time algorithm $A$ such that $A(x)=a$ for all $x\in dom(f)$ and $f(a)=x$.  Then the pre-image of $x$ under $f$ can be computed in polynomial time, and so $f$ cannot be one-way.  This is a contradiction, so $A$ cannot exist.  qed.


Relationship between CCA/CPA-security and PRFs I'm a bit confused about the relationship between CCA/CPA-security and PRFs and particularly when do we think of encryption and decryption as a PRF. Assume we have an encryption scheme $\Pi = (Enc, Dec, Gen)$ to be a CPA-secure. Can we say that:

$Enc$ must be a PRF?
$Dec$ must be a PRF?

What about the case when $\Pi$ is CCA-Secure?

My intuition is that we can have $Dec$ to be a PRF for both cases since it's deterministic, but not sure if that is actually required?

For $Enc$, it cannot be a PRF since otherwise, $\Pi$ won't be CPA-secure.

Thanks!

IND-CPA/CCA encryption schemes do imply PRFs: Does IND-CPA imply PRF?

But the above result does not mean Enc or Dec must be a PRF. From its definition, a PRF is indistinguishable from a random function for polynomial-time attackers. We can easily make Enc look non-random but still secure. For instance, you can append some 0 bits to the end of the ciphertexts. As for Dec, its domain is not easy to get. If the encryption scheme satisfies the integrity of ciphertext (INT-CTXT), then you cannot even find valid ciphertexts and almost always get nothing from Dec.

Btw, as you noticed, PRFs are deterministic, so you should consider the "random tape" inside Enc when comparing them.


I need help determining the best encryption options based on System.Security.Cryptography in .NET I asked a question here, and received a great summary but was redirected here. Covering the answers of the post, it was noted and suggested that:

Use of plain (CBC) mode. They suggested to use GCM but in my solution I need to avoid adding an additional library. Here are my options: https://docs.microsoft.com/en-us/dotnet/api/system.security.cryptography.ciphermode?view=netframework-4.7.2 (for AES essentially CBC, CTR and ECB)  Which one would be better to use? Is this too broad to ask? What are the benefits to each? If it was credit card data for example, which is more suitable?
Use of Use of PBKDF2 is outdated, and it was suggested to use Argon, but here is what I'm using. Not sure of what to replace this with within the constraints of .NET out of the box: https://docs.microsoft.com/en-us/dotnet/api/system.security.cryptography.rfc2898derivebytes?view=netframework-4.7.2

So taking a credit card for example, please help me answer these without introducing another library (i.e. BouncyCastle) or if it's absolutely necessary to include another library, please state why .Net's default cryptography is not suitable.

without introducing another library

Well, this isn't exactly an ideal situation, but there's still hope. After having browsed the list of available tools there are still some things that can be done, but of course the solution will be less robust and less modern than if one could rely on external libraries.

  Which one would be better to use?

This still depends. If you absolutely cannot tolerate ciphertext expansion under any circumstances whatsoever and if you absolutely cannot tolerate using external libraries under any circumstances whatsoever then yes, CBC-mode is your best choice. If you cannot tolerate ciphertext expansion, you want to look into using EME or XTS mode as a fallback, but for the rest of this section I'll assume that ciphertext expansion is acceptable.

Your best choice if you absolutely cannot tolerate using external libraries under any circumstances whatsoever is to use AES-CTR + HMAC-SHA256. You already found the Enum for CTR-Mode, this leads the question to HMAC-SHA256. The optimal way here is to take the entire ciphertext with all associated data (such as routing information and / or salts), run it through HMAC and append (or otherwise pair it with) the resulting authentication tag. Then on decryption reject any incoming messsage that either lacks a tag or has an invalid tag. The key should be derived as described below, but should definitely be independent of the AES key and the CTR IV.

  Use of Use of PBKDF2 is outdated, and it was suggested to use Argon,
  but here is what I'm using. Not sure of what to replace this with
  within the constraints of .NET out of the box

That's the problem. There is nothing. This is the only situation where falling back to PBKDF2 is acceptable. There are two things to still get somewhat good security out of PBKDF2 and you really want to do both:

Use a non-fixed iteration count. The one really nice thing about PBKDF2 is that its runtime is perfectly linear in its iteration count, so ideally you want to dynamically measure how many iterations per second you can do on your target system and then linearly extrapolate how many you actually want to do. Usually with this you want to target 100ms on something like a server, but the more CPU-time you can spare the better.
Aggregate-Derive-Expand. As pointed out as a "side-note" in the answer on CodeReview.SE the current PBKDF2 parameters lead three separate "chains" of derivation which are easily parallelized by an attacker. Ideally (and this is possible here), one concentrates the keying material into a single string ("aggregate") using eg a straight SHA256 hash (this may get more complicated for more complex keying material structures and properties), then one runs this through the expensive key-derivation function so this function gets called exactly once and thus can be as expensive as possible ("derive"). Finally one gets what TLS calls a "master secret". From this one derives the actual secrets needed like e.g. the AES key, the HMAC key and potentially the CTR IV ("expand"). Ideally one would do this using HKDF, but in this case PBKDF2 with a single iteration also does the trick as would do "label-driven-expansion" where you put the master secret into the key input of an HMAC instance and a label for the key (such as the string "AES key") into the message input.


Can one extract a private key from a series of carefully constructed signed messages? In a situation in which A handles a message P for B to sign using ECDSA, and that event repeats itself many times, is there a way A can discover B's private key?
A can carefully choose what will be P every time, and be confident that B is always the same person using the same key to sign.
Does it change anything if P is always a string of 32 bytes that B won't hash before signing, he will just sign directly -- as it would do with a message he had hashed himself.

It is not possible if the signature scheme is secure, under the standard notion of "existential unforgeability under chosen message attacks". According to this definition, the adversary is given the public key and can then choose messages to be signed one after another. If it can forge any signature, then the scheme is not secure. As such, if the scheme is secure, it's not possible to form special messages that result in the key being revealed, or any other vulnerability.


Collusion resistance in proxy re-encryption scheme depending on bilinear map rules A proxy re-encryption scheme is collusion resistant, if the proxy and a delegatee are not able to recover the secret key of the delegator. For example, when we have a message that was originally encrypted for Alice and a proxy re-encrypts it for Bob, Alice is the delegator and Bob the delegatee. Bob and the proxy should not be able to "collude" and recover the secret key of Alice.

I'm trying to understand if the first scheme in this paper https://eprint.iacr.org/2006/473.pdf is collusion resistant or not.

With $e:\mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$ a bilinear map, $\mathcal{H}_1:\{0,1\}^* \rightarrow \mathbb{G}, \mathcal{H}_2:\mathbb{G} \rightarrow \mathbb{G}_T$ two independent full-domain hash functions, the master secret key $\mathsf{msk}=s$, and $X \xleftarrow{R} \mathbb{G}_T$ we have:

a) Bob has his secret key $sk_{Bob} = \mathcal{H}_1(Bob)^s$,

b) the proxy has the re-encryption key $rk_{Alice \rightarrow Bob} = \langle \mathsf{Enc}(Bob, X), sk_{Alice}^{-1}\cdot \mathcal{H}_2(X) \rangle$.

So obviously, if the proxy and Bob work together they can recover $sk_{Alice}^{-1}$, because it's based on identity encryption and $X$ has been encrypted under Bob's identity. How difficult is it now for them to get $sk_{Alice}$, if they already have the inverse?

But maybe this is not necessary, because how decryption works in the scheme. To decrypt a ciphertext $c = \langle C_1, C_2 \rangle$ that has been encrypted for Alice we have to do this: $m = C_2/e(C_1, sk_{Alice})$.

If the inverse can be treated as any other exponent, then we have:

$\frac{C_2}{e(C_1, sk_{Alice})} = C_2 \cdot e(C_1, sk_{Alice})^{-1} = C_2 \cdot e(C_1, sk_{Alice}^{-1})$

So here are my questions:

1) Is 1. correct? That would mean the scheme is not collusion resistant.

2) If 1. is not correct, how difficult is it to get $sk_{Alice}$ from $sk_{Alice}^{-1}$?

A proxy re-encryption scheme is collusion resistant, if the proxy and a delegatee are not able to recover the secret key of the delegating party.

Are you sure that definition makes sense?  After all, if proxy has the Alice->Bob reencryption key, and Bob has his private key, then the two of them can jointly decrypt any message encrypted by Alice's public key.  And, the point of a private key is to be able to decrypt messages, so (no matter what we do) the proxy and Bob effectively have the private key (even if they might come up with the same bit pattern).

So, what does collusion resistance mean in this context?  If the requirement is that they cannot determine the bit pattern of Alice's key, well, we can easily do that by using a scheme with multiple equivalent keys (and so even if they can come up with 'a' key, it is unlikely to be Alice's bit pattern).  However, that doesn't sound very useful...


Comparison of different asymmetric signatures Please forgive me, because I suspect I don't even know enough to ask this correctly:

Can someone speak to the pro's and con's of the various asymmetric signatures?

I have a use-case in which I put data and a signature of that data in a QR code, where storage size is limited.  As such, I'm trying to understand the trade-off's between security / size (and any others trade-off's of which I might not even be aware).

Thank you!

Edit: I'm using RSA-512 and it works, but I'm most curious if there is a signature method that is secure but uses fewer characters.

In summary: forget the current RSA-512, which is ridiculously vulnerable. For signing QR/2D codes (where minimizing size of the data embedded in the code is essential) with contemporary security:

jump to RSA-2048 using message recovery of ISO/IEC 9796-2, giving a 256-byte 2D-code (including signature) for up to 222-byte useful message, and 34-byte overhead past that mark (but be aware that up to 222-byte of the useful message gets obscured until the signature has been verified);
or, if a 256-byte 2D code is too much and all messages are small (say less than 192-byte message before signature), use Ed25519 or perhaps ECDSA with curve P-256; either adds a 64-byte signature to the message (but has a more complex/power hungry/slower signature verification);
or  venture into relatively uncharted territory and head to the others section, where more compact schemes are discussed.

Also, consider a compact encoding of the useful message (perhaps using data compression), and pay close attention to how the signed message gets transformed into a 2D code: there are several options in format and encoding, and some make 2D code larger thus harder to scan than others.

RSA signature with appendix

Example standards: RSASSA-PSS of PKCS#1v2, ISO/IEC 14888-2 (preview)

Pros:

extremely fast/frugal signature verification (especially with $e=3$);
among the simplest;
widest use and support: this is the signature standard against which all others are compared;
approved by all security authorities.

Cons:

large size in addition to the message, by the modulus size, which is the defining security parameter: RSA-512 (64 bytes added) is trivially breakable with readily available services, RSA-1024 (128 bytes) is rightly considered obsolete, 2048-bit (256 bytes) is the minimum that won't get one shamed;
rather large key size (public key is slightly above signature size for the common format, and can only be about halved; private key is typically larger, that's seldom an issue, and would be fixable);
relatively slow signature generation (a sizable fraction of a second, multiplied by nearly 8 when the key size doubles).

RSA signature with message recovery

Typical standard: ISO/IEC 9796-2 (preview)

Pros:

yields the smallest size added to message (smallest/easiest to read 2D code) when the message is large (wgich is when size matters most): with SHA-256 (128-bit security level), it can be added as little as 256+16 bits or the key size minus that, whichever is larger (e.g. for RSA-2048: 34 bytes added for messages 222 bytes or larger, or whole signed message 256 bytes below that thresold);
about the same extremely fast signature verification (especially with $e=3$).

Cons:

at least some of the message is not in clear (in the 2D code), rather it is recovered by the signature verification process;
presently only common in Smart Cards, and then typically using mode 1 which is rightly frowned at by security certification authorities because it has a security flaw allowing attack in some (mostly theoretical) setups;
not widely supported (e.g. not part of Android, but in BouncyCastle's SignerWithRecovery; discard mode 1/ISO9796d2Signer in favor of mode 2 or 3/ISO9796d2PSSSigner for new applications);
same large large key size and slow signature generation;
not FIPS-compliant (but Common Criteria recognized).

Rabin/Williams (RW) variants of the above two

Example standards: ISO/IEC 14888-2, ISO/IEC 9796-2.

Pros:

even faster signature verification (nearly twice as fast as RSA with $e=3$), which is good for some very low end/power starved devices.

Cons:

more tricky signature process (a common implementation computes a Jacobi symbol, and an error there can destroy all security; as pointed in comment by Squeamish Ossifrage, there is however an alternative);
uncommon, seldom any security-certified device available to sign.

DSA

Example Standard: FIPS 186-4 section 6.

Pros:

smaller size added to message than RSA with appendix, and than RSA with message recovery for small message (only): with SHA-256 (128-bit security level), 64 bytes added regardless of message size (thus smaller 2D code than RSA signature with message recovery for messages below some threshold like 192 bytes, but like 30-byte larger for large message).
possibly faster signature generation than RSA, especially at larger security level;
well standardized in FIPS 186-4.

Cons:

slow signature verification compared to RSA (can by a factor well over 100 compared to RSA with $e=3$);
about the same large public key size as RSA;
failure of RNG on the signer side can be disastrous.

ECDSA

Example standards: FIPS 186-4 section 9, ANSI X9.62, Sec1v2+Sec2v2

Pros:

same small size added to message as DSA;
signature generation faster than RSA (by a factor like 10 and growing with security level);
signature verification and generation appreciably faster than DSA (by a factor like 20 and growing with security level);
small public key size (about the same as signature in a common variant);
same small private key size as DSA (e.g. half of signature);
has gained traction over DSA, thanks to the above and to NIST support.

Cons:

verification still much slower/more power hungry than RSA or RW;
more complex math and larger code than RSA or DSA;
many incompatible curves and formats around (though P-256/secp256r1 is a common choice for curve);
some variants/implementations may arguably have been patent-encumbered, or even could still be;
failure of RNG on the signer side has same disastrous effect as for DSA.

EdDSA

Example standards: RFC 8032, Ed25519

Pros:

same small size added to message as DSA/ECDSA;
amenable to faster implementation than ECDSA for signature generation and verification, especially for software implementations of signature generation that must resist side-channel attacks;
well-accepted and available in open source software;
signature does not require a RNG, thus can't fail for that reason;
stays relatively clear from a patent minefield.

Cons:

verification still sizably slower/more power hungry than RSA or RW;
not validated by FIPS or AFAIK by other governmental security authorities.

Others

Schnorr signature with appendix has existed for a long time and is academically well recognized, but seldom used. The original variant has a signature 25% shorter than (EC/Ed)DSA, and stands unbroken, but has no security reduction (contrary to variants with the same size as DSA), and (I guess, thus) is not standardized. EC-Schnorr exists (in all too many incompatible standardized versions, including EdDSA).

There are message-recovery variants of (EC)DSA and Schnorr signature (bibliography there), which save 25% in size (perhaps 50% which put them on par with RSA using message recovery, but apparently at the cost of giving up security reduction). They are great for QR codes conveying little data. Among these, I regard ECPVS of ANSI X9-92-1, which was developed for stamps, as among the closest to a practical and recognized standard (but it appears to be patented, at least in some implementation variants).

The most compact signature scheme with appendix might be Boneh–Lynn–Shacham but it is complex, verification is slow, there is no consensus on choice of secure parameters for compact variants (some formerly considered secure no longer are), and I can point a single use case (with, I'm afraid, marginal security by today's standards).


How can AES-CCM behave as an AEAD stream cipher? AESCCM-  Couter with Cipher Block Chaining Message.
As it uses cmac for generation for tag , which is internally aes-cbc (block cipher, need block size, may require padding) And Encryption is done with AES-CTR (can be used as stream cipher)
How AES-CCM can behave as a AEAD stream cipher , as it uses aes-cbc ?
Whereas in case of AES-GCM for tag generation uses GMAC and for encryption CTR is used , which are not dependent on block sizes. So this can be used as a stream cipher.

The property that you are looking for is the "online" property of a stream cipher. CCM was however developed for packet encryption where the size of the data is known beforehand. So CCM lacks the strict online requirements for an online cipher. However, since the cipher underneath still uses counter mode, the encryption itself can still be performed on each byte separately in an online fashion (performing online per bit encryption / decryption is not possible in most implementations).

Usually you'd want to verify the authentication tag for correctness before decryption for any AEAD cipher. That means that the online properties of the underlying counter mode are generally not used. Still, you could first verify and decrypt in online fashion afterwards using two passes over the ciphertext.

Furthermore, if the authentication tag is considered part of the ciphertext - like most libraries do - then it is unlikely that those libraries will expose the online properties of the underlying counter mode during decryption. The implementation will have to cache at least as many bits as present in the authentication tag before it decides that they are part of the counter-mode encrypted plaintext or part of the authentication tag. That means that during decryption the cache is always kept full until the end of the stream is reached.

That the CBC-MAC (not CMAC) used by CCM needs to process the data block by block us usually not considered a problem. Any MAC is required to keep state anyway, and the verification can simply take place when all the data has been processed. Note that GMAC within GCM also performs multiplication over 128 bit blocks. The online property is therefore considered for the cipher part of the AEAD mode only.

Conclusion: CCM has not been defined to offer online encryption / decryption, and there are serious issues with using AEAD ciphers for online encryption / decryption even if it was. That the CBC-MAC construction is used has little to nothing to do with the underlying issues.

I'd you're looking for an AEAD mode with better online properties and MAC based on the block cipher then take a look at EAX. EAX is basically a standardized way of using CTR mode and CMAC authentication.

There are two major drawbacks:

It has only been accepted as draft standard by NIST;
Due to the additional calculations for CMAC compared to CBC-MAC it adds a constant overhead preset message.

And you'd still have all the generic drawbacks mentioned for AEAD ciphers when it comes to online decryption, of course.


How should a string be converted to a number for use by a hash function? After reading this question/answer I thought I'd try and implement the SHA-256 for my own education. My initial thought for converting the input into a number was to use a line of code like sum([ord(character) for character in input_string]), I quickly realized this is a terrible idea because I'm greatly reducing the entropy of the input by mapping a lot of highly varied strings to a relatively small number of integers. My second though was to get a hex representation of the string then get the base 16 integer representation of that hex string

import binascii
input_integer = int(binascii.hexlify('hello world'), 16)

However since I'm not an expert in hashing algorithms there may be something wrong with my second implementation that I'm not aware of.

How do you convert a string to a number to be used in a hash algorithm?

My code is written in python, for reference

The input format of the data doesn't affect the security of the algorithm.

Any format that can be represented by a sequence of bits will be fine. You can use raw ASCII byte values, 6-bit Base64 values, anything which is in binary form.

If you convert your string into ASCII bytes, for example, you'll end up with a set of 8 bit numbers. Join them together and there's your input.

Since SHA256 uses 32-bit words, it's common to use a byte format for the data (4 bytes = 32 bits). After converting your input to a set of bits, your first task will be to append a 1 bit, pad with zeroes to 448 bits and then append a 64-bit length (the original bit length of the input data) to give you a 512 bit buffer.

I'm sure you can handle the rest.


Why is x^8 + x^4 + x^3 + x + 1 used in AES's Rcon? I am not familiar with field theory so please bear with me if this is obvious to you.

I was wondering why this particular reducing polynomial
$x^8+x^4+x^3+x+1$ is picked for AES' Rcon. Can't it be some other polynomials?

The polynomial $x^8+x^4+x^3+x+1$ is the minimal irreducible binary polynomial of degree 8, in the sense that:

it has the smallest possible number of terms for an irreducible binary polynomial of that degree, and
among all the irreducible binary polynomials with the same degree and number of terms, it has the smallest exponents.

In particular, it is the degree-8 polynomial listed in Seroussi's well known table of low-weight binary irreducible polynomials published in 1998, and the first degree-8 polynomial listed in Appendix 2, Table C of Lidl & Niederreiter's Introduction to Finite Fields and Their Applications (1986).  It's quite plausible that the AES authors may have simply looked it up in one of these tables, or in some other similar list.

In any case, the use of such "canonical" minimal polynomials is hardly unusual in crypto.  For example, the GCM mode polynomial $x^{128}+x^7+x^2+x+1$ is also the minimal irreducible polynomial of degree 128, while the Whirlpool polynomial $x^8+x^4+x^3+x^2+1$ (differing from the AES polynomial by the replacement of the $x$ term with $x^2$) is the minimal primitive binary polynomial of degree 8 and is explicitly documented to have been picked from the Lidl & Niederreiter table.


18 rounds encryption in embedded? I have a power trace of a decryption.
It seems like I'm watching a 18 rounds decryption algorithm.
I cannot think about any other algorithm implemented in ASIC except Cammelia who has 18 rounds.

Which other algorithms are commonly used in ASIC and has 18 rounds ?

Also it seems it receive 128 bits block size.

The only 2 "common" algorithms that I know off the top of my head with 18 rounds are Clefia and Camellia with 128-bit keys.

Anubis may also be an option, I believe that with a 320-bit key it uses 18 rounds, I have no idea why that would be used instead of AES.

I suppose it is also trivial to add rounds to AES or Twofish in hardware, both the key schedule and round function support additional rounds without modification to their core.


Weak Decisional Diffie-Hellman Problem Is this problem still hard?
Given $$(g,g^a,g^b,c)$$ decide if $c=a\cdot b$?
If there is an adversary that solves the standard Decisional Diffie-Hellman Problem then it can solve my new problem. But I can't understand that my new problem still hard or not.
Did anyone see this problem or similar to my problem? Can anyone help me?

Yes it is. It can be formally reduced to the hardness of the decisional square Diffie-Hellman assumption, which states that distinguishing $(g,g^a,g^{a^2})$ from random is hard (this is a well established assumption).
It follows in a relatively simple way from the answer I wrote here to a related question. I can let you work out the details in case you want to play a bit with these reductions. In case you cannot figure out the formal reduction, just ask in the comment and I will elaborate.


Zero-knowledge proof of knowledge without replay Given a hash function:

$H(x)$ = y

$y$ is publicly known.

Alice wants to prove to Bob that she knows $x$. Alice could create a non-interactive zero-knowledge proof, and share it with Bob. Then Bob could verify that Alice has a valid $x$.

The protocol is describe here:
https://media.consensys.net/introduction-to-zksnarks-with-examples-3283b554fc3b

Now suppose that Bob wants to prove to Carol that he knows $x$. Bob could re-send the same proof that Alice sent to him, even though he doesn't know $x$.

Is there any way to create a proof that cannot be replayed by a malicious verifier?

"She knows" has a definition: an extractor algorithm should exist that produces the witness $x$ while talking to the proving party in place of verifier. For zk-SNARK from Christian Lundkvist in the medium post you referenced, the protocol is non-interactive and the "proof of knowledge" is derived from the "knowledge of exponent assumption", not from the extractor algorithm. It seems there's a consensus that both definitions are good enough.

My point is, a non-interactive "proof of knowledge" is very different from an interactive one. It seems it was a design choice that zk-SNARK proofs should be verifiable by everyone without interaction.

There's a chance with a designated verifier (introduced in late 80s). As a setup, the potential verifier sends some hash $t$ to prover and runs this protocol to show he knows the witness $s$ for that additional hash: $H(s) = t$. The prover then runs a protocol to show his knowledge of either one of two preimages ($s$ or $x$).
This could mean a circuit representing equations:
\begin{gather*}
  z (1 - z) = 0 \\
  H(zs + (1 - z)x) = zt + (1 - z)y
\end{gather*}
It follows only that a verifier that keeps his $s$ secret can be assured original statement $H(x) = y$ is true.

Make a protocol interactive again :)


Better lower bound on min-entropy In “Randomness Condensers for Efficiently Samplable,
Seed-Dependent Sources” by Dodis, Ristenpart, and Vadhan (PDF), I have seen the statement that:

  any tuple of distributions $(X,Z)$ is $\varepsilon$-close
  to $(X′, Z)$ such that $$H_\infty(X′\mid Z) ≥ H_2(X\mid Z) − \log (1/\varepsilon)$$ offering a bound on min-entropy which may be better than $H_\infty(X′\mid Z) ≥ H_2(X\mid Z)/2$.

I can not see why this is the case. Could anyone please shed some light? Does it involve the Leftover Hash Lemma!?

The proof (courtesy of M. Skorski) relies on the so-called "smoothing" technique [Cac97,RW,Sko15].

For some $0<\epsilon<1$, let $B$ be the subset of heaviest points in $X$ whose mass add up to $\epsilon$ -- i.e.:
  $$\sum_{x\in B} p_X(x)=\epsilon, \text{ and } \min_{x\in B}p_X(x)\geq\max_{x\in\bar{B}}p_X(x).$$
Let $X'$ denote the conditional distribution of $X$ on $\bar{B}$ -- i.e.:
  $$
  p_{X'}(x):=
    \begin{cases}
      0 & x\in B,\\
      \frac{p_{X}(x)}{(1-\epsilon)} & x\in\bar{B}.
    \end{cases}
  $$
Note that the statistical distance between $X$ and $X'$, $\Delta(X,X')=\epsilon$.$^1$ Let $m:=\max_{x\in\bar{B}}p_X(x)$. Now, let's consider the collision entropy of $X$:
  $$H_2(X):=-\log\sum_{x\in X} p_X^2(x)\leq-\log\sum_{x\in B} p_X^2(x)\leq^2-\log (m\epsilon).$$
It follows that $-\log(m)\geq H_2(X)-\log(1/\epsilon)$, and the results follows as $H_\infty(X')=-\log(m/(1-\epsilon))$.

A similar argument can be made for a joint distribution too.

References:
[Cac97]: C. Cachin. Smooth Entropy and Renyi Entropy, EUROCRYPT'97.
[RW]: R. Renner and S. Wolf. Smooth Renyi Entropy and its Applications.
[Sko15]: M. Skorski. How to Smooth Entropy? SOFSEM'16

Footnotes:
1. Proof:
  \begin{align}
    \Delta(X,X')
      &=\frac{1}{2}\cdot\sum_{x\in X}\left|p_X(x)-p_{X'}(x)\right|\\
      &=\frac{1}{2}\cdot\sum_{x\in B}\left|p_X(x)\right|+\sum_{x\in \bar{B}}\left|p_X(x)-p_{X'}(x)\right|\\
      &=\frac{1}{2}\cdot\left(\epsilon+ \sum_{x\in \bar{B}}p_X(x)\left|1-\frac{1}{1-\epsilon}\right|\right)\\
      &=\frac{1}{2}\cdot\left(\epsilon+ (1-\epsilon)\left|1-\frac{1}{1-\epsilon}\right|\right)=\epsilon
  \end{align}
2. Proof: $\sum_{x\in B} p_X^2(x)\geq \sum_{x\in B}m\cdot p_X(x)= m\cdot\epsilon$


The length of the shortest vector in Lattice In Micciancio and Regev's paper "Lattice-based Cryptography",the length of the shortest vector is at least $\min\{q, 2^{2\cdot\sqrt{(n\cdot \log{q}\cdot\log{\delta}})}\}$ . I want to ask why the paper chose the latter as the length of the shortest vector rather than $q$ when considering concert parameters. In addition, whether the $q$ is normally more than $2^{2\cdot\sqrt{(n\cdot \log{q}\cdot\log{\delta}})}$?

Remember that we are considering $q$-ary lattices, as defined by

$$ \Lambda^{\perp}_q(\mathbf{A}) = \{ \mathbf{y} \in \mathbb{Z}^m : \mathbf{A} \mathbf{y} = \mathbf{0} \mod q \}. $$

Clearly the vector $(q,\mathbf{0})$ is in this lattice, and has length $q$. This is a trivial, uninteresting solution, as it doesn't give a better understanding of the lattice.

$\min \{ q, 2^{2 \cdot \sqrt{(n\cdot \log{q} \cdot log{\delta})}} \}$ refers to the shortest vector one can find using (then) state of the art lattice reduction algorithms. If you're choosing parameters in order to make a cryptographic scheme secure, you are trying to ensure that the shortest non-trivial vectors that can be found are not very short. If trivial vectors break your scheme, it is broken anyway, and no amount of parameter tweaking will fix it.


Do I understand (below) why Q = dP is easy while finding d is hard As we all know for discussion of Dual_EC_DBRG, the point on an elliptic curve Q can be calculated from P and some (large) integer d

$Q = dP$

And we know that knowledge of Q and P is not sufficient to be able to compute d efficiently.

My understanding

I've been hoping to explain why, and I believe that they answer is that when computing dP, one doesn't have to perform d - 1 additions, but instead can make use of the fact that you can calculate $\{2P, 4P, 8P, \dots, mP\}$ where m is the smallest power of 2 greater than or equal to $d/2$. That set of points can be calculated with $\left\lceil\log_2 d\right\rceil -1$ additions.  And then to compute $dP$ we will need an addition for every 1-bit in d.

So in worst case, computing $dP$ requires $2\log_2 d$ additions. But this short cut is not available for computing d from P and Q, and so the number of additions (subtractions) is closer to d itself.

Is this close to being a useful understanding?

Computing $d$ given $P$ and $Q$, with $Q = dP$ is known as the "elliptic curve discrete logarithm problem" and is considered to be infeasible under some hypothesis. The security of Elliptic Curves Cryptography is based exactly on the ability to compute the point multiplication and the intractability of the inverse operation: given two points find out the discrete operand $d$. The difficulty of the problem is given by the size of the elliptic curves.

One (of the best) algorithm to compute the discrete logarithm, Silver–Pohlig–Hellman algorithm, has complexity $O(\sqrt n)$ where $n$ is the order of the elliptic curve, but it is very efficient in the case of $n$ smooth (product of small integer). This is also the reason you don't want to have a curve with a smooth number as order.

The first part of your question shows a standard way to compute the point multiplication using the binary expansion of the multiplicand. It is usually known as "double and add" and corresponds to the "square and multiply algorithm".

If you're trying to understand how the backdoor in the Dual_EC_DRBG works you should read this answer  to the question  Explaining weakness of Dual EC DRBG to wider audience?. Roughly the $P$ and $Q$ used in the standard are generated in an unknown way. So, if NSA knows the $d$ scalar such that $Q = dP$ they can compute some values and synchronize with the generator. If you implement the same algorithm using two (provable) random points, the backdoor disappears. Usually a provable way to generate a point is to hash some not random english strings (as the US Constitution or the Shakespear's work or the Star Wars The Force Awakens original script, or ...) and use this output to generate the point.


Why do the signature and ciphertext size increase in post-quantum schemes? Why do the signature and ciphertext size increase in post-quantum schemes? And is there any table or comparison as to how much this increase happens for each scheme type (lattice, multivariate, code-based, etc.)

What you say isn't entirely correct. In some post-quantum schemes, the signature or ciphertext is actually smaller than the equivalent-but-classical security level analogue in ECC. See for example the MQ encryption scheme ZHFE (link) or the code-based signature scheme CFS (link). However, in these cases the public key is invariably huge. In other cases we have the opposite: e.g. in the hash-based signature scheme SPHINCS (link), the public key is nice and small, but the signatures are huge. Lattice-based schemes tend to produce public keys of roughly the same size as the ciphertext or signature, but both are noticeably larger than their ECC counterparts. So there is a question there, but it should be rephrased to something like "why is $|\mathsf{pk}| + |\mathsf{s}|$ or $|\mathsf{pk}| + |\mathsf{c}|$ always so large in post-quantum crypto, but not in classical crypto?"

The way all public key schemes work is by relying on hard computational problems with a very definite algebraic structure.* This structure is necessary to guarantee a link between the public and private keys, i.e., only the holder of the private key that matches the public key should be able to decrypt or sign messages. This stands in stark contrast to symmetric crypto, where security relies on breaking -not retaining- algebraic structure and no such link is necessary because there is no distinction between public and private keys. Public key schemes are the subject to more functional constraints than symmetric schemes and as a result there are fewer strategies for their construction. Of those strategies we know to work, only schemes based on number theory and elliptic curves are known to be broken by Shor's quantum algorithm. The others are consequently considered part of post-quantum cryptography. So maybe the best phrasing of your question is something like "why are schemes that are broken by Shor's algorithm, also the schemes with the smallest $|\mathsf{pk}| + |\mathsf{c}|$ and $|\mathsf{pk}| + |\mathsf{s}|$?"

This question has a straightforward answer: both number theory and elliptic curves, or commutative group theory in general, enable a very succinct encoding of computational hardness while retaining a lot of algebraic structure. Unfortunately, this copious algebraic structure comes back to bite you in the ass because it is precisely what allows Shor's algorithm to work.

The good news is that, like Yehuda says, there is no proof that hard algebraic problems that resist attacks on quantum computers cannot have a succinct encoding. So conceivably, it may be possible to design short public key and short signature/ciphertext post-quantum schemes. We just don't know of any that accomplish this.

In terms of a comparison of existing schemes, take a look at eBATS (link), a website that compares operational cost as well as key and message size of various pre- and post-quantum schemes.

*: The exception to this rule is the branch of hash-based signatures. But their notable lack of algebraic structure is also what causes the inherent statefulness (i.e. you have to keep track of all previous signatures to be secure) and what kills the possibility for public key encryption based on hash functions.


crypto design with AES-256 MODE OFB I have the following APP Design

key store (contains 1:n user payload as 1:n key store entries)
key store salt (is used to extend to key store password to 256 bits, stored in clear text)
key store entry (what the user wants to encrypt) with:

own entry IV (payload is encrypted with AES-256 MODE OFB, IV stored in clear text )
own entry SALT (64 bytes random appended to payload before encryption, SALT stored in clear text)

The encrypted entry is stored base64 encoded:

model (a): only passwords are allowed
model (b): additional data is allowed

Here the additional data may be comments / remarks in the users language,  links or email addresses.

The key store SALT is used for apple crypt function CCKeyDerivationPBKDF which extends the user password to 256 bits to be used for AES256.

Is it secure to allow multiple keys on the key store if the key store SALT is shared on all keys?

The number of used passwords is not detectable as the application accepts every entry as valid. You must decide on the decrypted information if the key is valid or not. This is also true for the user who should know the correct password.

Can an attacker use the shared SALT for some attack?
Is there a security risk when I use model (b) which allows the attacker to guess, that there is user language (or links / email addresses) in the encrypted entry?

Problem statement

You have a list of messages $(m_1, m_2, \dots, m_n)$, possibly with corresponding tags/descriptions $(t_1, t_2, \dots, t_n)$, that you want to store. You want to protect confidentiality of the messages (but not the tags/descriptions) against an adversary that compromises your storage. You have a single secret passphrase $pw$ at your disposal.

The adversary may know/be able to guess part or all of some or all of the messages.

Your solution

What you propose (based on AES-OFB, $c = \mathrm{AES{-}OFB{-}}\mathcal{E}(k, m)$, $m = \mathrm{AES{-}OFB{-}}\mathcal{D}(k,c)$, the encryption algorithm generates the IV and includes it with the ciphertext; your software may have a different interface):

Generate a salt $s_0$.
For each entry, generate a salt $s_i$.
For each entry, compute $k_i = \mathrm{PBKDF2}(pw, s_0 || s_1, \mathit{iterations})$.
Compute $c_i = \mathrm{AES{-}OFB{-}}\mathcal{E}(k_i, m_i)$.
Store the two lists $(c_1,c_2, \dots, c_n)$ and $(t_1, t_2, \dots, t_n)$.

Q&A

Q: Do you need the per-entry salts?
A: No. The salt is there to keep the per-passphrase search cost high for attackers that have compromised the stores of many users. The salt $s_0$ is sufficient.

Q: Is it a problem that the adversary can guess/know part of the message?
A: No. AES-OFB provides confidentiality against chosen plaintext attacks.

More than you asked for

You shouldn't be doing this kind of design on your own, nor should you rely on advice given on a random web site.

Don't think that the adversary won't be able to recognize correct passwords.
Don't assume that the user will be able to recognize an incorrect decryption.
Don't use OFB mode. It is sometimes inefficient and does not provide integrity.

The following natural proposal is better than yours (based on AES-GCM, a symmetric encryption scheme that encrypts messages and protects the integrity of associated data as well: $c = \mathrm{AES{-}GCM{-}}\mathcal{E}(k, ad, m)$, $m = \mathrm{AES{-}GCM{-}}\mathcal{D}(k, ad, c)$. (Note that I am assuming that the encryption algorithm generates a fresh IV/nonce for each encryption and attaches it to the ciphertext. Your software may have a different interface.))

Choose a salt $s$.
Use PBKDF2 (or something similar) to derive a key $k$ from $s$ and $pw$, using a suitable number of iterations.
Encrypt each secret as $c_i = \mathrm{AES{-}GCM{-}}\mathcal{E}(k, i || t_i, m_i)$.
Store the two lists $(c_1, c_2, \dots, c_n)$ and $(t_1, t_2, \dots, t_n)$.

PS. Don't use a scheme you got for free on the internet.


Do both client and server need to implement OpenSSL protections to protect from CBC attacks In regards to the protections implemented in OpenSSL 0.9.6d (described in section 2. http://www.openssl.org/~bodo/tls-cbc.txt). My understanding is that the mechanism prepends an empty record when sending data in order to make the IV unpredictable. however the client->server and server->client maintain separate IV data.

If relying on this mechanism to protect against CBC vulnerabilities (such as BEAST) is it required that both client and server have this mechanism enabled?

Yes, both the client and the server must have this mechanism enabled to get full protection from BEAST and similar attacks.

In particular, if the client is a browser with scripting capabilities, it is the client side implementation that must send empty packets before each content packet. Enabling this feature server side only, just means that the server will send such empty packets. This will provide no protection from script based attacks against browsers.


Elliptic curve cryptography G*G I understand how ECC works for the point multiplications and stuff.
All we normally do is to multiply a scalar number (lets say d as a private key) with the base point generator G to get a public key point on an elliptic curve.
I am trying to tweak the algorithm for some other purposes so I am just wondering whether an operation like G*G which is a point multiply another point is possible or not. And if it is possible how can we calculate that?

Such an operation is possible.

The ways of calculating that appear to be different for each curve.


CTR mode nonce with aggressive key rotation policy I'm writing a small encryption library which will be required to use the shortest possible amount of overhead for describing ciphertexts. I want to use CTR mode with a 6-byte random nonce.

Normally I would never disregard best practices like this, but I think in this context it is acceptable because the encryption keys will be rotated frequently. As I understand it, the weakness in CTR mode occurs when the same nonce AND key are used to encrypt. If the key is rotated, say, every 2 months, it's unlikely that there would ever be a nonce collision.

This is a heterodox use of CTR mode - feel free to savage my idea if it is flawed. Thanks for your help.

A 6-byte nonce can expect to receive a collision 0.01% of the time after around 240,000 nonce generations (based on a birthday attack). After 100 such rotations (a little under 17 years, based on your 2-month rotation policy), that comes out to a likelihood of just under 1% of experiencing a collision. On the surface, to me that seems like a reasonable margin of security.

If practical, you may also want to consider simply using an autoincrementing counter for your IV. Allow the first byte to be a machine identifier, and then use a mutex to synchronize access to the remaining five bytes. Whenever you need an IV, lock the mutex, read the current value as the IV, increment it by one, save it, and release the mutex. This allows you to encrypt over one trillion messages with a single key before the nonce rolls over, and has zero possibility of collision as long as you detect IV wraparound.


Attack MD5 with limited input and partial information If I know that MD5 input is limited to a character set. can I find any information on the input based on the output?
example:
input consists of 16 character from list of [1,2,3,4,5].
question:
based on the md5 output is there any way to find out information about the input? I.e. which character was at the beginning or that the input mostly consists of a particular character?

Let's begin with what is MD5;

MD5 has a 128-bit digest size, 512-bit block size Merkle–Damgård construction based hash function created by Ronald Rivest in 1992.
From a secure hash function we want, 128-bit pre-image and secondary pre-image resistance, and 64-bit collision resistance. MD5 collision resistance is broken, and finding collision can be done in minutes.
There is an attack on the pre-image resistance of MD5 that has $2^{123.4}$-cost however, due to the memory cost, you would not go in this way instead you will run full brute force or better build the parallel machine.

Pre-image attacks

Today's largest known collective computer power is the bitcoin miners that can reach $\approx 2^{92}$ SHA2d calculations per year. This means that even they need 35-years to find one.

The current best practical attack on the pre-images is when there are multiple targets ( we can always have if one still uses MD5 without salts, etc.). Build the parallel brute force machine and use Oechslin's rainbow table;
for $t$ targets built $t^2$ parallel machine with $p$ success probability for finding the first target, you need $2^{128}p/t$ area*time cost. This is much better than the brute force of a single target. See more here.

There is also Grover's unstructured quantum search algorithm to be considered that reduces the search time into the square root of it. If built, then (ignoring running cost) the search time will be around $2^{64}$.

It can also be parallelized; however, building $k^2$ machine will provide $k$ speed-up.

based on the md5 output is there any way to find out information about input? like which character was in the beginning or input mostly consists of which character?

No, what you are describing is actually destructive to pre-image resistance.
If you can find the first character (byte) then the pre-image resistance is fall to $c \cdot 2^{120}$ where the $c$ is the cost of determining the first character. The next question will be what is preventing the attacker to determine the next byte, then next? Hash functions are designed to have an avalanche effect that it changing one-bit of the input should have affect all the output bits randomly, i.e. all of the output bits flip with 50%.
If you can figure out the character space by looking at the hash ( let assume that there is an oracle that tells us this), like 5 numbers, then the pre-image search is crippled if you look into 128-bit information, $5^{16} \approx 2^{38}$. This doesn't mean that the pre-image has to be found in this 128-bit space. Still, we can look at the string length 32 and the search time will be $2^{76}$-time
Or, actually, you are asking something like that;

If the input space is low as 16 characters from $[1,2,3,4,5]$ then this is the short input space problem on the hash functions. Since the calculation of the hash is free, one can easily search these values. $2^{38}$ search space can be easily reached by today's ordinary CPUs.
To mitigate this you can use a keyed hash function like $\operatorname{HMAC-MD5}(k,m)$. As long as the key is kept secret, then you are fine. Note that, if there is no restriction to use MD4, prefer $\operatorname{HMAC-SHA-256}(k,m)$

actual problem is I have a SHA-256 string as input(64 characters and hex) and I want to show MD5 of this input to my users and it's important that they can't find any information based on the MD5 output. I want to know if its a short input space or not

A hex is 4 bits that you will have $4^{64}$ input space to search; that is $2^{128}$-bit. This is too high for a single target. However;

If the $t$ users can come together and can build the parallel machine using the rainbow tables then they can find the first target on  $2^{128}p/t$ area*time cost. So, you can tune your number with this information.


How to cipher with N public keys and decipher with ANY of the N private keys? X = plaintext

Given N key pairs:

P1 = (P1.private, P1.public)
...
PN = (PN.private, P1.public)

I want to find 2 function Cipher and Decipher such as

Cipher(X, P1.public, P2.public...PN.public) = X encrypted
Decipher(X encrypted, P1.private) = X
...
Decipher(X encrypted, PN.private) = X

Does such scheme exist?

Pick your favorite KEM, say RSA-KEM.  Let $P_1, P_2, \ldots, P_n$ be the public keys, and $(k, c) = \operatorname{Encap}(P)$ be a random key $k$ and encapsulation $c$ of the key that can be opened by $k = \operatorname{Decap}(S, c)$ if $S$ is the secret key corresponding to $P$.

Let $(k_i, c_i) = \operatorname{Encap}(P_i)$.  Pick $k$ uniformly at random and yield $$c = ((c_1, k'_1), (c_2, k'_2), \ldots, (c_n, k'_n)), \quad\text{where}\quad k'_i = k \oplus k_i,$$ as the encapsulation of $k$.  Then use $k$ as a key for a DEM, or authenticated encryption, say NaCl crypto_secretbox_xsalsa20poly1305, to transmit your message.  The $i^{\mathit{th}}$ recipient can recover $k$ by decapsulating $k_i$ from $c_i$ and computing $k = k'_i \oplus k_i$ and thereby decrypt the message.


Does the double-hash H(H(x)) have greater collision probability than H(x)? Let $H$ be a collision resistant hash function and $P_c[H](S)$ the collision probability about a sample set $S$ of input elements (eg. random numbers). It increases with double hash?  That is, $P_c[H\circ H](S) \ge  P_c[H](S)$   ?

Well... we need a precise $P_c$ definition.  Perhaps the problem here is also the choice of a good probability definition (see notes below).

NOTES

Answer's application: the answer is important in the context of checksums used for digital preservation integrity of public files.

Imagine the checksum (the hash digest $H(x)$) of a PDF article of PubMed Central or arxiv.org... And that we need to ensure the   integrity, with no "PDF atack" or minimizing it, in nowadays and in a far future, ~20 years.

If the answer is "YES there are a little increase", the recommendation will be "please don't use double-hashing as standard for checksum for PMC or  arxivOrg".

General probaility

The general collision probability is defined as

  Given $k$ randomly generated $x$ values, where each $x$ is a non-negative integer less than $N$, what is the probability that at least two of them are equal?

and depends only of the $|S|$, so $P_c[H\circ H] = P_c[H]$... There are a hypothesis of "perfect hash function", but I want to metric the imperfections.

If there are no error on my interpretations, I need other probability definition.

Counting the collisions

Suppose a kind of "collision tax", $\frac{N_c}{|S|}$, based on the number of collisions $N_c$ occured with a specific sample. So, for many different sample sets $S_i$ with same number of elements, $k=|S_1|=|S_2|=... =|S_i|$. Suppose a set $K$ of all sets $S_i$ and  $P_c[H](K)$ as an average of this collision rate.

This kind of probability seems better to express the problem.

... Bloom filter efficiency

Another metric, instead a probability. Perhaps using
Bloom filter theory as reference. A kind of efficiency-benchmark of two Bloom filters, one with $H$ other with $H\circ H$.

I'm not sure what the question here is, but obviously applying the hash function twice can never decrease the number/probability of collision as all collisions in the first invocation are maintained.

However if H is collision free( a permutation as opposed to a random function) doubling will not cause any more collision it will remain collision free. So we see the number of collision does not strictly increase.

For a PRF, the number of collision does clearly increase, this is one reason why when we iteratively hash passwords in for key derivation we mix in the input again every round and not simply hash calculate $H^n(salt || pass)$

If you look at the structure of a function you will see several cycles and threads(trees) leading into these cycles:

The cycles do not generate more collisions when doubled. Each thread meeting a cycle contributes one collision, If All the threads are of length 1 no more collisions are added when applying twice in any other case the number of collisions increases.


How does Montgomery reduction work? I want to reduce a multi-precision integer $x$ modulo a prime $p$, very fast. Performing the traditional Euclidean division for only calculating the modulo, is inefficient and modular reduction is at the heart of many Cryptographic primitives like Elliptic Curve Cryptography. There are other methods to perform the aforementioned task like Barret reduction, etc, but I would like to learn about Montgomery reduction and its peculiarities first, because of its practical significance.
Algorithm:
     Input : Integer x, n, k
     Output : (2^(-k) * x) mod n
    1. for t from 1 to k do
        1.1 if x is odd then
            1.1.1     x <- x+n
        1.2 x <- x/2
    2 Return x

There are restrictions on $x$ like, $0$ <= $x$ < $n^2$, and also, $n$ should be odd.
The book from which, I borrowed the above algorithm from , states two facts:

Fact 1 : Adding n to x does not change the residue, since in effect it adds one to the quotient ⌊x/n⌋. Another way to explain this is that
n is (or multiples of n are) congruent to zero modulo n. Adding zero
will not change the value of the residue.
Fact 2: If $x$ is even, then performing a division by two in $Z$ is congruent to $x · 2^{−1} \mod n$ . Actually, this is an application of
the fact that if x is evenly divisible by any $k$ ∈ $Z$, then division
in Z will be congruent to multiplication by $k^{−1}$ modulo $n$ .

I don't understand the meaning behind Fact 2. In reality, I'm having trouble in comprehending how the author transcends from regular arithmetic to modular arithmetic mod n ?
Why is it that division of $x$ by two in $Z$ (integers) is congruent to multiplication by $2^{-1}$ in modulo $n$. After all $2^{-1}\mod n$ can be  easily calculated by the extended euclidean algorithm:
Since, $n = 2*q + r$. Since $n$ is odd, $r$ should be $1$. Therefore on transposing, we get:
$n - 2*q = 1$. If we take this preceding equation modulo $n$, we get $-q$ as the multiplicative inverse of $2$ w.r.t mod n.
It would be highly appreciated, if I could get a good explanation of how Montgomery reduction works, in the first place. Why do we keep adding $n$ to $x$ , if $x$ is odd?
I am missing some very great clarity in my understanding! What are the solid principles behind Montgomery multiplication with reduction ? Since, I come from mostly programming background, I seem to be lacking some mathematical knowledge in this context.
Every help will be greatly appreciated!

In 1985, Montgomery introduced a new clever way to represent the numbers $\mathbb{Z}/n \mathbb{Z}$ such that arithmetic, especially the modular multiplications become easier.

Peter L. Montgomery; Modular multiplication without trial division ,1985

We need the modulus $n$ we are working and an integer $r$ such that $\gcd(r,n) =1$ and $r>n$
Definition: The Montgomery representation of $x \in [0,n-1]$ is $\bar{x} = (xr) \bmod n$
Definition: The Montgomery reduction of $u \in [0,rn-1]$ is $Redc(u) = (ur^{-1}) \bmod n$. This is also called $n$-residue with respect to $r$. Indeed, one can show that this set $$\{i\cdot r \bmod n | 0 \leq i \leq n\}$$ is a complete residue system.
In Cryptography, we usually work with prime modulus therefore we can chose $r = 2^k$. In this case the  $\gcd(r,n) = \gcd(2^k,n) = 1$ is satisfied.

Fact 1 :

Since we are working modulo $n$, this is an elementary result.

Fact 2: If $x$ is even, then performing a division by two in $\mathbb{Z}$ is congruent to $x\cdot 2^{−1} \bmod n$. Actually, this is an application of the fact that if $x$ is evenly divisible by any $k \in \mathbb{Z}$, then division in $\mathbb{Z}$ will be congruent to multiplication by $k^{−1} \bmod n$.

What they try to say is

Let $k$ divides $x$ then $u \cdot k = x$ take the modulus $n$ on both sides.  $$u \cdot k = x \bmod n$$ Since $n$ is prime than $k^{-1}$ exist in modulo $n$ and that can be found with the Extended Euclidean Algorithm. For Montgomery this is required only once for $r$. Now we have;

$$u \cdot k \cdot k^{-1} = x \cdot k^{-1} \bmod n$$
$$u = x \cdot k^{-1} \bmod n$$

1.2 x <- x/2

When the $r = 2^k$ this is usually performed by shift operations. This is a trick of the Montgomery. The trial division is transferred into shifts.
x = x >> 2

What are the solid principles behind Montgomery multiplication with reduction?

Montgomery Reduction This is the Wikipedia version.
input: Integers r and n with gcd(r, n) = 1,
       Integer n′ in [0, r − 1] such that nn′ ≡ −1 mod r,
       Integer T in the range [0, rn − 1]
output: Integer s in the range [0, n − 1] such that s ≡ Tr^−1 mod n

m = ((T mod r)n′) mod r
t = (T + mn) / r
if t ≥ n then
    return t − n
else
    return t

Now, the advantage is clear. Since $r= 2^{k}$ the division and $\bmod$ operations are cheap by shifting or masking.
The $n'$ is defined as  $rr^{-1} -n n' =1$
The correctness can be seen by

observe that if $m = (( T \bmod r )n^{'}) \bmod r$ then $T + mn$ is divisible by $r$.

$$T + mn \equiv T + (((T \bmod r)n') \bmod r)n \equiv T + T n' n \equiv T - T \equiv 0 \pmod{R}$$ There for the $t$ is integer, not a floating point.
The output then is either $y$ or $t-n$ ( remember the fact 1). Now let see why the output is $Tr^{-1}$. We again use what we know
$$t \equiv ( T + mn )r^{-1} \equiv Tr^{-1} + (mr^{-1})n \equiv Tr^{-1} \pmod{n)}$$
Therefore the output has the correct residue as we wanted.
Why the substruction? We need to keep track of the $t$'s size.

$m \in [0,r-1]$
$T+mn$ then lies between $0$ and $(rn-1) + (r-1)n < 2rn$. Since the divived by $r$ then $0 \leq t \leq 2n-1$. A single substraction can reduce the $t$ into the desired range.

Montgomery Product
We are going to define a function that is going to be very powerful. Remember $\bar{a} = ar \bmod n$

$MonPro(\bar{a},\bar{b},r,n)$
//outputs $t = MonPro(\bar{a},\bar{b},r,n) = \bar{a}\bar{b}r^{-1} \pmod{n}$

$ T = \bar{a}\bar{b}$
$m = T n' \bmod r$
$t = (T+mn)/r$
if $t \geq n$ $\text{return}(t-n)$
$\text{return}(t)$

Let us simplify the $MonPro(\bar{a},\bar{b},r,n)$ to $MonPro(\bar{a},\bar{b})$ since we keep them constant and $r^{}$ can be calculated as constant before the operations.

What will happen if we call : $MonPro(\bar{a},1)$?

$$MonPro(\bar{a},1) = (a r) \cdot 1 \cdot r^{-1} = a \pmod{n}$$

What will happen if we call : $MonPro(\bar{a},b)$?

$$MonPro(\bar{a},b) = (a r) \cdot b \cdot r^{-1} = a \cdot b\pmod{n}$$

What will happen if we call : $MonPro(a,r)$?

$$MonPro(a,1) = a \cdot 1 \cdot r^{-1} = a r^{-1} \pmod{n}$$


Information-theoretic bound on leakage by timing measurement I'm looking for an information-theoretic bound on leakage by timing measurement. I'm assuming that an attacker

wants to leak out of a black box a secret key of $k$ bits that is secretly injected into the black box;
has written the black box's code (which can read the key and act accordingly), and can craft this code to the point of choosing the duration of a function performed by the black box among $n$ equally spaced durations $t_j=t_0+j/(n-1)$, $0\le j<n$ ($t_j$ is in units of clock period), with $t_0$ known;
can measure the duration of that function with an uncertainty $u$ according to some distribution $U$, with $|u|<1/2$ unless otherwise stated, at each execution of that function.

and I'm looking for a tight upper bound on the number of timing measurements to leak the whole key (so that I can be sure that some of $k$ remains secret if we are below that bound).

An execution leaks at most $\log_2(n)$ bit worth of information by way of timing measurement, thus at least $\lceil k/\log_2(n)\rceil$ timing measurements are required to fully extract the key by that sole mean. That bound can be reached if the attacker further has $\big\lceil\log_2\big(\lceil k/\log_2(n)\rceil\big)\big\rceil$ bits of permanent storage in the black box that survive function execution, and are initially zero (sketch: we write the key $k$ in base $n$, and the permanent storage is used for a counter telling which digit of $k$ is leaked).

Update: I realize that the above bound of $\lceil k/\log_2(n)\rceil$ measurements also applies if the attacker can choose the input of the black box and have the code act accordingly; this makes Q1 and Q2 below far less relevant.

Q1: What if the attacker's code does not have any permanent storage, only a true random number generator internal to the blackbox? What's even an appropriate way to characterize the number of measurements required to leak the key?

Q2: What if in the situation of Q1, the attacker also obtains in addition of each timing measurement some large random input or output of the black box, also available to the attacker's code?

Q3: What if the attacker's uncertainty distribution $U$ becomes significant? Perhaps, consider that $U$ is the discrete uniform distribution on $[0\dots m-1]$; or $U$ is Gaussian; or something in between, like $U$ is the sum of two or three discrete uniform distribution on $[0\dots m-1]$.

Rationale: My true goal (hopefully reached is we can answer Q3 under the conditions of Q2) is assessing the demonstrable effectiveness of a countermeasure to timing attacks in Smart Cards (assumed running synchronously), consisting of inserting a random pause after a sensitive operation, as in Q3. The hypothesis that the attacker has written the code is of course a worst case scenario, crafted in order to obtain an upper bound of the leakage (a lower bound on the number of measurements necessary).
Q2 is asked because, in a real situation where the attacker did not write the code, it is reasonable to believe that there is no equivalent to permanent storage usable by the attacker, but that input (or output) has a deterministic effect on timing. Q1 is an introduction to Q2, without that data dependency.

As you say, if the measurements are accurate then the device can leak $log_2(n)$ bits of information on each invocation.  If it lacks internal storage then it can't track which parts of the key it has already leaked.  What it can do is leak a random set of bits, but the recipient has to know which bits they are.  I see two approaches.

If the timing channel is the only communication, then the $m = log_2(n)$ bits has to combine both key data ($d$ bits) and position ($p$ bits).  If position indicates which group of $d$ bits we are leaking, then $p >= log_2(k/d)$.  So for a 256 bit key this scheme requires that you be able to leak at least 9 bits at a time: 8 bits to indicate the key position and 1 for that key bit.  The position bits would be randomly generated.

Another approach would be to communicate the position differently: instead of using an RNG to select the position and include that in the leaked data, you could use data from the ciphertext if your threat model includes the attacker seeing that.  You could use the first $p$ bits of the ciphertext to choose/signal which key bits we are leaking, where $p = log_2(k/m)$.

In both cases, the solution to how long it takes to leak all $k$ bits of the key is given by the Coupon Collector's Problem, which is $O(n log n)$.  In the second example, this should come out to $O(k/m log(k/m))$.  Of course you don't have to wait to collect all of the sections.  Especially with a low bandwidth channel it would make sense to start brute-forcing as soon as feasible.


What is a branch number in the PAEQ algorithm? I'm reading an article about authenticated encryption algorithm - PAEQ.

It uses a permutation function AESQ, which has transormations from AES. And there is written about MegaSBoxes, which contain 4 rounds of AES transformation. So, there are 1 active MegaSBox in 4 rounds and 5 active MegaSBox in 8 rounds (because of branch number - 5).

So, the question is what is a branch number and why there are 5 MegaSBoxes, not 2?

More info in this paper (section 3.2.3, after lemma 3).

In AES, the MixColumns transform as a branch number of 5, this is because a change to a single byte input causes 4 of the output bytes to change. Like branches of a tree, 1+4=5. This is because MixColumns uses an MDS matrix for multiplications against the input.

AESQ operates on entire 128-bit blocks, which are further broken down into AES round operations. 2 AES round operations create full diffusion of the 128-bit block, so a single AESQ round consists of 2 AES rounds, in 4 parallel paths, followed by a shuffle operation so that 4 bytes from every AES round group go to a different group for the next round. What I am callling an AESQ round here is the output of a shuffle to the next shuffled output, I believe they call this 2 rounds in the paper.

Because the 2 AES rounds offer full diffusion, the branching of AESQ is a change 1 AES input block resulting in a change to 4 bytes of each AES output block. I color coded the blocks to show the distribution of modified bytes due to a change in any input byte over a single AESQ round (built from 8 AES rounds).

Therefore, just like in AES, we need 2 AESQ rounds for full diffusion of a single bit change to the the 512-input. This involves 16 AES rounds and 2 shuffle operations. This is considered MegaMixColumns plus MegaSubBytes, with a branch number of 5. This is called 4 rounds in the paper.