Why does gcd(m,N) have to be 1 in RSA? In the RSA algorithm, if an attacker wants to get $d$, the attacker does this simply by encrypting random messages $m < N$.

If the attacker ﬁnds a message $m_1$ that the attacker can not encrypt since $\gcd(N ,m_1) \neq 1$, does this help the attacker in any way in any way?

I don't know why the $\gcd(m,N)$ has to be $1$. What happens if $\gcd(m,N) \neq 1$?

What happens if $\gcd(m,N) \neq 1$?

Actually, RSA works just fine; we have $((m^e)^d) \equiv m \pmod N$ in all cases, includes ones which $m$ and $N$ are not relatively prime.

What is an issue is if someone notices that $\gcd(m, N) \neq 1$.  If that is the case (and $m \ne 0$), then $\gcd(m, N)$ is a nontrivial factor of $N$, that is, either $p$ and $q$, and so that rather leaks the factorization of $N$.

Now, the probability of guessing $m$ that is not relatively prime to $N$ is astronomically small for the sizes of $N$ we use in practice, and so we don't worry about it.


challenges in quantum key distribution Quantum key distribution (QKD) promises unconditional security in data communication and is currently being deployed in commercial applications. Nonetheless, before QKD can be widely adopted, it faces a number of important challenges such as secret key rate, distance, size, cost, and practical security. nature.com article

  What are challenges in quantum key distribution ?

The article cited in the question (Eleni Diamanti, Hoi-Kwong Lo, Bing Qi, and Zhiliang Yuan: Practical challenges in quantum key distribution, in npj Quantum Information 2016, a Nature Partner Journal) gives a list of challenges facing Quantum Key Distribution, but forgets several important ones:

Not fulfilling the market demand for simplified key distribution. When Man in the Middle attack is a threat, QKD only extends a pre-existing initial secret key, which still must be distributed by trusted means such a courier. QKD is thus not easier to use than classical key distribution and offers no clear advantage compared to distribution of a USB key with a One Time Pad by that same courier.
QKD's claimed security covers keys distribution, not data transmission at commercial speed. The later still relies on classical symmetric cryptography (lacking mathematical proof), with QKD protecting only the low trickle of data that constitutes the keys for classical crypto. Therefore, use of QKD does not unconditionally prevent interception of the bulk data for later decryption by hypothetical improved attacks.
Incompatibility with deployed infrastructure: existing active electronics at optical fiber ends, including in repeaters (often underwater), are incompatible with QKD. Some of the existing fibers might be re-purposable, but at extremely low QKD rate, which worsens the above issue.
QKD does not scale to a global network. What's currently experimented is end-to-end only, or (marginally) with special optical routers that further reduce the usable distance. Blueprints for large networks require trust in the routers, when classical crypto does not.
Complexity of the indispensable information-theoretic (mathematically provable) paraphernalia necessary for QKD to work both reliably and safely. A most cited method for that appeared only 9 years after the birth of QKD, and despite its complexity leaves it to the practitioner to deal with power outages other than by using another courier for a fresh initial secret key.
Lack of security certification: there was no security-certified Quantum Key Distribution system last time I checked, nor any planned reference framework for such certification. Market and laws demand certification (rightly so: several QKD systems have been hacked).


Set an initialization vector to HMAC/SHA different from default in Java I know that for HMAC/SHA there are default IV values. But if I want to supply my own IV (different from a default), there doesn't seem to be a way to implement it in — for example — Java. (At least, so far I hadn't found a solution in javax/bouncy castle. Looks like MessageDigest class isn't providing us with such methods).

Why are default values for IV (HMAC/SHA) used? What is the reason not expose them to a user?

Why are default values for IV (HMAC/SHA) used? What is the reason not expose them to a user?

Actually, if you go through the theoretical basis of HMAC as explored in this paper, they start with NMAC, which is essentially what you are asking for.  That is, it's a nested hash construction (just like HMAC), however instead of prepending the hash with keying material, they set the IV for both levels to keying data.

They then go on to HMAC, and show that HMAC is as secure as NMAC; the prepended keying material (which occupies precisely one hash block) sets the hash internal state to a value which is unpredictable to someone who doesn't know the key.  HMAC also has the advantage that it can be implemented using a standard hash implementation.

Hence, the answer is "you don't need to set the HMAC IV values; the HMAC keys do that for you"


How do I tack on "additional data" to libsodium's public-key authenticated encryption? I note that libsodium provides AEAD when using symmetric cryptography.

And yet, under section 8 (Public-key cryptography) there are no public-key methods described which allow for additional data (AD) to be included.

Keeping in mind cryptographic best practices, is there an elegant way to essentially add the feature of additional data to a public key cryptographic AE method like crypto_aead_chacha20poly1305_encrypt?  That is, suppose that the libsodium building blocks remain as they are.  How do I add additional information sent in the clear that becomes part of the authenticated message?

And I'm curious if the absence of such a method now is for any particular reason.

Internally, libsodium public key encryption uses the same primitives as the (nonAEAD) secret key authenticated encryption, namely XSalsa20 and Poly1305. NaCl, which libsodium is based on, does not have an AEAD interface at all. Instead, libsodium added it from a TLS draft. There is no similar reference for public key AEAD use of these primitives, since in TLS they are expected to be used with the negotiated secret key. That is my guess as to the main reason it does not exist in libsodium.

As an aside, the use case for public key AEAD seems a bit thin overall. Usually the additional data in AEAD is used for protocol information that is not secret but must be tied to a particular message. E.g. in TLS it includes the sequence number and compression details. However, if you have a protocol where multiple messages are sent, you do not really want to use public key encryption for each message, but rather a session key and symmetric encryption.

There are many ways you could go about constructing your own:

Simplest would be to just include the additional data in the message to be encrypted. That is wasteful if you also need to send it in the clear, of course, and you can only verify it after decryption. You can avoid duplicating long data by including only a hash of the data in the message.
Alternatively, you could sign the encrypted message + additional data. That requires a signing key-pair, the public key of which is known to the receiver. It also adds quite a bit of overhead. However, it does allow verification of the additional data before decryption.
Finally, you could negotiate a symmetric key and use the AEAD cipher already in libsodium. Simply generating a random symmetric key and encrypting it with public key authenticated encryption would work, but there are more complex ideas too, depending on what kind of security you need.

Note: the currently included AEAD cipher based on the draft only uses an eight byte nonce, which is too short to be safely generated randomly. A later version of libsodium will include the updated version with a longer nonce.


Are there any known collisions for the SHA (1 & 2) family of hash functions? Are there any known collisions for the hash functions SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512?

By that, I mean are there known values of $a$ and $b$ where $F(a) = F(b)$ and $a ≠ b$?

This answer is now out of date as on Feb 23 2017, a collision for SHA-1 was found. See What is the new attack on SHA-1 “SHAttered” and how does it work?

In short, no.

So, what is the current state of cryptanalysis with SHA-1 (for reference only as this question relates to SHA-2) and SHA-2? Bruce Schneier has declared SHA-1 broken. That is because researchers found a way to break full SHA-1 in $2^{69}$ operations. Much less than the $2^{80}$ operations it should take to find a collision due to the birthday paradox.

As far as we know, the best available collision attacks on full round SHA-2 hash functions is still brute force $2^{n/2}$ (where $n$ is the bit length of the output).


PRGs exist if computationally secret encryption schemes exist I have understood the "equivalences" between PRP, PRF and PRG. Now, I just read an statement in my lecture notes that made me think that there has to be a conversion between PRG and computationally secret encryption scheme:

  So, our definition of PRG is sufficient for the existence of a
  computationally secret encryption scheme. Later, we will see that this
  is definition is the right one as PRGs exist if computationally
  secret encryption schemes exist.

This means I can build a PRG from a computationally secret encryption scheme. What is the common and easy way to see this?

I don't know of any direct way of doing this. In particular, in contrast to the way most encryption schemes work in practice, in theory there is no requirement that the output of an encryption scheme look random at all. The only way that I know to do this is to prove that computationally secret encryption implies one-way functions (not hard to show, but not completely trivial, since it is only true when the amount being encrypted is larger than the key size). Then, using HILL, one can construct a PRG from any one-way function.


Is the 1st Encrypted Block Less Secure Than Subsequent Ones? It's my understanding that Electronic Code Book (ECB) produces similar cypher text for similar plaintext inputs which is not a good thing.  To get around that, Cypher Block Chaining (CBC) can be used to increase diffusion within the encrypted message.  For example an algorithm could take the previous block's cypher text and XOR that with next block's plaintext.  My question is, doesn't that make the beginning of a message easier to decrypt?  In my mind it seems like the 1st block of an encrypted message has a closer relationship to the original message (less mathematical permutations involved) than subsequently encrypted blocks?

In the first block, the IV provides the "randomness", and in subsequent blocks you just use the previous block of ciphertext instead. Based on the assumption, that the cipher is not weak and behaves like a pseudorandom permutation, this is basically the same: You XOR something unpredictable on the plaintext, and then encrypt.

As long as the IV is chosen randomly (and therefore, it should never be the same), there is no weak beginning. If you disregard the randomness and always start with the same value for a new message, then yes, the first block can be considered weaker. Because then you can distinguish, if two messages have the same beginning.


security for PRF when key is changed often Here's the situation. Suppose I have a secure PRF $F$ and use $F$ in the following way:

for equal size message $m_i$ in $\{m_j\}^{q}_{j=1}$( $q=poly(n)$, $n$ is security parameter ), randomly select $k_i \xleftarrow{\$}K$ and compute $c_i=F(k_i, m_i)$, where $K$ is key space. All previous computation results $\{(k_j, m_j, c_j)\}^{i-1}_{j=1}$ are revealed to adversary $A$ when using ($k_i$, $m_i$) to evaluate $F$. The main point is that the key is changed and some previous keys revealed, which is different to traditional pseudo-randomness definition of $PRF$. My security goal is adversary $A$ cannot distinguish $c_i$ from a random string $r_i$ using any $PPT$ distinguisher $D$. Intuitively, I think $F$ is secure in this setting. Is there any formal security model for this situation? and under what situation is it secure or insecure?

Yes, this is secure since the keys are chosen randomly. Remember that even in the "traditional" PRF game, the adversary can generate keys at random, so the output of F on past keys does not help him (since he can generate such outputs anyway).


RSA code giving result after more than 10 minutes I am trying to implement RSA algorithm. I got a code in python. When I run it, it takes more than 10
minutes even when the primes are within 100 and message size is 8 decimal digits. Plese suggest  what may be the problem in the code.
# Write Python3 code here
from decimal import Decimal

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

p = int(input('Enter the value of p = '))
q = int(input('Enter the value of q = '))
no = int(input('Enter the value of text = '))
n = p * q
t = (p - 1) * (q - 1)

for e in range(2, t):
    if gcd(e, t) == 1:
        break

