Analyzing security flaws of cipher I know using homebrew encryption can be very dangerous as it is very likely to have many flaws in its design. The following concept is just for learning purpose in case anybody is getting red flags reading this. Hopefully this is the right place to ask.

I have made up a block cipher and would like to know how I can possibly find flaws or might even break it. As it is self-made and I have no prior in-depth knowledge in cryptography I assume it is likely to find ways to attack this encryption. As there is no general breaking tool for ciphers (at least not from what I understand) I would be very interested if some of you might share some ideas.

The cipher is used in CBC mode has a block size of 512 bit and a key size of 1480 bit.
The 512 bit input is filled into 64 cubes (or matrices) consisting of 2x2x2 bit. Each cube is filled with 8 bit of consecutive data from the input. Three times for each cube we are reading three bit from the key to determine operations to be done. These operations are the rotations of a single layer of the cube selectively in X,Y,Z direction and a circular shift of the bit (probability of circular shift is higher 2/8)
The idea of using three operations is, that it cannot arrive at the initial position.
Then for each cube 4 bit from the key are used to xor the cube from top to bottom. This avoids same outputs for cube filled just with zeros (or ones) and in generally should increase security as it adds confusion to the input.
The 64 cube get shuffled, by using 64 times 6 Bit to determine a new position.
Then 8 cubes each are used to create a 4x4x4 cube. We apply four operations on each cube. Three of them are again layer rotation, circular shifting and new rotation of the entire cube identified from 4 bit of the key (all operations same probability). Another 2 bit are used to either mirror on an axis or invert.
Again the cubes get xored this time it needs 16 bit for each cube.
In the final step the cubes get shuffled and put into an 8x8x8 cube. We read the output of the cube as the output of the cipher.

What would be the first approach to possibly break it?

My thoughts so far were, that it should not be likely to have key collision as each bit of the key would cause a different behavior of the algorithm. The cipher strongly depends on the key, so small portions of the key leaking would greatly compromise the security. Slightly different input with the same key will produce very similar output.
Is it a security flaw that it cannot produce the same output as input as this could be case for the impossible differential cryptanalsis?

In case anyone is interested which I would greatly appreciate, there is an implementation that I could upload for further inspection.

When seeing clearly through all the cube "magic", one recognizes the following: All the cube operations are just key-dependent bit permutations. Therefore, the whole cipher is a sequence of key-dependent permutations and XORs with key bits.

This admits an algebraic description: For all keys, there is a permutation matrix $A\in\mathbb F_2^{512\times512}$ and a vector $b\in\mathbb F_2^{512}$ such that
$$\mathit{cipher} = A\cdot \mathit{plain}+b\text,$$
where $\mathit{plain}$ and $\mathit{cipher}$ are interpreted as vectors over $\mathbb F_2$ of length $512$. Therefore, the cipher is an affine map over $\mathbb F_2$. This is about the most undesirable property a block cipher can exhibit. An attacker has of course no direct access to $A$ and $b$, but there are lots of weaknesses: For example, in a chosen-plaintext scenario, an attacker can

encrypt $\mathit{plain}=0$, thus obtaining $\mathit{cipher}=b$; and subsequently
encrypt $\mathit{plain}=\mathrm e_i$, the $i$th unit vector, for all $i$. He can then subtract $b$ from the resulting ciphertext, yielding $A\cdot\mathit{plain}$, and check which entry of this vector is $1$ — this is the target of the $i$th entry of $\mathit{plain}$ under the permutation $A$.

A chosen-plaintext attacker is therefore capable of obtaining (information equivalent to) the encryption key using a very simple procedure, hence making the cipher, to put it mildly, rather unsatisfactory (which is a synonym for "absolutely broken beyond any hope" in cryptography).


Negating the risk of a random 64-bit nonce Given a stream cipher such as Chacha20, which uses a 64-bit nonce, it would be unsafe to use a random nonce because of the risk of accidental repetition (which if used twice with the same key would be disastrous). In environments where using a simple counter is not an option, consider the following construction:

staticKey: 256 bit cryptographically secure pseudorandom key
perEncryptionSalt: 128 bit random salt
perEncryptionKey: HKDF(staticKey, perEncryptionSalt, info)
perEncryptionNonce: 64 bit random nonce

Ciphertext = chacha20(clearText, perEncryptionKey, perEncryptionNonce)

The salt and nonce would be appended to the ciphertext and included in the mac. Given that the key changes with each encryption (and thus would unlikely ever be used in combination with the same nonce), is this construction safe? I'm aware of XChacha20/XSalsa20 and they already solve this problem, but I'm curious nonetheless.

Without looking at the code I would say your construction is pretty much the same as XChaCha20:

From https://download.libsodium.org/doc/advanced/xchacha20.html

  Internally, XChaCha20 works like a block cipher used in counter mode.
  It uses the HChaCha20 hash function to derive a subkey and a subnonce
  from the original key and extended nonce, and a dedicated 64-bit block
  counter to avoid incrementing the nonce after each block.

(emphasis mine)

I'm not sure if this HChaCha20 hash function has any specific properties but using HKDF is probably just fine.

Here is the paper on XSalsa20. It should be possible to adapt the security proof.


What could be the keylength of a DES encryption? What could be the keylength of the DES encryption if we have an output of 64 bytes?

DES has a 56-bit key in 8-bytes. The length of the output depends on the length of the input, mode and padding, not the key.

Note: The LSb (least significant bit) of each key byte is reserved for parity, depending on the DES implementation parity may or not be checked.

See: Data Encryption Standard.


Lamport-Diffie + attempting to invert OWF I am studying Lamport-Diffie signature scheme and in my lecture present the follow algorithm  for attempting to invert the one way function $f$, where $f$ is used to compute the public key of this signature from the private key $sk=\left(\begin{array}{rrrrrr}
x_{1,0} & x_{2,0} & \cdots & x_{l,0} \\
x_{1,1} & x_{2,1} & \cdots & x_{l,1}
\end{array}\right)$. My question is Why will be possible execute the sentence 2, if $x_{i,b}$ are part of private key?

The only requirement is $i,b \neq i^*,b^*$ where $i^*$ is a random value from $1$ to $l$ and $b^* \gets\{0,1\}$ So if $b^*=0$ then $b=1$.

Don't get confused by the $x$, it has nothing to do with the secret key, it's just a variable that later becomes $y_{i,b}=f(x_{i,b})$. It could as well be called $a$.


Does ssl_rsa_with_rc4_128_md5 have known weaknesses? My bank's website uses HTTPS with the cipher suite ssl_rsa_with_rc4_128_md5.

What are the known weaknesses of this suite? Do they have a practical impact for banking-related communications?

In a purist cryptographic sense, there are many vulnerabilities in this cipher suite that can be (theoretically and practically) exploited. There are much stronger versions of SSL/TLS, and much stronger cipher suites that could be used.

In a practical sense, it's not the end of the world - there are far worse cipher suites (e.g. those using intentionally weaked 'export' encryption, or weak ciphers such as DES), and you probably have more to fear from malware/phishing attacks etc. wrt interacting with your bank than from someone targeting your SSL connection.

Bear in mind that the cipher suite being used is what the bank web server chose to use based on the cipher suites your web browser told it could be used - if your browser is configured to disable TLS 1.0/1.1 for example, this may be the best the server could manage (although from the use of MD5, this appears unlikely).

If you're interested in the detail, then looking at each of the parts of ssl_rsa_with_rc4_128_md5 individually:

ssl - this indicates your site is using SSL, probably SSL 3.0. This is the older, and less secure version of TLS. Most web browsers now support TLS 1.0, 1.1 and 1.2, but only the most recent versions actually enable higher than TLS 1.0 by default.
rsa - this indicates the use of RSA for the key exchange/key agreement protocol. There's probably nothing to worry about here, although the use of RSA here uses the same private key every time you communicate with the site, so anyone who can record the encrypted traffic and at a later date steal the banks private key could decrypt the traffic.
rc4 - this indicates that the RC4 cipher is being used to encrypt traffic to and from your website. RC4 is considered broken (or at least suspect) for most uses, and 'practical' attacks have been demonstrated against it's use in SSL/TLS. 'Practical' in this sense still involves a fair amount of work on the part of the attacker, and you'd have to be a high value target to make that worth it. RC4 is still very commonly used in SSL/TLS, as it is immune to other attacks (such as the BEAST attack) that affect other ciphers.
128 - this indicates 128 bit encryption keys are being used. This is a good key size for most applications, and nothing to worry about.
md5 - this indicates the use of the MD5 hash algorithm to perform functions like deriving keys and authenticating messages in the SSL protocol. MD5 is considered broken as a cryptographic hash function, but it's use in SSL is either in combination with SHA1 (another suspect, but stronger hash function) or in an HMAC like construction, which makes attacking it a lot more difficult.

Most of these issues are in the walk, don't run, to the exit category (the use of MD5 being probably the most concerning issue) - it would be prudent for your bank (and you) to start using more modern cipher suites to protect traffic.


Give a distinguisher to differentiate between PRP and RPO I have understood the proof that shows that a PRP is a PRF except for negligible probability $\frac{q(n)^2}{2^{-l(n)}}$. My computations suggest me that the same argument, perhaps with minor mathematical details, can show that a PRF can be treated as a PRP (if we forget about the fact that a PRP needs to be a DPT computable permutation while a PRF needs not).

Now I stumble upon this question:

  Show that there is a PPT-adversary which distinguished a PRP F from  RFO with a negligible, but non-zero advantage.

My problem is to give the code in the distinguisher side. Let me phrase it:

Alice picks $b \stackrel{u}{\in} \{0,1\}$. If $b = 0$ sends to Eve the RFO and if $b = 1$ sends to Eve the PRP $F$.
Here I need to describe what the distinguisher $D$ does.

I guess that I should make $D$ query the oracle he receives a polynomial number of time $q(n)$ defined by its efficiency bound. But what can be the details of the construction?

Glossary

PRP = pseudo random permutation
PRF = pseudo random function
RFO = random function oracle
RPO = random permutation oracle

A RFO is essentially supposed to generate a random function in the sense that when a new input (it has not been seen before) it will assign to this input a random output. The RPO is similar to this construction but ensures that the output have not been used before for other inputs, so that the generated function is injective.

As you do not specify what the domain of the function is, I'm going to assume that we're talking about functions of the form $f:\{0,1\}^n \to \{0,1\}^n$.

The distinguisher works as follows:

Let $q(n)$ be some polynomial.
Choose $q(n)$ many distinct elements from $\{0,1\}^n$. Call them $x_1,\dots,x_q$.
Query each $x_i$ to the oracle and record the result as $y_i$.
If there exists any $y_i=y_j$ with $i\neq j$, output $0$, otherwise output $1$.

If the oracle is a PRP, then it is by definition a permutation (i.e. has no collisions) and since $x_i\neq x_j$ for all $i\neq j$ the distinguisher outputs $1$ with probability $1$.

If the oracle is a truly random function, then each $y_i$ is uniformly and independently distributed. The probability that there is at least one collision among $q(n)$ randomly sampled elements of $\{0,1\}^n$ is $$1-\prod_{i=1}^{q(n)}\frac{2^n-i}{2^n} \geq 1$$ and therefore the distinguisher will output $1$ with probability $1-\varepsilon(n)$ for some $\varepsilon(n)\geq0$.


Improve security of transposition ciphers As we know, breaking a Transposition Cipher is quite trivial and can be easily done by either exploiting single letter frequencies (not $d$-gram frequencies though, given that $2 < d < L$), or by employing a simple CPA, thus deriving the snippets length $L$ and the transposition matrix (key).

If we imagine to encrypt the plaintext twice, employing two different keys, would this help improving security?

If we employ the same snippet length $L_1 = L_2$, this clearly won't improve security as an attacker could easily find the key $k_3 = k_1 \times k_2$ (where $\times$ is the matrix product), without even bothering about $k_1$ and $k_2$.

However, that's not the case if $L_1 \neq L_2$. So I guess there's some kind of improvement; can you show me if and how this is true?

First determine the permutation domain. If $L_2 > L_1$, then the cipher is broken by $\lceil  log_2 (L_2) \rceil$ pairs of plaintext/ciphertect. The security improvement is small, as the attacker only needs to use $\lceil  log_2 (L_2) \rceil - \lceil  log_2 (L_1) \rceil$ additional pairs to find the key.


Does a conditional statement depending on a round number introduce timing attack problems? In a cryptographic implementation I’m playing with, there’s a round function which includes a conditional if statement.

Stripping the superfluous stuff, the C sourcecode looks like this:

void f(uint32_t *state) {
    …
    for(round = 0; round < 12; round++) {
        // functions working on state
        …
        if((round & 3) == 0) {
           // additional functions working on state
            …
        }
        …
    }
    …
}

Trying to check if this might introduce timing attack problems, I looked at cryptocoding.net which states:

  If a conditional branching (if, switch, while, for) depends on secret data then the code executed as well as its execution time depend on the secret data as well.

This seems to hint at the fact that, as long as the if function does not depend on the state itself (which is meant to be handled as secret), there should not be a problem because if in this case depends on the round number and not the secret state.

Is my interpretetion indeed correct, or does that if represent a potential problem regarding to timing attacks? In case my interpretetion is wrong and it represents a timing attack problem, would unrolling the loop (manually by rewriting the code) be a valid way to mitigate it?

Unless the number of rounds is secret, this does indeed not represent a secret-dependent branch.

(If the number of rounds is secret, a chap named Auguste would like to have a word with you.  Hope you speak French or Dutch as they were spoken a century ago.)


Why does WPA-PSK not use Diffie-Hellman key exchange? Is there a reason, why in pre-shared key mode, Wi-Fi session key is not secured with something like Diffie-Hellman but instead is derived from PSK key and some information exchanged in clear during sign-on?

As Thomas pointed out in his comment, in WPA-PSK the parties already have a shared secret (the pre-shared key), so there is no need to go through the step of Diffie-Hellman key-exchange -- unless you want perfect forward secrecy (PFS) (see update below).

In WPA, the client and the access point goes through a step known as the "4-way-handshake" to verify that the other party is in possession of the pre-shared key and to derive session keys for actual (encryption/authentication) usage. This step involves nonces from both sides, and some cryptographic computations, with the end result that 1) both parties can verify that the other party is in possession of the common secret and 2) they both have derived a shared session key which they will use for the actual encryption.

The picture below shows the steps in this process. The Supplicant is the client and the Authenticator is the access point. The PMK is the shared secret. In a typical home-user setup, the PMK is usually derived from a password using PBKDF (this password is what you normally punch in when connecting to a wireless network). The PTK is the derived key that they end up actually using for encryption.

UPDATE

As mentioned in the comments, the above does not actually answer why WPA-PSK does not use DH. However, before discussing that, let's clarify what DH has to offer over what's currently being used, and also why the use of pre-shared keys diminishes some of those advantages.
I claim that the one big advantage of using DH is that if offers perfect forward secrecy (PFS), while the ability to "separate" users from each other on the same WLAN is more debatable.

First we need to be clear about the kind of attacks we want -- and can -- be able to protect against.

Outsiders, i.e. attackers not knowing the PSK: If the PSK contains sufficient entropy (either drawn completely at random from a big key space or derived from a sufficiently long/complex password) and the PSK is kept safe and never leaked then DH does not offer anything over the current solution.
If, however, the PSK is either lost or derived from a weak password, then the current system is completely broken. The reason is that the session keys are completely derived from the PSK, hence anyone who knows this can decrypt all traffic. Even worse, since it does not offer PFS, an attacker can go back an decrypt all previous traffic as well. The use of DH would prevent this. Since in practice most home WLANs uses a weak password to derive the PSK, DH would indeed be an upgrade.
Insiders, i.e. attackers knowing the PSK: Now consider the scenario where the attacker knows the PSK. What could the handshake offer then? As mentioned above, with the current system the answer is nothing.  So what about DH? Assuming that in this scenario the PSK is only used to authenticate the DH exchange (say with a MAC), the DH would still offer security against a passive attacker, while nothing against an active attacker. Why? In the passive scenario, the attacker has to break the DH exchange which we assume is intractable. On the other hand, in the active scenario, the attacker can do a classic MitM attack, since he can forge valid handshake messages. Thus, under the typical conservative approach taken in formal security models, we would conclude that DH offers no security benefits over the current scheme since we always assume that the attacker is active. However, in practice, conducting an active MitM attack can sometimes be tricky to pull of. Thus, using DH significantly increase the cost and difficulty for the attacker. Since it forces him to be actively present during the hand shake, this also prevents large-scale passive snooping.

So to conclude, using DH would provide huge benefits in the sense of providing PFS. Also, it also provides some degree of protection of insider attacks, as long as the attacker stays passive.

So why was the 4WHS not designed to use DH?

Full disclosure:
this will just be speculation on my part, since I do not know the arguments that went in to the design decisions of the IEEE 802.1i standard.

I guess that at the time WPA (or more correctly IEEE 802.11 RSNA) was designed, the value of PFS was probably not fully appreciated. In hindsight of the NSA revelations, it is of course easy for us to understand its importance now, but at that time it might not have been so clear. Thus, if you are not required to have PFS, and you already have a PSK available to your protocol, then there is a very simple reason why DH would not be used: efficiency. Symmetric primitives are much much more efficient than public-key primitives, hence if you can get away with only using that, the choice is obvious.

*Incidentally, the IEEE 802.11 standard actually do support a DH-based key-exchange built on a password-based AKE called Dragonfly. However, this variant is only used when the network is in ad-hoc mode.


What is difference between Yao's "Garbled Circuit" and ther "Garbling Scheme" given by Bellare et al? What is difference between Yao's "Garbled Circuit" and the "Garbling Scheme" given by Mihir Bellare, Viet Tung Hoang and Phillip Rogaway in "Foundations of garbled circuits"?

I also want to know is it possible to use the garbling scheme / garbled circuit for multi party computation or it is only for 2 party computation.