for i in range(1, 10):
    x = 1 + i * t
    if x % e == 0:
        d = int(x / e)
        break
print('pvt key= ', d)

ctt = Decimal(0)
ctt = pow(no, e)
ct = ctt % n

dtt = Decimal(0)
dtt = pow(ct, d)
dt = dtt % n

print('n = ' + str(n) + ' e = ' + str(e) + ' t = ' + str(t) + ' d = ' + str(d) + ' cipher text = ' + str(
    ct) + ' decrypted text = ' + str(dt))

What we've got here is a so-called naive implementation, which doesn't consider time complexity of power-then-modulo operations involving large integers. I'd recommend you to read up on square and multiply, exponentiation by squaring, binary exponentiation, for a bit of context. Typical naive implementations have O(2m) complexity, while optimised versions could achieve only O(m).
If you replace the commented-out code with the uncommented, you'll get significant execution speed improvements:
# ctt = pow(no, e)
# ct = ctt % n
ct = pow(no, e, n)
...
# dtt = pow(ct, d)
# dt = dtt % n
dt = pow(ct, d, n)

See Python built-in function docs for more details of what I've done.
Please note I did not verify reminder of your algorithm.


Is there a way to compare the 923 bit pairing based key with RSA or AES, etc I've see many articles, most of them basically the same, praising Fujitsu for cracking what is referred to as a 923 bit pairing based encryption.  I understand that in comparing RSA to AES you've got something like a power of 10 for the key lengths to be equally strong.  From what I read it seems that this pairing based algorithm is a public key algorithm but somehow involving 3 keys.  I don't know much about the various algorithms but I have read that in the public key space eliptic curve algorithms can get away with much smaller keys than RSA.  I've seem some articles that rate the complexity of various algorithms based on key length, but I don't know nearly enough to understand the papers on this.  Is this new record similar to breaking something encrypted with a 923 bit key using RSA?  I've seen articles that I believe are badly overstating this by saying things like "if they can break a 923 bit algorithm, how secure is the standard 256 bits?"  I assume that's comparing apples and oranges, but I don't know nearly enough to really know.  Does anyone know how to compare these things?

There is nothing really new about this research. It is just a fast implementation of a construction known since 1994.

Source:

http://superconductor.voltage.com/2012/06/understanding-the-recent-fujitsu-discrete-log-calculation.html


identifying presence of encryption of zero in additive homomorphic encryption Lets say the server has corpus of ciphertext contains $enc(a),enc(b),enc(c), \dotsc enc(x)$. The encryption function is an additive homomorphic scheme (like Paillier). The server knows only the public key. The client holds both public and private keys.

Is there a way for client to identify if there is an encryption of $0$ in the corpus? i.e. is any of $a,b,c \dotsc x$ is a $0$. A trivial solution is for the client to iteratively retrieve each ciphertext and decrypt it to see if it is $0$. Can we do any better ? i.e. without iteratively retrieving each element or downloading the entire corpus of ciphertext ?

If it were a multiplicative homomorphic scheme, the server could multiply all the encryptions and give the result i.e. $enc(res) = enc(a)\times enc(b) \times \dotsc enc(x)$ , the client could just  decrypt the result to see if the result is $0$ . i.e. $dec(enc(res)) = 0$ if at least one of $a,b,...,x = 0$.

Are there any such tricks possible in additive homomorphic scheme ?

I do not think what you want is possible with any simple solution - by simple, I mean computationally less expensive than downloading and decrypting all the ciphertexts. Basically, multiplicative homomorphism allows you to check some algebraic "OR": if there is a single 0, then the product of all the plaintexts will be 0.

Additive homomorphism, on the other hand, only allow you to check some algebraic "AND", id est, to check whether all the encrypted values are 0 or not (this is done simply by computing some linear combination of all the ciphertexts with uniformly random coefficients, and decrypting the result ony; if it's zero, then with overwhelming probability, all the ciphertexts encrypt 0). What you're looking for is an algebraic "OR" on additive encryption, which typically require a linear number of ciphertexts (so basically, it will not be really better than downloading and decrypting everything).

(By the way, you mentioned that with a multiplicative scheme, "the server could multiply all the encryptions and give the result". You should note that here, you assume a multiplicative scheme which can encrypt the zero value. The only such scheme I know off (appart from fully homomorphic encryption) is the one I constructed in a recent paper)

EDIT: now, it depends on your setting. If you assume each plaintext $m$ was encrypted as $E(m), E(R\times b)$ where $R$ is a random coin, and $b$ is a bit which is 0 if $m$ is non zero, and 1 else, then you have a solution: the server simply computes and sends a random linear combination of the E(R^b), and the client decrypt the single resulting ciphertext. If it encrypts a random value, there was a zero; else, there was no zero. However, this extended encryption scheme $E(m), E(R\times b)$ is not additively homomorphic anymore.


Does Format Preserving Encryption have significant advantages over a randomly generated lookup table? I have a need to anonymise phone numbers so that I can carry out testing and analysis work on telecoms data sets and comply with GDPR.  I typically receive a batch of a few hundred thousand events containing phone numbers, and need to anonymise all the phone numbers in that batch under the following conditions:

A definable prefix of the number should remain the same - I should only transform the right-most n digits.  n will typically be between 2 and 6
I should always transform the digits in the same way - abcd should always be mapped to efgh
The transformation should be one-to-one - efgh should be that output for only one input
I should only output digits

If I then receive a further batch of events condition 2 is removed - I can use a new transformation for a new batch.

I've considered two approaches to this requirement:

Randomly create a lookup table mapping each n digit string to another n digit string - I will do this for all n digit strings as a one-time exercise prior to encrypting a batch, and generate a new lookup table for a new batch
Use one of the Format Preserving Encryption algorithms - e.g. Format-preserving, Feistel-based encryption (FFX) as implemented in the PyFFX or libffx libraries, or FE1 in the botan library

In some cases I may need to reconstruct the original phone numbers in the future in which case I will store the encryption key or lookup table in some secure fashion.  In some cases I know I will not need to reconstruct them in which case I will discard the key directly after encryption.

Is there any advantage to using approach 2 over approach 1?  I can see the following possibilities:

Using a random number generator in 1 may be slightly less robust than using FPE
The encryption key for FPE can be substantially smaller than the mapping table in point 1 if there is a need to retain it
A publicly available FPE implementation may contain fewer vulnerabilities than a home-grown random lookup implementation

Are there any other considerations I should have in mind?

any other considerations?

Yes.

In many common use cases the mapping table needs to be retained. That map changes each time a number is added; that's a backup / continuity of service headache.
The map is security-sensitive: it contains all the clear phone numbers, and information which (combined with other information) allows getting back to users.
The map can be large (at least about twice as large as the numbers themselves); that's a (perhaps minor) storage issue.
When the table grows large, there will be collisions in the mapping table, that's a special case which must be handled, and tested.
Timing attack on the map search code has the potential to leak information (that's also true of some FPE implementations, but proper FPE is less likely to leak something meaningful; in particular FPE won't leak if the creation of the entry was recent, which can happen with a map).
FPE's performance is predictable, when some map implementation have no specified worst-case performance.
FPE allows efficient implementation of direct and reverse map, when not all map implementations allow that.

Bottom line: encryption is desirable there. FPE is useful only if size or interoperability is a concern.


Why is "multiplying" $g^x$ and $g^y$ not possible? The computational Diffie-Hellman problem states that for a cyclic group $G$ of order $p$ and a generator $g$, it is hard to find the value $g^{xy}$ given only $g^x$ and $g^y$ (but easy if either $x$ or $y$ is known); the easiest way being to compute the discrete logarithm of either $g^x$ or $g^y$ and then calculating $(g^x)^y$ = $g^{xy}$.

This is probably just a big misunderstanding of group theory and/or modular operations on my part, but why is it not possible to just calculate the product $g^x \cdot g^y$ as a "regular" group operation (multiplication modulo $p$)? Is this also computationally difficult, or would the result be wrong?

$g^x \cdot g^y \;\;\; = \;\;\; (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x$ of them] $\ldots \cdot g\cdot g\cdot g) \: \cdot \: (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.03 in}y$ of them] $\ldots \cdot g\cdot g\cdot g)$

$= \;\;\; g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x\hspace{-0.05 in}+\hspace{-0.05 in}y$ of them] $\ldots \cdot g\cdot g\cdot g \;\;\; = \;\;\; g^{\hspace{.02 in}x+y}$