Link for garbling scheme is given in :
Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. 2012. Foundations of garbled circuits. In Proceedings of the 2012 ACM conference on Computer and communications security (CCS '12). ACM, New York, NY, USA, 784-796. DOI: http://dx.doi.org/10.1145/2382196.2382279

Yao's garbled circuits is a generic protocol for two-party computation, which uses garbled Boolean gates along with oblivious transfer in a specific two-round protocol with a generator and an evaluator. Bellare, Hoang, and Rogaway's paper proposes a security model for garbling schemes themselves (i.e. the operation performed on individual gates in Yao's protocol) along with some constructions of garbling schemes.

Yao's protocol can be generalized to multiple parties, but those settings are usually better served by a protocol that generically supports many parties, such as GMW.


AEAD (for AES128-GCM): is it necessary to add a zero-length AAD? In an implementation of AEAD_AES_128_GCM, if the AAD is defined as a "zero-length octet sequence", is it necessary to call the encryption code that adds an AAD at all? In particular, does an OpenSSL/LibreSSL libcrypto client need the EVP_En/DecryptUpdate invocation that adds the AAD, if its length is 0?

I'm working on an implementation of RFC 8188, a protocol for encrypting HTTP messages with AEAD_AES_128_GCM, which has this to say:

   The additional data passed to each invocation of AEAD_AES_128_GCM is
   a zero-length octet sequence.

Currently my test code (just in a mockup stage) has this:

static const unsigned char *aad = (const void *)&aad;
static const int aad_len = 0;

#if 0
    /* XXX not sure if this is necessary, examples work with & without */
    if (EVP_DecryptUpdate(&ctx, NULL, &len, aad, aad_len) != 1) {
        ERR("decryption: adding aad");
        return -1;
    }
#endif

The resulting code produces the expected decryptions and intermediate values for the examples in chapter 3 of the RFC. As you can see, this part is #if 0-d out, so in fact nothing is done to add an AAD.

Since this may seem like a remarkably silly question (already I'm pre-emptively embarrassed), let me explain why I'm asking:

The RFC has all of two examples, both of which decrypt ciphertext to "I am the walrus" (with two different record sizes). So the "it works" result may be a lucky accident of sparse test data.
Since the RFC goes to the trouble of saying "zero-length octet sequence", rather than something like "there is no AAD", it feels like there might be a reason for putting it that way.
An assumption on my part, a crypto layman, that "it's zero-length so I don't have to do anything" feels like the sort of thing that leads to errors and insecurity in code that uses cryptography. Operations on zero-length structures don't always mean the same thing as "do nothing" (consider SHA hashes of the empty string).

So I thought I'd ask others if there might be more going on here than meets the eye.

AES-GCM does not support ‘no AAD’ as distinct from ‘zero-length AAD’.  See NIST SP800-38D for details of how it works internally: the AAD is padded with zeros so it is a multiple of 128 bits long, and the length is hashed in at the end.  If the AAD is zero-length, then zero bits of padding are added and no time is spent hashing any AAD or AAD padding.

  Let $u = 128\cdot\lceil\operatorname{len}(C)/128\rceil - \operatorname{len}(C)$ and let $v = 128\cdot\lceil\operatorname{len}(A)/128\rceil - \operatorname{len}(A)$.
  Define a block, $S$, as follows: $$S = \operatorname{GHASH}_H(A \mathbin\| \mathtt 0^v \mathbin\| C \mathbin\| \mathtt 0^u \mathbin\| [\operatorname{len}(A)]_{64} \mathbin\| [\operatorname{len}(C)]_{64}).$$

  …

  In Steps 4 and 5, the AAD and the ciphertext are each appended with the minimum number of ‘$\mathtt 0$’ bits, possibly none, so that the bit lengths of the resulting strings are multiples of the block size.

  —NIST SP800-90A, §7.1 ‘Algorithm for the Authenticated Encryption Function’, p. 15 (emphasis added)

Note that if the AAD $A$ is empty, then $\operatorname{len}(A) = \lceil0/128\rceil = 0$, so $\lceil\operatorname{len}(A)/128\rceil = 0$, and thus the number of ‘$\mathtt 0$’ bits appended is $$v = 128\cdot\lceil\operatorname{len}(A)/128\rceil - \operatorname{len}(A) = 128\cdot0 - 0 = 0.$$  In other words, if $A$ is empty, then the prefix $A \mathbin\| \mathtt 0^v$ is also empty.

But it is a good intuition to wonder whether ‘no AAD’ and ‘zero-length AAD’ are distinct!  There are many applications that do make such distinctions, often to the advantage of adversaries or at least to the frustration of legitimate users.


Brute-force attacking One Time Pads feasible? I have a ciphertext encoded with One Time Pad. I do not know the key. How can I find the possible keys which when decoded, will result in a meaningful plain text?

The interesting property for the one time pad is that every plausible plaintext (given the length constraint, i.e. of same length as the ciphertext, maybe including some padding) has a corresponding key which produces a certain ciphertext.

As mentioned in the comment by CodesInChaos, this key can be retrieved by simply XORing both plaintext and ciphertext (if you are using the XOR variant of the one time pad ... for the addition variant you'll have to subtract).

Also, assuming a random key, every plaintext has the same probability, given the ciphertext, as it has without knowing the ciphertext (apart from the length).

This is known as perfect secrecy – you can get no information from the ciphertext about the plaintext which you didn't know before (apart from the length, but this can be hidden to a certain degree by padding, too).

Every cryptosystem with the perfect secrecy property must have a key as least as long as the messages, and each key must be used only once. This is why a one-time pad or other perfect encryption systems are not used often in practice.


Can one make a secure AEAD from any secure cipher and any secure MAC? Can one make a secure AEAD from any secure cipher and any secure MAC using encrypt-then-MAC:

with independent keys and IVs (any cipher and MAC)
if the cipher is a stream cipher (including a block cipher in CTR mode), using parts of the keystream (not used to encrypt plaintext) as the MAC key or keys and IV?

If so, then all of the following would be secure:

A stream cipher plus GHASH (of which GCM becomes a special case), with the stream cipher being used to mask the GHASH output.
A stream cipher plus any other Wegman-Carter authenticator, such as Poly1305, again with the stream cipher used to mask the output
A stream cipher plus HMAC.

Proof of the first two cases: since encrypt-then-MAC is secure we need only to show that

this is in fact an encrypt-then-MAC construction.
that the MAC is secure (we already know by assumption that the stream cipher is secure).

Firstly, we can assume that the parts of the keystream used for the MAC and to encrypt plaintext are independent, as any dependencies would be a distinguisher against the stream cipher.  Therefore:

is true because the construction uses a stream cipher to encrypt the plaintext, then applies a MAC to the ciphertext.

is true because the stream cipher is a secure PRF, so there is no way (for a resource-bounded attacker) to compute the (secret) MAC key (and block used to encrypt the MAC) from the (potentially known to attacker) part of the keystream used to encrypt plaintext.  Therefore, the attacker has no knowledge of the internal state of the MAC, and so the composition is secure if the MAC is.  For most Carter-Wegnam MACs, this is known unconditionally.

I have seen various special cases proven secure, but not the general case.

The encrypt-then-MAC paradigm works as long as the encryption is CPA secure and the MAC is secure under the standard definition. However, such a MAC must be secure for multiple messages. Therefore, using GHASH or Wegman-Carter authentication is not sufficient. (Indeed, in GCM, the result of GHASH is masked and not directly output.)

The proof of the general composition appears in two papers: The order of encryption and authentication... by Hugo Krawczyk, and Authenticated encryption: relations among notions... By Mihir Bellare and Chanathip Namprempre.

It is important to note that the paper by Krawczyk actually shows that in some important cases it is secure to MAC-then-encrypt. However, this is only true when the operations is atomic and it is impossible to know whether the MAC was incorrect or another error occurred.

However, in practice this is almost impossible to do right and has been the cause of multiple attacks on SSL over the past years. Therefore, this part of the paper should not be seen as saying that it's OK to every MAC-then-encrypt.


Randomness of Decision Learning With Error Problem I read the statement of the Decision Learning with error problem is:

distinguish between $(\vec a, \langle \vec a, \vec s \rangle + e)$ from uniformly random samples.

Can anyone explain what does it mean to distinguish $(\vec a, \langle \vec a, \vec s \rangle + e)$ from random samples?  Does it mean subjecting $(\vec a, \langle \vec a, \vec s \rangle + e)$ to some statistical test for randomness?
From what I understand a and e are both randomly sampled from a uniform distribution,  So why would $\langle \vec a, \vec s \rangle + e$ not look like random data?  Is it saying that $\langle \vec a, \vec s \rangle + e$ is a one-way hash function?

As Peikert has commented (and my first answer was not dealing with this issue carefully), the LWE problem asks you to distinguish between
$(\vec a, \langle \vec a, \vec s \rangle + e \mod q) \in \mathbb{Z}_q^{n+1}$
and $\vec u \in \mathbb{Z}_q^{n+1}$ (with each entry of $\vec u$ sampled uniformly from $\mathbb{Z}_q$) given many samples.

This is why the LWE problem is usually defined with a parameter $m$, which represents the number of samples
$(\vec a_i, \langle \vec a_i, \vec s \rangle + e_i \mod q)$
that you can get. Notice that all the samples use the same fixed secret $\vec s$.

The problem says nothing about how you are going to distinguish those two distributions. Given many samples, if you run an statistical test or some clever algorithm using lattices, it does not matter, as long as you can tell to which distribution those samples belong.

And about $b_i := \langle \vec a_i, \vec s \rangle + e_i \mod q$ being distributed uniformly on $\mathbb{Z}_q$, indeed, if you have a single sample, then that is the case, but again, if you have several samples, say, $m$,
then, the distribution of $(a_i, b_i)_{i=1}^m$ can possibly be distinguished from the uniform over $\mathbb{Z}_q^{n+1}$.
In particular, if you can recover $\vec s$, then you can simply compute $b_i - \langle \vec a_i, \vec s \rangle \mod q$ to get $e_i$, which are all small, thus, not uniformly distributed.

A final note, in your question you say "From what i understand a and e are both randomly sampled from uniform distribution", but actually, only $\vec a$ is uniformly chosen from $\mathbb{Z}_q$, the noise term $e$ usually follows a distribution that is likely to sample values much smaller than $q$ (like a Gaussian distribution with parameter approx. $\sqrt n$).


RSA Proof - di-mgt - modulo properties I´m trying to follow one of the very detailed RSA Proofs given by di-mgt: "RSA theory", but unfortunately I stuck at the beginning of solution (chapter 3).

I don´t understand where the second part of (8) is coming from:

$RsaPrivate(RsaPublic(m))\ =\ (m^e\ mod\ n)^d\ mod\ n\ =\ m^{ed}\ mod\ n$

How is it reduced? Where can I find this rule?

You'll probably know this relation, which should be obvious if you think about it:

$$(a \bmod n) + (b \bmod n) \equiv a + b \mod n$$

This means that when using addition you do not have to reduce the operands, only the final result. However, if the final result is an operand again it needs not be reduce. This means that long chains of modular additions can be computed using normal additions with one reduction at the end.

You can see $a\times n$ as a series of additions:

$$a\times n = \overbrace{
    a + \cdots + a
   }^{n \text{ times}}$$

You can see $a^b$ as a series of multiplications:

$$a^b = \overbrace{
    a \times \cdots \times a
   }^{b \text{ times}}$$

So we can see $a^b$ as a very long series of additions of the base. Thus we do not need to reduce the base:

$$(a \bmod n)^b \equiv a^b \mod n$$


Can non-assembly crypto libraries truly be secure against timing attacks? http://cr.yp.to/antiforgery/cachetiming-20050414.pdf states the following:

  So what went wrong? Answer: NIST failed to recognize that table lookups do not take constant time. “Table lookup: not vulnerable to timing attacks,” NIST stated in [19, Section 3.6.2]. NIST’s statement was, and is, incorrect.

Sections 10 - 15 (inclusive) of that paper propose that changes be made to how things are placed in the L1/L2 caches of the CPU to remedy the issue. However, you're only ever really going to be able to control what's in the L1/L2 cache with assembly.

So how secure can non-assembly code truly ever be against timing attacks?

In the case of AES the afore mentioned paper says that you can get closer to constant time by doing away with the s-box lookups but even then it seems that there could still be issues with what's in the L1/L2 cache. If not with the s-boxes then with the plaintext and ciphertext themselves or the various components of the key schedule.

So how secure can non-assembly code truly ever be against timing attacks?

First of all, let me state that this is a tricky subject.

The simplest method is of course to do away with the lookup tables or and other components that are vulnerable to timing attacks. So when a cipher designed, it should require a minimum of vulnerable components. And during execution a minimum of vulnerable constructs should be used to be absolutely secure. For instance AES can be implemented in various ways - some are more secure than others when it comes to side channel attacks. This is all stated by DJB in the paper as well.

It is extremely hard for a native library to control cache timings too. Generally libraries are generally not constructed for a specific CPU. It may be almost impossible to control and measure how the cache handling is performed - or even how much cache is present. So in that sense machine code is (almost) as vulnerable as non-native code.

One way to conquer such complexity is to have a CPU instruction, co-routine or co-processor perform AES. Such an instruction can be designed from the ground up to be invulnerable to timing attacks. If designed well it is completely independent from cache and memory and thus from side channel attacks that rely on them.

The fact that non-native code cannot directly control the instructions and memory addresses doesn't mean it cannot control it at all. Often you can still analyze what happens at a lower level. For instance, an array in Java is not stored in reverse. You know from the specifications that it will be a single, sequential block of data somewhere in memory.

If you are stuck with things like tables then you have various options. You can for instance make sure that an attacker simply does not have enough access to perform an attack. It may be hard for an attacker to put a table on two different pages in memory, for instance.

It may also be hard for an attacker to gain enough timing information. Almost any timing information may be extracted using statistics. But just like brute forcing, it may be that the amount of data required is too high for a practical attack.

Unfortunately this page is not large enough to discuss all measures that can be taken against side channel analysis, and then validate if they are secure for machine code and high level languages. Yes, there are constructs that are valid for both (RSA blinding is probably the most well known one). Is RSA blinding enough to show that code is secure against timing attacks? Probably not.

Note that pretty often the answer to the question is: we haven't tested the code against side channel attacks and hope our algorithms and protocols are secure enough.

One way to battle this in an organization is to buy a HSM (or TLS offloader or other secure system) which should be secure against side channel attacks, basically side stepping the issue completely. These things can be very expensive, but if you require the highest protection against side channel analysis you may have a lot to lose as well.


Elliptic Curve Cryptography, decrypting returns false result I build some application to encrypt and decrypting some text using ecc

My curve paramaters are

p = 59
a = 2
b = 2

resulting in 64 points including infinite point.

for encrypt and decrypt process i use

e1 = (3, 25)
d (private key) = 53

Here's the problem that i faced

let say i want to encrypt point (45, 48)
first, i generate random number k = 47 and i calculate e1 * k

C1 = k * e1
   = 47 * (3, 25)
   = (43, 57)

C2 = P + k * e2
   = (45, 48) + 47 * (53 * (3, 25))
   = (28, 11)

But, when i decrypt the c1 and c2

M = c2 - d x c1
  = (28, 11) - 53 * (43, 57)
  = (43, 57)

I tried to check my calculation in online calculator, but the result is not even in the curve

Can someone explain to me why? where did i go wrong?
Sorry for my english
Thank you

I would imagine your calculator doesn't know how to handle the point at infinity because it relies fully on affine points. You can compute that

\begin{align*}
    C_2 &= P + k*e_2 \\
        &= (45,48) + 47*53*(3,25) \\
        &= 5*(3,25) + 47*53*(3,25) & (\text{since }(45,48) = 5*(3,25)) \\
        &= 2496*(3,25) \\
        &= \infty & (\text{since }2496\equiv0\bmod 64)
\end{align*}
This computation seems to go wrong somehow, possibly because it can't represent $\infty$ internally.


Why the $IV$ used in Merkle–Damgård has to be fixed to a specific value? I just can't figure out why on earth the $IV$ in Merkle–Damgård has to be fixed (that's what the Katz-Lindell book says)? Because even if you choose it randomly from say $\{{0,1}\}^n$ then the resulting construction still remains collision-resistant, or not?

One reason is convenience: if the IV was variable, it would have to be transmitted to a party verifying the hash, and we'd have to deal with its integrity.

Another reason is that it avoids an attack in a Merkle–Damgård variant with padding reduced to appending a single 1 bit and as many zeros as necessary to end the block. With such scheme and common compression functions, like the ones in MD5, SHA-1, and the SHA-2 familly, ability to choose the IV implies ability to chose a secret prefix that does not change the hash.

Notice that the compression function $C$ used in these hashes is of the form
$$(X,K)\rightarrow C(X,K)=X\tilde+ E(X,K)$$
where $X$ is the current state (initially the IV), $K$ is the block to hash, $\tilde+$ is a variant of addition (with a few carries suppressed), and $X\rightarrow E(X,K)$ is a reversible block cipher with key $K$.

Who defined an $IV$ that's not a nothing-up-my-sleeves number could have chosen a secret one-block $K$, computed $IV = E^{-1}(0,K)$, which insures $IV=C(IV,K)$. That allows insertion of $K$ at the beginning of any message, without changing the hash.


How can I generate a one-time password? Through my reading about the generation of one-time password (OTP) I found that there are many algorithms that generate OTP and they are either based on time such as TOTP or based on mathematical computation such as HOTP and S/Key.

The problem is they do not depend on some parameters to generate OTP.

What I would like to know is which one I can use to generate OTP using hash function and some session tokens (IP address, etc.).  These tokens will be used as parameters of the hash function. Of course, I would prefer options that are secure and hard to break.

It sounds like you're trying to improve the security of OTP schemes by adding extra "random-ish" data. My answer will address that, please update your question if that is a wrong interpretation.

These schemes don't literally have multiple inputs that you could feed this extra data into, but you don't need them to. For example, with HOTP the security of the function lies in the secret key. If it's strong, you have nothing to gain by incorporating outside data like IP addresses that are neither random nor private.

It sounds like the problem is that you don't trust the key to be secure and you want to augment the security by throwing in a variety of other factors. But instead, just focus on generating a good key. Instead of having your OTP scheme take input from a variety of sources, you should have your key generation take input from a variety of entropy sources. All of your entropy, which might include things like network addresses, is then mixed together in one step, used to generate a key in another step, and then the key is finally plugged into an existing OTP scheme. Then your OTPs will be dependent on some of the data that you mention here.


What information to include when calculating the HMAC of ciphertext I'm aware that it's crucial to include the IV when calculating the HMAC of a ciphertext (assuming an IV is used).  Can anyone explain, in simple terms, why this is?

Furthermore, assume that there is other metadata associated with the cipher, which needs to be known to correctly decrypt the ciphertext (for example, the type of algorithm used, the mode, options such as configurable block size, etc).  Is there any sense in including this information when calculating the HMAC?  Or on the contrary, is the any reason not to?

Yes, it is best to include all that information in the HMAC. Otherwise an attacker can change those values and you would not get the correct plain text. This would mean that you get either incorrect information, or you leak information that could be used for padding oracle attacks.

In case of the IV, if you don't include it in the HMAC then the attacker can change the first block of plain text you get when you decrypt the first block (assuming CBC mode encryption here).


Proof of elliptic curve difficulty Are there any proofs that cryptographic functions on an elliptic curve are any more difficult than the analogues over modulo arithmetic?

While at present, ECC appears to be more difficult, as it is not as advanced as research into RSA etc., it seems to me there should be no reason why ECC is much stronger than, say, RSA and that the advantage of shorter keys might just be temporary.

I was wondering if there were any proofs that ECC was at least as strong as RSA etc. such that if you use a 2048 bit ECC key, then it is at least as strong as 2048 bit RSA key? I.e., ECC is not weaker than RSA for a given key length?

There are very few non-trivial proven lower bounds in computational complexity, and none whatsoever in cryptography, as far as I know.

Almost all results are of the form "If X is infeasible, then so is Y." For example, "If AES is a secure pseudo-random function, then so is CBC-AES given parameters such-and-such."

RSA and traditional Diffie-Hellman use integers and finite fields (integers modulo a prime). Those mathematical objects have, in some ways, "too much structure"; there are short cuts to factoring and to discrete log, so you have to use much larger keys than you would expect if you did not know about those short cuts.

As far as anyone knows, elliptic curves have "just enough" structure to do cryptography, but no additional structure that can be exploited to extract discrete logarithms via some short cut. That is why the number of bits for EC algorithms is generally chosen to be something like twice the symmetric key length, instead of something like 2048+ bits for RSA.

If you want some mathematical details, this thesis has a good overview:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.132.6034&rep=rep1&type=pdf

But again, none of these problems have been proven to be intractable. Maybe there is some linear-time factoring algorithm out there. Maybe elliptic curves -- or the particular curves approved by NIST -- have some unknown structure that could allow discrete log approaches with comparable complexity to those for finite fields. Maybe the NSA's mathematicians have found that structure ahead of everybody else...


Unbreakable Hill cipher Why don't we use hill cipher of 100 × 100? or even bigger. That would be closely unbreakable.
The number of keys possible 2 × 2 hill cipher is 157248. for 100 × 100 number is beyond limits.

The Hill cipher is vulnerable to known-plaintext attack. Once the attacker gets $n$ plaintext/ciphertext pair it can break the cipher by solving a system of linear equations. Consider AES, it is not proved but considered secure against known-plaintext attack, see this question for details.

And, also, key size itself doesn't represent the security. High key sizes are necessary but not sufficient. As an example from history, Enigma was beyond its time as having around $87$ to $88$-bit key size which is greater than the key size of DES. We have already know that Enigma is broken.

Answer to comment: We work in Kerckhoffs's principles and are not accepting security by obscurity. So the attacker knows everything but the key.


How many attempts does it take to crack a 32-bit password hash with this scenario? How many attempts does it take to crack (match) a 32-bit password hash from a database of 4 million password hashes?

Correct me if I'm wrong, but to crack a 32-bit password hash would take roughly 2^31 attempts, while the math for matching a 32-bit hash from 4 million hashes should take (2^31)/4M ~ 537 attempts.

However in reality, the 4 million passwords in the database are not unique, as certain combinations are used as common passwords. Thus, what would be a more accurate calculation of the above question?

Correct me if I'm wrong, but to crack a 32-bit password hash would take roughly 2^31 attempts, while the math for matching a 32-bit hash from 4 million hashes should take (2^31)/4M ~ 537 attempts.

It would take on average $2^{32}$ attempts to crack a single 32-bit hash.

If you've got 4 million unique hashes to test against then then each hash you generate you've got a $4,000,000(\dfrac{1}{2^{32}}) \approx \dfrac{1}{1073}$ chance of finding a matching one. So you're going to need to try on average $1073$ times.

Unless you know the distribution of passwords and which ones are more common than others and you incorporate that into your guessing, this is as accurate as it's going to get.


Why use HKDF for key derivation even it's not time demanding? KDF such as scrypt is memory (cpu) demanding so that the attackers cannot quickly decrypt the key.

Why use HKDF?  What's the application of it?
If the attacker knows the input space of HKDF, and since the procedure of HKDF is public, what's the extra benefit of using it?

HKDF is not used to generate a secret key from a public input or a low-entropy password. It's used to derive a key from some secret input (e.g., a DH result) with high entropy.


Complement property of DES I'm supposed to show the complement property of DES ($c=DES(p,k) => \bar c = DES(\bar p, \bar k)$).

My idea was to just start the algorithm with $\bar p$ and see what happens (ignoring the initial permutation for now). I looked at it step by step and got the the point where $R1 = \bar L1 \oplus f(\bar k1, \bar R0)$. So I figured I had to show that $f(\bar k1, \bar R0) = \bar f(k1,R0)$. Is that even right so far? Because I got stuck at the point where the S-Boxes are used. Why would $S(\bar x) = \bar S(x)$?

Somewhere else I read something about a formal prove using induction, but I don't know how I would do that either...

I think I got it:
I'm going to show that after round i the result will be $\overline{L_i}$ and $\overline{R_i}$ when the input was $\overline{L_{i-1}}$ and $\overline{R_{i-1}}$ and using $\overline k$ as key.

$L_i=R_{i-1} \implies \overline{L_i} = \overline{R_{i-1}}$

$\overline{R_i} = \overline{L_{i-1}} \oplus f(\overline{R_{i-1}}, \overline{k_i}) = \overline{L_{i-1}} \oplus f(R_{i-1}, {k_i}) = \overline{L_{i-1} \oplus f(R_{i-1}, k_i)}$.

$f(\overline R, \overline k)=f(R, k)$ because within the fuction the complement of expansion(R) and $\overline k$ are xored which eleminates the complement.

That way round the final result will be $\overline c$ when using $\overline m$ as input and $\overline k$ as key. The initial permutation does not change that.


Crypt-analysing modified AES algorithm with no shift-rows, and no key-expansion I came across an answer about consequences of AES without any of its operation In the question in the given link, it is mentioned that "if Shift Row is removed, then attacker can treat input block ($128$ bits) as $4$ independent $32$ bits block. Hence, attacker can attack these $4$ blocks one by one to recover key." I did not understand this statement. I request the community to please help me understand this question.

Since AES is block cipher, we have to encrypt each 16byte block at once, but how can we divide that 16byte into blocks of 4 bytes? If I have a plaintext-ciphertext pair of 16bytes, will it be enough to recover the key? If yes, then how?

AES works by operating on the 16 input bytes as a 4x4 matrix of values. The state looks like:

$$\begin{bmatrix}
    x_{1}       & x_{5} & x_{9} & x_{13} \\
    x_{2}       & x_{6} & x_{10} & x_{14} \\
    x_{3}       & x_{7} & x_{11} & x_{15}\\
    x_{4}       & x_{8} & x_{12} & x_{16}
\end{bmatrix}$$

Sub Bytes

The subBytes operation operates on one entry of the state at a time, and it replaces the value of each entry $x_{n}$ with another value.

Mix Columns

The mixColumns operation operates on a column at a time, independently:

$$\begin{bmatrix}
    x_{1}\\
    x_{2}\\
    x_{3}\\
    x_{4}
\end{bmatrix}
\begin{bmatrix}
    x_{5}\\
    x_{6}\\
    x_{7}\\
    x_{8}
\end{bmatrix}
\begin{bmatrix}
    x_{9}\\
    x_{10}\\
    x_{11}\\
    x_{12}
\end{bmatrix}
\begin{bmatrix}
    x_{13}\\
    x_{14}\\
    x_{15}\\
    x_{16}
\end{bmatrix}
$$

and it outputs a new column such that each entry in the column depends on all of the entries in the column.

Shift Rows

The shiftRows operation transposes individual entries from each column so that each output column consists of 1 entry from each input column:

$$
\begin{bmatrix}
    x_{1}       & x_{5} & x_{9} & x_{13} \\
    x_{2}       & x_{6} & x_{10} & x_{14} \\
    x_{3}       & x_{7} & x_{11} & x_{15}\\
    x_{4}       & x_{8} & x_{12} & x_{16}
\end{bmatrix}
\rightarrow
\begin{bmatrix}
    x_{1}       & x_{5} & x_{9} & x_{13} \\
    x_{14}       & x_{2} & x_{6} & x_{10} \\
    x_{11}       & x_{15} & x_{3} & x_{7}\\
    x_{8}       & x_{12} & x_{16} & x_{4}
\end{bmatrix}
$$

Removing Shift Rows

If you don't use the shiftRows operation, then there is no mixing of values between columns of the state. The state would effectively consist of four separate columns that do not influence each other.

Since there are four 8-bit bytes in each column, each column would effectively become a 32-bit permutation, instead of the 128-bit permutation that AES is supposed to be.

Breaking it

32-bits is easily within the range of brute force, and is usually considered small enough to be amenable to a lookup table. While you would have to perform 4 separate 32-bit brute force attacks to recover the key, this does not take nearly as much time as a single 128-bit brute force attack. This is because each column can be attacked independently and in parallel.


Hash functions to the power of two and three notation I have found in a Wireless Sensor Networks security paper, operations where cryptographic hash functions are elevated to the power of 2 and to the power of 3 (i.e. $h^2(x)$ and $h^3(x)$).

This might be a very simple question but I haven't found this notation in other literature. I wonder: does this notation mean that you need to compute the hash twice or thrice (i.e. $h(h(x))$ and $h(h(h(x)))$?

In the paper, $h$ is defined as a collision free one-way hash function.

Yes, these notations always seem to mean that H^n(x) (or $H^n(x)$ in mathematical notation) means that $x$ is the first input, and that the next outputs are a hash of the previous output:

H^0(x) = x           // just defined as x below
H^1(x) = H(x)
H^2(x) = H(H^1(x)) = H(H(x))
H^3(x) = H(H^2(x)) = ... = H(H(H(x)))
H^4(x) = ............... = H(H(H(H(x))))
...

so another way to define it is $H^n(x)=H(H^{n-1}(x))$ where $H^0(x)=x$. I've used uppercase H as that seems to be more common.

The construct seems to comply with the exponentiation property within abstract algebra as only the less strong power associativity is required for the function composition of the (hash) functions (beware - the answer on the math site requires some mathematical background).

Usually this kind of construction is used for key stretching; a method of calculating a key from a password (or other low entropy secret) that includes a work factor. In other words, both the user and an attacker are required to perform a number of operations, which makes attacking the password harder.


How to use Botan to verify a web3 wallet/password? The specification here seems quite clear, but unfortunately I'm still doing something wrong...
I have this (single small c++ file) repository which very straightforwardly follows the password/wallet verification process. However, the result of my cryptographic operations do not match with the wallet's mac key (the signal that the password is correct).
I have verified that thisisatestwallet.json (included in the repository) does open with the password thisisatestwallet, and the spec seems so simple there isn't much room for me to screw up. And yet...
If anyone could glance at that and tell me what I'm doing wrong, I'd appreciate it!
The output I'm currently getting is as follows:
pkey:           2F299FEF2CA3390C63DABA7A13BA4CE9D60B7FC1E58DAFD5E1089D32CFD7219C
ciphertext:                                                                     C6D18F78AF6E5E7CEA4AB804D8B9A5F974CCF92EA2537416B90ABEBD77C6B580
cipher input:                                   D60B7FC1E58DAFD5E1089D32CFD7219CC6D18F78AF6E5E7CEA4AB804D8B9A5F974CCF92EA2537416B90ABEBD77C6B580
keccak out:     7D31B612939A26418CAB1DF332D27B711CAACAA7A119013A01E1DB75DE508DAA
mac:            89655FD4BB9CCF9DE0D8F1A78025A8616C9416EC700CFAAFEF17E76C7C47338E

Ah, the misunderstanding was that the spec says SHA-3 (Keccak-256), which I had assumed was SHA-3-256, but is actually Keccak-1600(256), which is part of the SHA-3 standard. Fixed.


Elliptic Curve Cryptography Encryption and text representation implementation I'm writing a coursework and right now I've implemented the ECDSA algorithm, but I also need to encrypt and decrypt small text files (.txt) using elliptic curve cryptography.

The problem is that I do not know how to represent the message in the file.

I don't know your exact scenario. However you have two options to encrypt data using elliptic curve cryptography (ECC). I'd recommend going with the first option I present.

Use elliptic curve integrated encryption scheme (ECIES). ECIES basically performs ElGamal-like encryption on a key. The key is generated at random and encrypted like in ElGamal (replace the multiply operations with add operations). One then can use this symmetric key to symmetricly encrypt and authenticate the data. ECIES defines how to exactly do that. You then go ahead and simply process the data as you normally would using a symmetric encryption scheme.
Use generalized ElGamal on elliptic curves (no abbreviation, likely never deployed or proposed outside of ECIES). You can as well simply use the generalized ElGamal construction and somehow represent the data you want to encrypt as a point on your curve (which is harder than it sounds).I do not recommend this method. The reason is that you're limited to a message space of 256 to 512 bit (32-64 bytes) and that representing your message may actually be quite difficult, as the reconstruction of the message data from the "decrypted" point won't be easy.

If you're question was only aiming at "How can I represent my bytes in the textfile for the encryption?", then by using approach no. 1 the solution is rather straightforward and with approach no. 2 you have to invent some scheme yourself to aid re-construction. This could go as follows:

Represent your message as octet string $B$.
Convert the octet string to an integer $b$.
Initialize $c=0$
Check if $b$ is a valid x-coordinate on your curve, if yes go to step 6
Set $b=b+1$ and $c=c+1$ and go to step 4
Encrypt the data and append $c$ (maybe with some sort of separator)

Reconstruction should be more easy. You retrieve $b$ by decrypting the message and setting $b$ to be the x-coordinate of the resulting point. Now you simply subract $c$ from $b$ yielding the original $b$ value and making you able to reconvert the integer to a byte array (the text in your file).

Note: If an attacker tampers with $c$, he can let you decrypt the ciphertext to arbitrary messages. Because of this property you should always prefer ECIES.


Adding parameters to sponge's capacity Is it safe to XOR parameters like domain, length of the message or block counter into sponge's capacity or that gives attacker control over capacity?

For example NORX XORs domain into capacity.

Does this break sponge security proofs?

What about adding bit into capacity to denote that there was no padding since message was multiple of rate and therefore reducing number of permutation function executions?

PRIMATEs use padding spilling which is similar to no-padding bit. Their paper says:

  Note that the spilling of the padding in case |M[w]| = r causes
  security to degrade by half a bit: intuitively, APE is left with a
  capacity of c' = c - 1.

However, it looks like this doesn't apply to HANUMAN and GIBBON which also use the same padding spilling.

It is safe to xor parameters into the sponge as long as they are uniquely encoded so that they can't be confused with part of a message.  The same goes for padding: if two distinct messages are treated the same way because you skipped padding, you're in trouble; e.g., if you use a length prefix then no padding at the end is necessary but you need to know the length up front.

This is not like JWT where the adversary can change one part of the JSON like the algorithm tag to control what algorithm the receiver uses to verify the rest of the JSON: you can't recover parameters from a hash anyway if it's worth its salt as a hash, so legitimate users aren't even temped to do that.

Even better, hashing the parameters means that an adversary can't reuse a hash made with one set of parameters for an application that uses another set of parameters—hashing the parameters makes the hashes used by the two applications essentially independent.

As a pathological example of how this could go wrong, imagine a protocol where one part uses $\operatorname{SHA-256}(x)$ as a public identifier for something, and another part uses $\operatorname{SHA-256}(\operatorname{SHA-256}(x))$ as a secret, each of which use is independently essentially fine (except for potential generic issues with $H^2$).  Obviously this combination of uses could be exploited to learn the secret.  Were the number of iterations of SHA-256 hashed into the message, as in $\operatorname{SHA-256}(1 \mathbin\| x)$ and $\operatorname{SHA-256}(2 \mathbin\| \operatorname{SHA-256}(2 \mathbin\| x))$ instead, there would be no such danger.


Interpreting the Hash type in a TLS ciphersuite There are ciphersuites with SHA256, and SHA384.
In the following TLS ciphersuite, the SHA types is not specified. Does this always refer to SHA1 (there is SHA0 as well) so which one of them?

TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA

Does this always refer to SHA1

Yes, within TLS ciphersuites, an unadorned "SHA" means SHA-1.  The oldest of these ciphersuite names predate any of the SHA2 hashes (and so if they use them, they'll explicitly list the size, e.g. SHA256), and SHA-0 is never used.

From the Glossary (appendix B) in RFC 5248: TLS 1.2:

  SHA

  The Secure Hash Algorithm [SHS] is defined in FIPS PUB 180-2.  It
        produces a 20-byte output.  Note that all references to SHA
        (without a numerical suffix) actually use the modified SHA-1
        algorithm


Are there any benefits to using ECB over CBC? From what I have understood about ECB and CBC, CBC is far better as it doesn't reveal any pattern. There have been several questions here about how ECB is bad:

Should I use ECB or CBC encryption mode for my block cipher?
Can someone explain the ECB Penguin?
Why shouldn't I use ECB encryption?

But are there any cases where ECB is better than CBC, or at least is still usable?
My guess is that for high entropy messages, without any pattern, the major flaw of ECB is irrelevant, but are there any benefits to using ECB over CBC?

ECB benefits:

It's a tiny bit easier to implement.
It allows for parallel encryption and decryption (CBC only decryption).
A single corrupted cipher block corrupts only one block of plain text(in CBC it is 2)
It doesn't need an IV

ECB downsides:

In almost all cases it is insecure.

For comparison, CTR mode allows parallel encryption and decryption and a single corrupted bit corrupts only 1 bit (not even a whole block as in ECB). Also CTR doesn't need padding or have padding related weaknesses.

If you have high entropy messages where message blocks never repeat ever then ECB could be acceptable, but it's just asking for trouble.


What is the proper usage of GCM nonce in TLS1.2? I have written a program with the help of the bouncy castle for C# library.

I am monitoring the traffic which is send between the client and the server and found something (i find) strange. The client sends application data to the server using the following ciphersuite: TLS_PSK_WITH_AES_128_GCM_SHA256. The GCM nonce starts at 1, then the server sends data back with nonce 1, then client sends data with nonce 2, server sends back with nonce 2, etc.

Is this correct? shouldn't the nonce never be the same twice? so shouldn't the server respond with nonce 2 instead of 1?

TLS has different keys for the two different directions.  That is, the server-to-client connection is encrypted with one set of keys, and the client-to-server connection is encrypted with another.  Both sets of keys are derived at the same time, however they are distinct.

Because the keys are distinct, using the same nonce isn't an issue.

Technical point that doesn't actually change the answer: actually, what's sent over the wire is actually the latter 64 bits of the nonce; 32 bits of the nonce are also derived when we generate the keys.  Of course, the same 32 bits might be picked for both directions.  On the other hand, even if they do, as above, that collision would be harmless (unless the keys also happen to collide)


How many p and q pairs are there in a 1024 bit modulus? I was reading:
Is sharing the modulus for multiple RSA key pairs secure?.

My question is: Given a 1024 bit modulus, how many pairs of 512 bit p's  and q's are there that would be able to be combined to create a 1024 bit modulus for use in RSA?

Since a 1024 bit modulus has not been factored, I am guessing we don't know, but I wonder if there is an equation?

I thought it would only be one set honestly: one p and one q multiplied together to get n. (Mainly because they only show 1 set in the wikipedia article: https://en.wikipedia.org/wiki/RSA_numbers#RSA-768)

Maybe I don't understand but the side question would be: Given a 1024-bit modulus, how many pairs of e and d could one come up with?

Given a 1024 bit modulus, how many pairs of 512 bit p's and q's are there that would be able to be combined to create a 1024 bit modulus for use in RSA?

The fundamental property is that any integer is a product of a unique multiset of primes.  As such, given an integer $n$ that is a product of two primes, those are the only two primes that, multiplied together, produce that $n$.  So, the answer is 1 (if you ignore swapping which prime you call $p$ and which you call $q$).  The fact that factorization is difficult means that it's hard to produce $p$ and $q$ given $n$; however that doesn't change the fact that $p$ and $q$ are unique).

  Given a 1024-bit modulus, how many pairs of e and d could one come up with?

That is a harder question to answer; given that there is no natural bound on how large $e$ and $d$ can be (as you can find arbitrarily large values that work), one answer might be "infinite".

If we ask for the number of $e, d$ pairs where both are limited to $\textit{lcm}(p-1, q-1)$ (which may sound like an odd limit, but turns out to be reasonable), well, we first note that $e$ can be used as a public exponent iff it is relatively prime to $\textit{lcm}(p-1, q-1)$.  In addition, for any $e$ which can be used as a public exponent, there is a unique $d$ within the range that works as the decryption exponent (which is why that odd looking limit is a reasonable one), hence counting potential $e$ values is equivalent to counting $(e, d)$ pairs.  And, given that the number of values relatively prime to $\textit{lcm}(p-1, q-1)$ is $\phi(\textit{lcm}(p-1, q-1))$, well that's your answer (or one less, if you don't count the $e=d=1$ pair.


When is data origin authentication necessary but non-repudiation not? I have been considering this question now for a week and I just cannot find an answer.

I understand that non-repudiation cannot be provided without data origin authentication but I cannot think of an application which satisfies that non repudiation is not necessary.

Can anyone suggest an example of an application where we need to know who sent the data but it doesn't really matter if they later deny that they sent it?

Can anyone suggest an example of an application where we need to know who sent the data but it doesn't really matter if they later deny that they sent it?

I would argue that most situations where you need authentication are like this. You very rarely need to be able to prove anything to third parties.

For example, if you have a TLS connection to a server, you need to know that the data is coming from the server and not a man-in-the-middle attacker, but there is usually no need to later prove that the server sent you the piece of data it did.

Note that non-repudiation does not mean you cannot "prove to yourself" who sent the data. If you use symmetric authentication and know only two parties have the key, then you know that any MAC you did not create was created by the other party. However, since you could have created the same, you cannot prove it to anyone else.


Rabin: how discover P and Q? I'm really lost.

I'm creating a classroom lesson about Rabin encryption and I had understood the encryption process, the creation of public-key (N = p*q) and the steps I need to find the 4 values that can be the solution.

BUT, every sample I find consider the true P and Q to demonstrate the decryption process (Extended Euclidean or Euclidean) and most of them using p=7, q=11, N = 77!

I mean, how they have P and Q?

For instance: this and this and some other as in Applied Cryptography (section 8.12) and so forth.

Is the factoring of N the first step to calculate the secret-key?
Or the solution of trying random values to put into Chinese Remainder Theorem? I can't believe in this because doing so, I would be considering Bob like Eve (have to try a lot of values to get P and Q)!

Can you light my way?
I appreciate in advance.

The intended users know, in fact choose $p,q.$ The attackers aren't supposed to know. Once you know $p,q,$ you use the Chinese Remainder Theorem for efficient computations.


Picking 'e' for RSA encryption What is the reason behind picking either $3$ or $2^{16}+1$ for generating the public key in RSA?

The cost of computing $x^e \bmod n$, which is the bottleneck in any RSA-based cryptosystem, is $\lfloor\log_2 e\rfloor$ squarings and $H(e) - 1$ multiplications modulo $n$, where $H$ is Hamming weight.*  Since $e$ is required to be coprime with $\operatorname{lcm}(p - 1, q - 1)$, the most efficient possible choice is $e = 3$.†

Originally, the 1977 RSA proposal (which was broken by modern standards in several ways, even ignoring parameter sizes) was to choose $d$ at random and derive $e$ from it.  But there's no security advantage to that, and it's much cheaper to choose $e$ to be small.

Historical RSA-based cryptosystems were badly designed and failed to provide meaningful security: if you naively try to encrypt a message $m$ like a 256-bit secret key by computing $m^e \bmod n$, and $e = 3$, and $\log_2 n > 768$, then it turns out $m^e \bmod n$ is just the integer cube of $m$ and an attacker can recover $m$ from $m^3$ just by computing integer (i.e., real number) cube roots.

So, in an attempt to stem the bleeding of such painfully naive use of RSA like this, people started using bigger exponents like $F_4 = 2^{16} + 1 = 65537$, despite the additional cost it imposes.

The sensible thing to do would be to choose $x$ at random, use a hash of $x$ as a secret key for an authenticated cipher, and transmit $x^3 \bmod n$ alongside the ciphertext—we call this RSA-KEM today.  But because of the decades of RSA abuse, people developed PTSD about small exponents with RSA, and some still break out in a cold sweat when you mention any exponent smaller than 65537.

* For certain exponents the cost may be a little lower with an appropriate choice of Lucas chain, but when $H(e) = 2$ as in $e = 3$ or $e = 2^{16} + 1$ there's not much improvement to be had over the naive square-and-multiply algorithm.

† Rabin-type cryptosystems use modular squaring, or ‘$e = 2$’, but they are qualitatively different from RSA-type cryptosystems.


Why authors of bcrypt have chosen blowfish and not some hash function like SHA-1? I wonder what are the advantages of using bcrypt over an iterated and salted KDF based on some cryptographic hash function like SHA-1 (or SHA-3)? I guess the authors of bcrypt chose Blowfish (a block cipher) for a serious reason, but we could barely replace it in with SHA-1/SHA-3 (a hash function). What is wrong with such an approach? What are security properties brought by a block cipher that are not by hash functions?

The bcrypt KDF does not use the entire block cipher as-is. It relies on a modified version of its key schedule. This is important because blowfish, unlike many other ciphers, has an extremely expensive key schedule. It requires about four kilobytes of fast memory, compared with SHA-1 which is so light that it can almost be computed entirely in x86 registers. Although bcrypt is not nearly as memory-hard as other, modern KDFs like Argon2, it was still quite good at the time and is still better in many ways than PBKDF2, which internally uses a hash function like SHA-1 or the SHA-2 family.

See Why can't one implement bcrypt in Cuda? for more information on why memory hardness is good. It explains why you can't get as much out of the massive parallelism of a GPU with bcrypt. There's also the wonderful answer by Thomas Pornin elsewhere which goes into more detail about bcrypt's security.


Simple digital signature example with number I've been looking for a simple which signs a number with some randomly generated key and then verified(decrypts the original number) with the public key, which is generated by the private.

All the examples I've found does not feature an example with real numbers, and all the keys/numbers described with a single letter, which is not really that clear.

I'll give a simple example with (textbook) RSA signing. I'm going to assume you understand RSA.

First key gen:
$p\gets 7,q\gets 13,n\gets pq=91, e\gets 5, d\gets 29$

Thus your public key is $(e,n)$ and your private key is $d$.

Say we want to sign the message $m=35$, we compute $s=m^d\bmod{n}$ which is $s\gets 42\equiv 35^{29}\bmod{n}$.

The message and signature get sent to the other party $(m,s)=(35,42)$. Who takes the signature and raises it to the $e$ modulo $n$, or $42^{5}\equiv 35 \bmod{n}$. Then makes sure that this value is equal to the message that was received, which it is, so the message is valid.


How to encrypt the number one using RSA? for example: if we have public key : (5,221) and private key : (77,221) and we want to encrypt 1:

c(m) = (m)^p mod n
c(m)=(1)^77 mod 21 =1

so how to deal with that? is there some work around ?

The algorithm you quote is usually called textbook RSA and is not used in practice for numerous security reasons (the problem you pointed out, is just one of them).

In practice, you have to pad (or armor) your message. This should be done using the RSA-OAEP (also called PKCS#1 v2.0) scheme. It transforms your message (1) into a pseudorandom block (not 1) which is then processed by the RSA encryption.


How to calculate the needed encryptions in salted passwords? Consider if a 16-bit salt is used, and it is uniformly applied over a very large password file (200,000 entries). An attacker wants to see if one particular password (say, "bubba") is used by any of the password entries. How many encryptions must be calculated, and how many comparisons must be made (of their generated-hash vs. stored hash values)?

Assume the attacker has the stored-hash-values, but he does not know which salt is used for any individual password hash. In other words, they can see /etc/passwd (so they know the 200,000 usernames), and have only gained access to the hash (but not the salt-portion) of what is stored in /etc/shadow.

In your case, you say the salt only has 16 bits of entropy, which is pretty weak.

To see whether 'one particular password' was used, the attacker would have to attempt 65,536 possible Salt combinations, for each 'particular password' that must be tested. The number of users does not  matter because we have now established a need to brute-force the (weak) salt, and only try a single particular password.

On the other hand, with a properly implemented modern Password Hash, where sufficiently strong (e.g. 72 bits of entropy) salt is used, if the attacker fails to acquire the salt, then there would be no practical way for him to brute-force the hash.


Is it possible to test implementation for side-channel attacks? When it comes to implementing cryptographic algorithms, there seems to be a big focus on the difficulty of doing so without introducing the potential for side channel attacks and the knowledge required.

Along with that seems to go the assumption that such code needs to be very carefully written and reviewed but I haven't found much in regards to testing.

Now of course it's hard to test in software whether an implementation is vulnerable against some side channel attacks but it seems to me that it should be possible for timing and maybe even cache based attacks.

Is that actually possible and where can I find information on that topic?

In particular I imagine one could observe how an implementation performs under random inputs and use CPU performance counters to monitor instruction counts and cache misses. Differences here for different inputs would probably be bad. At least for compiled languages it should also be possible to have tools that perform static analysis on machine code, shouldn't it?

At least for compiled languages it should also be possible to have
  tools that perform static analysis on machine code, shouldn't it?

Indeed, such tools exist. There are companies specialized in this domain which provide this kind of tools (see this datasheet for example). But you should note that an only software tool will not be able to detect all weaknesses against certain types of attacks (e.g. some fault injections).

  it should be possible for timing and maybe even cache based attacks

There is also CacheAudit which is a tool for the static analysis of cache side channels (plus, it's free). It can be configured to test your implementation against several architectures (e.g. separate or shared cache for data and instructions) and several attack models. Here is the description of the framework and you can download it here. To put it in a nutshell:

  CacheAudit takes as input a program binary  and  a  cache
  configuration  and  delivers  formal  security  guarantees  that
  cover  all  possible  executions  of the corresponding system.


Impact of the hash algorithm on a PRNG Pseudorandom number generators often use hash functions for the generation. Some applications allow the users to choose this hash function, for example OpenVPN.

From the OpenVPN manual:

  --prng alg [nsl]
      (Advanced) For PRNG (Pseudo-random number generator), use digest algorithm alg (default=sha1), and set nsl (default=16) to the size in
  bytes of the nonce secret length (between 16 and 64).

Set alg=none to disable the PRNG and use the OpenSSL RAND_bytes function instead for all of OpenVPN's pseudo-random number needs.

What impact does the hash function have on the randomness of the resulting pseudorandom number?

For example, SHA1 suffers from proven hash collisions. Does that impact the pseudorandom number?

Would SHA2 be considered more secure or is the impact of the hash function not that crucial on the randomness?

What impact does the hash function have on the randomness of the resulting pseudorandom number?

None.  A good cryptographic hash function like the ones you mention will  produce output that is uniformly distributed random.  Given a long stream of output, you will not be able to identify what hash function was used.  The actual stream of numbers will however totally change if you change the hash, but they'll all be just as random.  It should still be impossible to distinguish a good PRNG's output from true randomness, no matter how much effort you use.

  For example, SHA1 suffers from proven hash collisions. Does that impact the pseudorandom number?

That's a highly contrived example in a very particular situation.  We're not at the stage yet where we can immediately invert a SHA-1 output to determine the input.  And actually, collisions in a PRNG output are nothing to be feared.  You would expect these to occur naturally (but infrequently) as you produce the output.  Random numbers repeat sometimes.  What's important is that again given a  long sequence of output, we can't at the moment discover the input sequence and therefore the generator's internal state.

  Would SHA2 be considered more secure or is the impact of the hash function not that crucial on the randomness?

At this stage, it doesn't make a difference.  /dev/random and Java's SecureRandom still use SHA-1 mixing functions and they're considered unbroken.  If you specifically focus on the randomness, that's not a direct product of cryptographic security and invert ability.  It's a  function of the avalanche effect.  Any hash function that exhibits the avalanche effect will generate perfect random output.  For  example a simple algorithm based on a substitution permutation network or matrix multiplication will produce perfectly random output.  You'll just be able to invert it and therefore those wouldn't be suitable as cryptographic PRNGs.


Difference between Symmetric and Asymmetric. Is this answer correct, based on a written test? I asked the following question on a final exam:

  Symmetric Ciphers (e.g. AES, DES, Blowfish) use up to 256 bit on the
  best case, which are considered strong against brute-force attacks. On
  the other hand, asymmetric cryptography (e.g. RSA, DSA, Elgamal) use a
  higher amount of bits (~2048). Explain the reason of the bit
  difference between Symmetric and Asymmetric Ciphers.

His answer was:

  Asymmetric Ciphers use more bits because generally it uses powers,
  which generates a bit increase. Additionally, Asymmetric Encryption
  requires more processing time than Symmetric, which leads to a higher
  cost on a bit level.

By “powers”, he meant “math powers”. He quotes the following from the internet to support his answer:

  "The algorithm is slow, since it uses math operations which have a high
  cost and works with big key sizes. Part of the problem is on the
  choice of the exponent"

And finally:

  "Although is not mathematically exact, the first operation could be
  accepted as linear since the number of operations is directly
  proportional to the size of both operands. On the other hand, the
  second operation is an exponential type because doubling the input
  size, the number of operations to make does not double, it increases
  exponentially in time."

Although the answer is here, I see that part of his statements are correct, but is he answering the question correctly?

I don't believe he is answering the right question.  You essentially asked "why are public keys so much larger than symmetric keys", and after his first sentence (which started to address the question, but was a bit vague), he tried to answer the distinct question "why are public key operations so much slower" (not that he got the details of that correct; his last sentence appeared to imply that public key operations take an exponential amount of time).


Why do we use encrypt-decrypt-encrypt (EDE) in 3DES, rather than encrypting three times? I'm wondering why we use encrypt-decrypt-encrypt (EDE) sequence in 3DES (also known as DES-EDE, TDES or TDEA) with three keys instead of three times encryption (EEE) with three different keys?

Well, the standard answer is to preserve compatibility with DES; a hardware circuit that implemented 3DES (with EDE) could also be used to do DES as well (by, say, making all three subkeys the same).

Now, there is one slight problem with this straightforward argument; 3DES (EEE, that is, with three encrypt operations) would have this property as well; if we select the first two subkeys to be the same weak key, the second encrypt with the weak key would exactly undo the first, and the plaintext block will be operated on by the third subkey (which is the DES operation we really want).

However, it's not the case that whoever designed 3DES missed this point.  Instead, they were also considering a third option as well, 2 key 3DES (which is normal 3DES except that the first and the third subkeys are the same).

Now, if we had a 3DES EEE implementation with three independent subkeys, we could support DES (using the weak key trick), 2 key 3DES (EEE), and 3 key 3DES (EEE).  However, that wasn't the only situation they had in mind; they also considered the case where someone implemented 2 key 3DES in hardware (which the first and last subkeys were constrained to be the same).  That's one thing EEE mode can't do; we can't use the weak subkey trick with 2 key 3DES (if we make two of the adjacent subkeys the same weak key, then all three subkeys are the same weak key).  However, the EDE trick still works.

Hence, the full answer is so that one hardware circuit can support both DES and 2 key 3DES (where the hardware circuitry insists on using the same subkeys for both the first and third subkeys), and also one hardware circuit can support DES, 2 key 3DES, and 3 key 3DES.


Why is H(k || m || k) secure against birthday attack? I don't know if my opinion is correct. I think that H(k || m || k) (I mean using Merkle and Damgard algorithm where k is a secret key shared by two parties and m is the message sent) is a good keyed hash function with respect to birthday attack because:

if the attacker finds another message m' different from m such that h(m') = h(m) this doesn't guarantee that the prefix of m' is equal to the prefix of m, so with high probability H(k || m' || k) will be very different from H(k || m || k).
if the attacker wants to append extra bits to H(k || m || k) and compute another step of Merkle and Damgard algorithm he/she can't because he/she doesn't know the last block (that is the key), he/she only knows message blocks sent during the communication.
if the attacker finds with birthday attack a message m' such that h(m') = h(k || m || k), he/she cannot verify if that authentication tag is correct because he/she doesn't know the key k. So the attacker to find a message m' such that h(m') = h(k || m || k) generates all possible hashes (considering the rule of birthday bound) in order to find the same value of H(k || m || k).

I'm not sure about this statements, above all the third.
Can anyone confirm me the correctness of this statements and eventually explain me possible mistakes? Thanks!

if the attacker finds another message m' different from m such that h(m') = h(m) this doesn't guarantee that the prefix of m' is equal to the prefix of m, so with high probability H(k || m' || k) will be very different from H(k || m || k).

Correct: an adversary can't do a collision search offline because the adversary can't even evaluate the function $m \mapsto H(k \mathbin\| m \mathbin\| k)$.

  if the attacker wants to append extra bits to H(k || m || k) and compute another step of Merkle and Damgard algorithm he/she can't because he/she doesn't know the last block (that is the key), he/she only knows message blocks sent during the communication.

Correct: although if given $h = H(k \mathbin\| m \mathbin\| k)$ the adversary could compute $H(k \mathbin\| m \mathbin\| k \mathbin\| m')$ for some suffixes $m'$, that is of no consequence unless by luck $m'$ happens to end with $k$, which is completely improbable.

  if the attacker finds with birthday attack a message m' such that h(m') = h(k || m || k), he/she cannot verify if that authentication tag is correct because he/she doesn't know the key k. So the attacker to find a message m' such that h(m') = h(k || m || k) generates all possible hashes (considering the rule of birthday bound) in order to find the same value of H(k || m || k).

I don't really understand what you're getting at here, because $H(m')$ is not relevant to the authentication system.

All that said: The birthday paradox is nevertheless relevant even if the adversary can't perform an offline collision search!

Suppose you're using a 128-bit hash like MD5, and you learn the authentication tag $H(k \mathbin\| m_i \mathbin\| k)$ for a whopping $2^{64}$ messages $m_1, m_2, \dots, m_{2^{64}}$.  Suppose for simplicity that $k$ and the $m_i$ are all at least one full block long—at least 512 bits, for MD5.  With high probability, there will be a pair of messages $m_i \ne m_j$ with $H(k \mathbin\| m_i) = H(k \mathbin\| m_j)$, which means not only that $H(k \mathbin\| m_i \mathbin\| k) = H(k \mathbin\| m_j \mathbin\| k)$ but also $$H(k \mathbin\| m_i \mathbin\| m' \mathbin\| k) = H(k \mathbin\| m_j \mathbin\| m' \mathbin\| k)$$ for any common suffix $m'$, enabling forgery of many additional messages!  This is why for an iterated hash with an $n$-bit state, you should use it only for ${\lll}2^{n/2}$ messages.

To my knowledge, this was first described by Preneel and van Oorschot in their 1995 MDx-MAC paper.  It is a general attack on any hash of this sort with an $n$-bit state; the same idea applies to HMAC too even though HMAC had not yet been invented and Preneel and van Oorschot sensibly chose not to disrupt the natural flow of time by describing how it applies to HMAC.


Existence of a map $\phi:\mathbb{Z}_{N^2}^* \mapsto \mathbb{F} $ Is there a map between the group of $\mathbb{Z}_{N^2}^*$ where $N$ is a composite number , a product of two equal size secure prime numbers $p$ and $q$ and a finite field $\mathbb{F}$, such that for all $x \in \mathbb{Z}_{N^2}^*$ there is a polynomial representation of $x \in \mathbb{F}$ ?

So if you want a homomorphism from $\mathbb{Z}_{N^2}^*$ into the multiplicative group of a field, you have to adjust the number of elements in the field. With $p=2a+1$ and $q=2b+1$ (with $a,b$ prime), you have
$$|\mathbb{Z}_{N^2}^*| = 4pqab$$
The multiplicative subgroup of a field $F_{x^y}$ with prime $x$ and exponent $y$ has $x^y-1$ elements. At this point you could choose a specific $N$, that the according cardinalities match ($4abpq=x^y-1$), but if you have to apply this to arbitrary $N$, it won't work this way. Then all you can do is try to find $x^y$, s.t. $(x^y-1)$ is a factor of $4abpq$. If you use e.g. $\mathbb{F}_p^*$ or $\mathbb{F}_q^*$, this will work. But I can't think of any other fields which have this property from these given values.

As an example for an homomorphism you can use $f(x) = x^{pq(q-1)}$ to get a subgroup of order $p-1$, which you might be able to find an isomorphism into the multiplicative group of $\mathbb{F}_p$.

However, a bijective function (isomorphism) is quite unlikely to exist.


RSA 1024 bit forge a new matching signature from a chosen message I have an RSA signature scheme with 1024-bit key where I know the following:

Public modulus $N$
Public exponent $e=3$
A lot of signatures

Summary:

To compute a signature, an MD5 hash is calculated from a collection of byte and the textbook RSA private key function is applied to that. The verification procedure for a signature $S$ is to check that $S^e\bmod N$ is the MD5 hash of the alleged message.

Our teacher give us more than one signature.

Question:

Can someone give advice to find a practical way to find a new matching signature from a chosen message?

We assume an RSA signature scheme with appendix where the signature of message $M$ is $S=\left(\operatorname{MD5}(M)\right)^d\bmod N$, and the verification procedure checks that $0\le S<N$ and $\left(S^e\bmod N\right)=\operatorname{MD5}(M)$, with $e=3$ (or other relatively small odd $e\ge3$). Eve somewhat got $k$ rightful signatures $S_i$ and perhaps the corresponding messages $M_i$ (which Eve could not influence). Eve wants to construct another $M$, and matching signature $S$.

Eve will make a multiplicative forgery: she'll find a message $M$ and a matching set of $k$ non-negative integers $e_i$, such that $\operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i}$ is an $e$th power, then compute the signature of $M$ as
$$S=\left(\sqrt[e]{\operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i}}\right)\cdot\left(\prod S_i^{e_i}\right)^{-1}\bmod N$$
which verifies $\left(S^e\bmod N\right)=\operatorname{MD5}(M)$.

Define $m_{i,j}$ as the multiplicity of prime $p_j$ in the factorization of $\operatorname{MD5}(M_i)$, and define $m_j$ as the multiplicity of prime $p_j$ in the factorization of $\operatorname{MD5}(M)$. The goal of Alice is that $\forall j,\; m_j+\sum_i m_{i,j}\cdot e_i\equiv0\pmod e$. That linear system of equation with unknowns $e_i$ is equivalent to $\operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i}$ being an $e$th power.

Eve computes the hashes $H_i=\operatorname{MD5}(M_i)$, directly or as $S_i^e\bmod N$. She factors the $H_i$ at least partially (with $H_i<2^{128}$, even complete factorization is feasible). She can ignore any $H_i$ with a prime factor $p_j$ not appearing in the other $H_i$ [and $m_{i,j}\not\equiv0\pmod e$, but that is likely for $k$ large enough to carry the attack]; in particular she can without loosing much ignore those $H_i$ with a prime factor larger than about $k^3/\log(k)$, which are unlikely to be of any help.

Outline of the rest: Eve repeatedly

selects a message $M$ of her choice [that she did not previously select, and distinct from the $M_i$ if these are given]
computes $\operatorname{MD5}(M)$ and factors it at least partially
if that factorization consists entirely of primes occurring in the factorization of at least one of the $H_i$ kept [in that screening Eve could exclude primes with multiplicity $m_j\equiv0\pmod e$ in the factorization of $\operatorname{MD5}(M)$, and occurrences with multiplicity $m_{i,j}\equiv0\pmod e$ in the $H_i$, but that won't make much of a difference for $k$ large enough to carry the attack]

attempts to solve the linear system, and if that works

computes $S$, noting that the $e$th root extraction reduces to dividing the exponents by $e$ in the known factorization of $\operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i}$
outputs $M$ and $S$.

It will help to have preprocessed the system of linear equations. For larger $k$, solving the linear system will succeed for a large proportion of $M$ having passed the screening; or/and it will be possible to put an upper bound of the $p_j$ early on, making the factorization easier and the linear system smaller, thus easier to manage.

A small $e$ helps the attack, but with a large-enough $k$ it can be carried for any $e$. The size of the public modulus $N$ of the RSA key is essentially immaterial; what matters most is the width of the hash, which at 128-bit is grossly insufficient.

A slightly simpler variant of the problem (where all the messages are chosen, which is moot for a hash without collision resistance as $\operatorname{MD5}$ is nowadays) is discussed by Jean-Sébastien Coron, David Naccache and Julien P. Stern in section 2 of: On the Security of RSA Padding (in proceedings of Crypto 1999); or, when we set $\mu$ to $\operatorname{MD5}$, by Don Coppersmith, Jean-Sébastien Coron, François Grieu, Shai Halevi, Charanjit Jutla, David Naccache, and Julien P. Stern in section 3 of: Cryptanalysis of ISO/IEC 9796-1 (in Journal of Cryptology, 2008). The idea of a building coefficients by solving a linear system based on prime multiplicity was introduced by Yvo Desmedt and Andrew M. Odlyzko in A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes (in proceedings of Crypto 1985).


Security guarantees of Shamir's secret sharing when some co-efficients are zero Shamir secret sharing techniques rely on polynomials for splitting and reconstructing. It's security properties are very good, i.e. it is impossible to reconstruct the secret when $t-1$ shares are given.

The coefficient for the highest term of a polynomial should be non-zero.
But is it mandatory for other co-efficients of polynomials to be non-zero ?

Is there an impact to security guarantees when few co-efficients (other than the highest term) are zero ?

The coefficients must be uniformly chosen. If you do not choose your coefficients uniformly, then by Kerckhoff's principle, the attacker knows this, and that makes it easier than normal to reconstruct the polynomial, and thus to obtain the secret.


CKKS security estimation for Palisade My question is rather practical and specific. I am trying to setup an efficient CKKS scheme in Palisade. To this end, the automatic choice for secure parameters has to be turned off and I rely on the LWE estimator which estimates the security of an LWE instance. Now, the estimator provides a security estimation for an LWE instance $\mathrm{LWE}(n,\alpha,q)$, where $n$ is the dimension/ring dimension, $\alpha$ depends on error distribution, and $q$ is the ciphertext modulus. However, in Palisade there seems to be no possibility to setup the error in CKKS (this is easily possible in BGV). This way, $\alpha$ remains unknown and the security can not be estimated.
Therefore, how is the error chosen in Palisade for CKKS and how can this value be accessed?

In PALISADE, CKKS is configured to use $\alpha = 8/q$ (using the definition of $\alpha$ in the LWE estimator). This corresponds to the standard deviation of $8/\sqrt{2\pi} \approx 3.19$. This value was chosen based on the HE security standard at https://homomorphicencryption.org/standard/
You can manually change this value from 3.19 to something else by modifying $\textbf{genCryptoContextCKKS}$ in https://gitlab.com/palisade/palisade-release/-/blob/master/src/pke/lib/cryptocontextfactory.cpp


Why is XOR preferred over XNOR? The XOR operator seems to be a frequently used building block inside many cryptographic primitives.  As far as I can see, its most desirable properties seem be that for the XOR of two bits $a\oplus b=c$:

The information is preserved.  Either $a$ or $b$ can be recovered from $c$ and the other bit.
The information is hidden.  An adversary can not learn anything about $a$ or $b$ from $c$ alone.

Neither AND nor OR has these properties but XNOR does.  It seems like any cryptographic application using XOR could be constructed equivalently with XNOR, without incurring any loss in security.  One possible reason to prefer XOR might be that XOR is equivalent to addition modulo 2, whereas XNOR would be addition plus 1 modulo 2, but this seems to be entirely mathematical, and I'm not sure if it actually results in any additional hardware complexity in practice.

Is the choice of XOR then an arbitrary one, made for historical reasons, or is there any tangible underlying motivation for using it over XNOR?

$\operatorname{XOR}$ is similar to addition when working on Booleans; by contrast, $\operatorname{XNOR}$ is not a group law if we want to use $0$ as neutral.
Economy for extension: we can build a 3-inputs $\operatorname{XOR}$ from two 2-inputs ones; we can't for $\operatorname{XNOR}$.
Economy for making one: we can build $\operatorname{XOR}$ with four identical 2-input $\operatorname{NAND}$, but that can't be done for $\operatorname{XNOR}$. The construction goes:

$z\gets(a\;\operatorname{NAND}\;b)$;
$x\gets (a\;\operatorname{NAND}\;z)$;
$y\gets(b\;\operatorname{NAND}\;z)$;
$c\gets (x\;\operatorname{NAND}\;y)=(a\;\operatorname{XOR}\;b)$.

Update: the later argument works only because/when $\operatorname{NAND}$ is cheaper, faster, or/and less power-hungry than $\operatorname{NOR}$. That indeed was the case in TTL logic: that source shows 4 NPN transistors for $\operatorname{NAND}$, including one with two emitters, versus 6 for $\operatorname{NOR}$. The same holds for RTL logic made from PNP transistors, which used to be popular when these where made using germanium. However, RTL logic using NPN transistors (typically, on a silicon Integrated Circuit), which favors $\operatorname{NOR}$, has also existed. Famously, the Appolo Guidance Computer was built from 3-inputs $\operatorname{NOR}$ gates, two per IC.