What is the maths behind Bitcoin's BIP32? I've read about BIP32 key derivation functions.
I'm trying to understand how, given a secp256k1 key pair, that "child" public keys may be generated from just the public key, and the corresponding child private keys can be generated from the private key.
It seems to me (and I'm probably mistaken) that the HMAC-SHA512 and concatenation is not important, and that there is a simpler way of making child keys from just the appropriate type of parent key.
Is BIP32 as simple as it can be for the case of non-hardened child keys?
Or are there functions which just depend on a child-number, i, and the parent key of the appropriate type, to generate child keys?

It seems to me (and I'm probably mistaken) that the HMAC-SHA512 and concatenation is not important, and that there is a simpler way of making child keys from just the appropriate type of parent key.

Yes you are mistaken - the trick definitely lies in the HMAC (or similar) one way function that protects the parent keys. This is also where the "chain code" comes at play, since it protects the parent keys with the HMAC (or similar).

Or are there functions which just depend on a child-number, i, and the parent key of the appropriate type, to generate child keys?

There are but they are not considered safe - imagine putting sha256(parentPivateKey || i) to the public where i is known and the length of your parentPivateKey is known, that could be attacked in a lot of ways.
PS: Instead of "child-number" you meant probably a child identifier


Design criteria for AES I hope somebody can help me understand the design criterias for AES. Therefore, I would be really thankful if somebody could explain "non-linearity" in this context.

A criteria for the s-box in AES is non-linearity, where the maximum input-output correlation amplitude must be as small as possible. Why is a look-up table non-linear?

The maximum difference propagation probability must be as small as possible. This means to get closer to a uniform distribution?

MixColumns offers linearity - because it is a function which transforms values in a deterministic way?

Generally speaking, a function $f()$ is linear if $f(x+y) = f(x)+f(y)$ and $f(ax) = af(x)$.

The AES S-Box, which is a specific, predefined (key-independent) lookup table, doesn't satisfy these properties. You can do a quick verfication by picking two values $x,y \in GF(2^8)$ and verifying that $S(x+y) \neq S(x)+S(y)$ (where the addition operation is done in the field $GF(2^8)$, and is thus essentially the XOR operation). But the S-Box not being fully linear is not enough. It's very bad if it's just somewhat linear, in the following sense. There are various ways to define it. One of them is the Linear Property of the S-box, $LP(S) = \max_{a,b} (Pr_x(a(S(x)) == b(x)) - \frac{1}{2})^2$ which has to be low. It measures the existence of two linear functionals $a(),b()$ which tend to agree (correlate) or disagree on the input and output of the S-box.
If you were to calculate $LP(S)$ you would find that it is considerably lower than for a random lookup table ("the maximum input-output correlation amplitude must be as small as possible").

As for difference propagation, a similar property exists $DP(S) = \max_{a,b\neq0} (Pr_x(S(x)\oplus a == S(x \oplus b)))$, which measures the existence of two  differences (deltas) $a,b \neq 0$ which propagate through the S-box. Again this has to be minimal, and if you were to calculate $DP(S)$ you would find it is indeed lower than for a random lookup table.

MixColumns offers linearity because it is defined as a linear mathematical operation, not because it is deterministic (the S-Box is also deterministic, but not linear...).


Does encrypting with MGF1/SHA-512/1024-bit seed equal to a 1024-bit key block cipher? Suppose:

Alice uses SHA-512 with MGF1(as in PKCS#1 V2) and a 1024-bit random seed to generate a mask, XORs the mask with a message(M), gets a cipher text (CT), and sends the CT to her old friend Bob. Of course, curious Eve is listening...
Alice and Bob exchange the seed in a secure way (while Eve sleeps and does not know about it); they do not care about the speed of this algorithm.

Questions:

Is CT as secure as being encryted by a 1024-bit block cipher?
Why?

This is not a block cipher.  It is a stream cipher: you are using SHA-512 to generate a one-time pad to encrypt the message.

The security—meaning the attacker's expected cost to break it—is at most $2^{512}/t$ if there are $t$ users of the system.

How the best possible security of this system relates to the best possible security of a 1024-bit block cipher depends on the block cipher.  The idealization of this system—a uniform random 1024-bit pad—has the same security as an ideal 1024-bit block cipher.  But a practical block cipher has a key, and it is typically smaller than $\log_2 2^{1024}! \approx 1024 \cdot 2^{1024}$ bits long.

In practical terms, you should focus more on everything else about your application's security.  For example, you didn't mention authentication, which suggests I can possibly destroy confidentiality by forging messages like EFAIL.  There is no point in pushing anything beyond a 256-bit security level, if there was any point going beyond a 128-bit security level in the first place as you get with AES-256-GCM or crypto_secretbox_xsalsa20poly1305.


Proving property of Modified Rabin Signature I'm trying to prove one of the properties of the “Modified Rabin Signature Scheme”:

  If $\gcd(x, n) = 1$, then $x^{\frac{(p−1)(q−1)}{2}} \equiv 1 \pmod n$

This is what I’ve got so far…

Proof

Let $p$ and $q$ be primes such that $p \equiv 3 \pmod 4$ and $q \equiv 3 \pmod 4$

$$p = 4 t_1 + 3 , \, q = 4 t_2 + 3 \,\,\,\,\,\,\,\,\,\,-(I)$$

Then ($s$ = odd)

$$\frac{\phi(n)}{2} = 2 s\\$$

From the “Euler theorem” we know that

$$x^{\phi(n)} \equiv 1 \pmod n$$

Taking square root both sides

$$x^{\frac{\phi(n)}{2}} \equiv \sqrt{1} \pmod n$$

assuming

$$x^{\frac{\phi(n)}{2}} \equiv -1  \pmod n \,  \text{ i.e. } \, x^{2s} \equiv -1  \pmod n\\
\implies x^{2s} -1 = nk$$

subsituting values of $p, q$ from $(I)$ we get

$$x^{\text{even}} = (\text{odd})k + 1$$

Now, I want to show that

$$x^{\text{even}} \neq (\text{odd})k + 1$$

… but I'm kind of stuck here.

Can anybody help me complete this proof of one of the properties of Modified Rabin Signature?

In short words: when you compute things modulo $n = pq$, you are really computing things simultaneously modulo $p$ and modulo $q$. That's the gist of the Chinese Remainder Theorem. So to prove that $a = b \pmod n$, you just have to prove that $a = b \pmod p$ and $a = b \pmod q$.

Modulo $p$, for any $x$ that is not a multiple of $p$, $x^{p-1} = 1 \pmod p$ (this is Fermat's little theorem). Therefore, $x^{k(p-1)} = 1^k = 1 \pmod p$ for any integer $k$. Now, $p$ and $q$ are big primes, so they are odd. It follows that $q-1$ is even, therefore $(q-1)/2$ is an integer. So $x^{(p-1)(q-1)/2} = 1 \pmod p$. The same holds modulo $q$ for the same reason. By the CRT, you get the result modulo $n$.

Note that while Rabin's cryptosystem is defined with $p = 3 \pmod 4$ and $q = 3 \pmod 4$, these properties are not necessary to demonstrate that $x^{(p-1)(q-1)/2} = 1 \pmod n$. It also works when $p = 1 \pmod 4$ or $q = 1 \pmod 4$. The only requirement is that $x$ is relatively prime to both $p$ and $q$, which is exactly what $\mathrm{gcd}(x,n) = 1$ means.


Arguing security of an encryption scheme I have an encryption scheme which masks the message m by multiplying it with a secret random group element i.e $g^r \cdot m$. I should allow decryption and get $g^r$ if I have a valid secret key; otherewise I will only reveal $(g^L)^r$, where $L \in Z_n$ and $g^L$ is known to the adversary.

Is this secure? If yes, how can I argue about the security.

If the adversary knows $L$, then he can find $L^{-1}$, the multiplicative inverse of $L$ modulo $q$ where $q$ is the order of $g$. Then he can compute $g^r =((g^L)^r)^{L^{-1}}$. Once he find $g^r$, he can compute $m$ by eliminating $g^r$ from $m\cdot g^r$.

If the adversary knows only $g^L$, then it is ok. This case is like El Gamal. Let $h=g^L$, what you reveal is $(h^r,m\cdot g^r)$. Your private key is $L^{-1}$.


How secure are public hashed passwords (with a salt)? I'm working on a blockchain-based distributed application which stores Client information. I'm thinking of alternate ways to authenticate Clients on the network. One idea I got was to associate a Username and Password with the Client data structure -- where Password is a Hash(salt+password) where salt is securely stored only with us (the blockchain operator).

The clear security concern is that all participating members in the network can now view the hashed version of these passwords -- so how secure is this? Are there any other approaches I should be thinking about?

The main problem will be the password policy and users. If you let the users to choose any password, then they will tend to use 1234 as a password. A malicious user in your system can easily bruteforce all widely used insecure passwords. If you have a good policy, the only way is brute-forcing since we cannot reverse the hash and the salt prevents rainbow tables. For a general guideline for passwords, see NIST Digital Identity Guidelines 800-63B.

While considering the attack risks, we already assume that an attacker access the database of the users and we design our password systems as a last defense against the attacker. According to this, we design our system not by security by obscurity. So, you already in this stage.

Actually, we don't use a simple hash technique to store passwords. For example, iteration as in PBKDF2 can decrease the time of the attacker like 10000 times. Also, you need to protect against massive parallelization as in GPU usage of hashcat.

You should use PBKDF2, Bcrypt, or better argon2  which is the winner of the password hashing competition.

Also, for general advice see the How to securely hash passwords? from Information Security.


BN-Curves for 256-bit symmetric security I'm just studying the purpose of BN-Curves and I am interested in a setting for a 256-Bit security.

So could you tell or link me to any information about this?

are BN-Curves efficient for this security issue?
which embedding degree is recommended?
what about ARM-Cortex M0-4 µC?

I'm searching for days now to get any information about this. But there is nothing that point out the usage of BN-Curves on that security-level.

A BN-curve over a 256-bit prime field $\mathbb{F}_p$ has, being an elliptic curve, a 256-bit group attached to it, say of order $N$. As the best known attacks take $\approx\sqrt{N}$ times, this gives us 128-bits security against discrete logarithm attacks.

The curves also have embedding degree 12. That means we can use a pairing to map a discrete logarithm problem to $\mathbb{F}_{p^{12}}$. Given that $p\approx 2^{256}$, we know that $p^{12}\approx 2^{3072}$. Hence $\mathbb{F}_{p^{12}}$ is a 3072-bit finite field, and solving a DLP there should (see warning below) take about $2^{128}$ effort. So mapping the DLP to a finite field does not help an attacker, which is great.

If we move to 256-bit security, we will need a 512-bit group on the curve. Thus, we need to choose $p\approx 2^{512}$. The embedding degree remains 12, and we can still use the same pairing to map the DLP to $\mathbb{F}_{p^{12}}$. In this case $p^{12}\approx 2^{6144}$. According to the slides you refer to, this only gives a $<192$-bit security level. Thus $p\approx 2^{512}$ is too small for a 256-bit security level.

To obtain a 256-bit security level in the finite field, we actually need $p^{12}\approx 2^{15424}$ (according to the slides you refer to). Thus, $p\approx 1285$. This is very large, and will make computation very slow. Therefore BN-curves are great at 128-bit security level, as they make an optimal trade-off there, but do worse as the security level increases.

Warning: new attacks show that finite fields of size $2^{3072}$ do not actually provide a $128$-bit security level any more, although they did at the time of the proposal of BN-curves. So currently they are on shaky territory.


Differences between hashed text and encrypted text I was wondering if it's possible to tell if the text is hashed or encrypted. For example, if someone has given you a a chain of random characters. Would you be able to tell if it's encrypted? Which you could be able to retrieve the original text by having the private key. Or it's hashed which there is no way to reverse it.

Hash is very short, e.g. 8 bytes, 32 bytes, 64 bytes, no matter how long the original text is. Where as encrypted text is actually unlimited.

If the encrypted text is relatively long, you can calculate some statistical values. Where as hash is short and is no sufficient for any statistics. E.g. how will you speak about some frequency if you only have 32 bytes?

Hash is a one way transformation. In a normal case there is no way to restore the original text. If you had a text of 1000000 bytes and hash of 64 bytes, it is clear that  there is no way to obtain 1000000 bytes from 64 bytes.

To randomness: It is one of the goals of good encryption to make the encrypted message indistinguishable from a random sequence of bytes.


Why does a perfect secrecy can be achieved when decryption correctness is not totally required? By Shanon theorem, a perfect secrecy encryption scheme must use a key space of equal size as the message space.

But when the correctness requirement is weakened such that $Pr[Dec_k(Enc_k(m))=m]=1/2$ we know that the key space may be smaller than the message space.

Generally, what is the lower bound of the key space when the scheme correctness requirement is $Pr[Dec_k(Enc_k(m))=m] >= 2^{-t}$? (and why?)

I'll further explain the comment of @CodesInChaos and then give a simple example:

Explanation

When the correctness requirement is weakened the encryption scheme can omit part of the message $m$ (of length $|m|$) to be encrypted and just "loose" it in a way that the cipher (the output of the Encrypt method) is totally independent of that part. Thus the message that effectively is encrypted is not $m$ but rather just part of it of length $|\ell|<|m|$ and thus the key doesn't have to be of length at least $|m|$ but rather be of length at least $|\ell|$.

Example

The most basic example is an encryption using the One-Time-Pad Scheme, in a model where the correctness requirement from the scheme is weakened to: $Pr[Dec_k(Enc_k(m))=m]=\frac{1}{2}$. Take a message $m$ of length $|m|$ and a random key $k\in\{0,1\}^{|m|-1}$; the encryption method take the first $|m|-1$ bits of $m$, call it $m'$ and output the cipher $c=m'\oplus k$. Then, given $c$ and $k$, we can decipher (or decrypt) the cipher correctly with probability of exactly $\frac{1}{2}$ by computing $m'=c\oplus k$ and then randomly guessing the $|m|^{th}$ bit of $m$; since we get the correct bit with probability $\frac{1}{2}$ we satisfy the correctness requirement.

About the bound

We can say the when the correctness requirement is $Pr[Dec_k(Enc_k(m))=m]\geq\frac{1}{2^t}$ the key space must be of length no less then $|m|-t$. If the key in the example above is of length $|m|-t$ then the decryption algorithm can guess the omitted $t$ bits of the message with probability $\frac{1}{2^t}$ as required.


Anonymous Multi-Receiver Identity-Based Authenticated Encryption with CCA Security? OK, I am confused. Does it mean that that the various anonymous multi-receiver IBE implementations actually do not have single public key per Identity, as as is the in the original IBE implementation?

Example paper: Anonymous Multi-Receiver Identity-Based Authenticated Encryption with CCA Security (PDF) by Fan et al.

As always there is only one system public key (also called "public parameters" or simply "parameters"). In IBE, the identifiers of users are publicly known which can be used in conjunction with the public key to compute temporary group elements.

If you look into the scheme you're linked to, you should see that there is only one set of "params" which represent the public key with all of its configurations.

Of course, the user identifier must be kept authentic in the same way that RSA public keys of all of the recipient users must be kept authentic. If an attacker makes you believe to encrypt some data to their own identifier, then you have lost, but that doesn't have anything to do with a scheme and more of an issue with fully designed systems.


Counter Mode: static IV but different keys Given we are using AES counter mode, suppose we randomly generate several keys, all of them are using same IV (say, zeros). Does this lead to any security issue?

I know that in CTR mode, same key-iv pairs would lead to two-time-pad. But the above construction will not have the same keys.

In application:

Let's say Alice and Bob communicate through TCP. They agreed on using AES-CTR. For each connection, they randomly generate a key but always use a static IV.

(BTW, all encrypted data will be HMACed)

If you assume AES is a pseudo-random permutation(which is pretty much necessary for it to be secure), then yes. However, it's way easier to just use a random IV/noce and keep the keys. Your new  key must be distributed to both parties secretly, the IV/nonce can be public, so you can just send it (HMACed of course) in the clear. You obviously can't do this with a key and you may introduce problems depending on how you try to send it.

Typically the IV in CTR mode is called a nonce (shot for number used once). The reason for this is that it, unlike most uses of an IV, need not be random, just only used once. Since we assume the block cipher is a pseudo-random function, we just need to ensure it doesn't get the same value feed into it twice and it will giving us random looking output. Strictly speaking, we just care that the same (Nonce,counter) pair is not used twice, but since we have no control over the  counter value, we make sure the nonce is unique..

Assuming that the block cipher is a pseudo random permutation also tells us we only care if the same (key,nonce, counter) is used. Effectively, the key is just selecting at random the permutation we use from the set of all permutations of a given length( the cipher's block size). For each permutation, the output on (nonce,counter) is unique, so we don't care about repeats under different keys.


How is a message digest decrypted? Trying to get my head around digital signatures and hit a slight block. The book I am using gives the following information

Device A hashes a message to create a message digest
Device A encrypts the digest with device A's private key to create a signature
Device A adds the signature to the message Device A encrypts the whole message (including the signature) using device B's public key
Device A sends the message to device B

Device B decrypts the message with device B's private key
Device B splits the signature off of the message
Device B decrypts the signature using device A's public key to get the message digest
Device B hashes the message to get a message digest
If the message digest device B created is the same as the one decrpyted, the message has not been tampered with

All fine, but how does device B know what hashing algorithm was used to create the message digest?

First of all signing does not equal encrypting. It only works on some crypto systems and even then it is not the whole picture.

Hash algorithms are used for various reasons. One of them is to reduce the size of the signature since the digest is generally a lot smaller than the message itself.

But the main cryptographic reason behind hash functions is to make it so that a possible attacker cannot force the message he wants to forge a signature for, to have a certain property.

It is a bit technical but for example in the ElGamal cryptosystem if you sign the message itself then it is possible for an attacker to produce a valid signature without knowing the secret key. If however you sign the hash of the message  then this is not possible.


Security limits of password-based encryption A reasonable way to do password-based encryption is:

put the passphrase¹ and nonce in a well-parametrized memory-hard iterated hash function like Argon2, to derive a key 128-bit or larger.
output the nonce, followed by the ciphertext per some strong authenticated encryption; AES-GCM-SIV or ChaCha20+Poly1305 comes to mind.

Legitimate decryption with the password is trivial. The best generic attack enumerates passwords from most to least common, starts to decrypt, obtains the start of the plaintext, tests it per some criteria and moves to the next password until one matches. Assume known plaintext at the start of the file².
The security depends on the good choice of password and the parametrization of the iterated hash. It's very hard to give figures, but assume 32-bit² entropy for password and a few seconds of Argon2 on one's PC. However one counts, the security in bits is far from academically acceptable levels.
Main question: Can we do better, assuming a plaintext of significant size, say $n=2^{20}$ or $2^{30}$ bits? How much better? What's the theoretical limit of the gain we can get from large $n$?
I'm thinking of using an all-or-nothing transform, perhaps approximated by 2 passes of AES-128 in PCBC mode, and two keys derived from the password, because we can at almost no cost. That idea is not new: ref1; ref2. But I still hope for an answer that takes into account memory-hardness.

Here is my work so far, very tentative. One can raise questions: criticize!
Taking the scheme at the start of the question as a reference method, let $t$ be the time (in seconds) spent in password-to-key conversion by Argon, $m$ the memory (in bits) used for that, $c$ the throughput (in bit/s) of the cipher itself, and $\ell$ the message length (in bits). The total time to encipher is thus about $T=t+\ell/c$. We do not want to wait more than that.
There is something to be gained by loading whatever of the plaintext fits in memory, and spending the time $T=t+\min(\ell,m)/c$ on password-to-key transformation while enciphering the plaintext at the same time in an hypothetical iterated-all-or-nothing memory-hard transform, performing the encryption for free; then using the key thus produced for the rest of the plaintext. If we assume there is at least 128-bit of entropy in the part of the plaintext that fits memory, which is a plausible assumption, good: that makes the rest essentially invulnerable until the password is found by crunching all the beginning.
Assuming our iterated-all-or-nothing memory-hard transform is as good at password-stretching as Argon2 is, I tentatively get as gain on "stretched password entropy" (or, more rigorously, for the base-2 log of the multiplicative factor for attacker cost):
$$\log_2\left(1+\frac{\min(\ell,m)}{c\,t}\right)\text{ bit}$$
That's next to nothing when $\min(\ell,m)\ll c\,t$, and otherwise grows with $\ell$ until reaching a maximum at $\ell=m$, then stops growing.
Assuming $t=2^2$ (4 s), $c=2^{32}$ (512 MiB/s), $m=2^{36}$ (8 GiB), we gain ≈2.32 bit. That's much less than a decimal digit in a random passcode (≈3.32 bit), and at best in the order of a character more in a passphrase.
The faster the cipher we replace, the less gain. The more RAM, and until the plaintext does not fit, the more gain.
Unless I err, asymptotically, when we double the RAM and until all the message fits in there, we seem to quadruple rather than double a memory-bound attacker's cost. I'm still scratching my head for CPU-bound.

¹ Rather call it that: it is easy, unobtrusive, and has gone miles to improve security of PGP.
² In practice, a compressibility test will do if there is even mild redundancy in the plaintext.
³ The only power of two in [28-44].

An $O(\log l) $ cost for $l \le m$ seems a little simple given the many components (Argon, AES, hard & soft optimisations and bounded RAM & I/O).
Have you considered an empirical simulation?  You could lash something together in your favourite programming language, set all soft and hard parameters to reasonable levels and just see. So either an iterated approach, or a Monte Carlo simulation. It might at least suggest a real world relationship between all the parameters.
I don't know whether they'd talk to you about scale, but is it worth asking someone who actually does this? Apparently the Inmanis appliance has 'monstrous performance'.
P.S Whilst the application of your theory to a singular very large message seems sound on the face of it, the password wouldn't be recovered from such (knowing the presence of AoNT). Clearly you'd attack the shortest  message which might be "Toodles" covered by the same password. Don't know whether that has any bearing on what you're trying to demonstrate.


Understanding the definition of HGD On the section 4.2, page 10, of the paper Order-Preserving Symmetric Encryption, the authors define two subroutines: the first one is called $HGD$ and the second one is $GetCoins$.

I have doubts about both, but I am mainly interested on the first.

It is said that

  The first, denoted $HGD$, takes inputs $D$, $R$, and $y \in R$ to return $x \in D$ such that for each $x^∗ \in D$ we have $x = x^*$ with probability $P_{HGD}(x−d; |R|, |D|, y−r)$ over the coins of $HGD$, where $d = min(D)−1$ and $r = min(R)−1$.

So, my questions are the following:

1 - What does "over the coins of $HGD$" mean?

2 - Since $D$ is a set, it does not have repeated elements, so, the probability of $x$ being equal to $x^*$ is $\frac{1}{|D|}$, isn't it? Well, I don't understand how can I fix a element $x$ in $D$ such that the probability of any other element being equal to $x$ follows a hyper-geometric...

Any help will be appreciated.

In cryptography it is common to reason about the probability of an event in the probability space of all the random choices made (i.e. the random bits generated) during an algorithm's execution. So, in this description, "over the random coins of HGD" means the probability is computed over the probability space defined by the random bits used during HGD sampling.
You are, I think, confused here by the difference between the uniform and hypergeometric distributions. If the sampling is uniform, the probability of the sample $x$ being equal to any other particular $x^*$ is exactly $\frac{1}{|D|}$. However, the sampling here is actually done according to the hypergeometric distribution, so the probability of the sample $x$ being equal to some $x^* \in D$ is exactly $P_{HGD}(x−d;|R|,|D|,y−r)$.

The wording here is on the formal side, but the intuitive takeaway is that the distribution of the output of the HGD subroutine is hypergeometric. Think of it as a black box that takes in some arguments (and random bits) and spits out a sample from the right distribution.


Encryption of plain text using stream cipher algorithm We know that in stream cipher algorithms plain text and generated key are Xored byte by byte. Generated key depends on how much plain text there is and on that basis key will generate and plain text is encrypted. So my doubt is I am using the latest stream cipher algorithm that is Rabbit and encrypting plain text using the Rabbit stream cipher so in that Rabbit's input key is 128-bit and after all operations output will be a 128-bit key that will Xored with Plain text and give cipher text. As here output is fixed 128-bit so if our data is more than 128-bit then how it will encrypt data? Do we have to do padding with our plain text to make it a multiple of 128-bits?

The stream cipher generates 128 key stream bits per iteration. Usually these bits are buffered internally. When the encryption or decryption (identical operation, encryption = decryption) takes place then the bits are taken out of the buffer and the plaintext at the same location is xorred with it. When the keystream buffer is exhausted the next iteration takes place, making another 16 bytes of key stream available to the user.

Some implementations do wait for the full block to become available. This should however be the exception rather than the rule. The last (possibly incomplete) block just takes as many bits out of the buffer as necessary. The other bits are simply discarded.

Note that this is entirely the same scheme as used by e.g. AES in counter mode. One possible performance enhancement is to enlarge the buffer and generate more 128 bit blocks of key stream in one go. This may have benefits if the generation of larger amounts of keystream is less CPU or CPU-cache intensive.


Are digital signatures secure for signing lots of small messages? I need to sign the numbers from 1 to 1 billion (literally this, it's not an analogy) using a digital signature and then send these numbers in a particular order to someone. The message is not private and the receiver should be able to verify its authenticity without having to reply; it's a one-way public communication channel.

Are there any algorithms that are safe enough for this? How many bits should the key have and how many bits will the signature have?

Yes.  Any good standard digital signature algorithm will be secure in this setting.

Digital signature algorithms are designed to be secure against chosen-message attacks, where the attacker can choose any set of messages and learn the signatures on those messages; the security of the signature scheme means that this doesn't help the attacker at all.  This means that it's safe to sign arbitrary messages; there's nothing dangerous or special about messages that are small numbers.

You should choose the key size based upon the desired security level.  A bare-minimum security level is 80-bit security; that then translates to a key size (in a way that is dependent upon the specific signature algorithm you choose).  Similarly, the size of the signature will depend upon the particular signature algorithm you use.


Security levels in NIST Post-quantum project: e.g. AES-128 vs SHA-256 In an article about NIST Post-quantum Standardization project I read about the security criteria of the proposed schemes and there was this table (Level I lowest security, level V highest):

Level I:  At least as hard to break as AES-128 (exhaustive key search)

Level II: At least as hard to break as SHA-256 (collision search)

Level III: At least as hard to break as AES-192 (exhaustive key search)

Level IV: At least as hard to break as SHA-384 (collision search)

Level V: At least as hard to break as AES-256 (exhaustive key search)

If I understand it correctly, then (in classical way, not using quantum computers and the Grover's algorithm) for exhaustive key seach on AES-128 we need to go through $2^{128}$ possibilities and in collision search of SHA-256 we need to go through $2^{128}$ possibilities to find a collision (thx to the Birthday paradox).

So my question is - how does the security Level I and Level II differ?  And the same - why is security of AES-192 lower than security of SHA-384.

This is due to the Brassard et al.'s method on hash functions. That has $\mathcal{O}(\sqrt[3]{n})$ attack time for n-bit hash function where as the Grover's method has $\mathcal{O}(\sqrt{n})$-time.

Level I: At least as hard to break as AES-128 $\mathcal{O}(\sqrt{2^{128}}) = \mathcal{O}(2^{64})$ - by Grover
Level II: At least as hard to break as SHA-256 $\mathcal{O}(\sqrt[3]{2^{256}}) \approx \mathcal{O}(2^{85})$ - by Brassard et al.
Level III: At least as hard to break as AES-192 $\mathcal{O}(\sqrt{2^{192}}) = \mathcal{O}(2^{96})$ - by Grover
Level IV: At least as hard to break as SHA-384 $\mathcal{O}(\sqrt[3]{2^{384}}) = \mathcal{O}(2^{128})$ - by Brassard et al.
Level V: At least as hard to break as AES-256 $\mathcal{O}(\sqrt{2^{256}}) = \mathcal{O}(2^{128})$ by Grover

The space-time comparisons of the two quantum hash collisions methods.

\begin{array} {|c|c|}\hline
 & \text{time} & \text{space} \\ \hline
\text{Grover} & \mathcal{O}(\sqrt{n}) & \mathcal{O}(\log{n}) \\ \hline
\text{Brassard et al.} & \mathcal{O}(\sqrt[3]{n}) & \mathcal{O}(\sqrt[3]{n}) \\ \hline
\end{array}

Bernstein has a nice article "Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete" about comparison with parallelized van Oorschot–Wiener. You can also read Squeamish Ossifrage's answer.


Can BLS aggregate signatures be merged? In some non-interactive, pairing-friendly signature scheme, such as BLS12-381, is it possible to merge partially-overlapping aggregate signatures?

For example, say you have two aggregate signatures, $X = a + b + c$ and $Y = b + c + d$, and the (unique) public keys and messages for individual signatures $a$ through $d$, but not the individual signatures anymore.

Can you make a "merged" aggregate signature $Z = a + b + c + d$?

Can you make a "combined" aggregate signature $W = a + 2b + 2c + d$ that can still be verified, perhaps by keeping track of the individual multipliers?

You cannot create a verifiable $Z$ but you can create a verifiable $W$ but you have to add public keys multiple times as well. So $W$ can be verified using a key $PK_a + 2*PK_b + 2*PK_c + PK_d$ if you had the same message or doing having multiple pairings for each repeated key in case of distinct messages


Quantative criteria to measure confusion and diffusion property of encryption algorithm I am new to crypto subject.
I am studying the confusion and diffusion in AES etc.
Is there any general quantitative method to measure these properties.
Let us say Algorithm A produces cipher having more confusion/diffusion with respect to Algorithm B. How can one quantify these criteria? Any specific Model or formula for same?

Diffusion

Diffusion can be quantified by examining the branch number of the diffusion layer. The branch number indicates how much a difference in the input will spread around the rest of the state after the transformation has been applied.

The branch number can be used to prove lower bounds on the amount of diffusion that the permutation provides.

Measuring avalanche statistically can only tell you if your diffusion is awful, it can't really be used to prove that diffusion is complete and even throughout the state, or that one design is better then the other (assuming that both have decent diffusion).

Confusion

Confusion, or non-linearity, can be quantified by measuring stats such as differential and linear probability. For small enough mappings, it is easy to take these metrics by simply building a difference distribution table and linear approximation table and simply examining the results. For larger mappings this may prove challenging if not intractable.


CRC32 vs. low 32 bits of cryptographic hash I was having a discussion with a colleague yesterday whose education and experience exceeded mine.  He said something yesterday that sounded incorrect to me intuitively, but I don't have the knowledge to contradict it.

He claimed that the only reason a secure cryptographic hash is better at detecting tampering or corruption is because it has more bits in the output (e.g. SHA-256 has a 256-bit output vs. CRC32's 32-bit output).  Right now, we're only talking about detecting corruption/tampering, not recovering data.

My intuition tells me that given the choice of CRC32 or SHA256 (and taking only the low 32 bits), the hash is going to be much more secure as far as detecting changed bits (particularly in the face of a malicious and intelligent attacker, but even due to corruption in "just the wrong way").

Can someone either tell me why I'm wrong & the 2 are essentially equivalent, or support my intuition with math and or proof/reasoning?

If we're talking about a malicious and intelligent attacker, you are mostly wrong, but not for the reasons you might expect.

If we assume an intelligent attacker, then a CRC does not help; they can obviously modify a file, and either figure out how to update the CRC32, or how to make sure that the modifications do not change the CRC.

On the other hand, if we use a SHA256 hash, that's not much better; if they can modify the hash as well, then they can compute the SHA256 on the new file, and replace that hash with that.  If they cannot modify the hash of the file, then if we truncate the hash to 32 bits, then they can try to modify the file $2^{32}$ different ways, and compute the hash on each; it's likely that they'll find a modification that leaves the hash unchanged.  This is obviously more work for the attacker; however it might be a weekend project for a single PC.

So, the bottom line is that there isn't a great deal of difference between a CRC and 32 bits of SHA256 in this scenario.

And, if we start looking at random changes, the CRC might actually be stronger in that case; if a random change is isolated to be entirely within a block of 32 bits, then a CRC will always detect the change (because the CRC will always change); the SHA256 will detect it with probability $1 - 2^{-32}$.

The first answer we have for strong integrity checking is to use a Message Authentication Code; this assumes that the entity generating the MAC and the entity checking for corruption share a secret key (that no one else has); this key is stirred into the generated checksum, and someone who doesn't know the secret key cannot modify the message and the checksum (with any probability better than random guessing).


Encrypt a message with hash function, shared symmetric key, but no cipher I am very new to Crypto and need some clarification or input. The question is:

  Suppose that Alice wants to encrypt a message for Bob, where the message consists of three plaintext blocks, $P_0$, $P_1$, and  $P_2$ - Alice and Bob have access to a hash function and a shared symmetric key $K$, but no cipher is available. How can Alice securely encrypt the message so that Bob can decrypt it?

What I had came up with appears to work but seems way too complicated.

Alice can compute an HMAC using the hash function, message and key for integrity and send it to Bob like so:

Let $M$ = the plaintext consisting of $p_0, p_1, p_2$,
Let $B$ be the block length of hash in bytes,
ipad = 0x36 repeated $B$ times,
opad = ox5C repeated $B$ times.

Then the HMAC of $M$ is defined to be:

$$HMAC(M, K) = H(K \oplus opad, H(K \oplus ipad, M))$$

Since there is no cipher for the symmetric key,  Alice can send Bob a public key where only she has the private key.  From here she can send the ciphertext $C = [M]$. Alice to Bob and Bob can verify decrypting ${M}Alice = M$ and plugging it into $HMAC(M, K) = H(K \oplus opad, H(K \oplus  ipad, M))$  is consistent with what Alice had originally sent.

First, is this a way to encrypt/decrypt a message? Second, is there an easier way? No cipher available means the message cannot simply be encrypted/decrypted with the symmetric key, correct?

There is a simpler way: implement a stream cipher using the hash function, and use that to encrypt the plaintext.

Probably the most used stream mode is counter (CTR) mode, which is normally defined for block ciphers. CTR mode works equally well with a PRF (MAC) as with a PRP (block cipher). It only uses the function as a one-way function; with a block cipher either the encrypt or decrypt direction (of the block cipher) is used.

The CTR mode for HMAC can be implemented as follows: $C_i = HMAC(k, {nonce} | {I2OS}(i, 4)) \oplus M_i$ where:

$C$ is the ciphertext;
$i$ designates the block;
$k$ is the key;
$nonce$ is a value that is changed for every ciphertext computation;
$I2OS$ is a conversion method to convert an integer to a binary encoding and
$M$ is the message to encrypt.

$I2OS$ is configured using a static size of - in this case - 4 bytes. The blocks have the same size as the hash output. For the last block only the leftmost bytes can be used.

The $nonce$ or IV could be a random value that sent with each ciphertext. In principle it can have any value as long as it is unique. It forms the counter value together with the encoded value of $i$.

Decryption is of course identical: $M_i = HMAC(k, {nonce} | {I2OS}(i, 4)) \oplus C_i$

Your scheme may work: basically you can perform $T=HMAC(K, K_{pub})$ and send $K_{pub}|T$. Then the receiver party knows that the public key is indeed from the sender, and they can use it to encrypt.

However:

this still needs an encryption primitive, i.e. a cipher;
this is an online protocol rather than direct encryption;
this is probably not what was meant, as the split of the message $M$ into blocks indicates.


A confusion on the proof of Yao's theorem (Yao 82) I'm reading the proof of Yao's theorem on Boaz Barak's lecture, the main part of the proof is the following claim:

My question is:

  How can we say "without loss of generality" here? Since $H^i$ and $H^{i-1}$ are probability ensembles, hence for a fixed $D$, whether $\mathrm{Pr}[D(H^i_n)=1]\ge \mathrm{Pr}[D(H^{i-1}_n)=1]$ or not may not necessary the same for all $n$, where $H^i_n$ is the $n$th distribution in that ensemble. So, when one wants to design the algorithm $P$, one need to encode these relation information, how can we do this?

He's doing a pretty poor job of expressing a very simple idea here, which is that if there exists a distinguisher $D$ for which $Pr\lbrack D(H^{i-1})=1\rbrack$ > $Pr\lbrack D(H^{i})=1\rbrack$ (which means the advantage is negative before taking the absolute value), there also exists a distinguisher $\overline{D}$ for which $Pr\lbrack D(H^{i})=1\rbrack$ > $Pr\lbrack D(H^{i-1})=1\rbrack$ (i.e. the advantage is positive before taking the absolute value) by just defining $\overline{D}(H^*) = 1-D(H^*)$ for $H^* \in \{H^i,H^{i-1}\}$. Informally, this distinguisher runs $D$ on its input and just flips whatever $D$ outputs.

Thus, w.l.o.g. we can assume the distinguisher has a higher probability of outputting a 1 given a sample from $H^i$ than from $H^{i-1}$, which means we don't need the absolute value.


AEAD without explicit authentication tag I'm trying to understand the purpose of tag in AEAD. As far as I can understand, the resulting ciphertext will be slightly longer than the plaintext due to the authentication tag. Will it reduce the security of AEAD if the authentication tag is embedded to the ciphertext(e.g. by performing XOR/modular addition to the last block of ciphertext)?

As discussed in RFC 5116, AEAD is the tuple of encryption and decryption function:

An encryption function that takes a key, a nonce, a plaintext and a header (associated data), and produce a ciphertext and a tag.
A decryption function that takes a key, a nonce, a ciphertext, and a header, and produces either 1) the plaintext, or 2) decryption failure indication.

The tag part you're concerned with is used to verify the decrypted plaintext (roughly speaking).

However, there's a requirement that can sometimes be a pitfall in the real world: the nonce must be unique for most AEAD algorithms to be secure. So the clever people invented "deterministic authenticated encryption" (DAE in short, a.k.a. key-wrap in some contexts). These encryption algorithms advertise the property of "misuse-resistance".
And AES-SIV is one such example.


Given enough length, which string of symbols will have the greatest entropy? Which arbitrarily long string will have the greatest entropy?

A string constitued of random letters, with each letter having a probability of being picked equal to its frequency of apparition in the english language.
A text written in english.

Let's assume there's only 27 different symbols (letters+space), and each symbol is coded on 8 bits.

As examined by Shannon in his paper "Entropy of printed English", higher order models which allow for dependencies between nearby characters are more accurate models of English. And in general, dependencies reduce but never increase entropy, so @Guut Boy is correct, the first shall have higher entropy. In the extreme case there is essentially zero entropy about the $(n+1)$st character if the $n$th character is q, it is almost always followed by u ("coq au vin" is taken to be French).

Edit To verify this experimentally given the string $(x_1,\ldots,x_n)$ over the alphabet $A$ define the sequence $(y_1,\ldots,y_{n-k+1})$ by
$$y_i=x_i,x_{i +1},\ldots,x_{i+k-1},\quad i =1,\ldots,n-k+1,$$ over $A^k.$

Compute the entropy corresponding to the frequencies of the $y_i$ sequence. Divide by $k$ to obtain entropy per symbol.

Put simply, $k=2$ would give the entropy of bigrams and divided by 2 it should be lower than that given by monogram frequencies.


Checksum for bailing early on first corrupt byte in stream? Suppose you want to transmit bytes of a file from computer a to b, but you want to bail early if any of the bytes are wrong.

It’s easy to prescribe a hash/checksum implementation for the entire file. For example, sha-256 is probably sufficient and only requires 256 extra bits to be transmitted, and for any file of significant size, 256 extra bits are negligible.

But if you want checks at multiple points during the transfer, so you can bail early, I assume the cost of transmitting hashes grows as the interval of checking approaches checking every single byte... unless I am missing something clever, I think that it becomes hard to justify.

Do you know how others have dealt with this issue or have any advice? Maybe there is no clever way around it and you must just choose a reasonable compromise, like one hash per every megabyte?

(My application is that I want to build a small/safe virtual machine + language that implements arbitrary compression/decompression algorithms to produce files. For decompression, I would like the machine to halt early if any unexpected bytes are emitted. )

..how others have dealt with (bailing early if any of the deciphered bytes are wrong)

A relatively common practice with this side effect is to restrict bytes in the plaintext to a certain discrete subset (e.g. Base64 characters, or those with an odd number of bits set) and stop at the first decoded byte that does not belong to this subset. Don't do this, for two reasons:

If the adversary can detect when the receiver aborts (which is common and should be the default assumption), it often opens to padding oracle attacks which compromise message secrecy.
It is not secure against adversarial modifications, to a degree varying with the cipher. The worst case is stream ciphers, including CTR and OFB, where the ciphertext can be trivially altered to escape this detection method, often even if the original plaintext is not known. It does not work well either in most other modes, especially when some plaintext is known.

  Any advice?

There is a compromise between immediately detecting individual byte corruption and lost bandwidth. By a counting argument, for residual probability $\epsilon$ of not immediately detecting corruption over $n$ bits, we need to sacrifice $\log_2(1/\epsilon)$ bits for each $n$ bits. The only way to keep the relative overhead $1/(n/\log_2(1/\epsilon)+1)$ low with low residual odds of not immediately detecting an alteration is to increase the block size $n$ to more than a byte.

TLS has the functionality of authenticating individual enciphered blocks, and I'm confident that whatever it does in its modern ciphersuites is fine, and could be reused with some care. But I do not know what method(s) it uses.

A recommendable method is to use multiple independent blocks of information each individually enciphered and authenticated with an authenticated encryption mode, with some measure to prevent substitution of blocks. The simplest is numbering them using an explicit incremental block number. But we want to minimize lost bandwidth:

The block numbers can come for free: we include them in the authenticated payload, but neither encipher nor transmit them. AES-GCM supports that.
The IVs/Nonce of the authenticated mode can come for free: they can be derived from a CSPRNG seeded with an extra key (with perhaps that key and the encryption key derived from the main key).

We might additionally want to use a short authentication tag for intermediary blocks in order to conserve bandwidth, but maximize odds that a previous alteration that went undetected because of that is detected later. I know no standard method, but it is possible to improvise one if computational efficiency is not an issue: we can include a MAC (made with an independent key, e.g. derived) of the previous block (including its authenticated data) in the next block's authenticated and implicit data. Further, we can use a hash rather than a MAC if the authenticated encryption is such that passing it's integrity test does not compromise the confidentiality of authenticated data when that's implicit (which is the case at least if that integrity is checked using a MAC).

If we use a large authentication tag for the last block only, there must be some safe way to recognize that block, and that's not to be taken lightly. A safe method is to make it of a recognizable length and use a different derived key for that block.


Why don't we use an Extendable Output Function to efficiently store the public key of Regev's LWE-based encryption scheme over standard lattices? In LWE-based schemes the public key is generated by choosing a random matrix (or polynomial) $A$, and outputting the pair $(A, b = A\cdot s + e)$, where $s$ and $e$ are vectors/polynomials with coefficients taken from some error distribution.

In the Kyber encryption scheme the first part (the matrix/polynomial $A$) is not a part of the public key. Instead they save the seed to the (publicly known) extendable output function (EOF) that was used to generate $A$. If someone wants to know the public key, then he can just ask for the seed and generate $A$ himself. This saves a lot of space.

Why is this not proposed for schemes based on general lattices (standard LWE)? The big problem of these standard LWE schemes is the huge public key size, but this EOF solution would resolve that. However, it is not mentioned in any of the implementations that I found, like this one.

I believe it is also used in other lattice based schemes that use standard LWE. For example, the Frodo paper. They used a $seed_A$ and a Gen($\cdot$) function to compute $A$. Then Alice sends $seed_A$ instead of $A$ for the actually exchange. Gen($\cdot$) is a prior-agreed pseudorandom function that extracts and extends the seed.


Merkle-like hash tree that mirrors existing tree structure I'm wondering about the security of a hash-tree structure that mirrors the structure of another tree. In an ordinary Merkle tree the block hashes form the leaves of the tree, and all internal nodes are computed by hashing their children, but what if the data being hashed already conforms to a natural tree structure T? Could you securely create a hash-tree from T by replacing the leaf nodes of T by their hashes and the internal nodes of T by the hashes of their children?

My motivating example for this data-structure is a hierarchical filesystem. I've written some code that realises this idea but I'd like to know if this method is actually secure.

Proof-of-concept code here: https://github.com/michaelsproul/antifa/tree/master/src

I've attempted to make it second-preimage resistant by adopting the framing bytes from Certificate Transparency. The hash of a file is h(00 || contents) and the hash of a directory is h(01 || child1 || child2 || ...). Children are sorted by name before hashing, but their names aren't included in the hash (although perhaps they should be to avoid an order-preserving renaming attack).

Here's an example run on the src directory of the PoC:

$ tree
.
├── bin
│   └── shasum.rs
├── hash.rs
├── lib.rs
└── main.rs

1 directory, 4 files

$ cd .. && target/release/antifa src
[]: SHA-256:9c9489d389f253820a7b7b04a00f38cc04e7d9381e6e6792a69cade7982c6ab1
["lib.rs"]: SHA-256:e070004ebdeca318c5451f5f4e716d5322c286e7a347b3bef987402efc362454
["main.rs"]: SHA-256:83e39d33c072b917ac299bb761442f51e473ccb69b0b40cbf87a80e892fb68b6
["bin"]: SHA-256:22065eed254ac789dddc348d1f429f0e27a09f4e7f0a432d7c4f70e26d5b0e4a
["bin", "shasum.rs"]: SHA-256:c91146c4ac71b8b336cdd8d70475ea8fed3186b16e189ba9d3e003fc80da9113
["hash.rs"]: SHA-256:984b35e7bb55608982bcf1e76d461e0bacd6e75b54f0f0fca5dfac12b23e6135

(the file paths are shown as a list of their components for now)

Yes: this allows the root hash to authenticate the entire content of the directory tree so that, e.g., a malicious storage server cannot fool you into accepting a forgery replacing a file you previously asked it to store.  This is how Tahoe-LAFS is structured, or at least the immutable parts, and how ZFS block pointers are stored when authentication is enabled.  More broadly, there is a modest literature on authenticated data structures that are all built out of essentially this idea.


Can I replace SHA-1 with SHA-512/160 to address Shambles? The destination is software (within a remote trust boundary) that expects SHA-1 results. Would it be safer for the source (that's within my own trust boundary) to replace my SHA-1 computation at my source with a SHA-512/160 instead?

Generic collisions

The generic collision attack on SHA-512 trimmed to $n=160$-bit will require $2^{80}$ complexity by the birthday paradox with a 50% success probability. The generic attack doesn't require any knowledge about the internals of the target hash function. It is about collecting hash outputs and looking collision among them by building a table and hoping that you find a collision. The cost is $O(2^{n/2})$ time and $O(2^{n/2})$ space to store the table.

If you are using a variant of Pollard's $\rho$ you can achieve constant $O(1)$-space with $O(2^{n/2})$-time. The best known is the van Oorschot–Wiener Time-Momory Trade-off technique with cost $O(2^{n/2})$. This can be parallelized with a linear speedup. Use $O(2^{n/4})$ machine to parallelize and get an answer in $O(2^{n/4})$ time at the same cost of $O(2^{n/2})$.

If you consider the Quantum attacks on hash functions, you should use 384 or 512 output sizes due to Brassard et. al' work. That has $\mathcal{O}(\sqrt[3]{n})$ attack time for n-bit hash function (for 256-bit $\mathcal{O}(\sqrt[3]{2^{256}}) \approx \mathcal{O}(2^{85})$). See the timing table in this answer.

SHA-1 weakness and Shamble

The researches use weaknesses that lie in the internals of SHA-1 and The Shambles' researches reduced the collision to $2^{61.2}$, see the list of other work in here. The Shambles' team used 900 GPUs that cost around $75.000 with their new method and calculated the forgery at most in two months. This is why they called practical. Their new records;

They reduced the use of neutral bits BCJ+05 and boomerangs JP07 from $2^{64.7}$ to $2^{61.2}$
Also, they improved graph-based technique (LP19) to compute Chosen-Prefix Collision from $2^{67.1}$ to $2^{63.4}$.

The Machines

There are machines already exist way before the attack's 900 GPUs, like the Summit in Oak Ridge that can reach $2^{63}$ SHA-1 calculations in a day. As long as, one cannot find a weakness in SHA-512/160, it will have an 80-bit classical collision resistance.

80-bit is no longer secure

Today, 80-bit collision resistance for any hash function is not considered secure. The NIST removed SHA-1 signatures from the recommendation in 2011.

  NIST formally deprecated use of SHA-1 in 2011 [NISTSP800-131A-R2] and disallowed its use for digital signatures at the end of 2013.

R2 in 2019 on page 18 NIST allows it for nonsignature, although by that time it's clearly a bad idea (Thanks to Dave).

Actually, one can consider that it is not the SHA-1 is removed, the 160-bit hash output is removed from the recommendation. The 160-bit was related to 80-bit security that was enough during the early 2000s. And, note that the 50% probability of the birthday attack is not negligible in the view of the attackers. One must consider the lower probabilities.

Recommendation

It is wiser to update the software to new recommendations like the SHA3 series with good hash sizes like 256, 384, or 512 if you are working with the US government. If not, you can also use other good hash functions like Blake2. If you consider Quantum attacks, you should bigger than 256.

You can use it if you are satisfied but not advised.

Migrating the software shouldn't be a big problem. It is strongly recommended.


Purpose of outer key in HMAC From what I know, the HMAC constructions has two strength:

It's resistant to length extensions
Since the key is consumed before the message, the attacker does not know the initial state, preventing simple collision attacks.

But the simple construction $ \mathrm{Hash}(\mathrm{Hash}(\mathrm{key} ∥ \mathrm{message})) $ would offer those properties too.

HMAC on the other hand uses the more complicated construction $ \mathrm{Hash}((\mathrm{key} ⊕ \mathrm{opad}) ∥ \mathrm{Hash}((\mathrm{key} ⊕ \mathrm{ipad}) ∥ \mathrm{message})) $. I assume the more complicated construction of HMAC is required for some security proof, but I don't immediately see why.

For SHA-3 candidates, Hash(key||message) is claimed to be secure, since they're resistant to length extensions, without consuming the key twice. I believe Skein even has some security proof for a very similar mode.

So why does HMAC need to inject the key twice?

You're missing the most important strength of HMAC: it comes with a proof of security (under some plausible assumptions).  The outer key plays an important role in the proofs.  The best place to learn more is to read the HMAC papers:

Message authentication using hash functions: The HMAC construction, Mihir Bellare, Ran Canetti, Hugo Kawczyk, CryptoBytes Spring 1996.
Keying hash functions for message authentication, Mihir Bellare, Ran Canetti, Hugo Kawczyk, CRYPTO '96.

In particular, it is very important for their proof that the outer function be keyed.  In your scheme, the outer function is not keyed, so their proof of security will not apply.

As they explain in the paper, the role of the inner function is to provide collision-resistance (to compress a long message down to a short fingerprint, in a way so that someone who does not know the key cannot find a pair of messages with the same fingerprint), and the role of the outer function is to act as a message authentication code on this fingerprint.  Their security proofs show that if the inner and outer functions each correctly implement their roles, then the combination (HMAC) will be a secure message authentication code.  Because the outer function needs to be a secure message authentication code, that means the outer function needs to be keyed for their proof methodology to apply.

Read the papers.  They are surprisingly readable, for a theoretical piece of work.


Given an AES-CBC encrypted string, IV, and plain text, how can I compute the key? If I have the AES-CBC encrypted string along with the IV and the plain text before encryption, how can I compute the key which was used for encryption?

If I had a way to do this, I would be rich (at least temporarily, until I moved on to smashing the capitalist system before the money got to my head), because trillions of dollars of economic value in communications across the world are secured by the assumption that you can't.

It's kinda one of the design principles of modern cryptography.  Not only can you not figure out the key, but you can't even distinguish another encrypted message under the same key from random noise, no matter how many plaintext/ciphertext pairs you have of your choosing, up to limits that are beyond the reach of humanity.  This property is sometimes called ‘indistinguishability under chosen plaintext attack’, or IND-CPA.


Increasing number of rounds in AES AES-128 requires 10 rounds ( AES Description, Wikipedia )

However Bruce Schneier has recommended AES-128 use 16 rounds ( Schneier on Security: New Attack on AES )

Could that be implemented as two full encryptions of AES-128? That is:

AES_128_ENCRYPT(key, data, mode); // 10 rounds of normal AES 128
AES_128(key, AES_128(key, data, mode), mode); // would this be 20 rounds of AES?

Would this need to be with two separate keys like in Triple DES ( Triple DES, wikipedia )?

The de-facto answer to any question about increasing the AES rounds is that as yet there doesn't appear to be any need, and any time you do so involves implementing at least some of it in custom code, which is inherently risky.

As far as running AES twice goes, have a look at Meet in the Middle (MITM) attacks. I don't know how relevant these will be to your target scenario given the space requirements, but in general they mean that running two encryptions is only twice as good as running one.

Throughout this post I'll refer to AES-128 as simply AES.

You certainly wouldn't be able to use the scheme you describe with the same key as this would not lead to 20 rounds of AES, because the key schedule would be incorrect for the second half of the rounds. Moreover, since the last round of AES is not the same as the intermediate rounds, you would end up with

[pre-whitening + 9 rounds + 1 last round ] + [ pre-whitening + 9 rounds + 1 last round]

If you were to extract the final values from the key schedule, you could use these to generate the next iteration of the key schedule. Using these two sets of data and your own implementation of AddRoundKey, you could remove the final round key, complete the final round into a full intermediary round and invert the pre-whitening that was about to occur (since pre-whitening just involves xoring in the next round of the keyschedule).  However, by the point you've done this you've basically ended up implementing most of the internals of AES yourself, and in a very messy way. Worse still, any home-brew AES implementation is likely to have significant side-channel weaknesses, so should be avoided.

The following question (suggested by SE to the right) might help with understanding the key schedule side:
how can i add more rounds to aes


Is libsodium's `box` construct secure without additional manual padding of the plaintext before encryption? I have read the following questions and answers:

How safe are Libsodium Crypto Boxes?
What can be learned from the ciphertext of LibSodium's crypto_box_detached()?

However, neither of these discuss an important detail that caught my attention while reading the libsodium documentation on the padding API:

  Most modern cryptographic constructions disclose message lengths. The ciphertext for a given message will always have the same length, or add a constant number of bytes to it. For most applications, this is not an issue. But in some specific situations, such as interactive remote shells, hiding the length may be desirable.

As far as I can tell, this also applies to boxes, because they use a stream cipher, XSalsa20, under the hood. However, the docs for the Box API claim that:

  The _easy and _detached APIs are faster and improve usability by not requiring padding, copying or tricky pointer arithmetic.

I've also read in various places that unpadded symmetric key cryptography is not secure for several reasons (e.g. malleability caused by determinism). However, in the Box implementation, the asymmetric keys are not used for encrypting the plaintext itself, but for deriving the shared secret key for the XSalsa20 symmetric cipher.

Overall, this made me wonder whether the problem of padding is still relevant, and whether I should manually pad my messages before passing them to crypto_box_easy (and obviously, unpad them when they are returned from crypto_box_easy_open) for better security? I can't quite connect the dots, and I don't want to uselessly complicate the crypto code I'm writing either (because that in itself could grow the security attack surface).

The _easy and _detached APIs are faster and improve usability by not requiring padding, copying or tricky pointer arithmetic.

This refers to the way the original NaCl API worked. You had to add some zeros before the message, and remove them after decryption. But this is just how the functions had to be used. It made the primitive implementation easier, but usage trickier. It didn't add any actual padding to the messages.

  (e.g. malleability caused by determinism)

Irrelevant here. The nonce ensures that the same message encrypted twice produces different ciphertexts.

Padding should be added only if you consider that an attacker may learn something relevant from the length of the messages. If you are sending encrypted passwords, this will reveal the length of the passwords, which may not be desirable. If the only messages that can be exchanged are "yes" and "no", the attacker will not require to decrypt anything to guess the message. Here, padding would be useful.

But for most applications, it is useless.


Main purpose for Carmichael's Function in RSA I'm trying to understand the RSA cryptosystem, these are the steps:

Generate two large different prime numbers $p$ and $q$.
Calculate modulus $n$ ($n=pq$)
Calculate: $λ(n) = \operatorname{lcm}(λ(p), λ(q))$

I'm trying to understand the step 3. As we know, the original RSA document uses Euler's Totient Function - $\phi(n) = (p-1) \cdot (q-1)$ (which outputs the amount of numbers that are coprime to $n$).

But, Carmichael's function is smallest positive integer $m$ such that: $$a^m \equiv 1 \pmod n.$$

From my knowledge, $λ(n) \mid \phi(n)$ according to Lagrange's theorem (abstract algebra group theory). Thus that seems to be the only reason why Euler's Totient Function was used in the past, making Carmichael's function more appropriate?

The fourth and fifth step is to create public exponent and modular multiplicative inverse of modulus n as decryption key.

The public exponent must be $e$ such that: $$1 < e < λ(n) \quad\text{and}\quad \gcd(e, λ(n)) = 1.$$

Is the "rule" above necessary? I think I've seen different versions of RSA cryptosystem where large exponents are randomly generated (exceeding output of $λ(n)$).

The private key is found by this congruence: $$d ≡ e^{−1} \pmod{λ(n)}.$$

Meaning, utilization of Extended Euclidean Algorithm is not necessary?

I understand Bézout's identity, Euclid's lemma, Euler's totient function, and multiplicative group of integers modulo $n$ (a little). But what is the easiest explanation for the purpose of Carmichael's function in RSA algorithm?

Thank you!

You're have everything basically right.  Modern RSA-based cryptosystems, as in PKCS#1, do indeed use the Carmichael function.  Usually we pick $e = 3$ or $e = 2^{16} + 1$, try a different modulus if $e$ divides $\lambda(n)$, and otherwise use $d \equiv e^{-1} \pmod{\lambda(n)}$.

I'm not sure how you conclude that the extended Euclidean algorithm is not utilized—usually that is how we compute $d$.  The EEA, given $e$ and $\lambda(n)$, computes coefficients $c$ and $d$ satisfying Bézout's identity $c\lambda(n) + d e = \gcd(e, \lambda(n)) = 1$, meaning that $d e \equiv 1 \pmod{\lambda(n)}$, or $d \equiv e^{-1} \pmod{\lambda(n)}$.  Of course, we require $\gcd(e, \lambda(n)) = 1$ or else $e$ doesn't have an inverse modulo $\lambda(n)$ or $\phi(n)$ at all.

You can use $e > \lambda(n)$ or $d > \lambda(n)$, but it's no different from using $e \bmod \lambda(n)$ and $d \bmod \lambda(n)$, so there's no sense in wasting space for a larger number except in exotic applications.  You can also pick $e$ at random, but it offers no security and only hurts performance: roughly, the Hamming weight of $e$ determines the number of multiplications modulo $n$ to compute the public key operation, and $\lfloor\log_2 e\rfloor$ determines the number of squarings modulo $n$ needed to compute it.  (Certain exponents may also admit more efficient Lucas chains than the naive square-and-multiply algorithm.)

You want to minimize these because they make up the bulk of the public key operations.  Using the fastest option $e = 3$ is perfectly fine for sane RSA-based cryptosystems like RSA-KEM and RSA-FDH signature, and even the standard and fairly widely used RSAES-OAEP and RSASSA-PSS, but people are terrified of $e = 3$ because there are some ways to use RSA stupidly that enable, e.g., decryption or forgery by computing real number cube roots, so $e = 2^{16} + 1$ is a more popular choice.  $e = 2$ brings you into the territory of Rabin cryptosystems, which are qualitatively a little different, but have a neat reduction to factorization.

(If you pick $d$ small to speed up the private key operation instead of picking $e$ small to speed up the public key operation, you expose yourself to Wiener's attack.)


Efficient attack on RSA with known padding scheme and public key I am having some trouble with an assignment problem. I hope I can get some guidance here. The question provides us with a public key, $N$ and the padding scheme.

This is the padding scheme "Assume PIN is a positive integer smaller than $2^{16}$. Instead of directly encrypting the PIN, she writes the PIN in binary format ﬁrst, then she appends 2048 1 bits at the right most side of the binary representation of PIN. For example, integer $abcd$ in hexadecimal becomes an integer $x$"

$c = (m^e) \bmod N$

The length of both $N$ and $C$ is 923 digits of hexadecimal.

From this knowledge we are supposed to perform an efficient attack on the ciphertext by which we can recover the plaintext.

Me and my team have tried to implement multiple cca aswell as cpa techniques, however we have been pretty much unable to find any thing that would work. Of course I understand that the trick to solving this question is in the padding, but we have yet to be able to discover how to do so.

I would appreciate any help in this regard.

Edit: The value of $N$ is

0xa05bb3783769b832a2d022646c48344948282cdcd42bff414ec90f23b7e3b1b817137664f4016319586395741996245f9c2c66dee453352dc329fe54228beaa559a610114dbe902c32572e954660adbd06f8da8c770c33bb5ad15f506073ea0c50ff4e9906e16ee70d1311e0ad81896f4807282361f5b2116488de06966b571cdb15da536226378bc1fba8a3476c5809b5a274a0117b5de3e52278d39fdfa62de29f338b0453ac3af61a30dcb2975949a3d0ec2d2b7f0d2c4d2e3ef6ddefa8caad21bc16972dcecfcd5f9332373a759632f7f02c52dd424b83985eaa673ce67023366e85899729fc1d1fede02fa9c53aa01328c9108a3c5145f47ef988688f3076d49821314210d1f4db88fa836d41f3dc3960499eb46b28261aaa1515e0fb6d7481ae051b607683cbfdc18d6b692f93d6facf4002d6fa835aac4d61911b66859a81043763e1d0ef6e47f1a7a4c8d57993b0fb67b5758ed3aca9540d39e150935cdd0c320d166da65612ae78322f96853885e6a44add306a899fab2f87cf2a1d

and the value for $C$ is

0x90fdea0c662ed2cef739c491c2f391d8cf636b80144c412580c02e3262e4fa10c6e101f4c53d09619c7cb6fc9d8edfe2a676c1c128bd8e32528aff243101b9daf655bcd5460a9bf020ff4bef0f61b94304b142b6b18830b8b4d5574e8b54903de67df71f39234fdf9f66723ab1bf426d1c0a95fabae8485e9edf7f4c868ca2816398b1f46ffda2a84b5d52ff36bad829ddc2e123f86cb266256824f047fb6f6a1c7593eaf4ae5c47c6f5e633370d832345fde53324d02687a9b21e60fcefb5e2e2eb1ace969fe72afca67847acad093dec8976336ace5f135257f740f625851a3258854775a3f4f123eae1a6253b2740de37d112bca596f36e4c0d4cfc50b05643b8ec0b52619ae7d0ae990e041ba01bc149ac4a510c81e3aef3f4f2843a50f15c637e274e714c6a768e0c7d96e28a5365b64aee0315623794724573648516ebc9b0f5135a180ac3141a98f2ef0f005f6980781036c9b1c7975774708d1929d1935ae782de80722124220a9dd3fadc457d8bdb8be762b0158187ee619142637d

As the padding is deterministic and the amount of input values is minimal, you can just try and encrypt each possible value with the public key. If the result - the ciphertext - is identical to the one you have then you've found the input value and therefore the PIN. You are guaranteed success in $2^{16}$ tries after all, that's 65536 tries in total.


Is there an efficient solution? Finding the number of matching items in lists with a threshold Alice and Bob both have a list of n items. They want to know the number of items that are occurring in both lists. The catch is, that they should receive 0/no result as a result if less than k items occur in both lists. If more than k items occur in both lists, they can learn anything from each other.

I think this can be done by generating all possible subsets of k items and multiplying the hashes of the items in the subsets with the generator point on an elliptic curve.
Then all resulting points for Alice and Bob for all subsets could be compared.

However, that solution would grow exponentially with k. Is there a better solution to solve this problem?

There has been work on finding the size of the set intersection. I haven't read this paper, but this would be a good place to start your research: Fast and Private Computation of Cardinality of Set Intersection and Union.


Why does the ZUC need an initial vector? After reading the Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3. Document 2: ZUC Specification, I just cannot figure out why does zuc need an initial vector, my current understanding is that the initial key and the initial vector are playing the same role in ZUC, is there anything that I miss?

The initial vector is also known as an initialisation vector (IV). As mentioned by Mr Smet in the comments, it allows a user key to remain constant, yet the cipher text to be unique for every transmission even if the plain text is also constant.  So simply put, sending "Hello Mr. Feng" with the same key over and over will result in unique cipher texts. This feature disguises that you're sending the same message and helps resists crypt-analysis.

Strictly put, the cipher text will still be generated correctly if you didn't use an IV, it's just more secure to do so.  Your ZUC document just assumes that implementors know what an IV is. There's more detail at the Wiki entry and at What is the main difference between a key, an IV and a nonce?

There are strict rules for generating the IV that you can easily look up, such as uniqueness and randomness.


Algorithm Design for only Mutual Information Sharing Bob and Alice each have a bit string they want to keep private. They each want to know what the bitwise AND of their two strings would be without telling the other or anyone else listening to their exchange their actual bit strings... how can they do this? Keep in mind that even once they both hold the AND of their two bit strings, they should still not be able to calculate the other person's string exactly (unless of course one of their strings was all 1s).

I know that I have seen something similar before in some sort of mutual key system/voting system but I couldn't remember where. It has to be something like make a private random key, xor it and use that somehow... but I couldn't work out the details. Any clever encryption design people out there?

Aaron Roth on theoretical CS was kind enough to answer with the following answer for anyone out there who is interested.

What you want to do is called "Private Set Intersection". You can think of Alice and Bob as each holding sets (the indices for which their strings are "1"), and they want to compute the intersection (the bitwise AND) so that neither of them learns anything about the other's set except what is implied by the intersection itself.
This problem is well studied. See, for example, Freedman, Nissim, and Pinkas: http://www.pinkas.net/PAPERS/FNP04.pdf


Should I split a 3MByte block into smaller blocks if using XXTEA? Given that I have a 3MByte block of data, a random key and need to use XXTea, is there any advantage in splitting the block of data into smaller blocks and encoding / decoding each separately?
Is there a sensible upper limit to the size of block as far as encryption / decryption is concerned?

You should not use XXTEA, especially in its large-block variant. It's reported as broken, and that seems very credible. Some of the problem is with the overly aggressive $6+52/n$ rounds, but beside this, the cipher has not attracted wide review.
This question discuss other variants of TEA.
Except in the specific cases that you need an all-or-nothing bijection of a block (because you can't afford that encryption makes the ciphertext any larger), or code space is extremely scarce, my recommendation is to use a standard authenticated encryption cryptographic primitive such as AES-GCM. Libraries for that are available in most major languages.