Shannon theorem of perfect secrecy From the class:

Shannon Theorem: For a perfect encryption scheme, the number of keys is at least the size of the message space (number of messages that have a non-zero probability).
Proof:
Consider ciphertext $c$. $c$ must be a possible encryption of any plaintext $m$. But, for this we need a different key per message $m$. $m \neq m' \iff c \neq c' $. Why?

Can someone explain the logic behind the proof? I understand that the one above is a partial one but still can I have an easy to understand explanation? No need a formal one.

$c$ must be a possible encryption of any plaintext $m$.

I understand that.

But, for this we need a different key per message $m$.

Why? I can have the same key for different messages and still produce different ciphers, and those ciphers would be " a possible encryption of any plaintext m ".

$m \neq m' \iff c \neq c'$  Why?

Didn't understand that either, could have different messages but same ciphers.
But if we indeed force that each message has it's own unique key then it is true, and then we showed that size of keys space > size of messages space.

If $c$ is a possible encryption for each $m \in M$, that means that for each message $m$ exists a key $k$ such that $Enc_k(m)=c$. Now, if you encrypt, you need to be able to decrypt. Since $c$ is fixed, the only variable for $Dec_k(c)=m$ is $k$. Since you need to be able to use the decryption process to get any value of $m$, that means that you have $|M|$ values of $k$.

In other words, you need to be able to go from the any value in the message space to any value in the ciphertext space (encrypt) and from any value in the ciphertext space to any value in the message space (decrypt), and for that you need $|M|=|C|$ keys.


Laplace Mechanism Proof: Why this product operator? The equation below shows the proof of Laplace mechanism for differential privacy. I am not understanding the product operator, is this a common rule?

$$
\frac{p_x(z)}{p_y(z)} = \prod_{i=1}^{k}\left(\frac{exp(-\frac{\varepsilon |f(x)_i - z_i|}{\Delta})}{exp(-\frac{\varepsilon |f(y)_i - z_i|}{\Delta})}\right)
$$

While $p_x$ and $p_y$ denote the pdf of mechanisms $\mathcal{M}_L(x,f,\varepsilon)$ and $\mathcal{M}_L(y,f,\varepsilon)$ respectively. Important to notice that $x$ and $y$ are neighbor datasets. $x, y, z \in \mathbb{R}^k$

Thank you in advance.

The definition of Laplace Mechanism:
$$
\mathcal{M}_L(x, f(\cdot), \varepsilon) = f(x) + (Y_1,\ldots,Y_k)
$$
Once each $Y_i \sim Lap(\Delta f/\varepsilon)$ they are indepedent of each other. So we can calcule the joint probability of them using the product of marginals.

As we know $p_x = \mathcal{M}_L(x,f,\varepsilon)$ and $z \in \mathbb{R}^k$, thus is possible to do:

$$
p_x(z) = \frac{\varepsilon}{2\Delta f} exp\left(-\frac{\varepsilon |f(x) - z|}{\Delta f}\right) = \prod_{i=1}^k \frac{\varepsilon}{2\Delta f} exp\left(-\frac{\varepsilon |f(x)_i - z_i|}{\Delta f}\right)
$$

I think that is the answer.


Shamir's Threshold Scheme (Theory Part, Need some help understanding a term that I can't find online) What does the max(S, n) part mean, and what am I supposed to do with it? I somewhat understand, but it is still confusing. I don't know what it exactly represents. Can you help me please?

By definition, $\max(a,b)$ is the largest of $a$ and $b$. That's also the meaning in many computer languages, e.g. Python's max.

Thus $p>\max(S,n)$ means: $p>S$ and $p>n$.


How to compare between two cryptographic algorithms in terms of security? How to compare between two cryptographic algorithms (e.g. SHA-1 and SipHash) in terms of security? That is, how could one prove that algorithm X is more secure than algorithm Y?

TL;DR, you don't.

At this point, we have algorithms we believe are unbroken by current adversaries. For hashing, this includes the SHA-2 family of hashes, SHA-3, BLAKE2b and others. For authentication, we have the HMAC family of functions, the UMAC family of functions, Poly1305, and others. For symmetric encryption, we have AES, ChaCha20, and others. For asymmetric encryption, we have RSA, too many elliptic curves to name, and others. For digital signatures, we have RSA, ECDSA, and others.

When used correctly and with appropriate key sizes, all of these algorithms are considered secure. "More" secure without additional context is a mostly meaningless question: none of these algorithms will ever be brute-forced. Some or all of these algorithms may contain flaws in their design which could render them useless or weakened tomorrow, next year, or a century from now. Some or all of these algorithms may never be broken. But there's no way to know which ones will fall into which category until this happens.

In specific contexts, some algorithms may have desirable properties. The so-called safecurves, for example, are considered more resilient against poorly-written implementations. Block ciphers like AES in virtually all real-world scenarios must be used in a mode of operation that should be chosen based on  the (not necessarily security-based) requirements of your application.

When misused, any algorithm is typically susceptible to catastrophic failure. And unfortunately, virtually any implementation or composition of cryptographic primitives by amateurs (and even, frequently, professionals) is prone to mistakes.

The solution to this is to operate at the highest level of abstraction available to you which is provided by respected cryptographers and software developers. Typically, this means GPG for data at rest, TLS for data in motion. These projects have the benefit of many eyeballs, decades of fixing security issues, and reasonably general default choices for algorithms.

If you're not a seasoned cryptographer and you're making a decision about what cryptographic primitive to use, you have already lost.


One-time pad, zero key and Shannon I'm supposed to prove that OTP without the zero key $k=0^n$ is not perfectly secret anymore. I understand that it's not because an attacker learns something by looking at the plaintext and ciphertext. But I don't know how to prove it formally.

I was thinking about using Shannon. But to do so $|K|$ needs to be equal to $|P|=|C|=|{0,1}^n|$, which is not the case if I define $K={0,1}^n$ \ $0^n$. So my idea was to include the zero key to the key space K, but set the probability for $p(k=0^n)=0$. Doing so would allow me to have $|K|=|P|=|C|$ and to use Shannon.

PS: I'm aware of the somewhat similar question (One-time pad and zero key), but we didn't have any rule for $|K|>=|P|$ in order to achieve perfect secrecy. Also I am interested in my question about Shannon.

Well, for perfect secrecy, we require that for all message distributions over $\mathcal{M}$, all messages $m\in\mathcal{M}$, and all (possible) ciphertexts $c$ it holds that

$$Pr[M=m\ |\ C = c] = Pr[M=m]$$

In particular, that means, if we can find a single counterexample, i.e. a distribution over $\mathcal{M}$, a message $m\in\mathcal{M}$, and a ciphertexts $c$ such that

$$Pr[M=m\ |\ C = c] \neq Pr[M=m]$$

then, by our definition, the encryption scheme does not offer perfect secrecy.

So, let's take the uniform distribution over $\mathcal{M}$. For this distribution, we obviously have $$Pr[M=c]=1/|\mathcal{M}|.$$
Now, given that $0^n$ is not a valid key, what is the probability  $$Pr[M=c\ |\ C = c]?$$ Are the two probabilities equal?


Diffusion in Shamir's secret sharing scheme The popular command line utility ssss implements the classic Shamir's secret sharing scheme over the generic field $GF(2^q)$ with $8 \le q \le 1024$.

When $q>=64$, the constant coefficient ($c_0$) is not the secret but a transformed version of it, obtained by means of 40 rounds of XTEA-based permutation. As result, the secret is somewhat diffused over the entire $q$ bits.

Why is that? Which attack does it prevent? Does it help when the secret has a short bit length?

I took a brief look at the code, but I fail to see how this transformation could introduce any additional secrecy. If the randomness used to define the polynomial is good, then Shamir's secret sharing provides information theoretic secrecy (no matter how the secret actually looks like). What Ricky points out in his answer seems reasonable, i.e., to provide some means against the malleability of the secret sharing. Since Shamir's approach is linear, one can "update" the shares to "update" the secret and if you add an additional layer of diffusion to the secret before sharing such "updates" are no longer possible in a straightforward manner. Note, however, that this does not influence the secrecy of the secret but against active attacks on modifying the shares.

Another issue which I initially thought could be the case comes below.

If your secret is larger than what
can be represented as an element of the used field, then computational secret sharing (CSS) can be used, but it is not implemented in ssss (it's only linked as an alternative at the bottom of the page).

Basically,  with CSS it is possible to make shares in a secret sharing scheme shorter at the cost of losing the perfect
secrecy guarantees provided by Shamirs approach. One only achieves computational instead of information
theoretic security.

The idea is to use any IND-CPA secure symmetric encryption scheme in the following (obvious) way:
Choose a random secret key $k$ of a suitable symmetric encryption scheme and encrypt the secret $s$ using $k$.
Then one uses polynomial secret sharing to compute $n$ shares $s_1 ,\ldots , s_n$ of the key $k$.
Note that the field $\mathbb{F}$ used for secret sharing here can be much smaller as in Shamir’s original approach,
as you only need to represent the key $k$ as field element and not a potentially large secret $s$.

Note that if you use Shamir's secret sharing directly on $s$, then $s$ needs to be represented as a field element (as the constant coefficient of the polynomial) and also the shares will then be of that size. If your secret is large, then CSS is an efficient alternative.


Signing data packets increases data size too large for packet to contain In a setup where the client signs then encrypts outgoing data packets to a VPN server / onion network, an ECDSA signature appended to the plaintext before encryption could cause the data to be too large to be contained in the packet. How is this avoided??

Side note: Encryption will be with a stream cipher, so the data size wont increase after encryption of the ECDSA signature appended to the plaintext.

How is this avoided??

Well, if it add any sort of integrity check to the data (be it a signature or a more sensible MAC), well, that increases the size of the data (packet), and so can potentially push the packet to be larger than the MTU size (assuming the inbound and outbound MTU sizes are the same).

However, the TCP/IP protocol has mechanisms to deal with this.  The details depend somewhat on whether you're encrypting as an end host, or you're a security gateway - since you talk about encrypting traffic from a website, I'll assume you are (at least partially) talking about a security gateway (that is, something that sits between the two end points).

The most obvious one is to advertise a smaller MTU size; that is, if you get a packet that (after encapsulation) would be too big, you reject it with the appropriate ICMP message (giving the largest MTU size that you could process).

This works; however IPv6 doesn't allow you to advertise an MTU size smaller than 1280; if the path that handles the encrypted traffic is close to that size, this doesn't work.

The fallback is to do packet fragmentation yourself; you divide the packet into two (along with some notation to the decryptor about what you did), and encapsulate each packet separately.  This is uglier, however it does work.

The IPsec RFC (4301) goes through this rather explicitly...


Question about ChaCha20's security I wonder the Stream Cipher ChaCha20 only changes 96 bits each block,
         why it can produce 512 bits keystream block,
         I mean in the concept of  a random number generator,
         the entropy should be at least equal to the output.
         However,  change 96 bits to produce 512 bits keystream seems have some secure problem.

The fact that few bits change at the input of ChaCha's "core" function does not compromise the security of the ChaCha20 stream cipher.

The design principle of the stream ciphers Salsa and Chacha is to use a "core" function $C:\,\{0,1\}^{512}\to\{0,1\}^{512}$ over the set of 512-bit bitstring (equivalently the set fo 16 words each 32-bit). Among the 512 input bits, 128 are set to arbitrary public constant values $c$, turning the remaining into some function $C_c:\,\{0,1\}^{384}\to\{0,1\}^{512}$.

$C_c$ behaves essentially like a function chosen at random in the set of functions with such input and output domains. In particular, it is conjectured that not knowing $k$ of the 384 input bits chosen at random, the function $C_c$ can't be distinguished from a random function with works less than $2^k$ operations (each requiring a sizable number of CPU cycles), for $k$ up to some comfortable limit (like 160 to 256).

Of the 384 input bits of $C_c$, $k=$256 are for the key, 64 for the nonce/IV, 64 for the counter. The full 512-bit output forms the keystream. As long as the key is random and secret, and the combination of IV and counter value does not repeat, the above conjecture demonstrably implies security of the stream cipher in all common security models, including for related keys.

That's even though, for most blocks of a large keystream, the input of the core function differs by a single bit from the input for another block, and 256 bits (including all those that vary) at the input of the core function are public.

The supporting argument for the stated security conjecture is the design of the core function per $C(x)\gets G^r(x)\boxplus x$ where $G$ is a bijection iterated for $r$ rounds, and $\boxplus$ is a group operation on $\{0,1\}^{512}$. Bijection $G$ is optimized for fast diffusion when iterated.

Note: diffusion is the main area where ChaCha improves (slightly) on Salsa. Another it is that it removes a harmless class of collisions in $C$, see this.


Is this an acceptable authenticated encryption? After much deliberation, I've decided to use a normal Encrypt-then-MAC scheme instead of an authenticated encryption mode such as GCM as authenticated encryption primitive. This is due to the lack of good, clean and reliable implementation across all the platforms I intend to support.

Background

This is for a multiplayer [strategy] game over TCP/IP. In particular, a player will log in and play every day (or every other day) for about 1-2 months (the typical playing time).

The reason why we use encryption at all, is to:

prevent sabotage (replay another player's login + actions to make him waste his daily turns, modify actions in flight)
prevent eavesdropping (stealing login credentials, monitoring actions, stealing in-app purchases)

Proposed Authenticated Encryption Primitive

At a new connection derive the IV, encryption key and signing key using HMAC-SHA512, using a secret (lifetime - max 24 hours, randomly generated) and public client + server nonces and two salts (one for each direction). We simply split the resulting 64 bytes to form 16 byte IV, 16 byte key and 32 byte signing key.
We set up two AES-CTR ciphers (one in each direction) using the IVs and the encryption keys derived in step 1.
For each packet to encrypt, we perform the following steps:

Encrypt the packet with the next [plaintext number of] bytes of AES-CTR.
Calculate HMAC-SHA256(signing key, 4 byte message number || 4 byte message length || ciphertext)
Increase message number by 1.
Send ciphertext || first 8 bytes of HMAC

On decryption, checking HMAC is made so that successful matching the HMAC and failing to match the HMAC should execute equally fast.

Example code:

int hmacFail = 0;
int hmacSuccess = 0;
while (hmacPtr < hmacEnd) {
    if (*(hmacPtr++) != *(hmacOurPtr++)) {
        hmacFail++;
    } else {
        hmacSuccess++;
    }
}
if (hmacFail > 0) -> Raise HMAC invalid error

On failed packet authentication, the connection is dropped. On the consequent reconnect a new server and client nonce will be used, so IV and keys will not be reused. Typically a connection lives for about 5 minutes, but may stretch into 1-2 hours.

Messages are typically small (less than 100 bytes) and infrequent (usually no more than a few messages a second)

Questions

Is something missing from the MAC?
I'm fairly confident that reducing the HMAC to 8 bytes should be ok, as the behaviour of dropping a connection (and thus forcing a new signing key). It might be quite ok to reduce it further.
As far as I can tell from some initial benchmarking, the dominating cost is in calculating the hash. What are my options if I want to reduce this cost while using readily available hash primitives? Going to SHA1 or even MD5 would make it faster (in my particular test, SHA1 was around 50% faster, MD5 100% faster). Any tips and tricks given the circumstances?
Anything else I've forgotten to take into account?

This is basically a description of a protocol, I'll just go over the cryptography related points that you've raised.

At least the nonce is missing from the calculation. Just to be sure I would include the entire counter value used in the CTR encryption.
64 bit of MAC output should be OK, both NIST SP 800-107 Revision 1 and NIST SP 800-38B define 64 bit of hash output as acceptable. See NIST SP 800-107 table 2. If less bits are used additional security proof would be required.
It is possible to go for an AES based MAC instead (AES-CMAC). AES is likely to be faster - especially if encryption is currently not the dominating cost; this depends on the deployed hardware and runtime environment of course.
That's hard to tell without taking the complete protocol into account. Most of the time the symmetric algorithms are not the hard part of the protocol - authentication and key management are much harder parts to get right. This is why choosing TLS should be preferred.

There are two side channel attacks that are often forgotten when creating an online protocol.

Timing attacks are particularly dangerous, especially during the authentication/session key derivation phase.
Ciphertext length based attacks are particularly dangerous on the application level, including the authentication phase (e.g. of username/password).

Please take both into account when designing any secure transport protocol.


Constant size commitment to a membership of a fixed size of elements Suppose there is a global set of $n$ elements, out of which I want to commit to $2n/3$ elements, i.e., anyone can take my commitment and test what $2n/3$ of the possible $n$ elements I committed to.
Is there any way to do so with a constant size commitment that doesn't require exponential calculations. I had Merkle tree root in mind, but of course that doesn't work without a bit-vector of the elements included in the root.

I will first restate the question as I understand it after the clarifying comment. If I'm misunderstanding something, please let me know.
Let $M$ be a set of size $n$. There are two parties $A$ and $B$.
We are looking for a protocol that does the following.
$A$ chooses a subset $N\subseteq M$ with $|N|=2n/3$ and computes some message $m$ with $|m|=\ell$, where $\ell$ is a constant, independent of $n$.
Given $m$, party $B$ is able to reconstruct and output $N$ with probability $1$.
If that is a correct description of what you're looking for, then it's sadly impossible, since it would imply infinite lossless data compression.
There are $\binom{n}{\frac{2n}{3}}$ many possible subsets, so by sending $m$ you are transferring $\log_2 \binom{n}{\frac{2n}{3}}$ bits of information.
We have
$$\log_2 \binom{n}{\frac{2n}{3}} \geq \log_2\left(\frac{n}{2n/3}\right)^{2n/3}=\log_2\left(\frac{9}{4}\right)^{n/3} > \log_2 2^{n/3} = \frac{n}{3}.$$
Since $m$ is only $\ell$ bits long, the pigeonhole principle tells us that you cannot transfer more than $\ell$ bits of information. For any $n>3\ell$¹ that's clearly being violated here.

¹This happens even earlier, I just can't be bothered to do a tight analysis here, we're using pretty loose lower bounds.


linear computations over bilinear pairings Does this hold in asymetric bilinear pairings?

$e(x_1,x_2)e(x_3,x_4) = e(x_1x_3,x_2x_4)$, where $x_1,x_3 \in \mathbb{G}_1$ and $x_2,x_4 \in \mathbb{G}_2$ for a bilinear pairing $e$

For clarity, I will use an additive notation in the groups $\mathbb{G}_1$ and $\mathbb{G}_2$, and denote group elements with the "$x$" letter, not "$e$".

For all $x_1, x_3 \in \mathbb{G}_1$ and $x_2, x_4 \in \mathbb{G}_2$, we have the following:

\begin{eqnarray*}
e(x_1 + x_3, x_2 + x_4) &=& e(x_1, x_2 + x_4) e(x_3, x_2 + x_4) \\
&=& e(x_1, x_2) e(x_1, x_4) e(x_3, x_2) e(x_3, x_4)
\end{eqnarray*}

(First equation is by linearity of the pairing for its first operand, second equation is by linearity for its second operand.)

Therefore, one can have the property you seek only when $e(x_1,x_4)$ and $e(x_3,x_2)$ happen to be opposite of each other, which is not true in general (unless the pairing is degenerate, in which case it is quite uninteresting).


Generating RSA signature, by manipulating shorter message signatures? Given a server that can return me RSA sign for any plaintext shorter or equal length of the given plaintext (excluding the given plaintext), how can I fraud/get the sign of the given?

$$sign = M^{d} \pmod{N}$$

$m$ is 63 bytes, if not it is left-padded with zeroes
$M = \mathtt{0x00}\mathbin\|m\mathbin\|\mathtt{0x00}\mathbin\|m$, which is always 128 bytes
$(e,N)$ is public key
$(d,N)$ is private key
$N$ is 128 bytes long

We notice that $M=k\cdot m$ with constant $k=2^{512}+1$. Hence the signature $\mathcal S(m)$ of $m$ is $\mathcal S(m)=k^d\cdot m^d\bmod N$.

It follows that for any valid messages $m_0$ and $m_1$ with $m=m_0\cdot m_1$ a valid message, we have $\mathcal S(m)\cdot\mathcal S(1)\equiv\mathcal S(m_0)\cdot\mathcal S(m_1)\pmod N$.

Hence, when we can write $m$ as $m_0\cdot m_1$ with $m_0>1$ and $m_1>1$, we can obtain the signature of $m$ by asking to the server the signature of $m_0$, $m_1$, and $1$. We can then compute $\mathcal S(m)$ as $\mathcal S(m_0)\cdot\mathcal S(m_1)\cdot\mathcal S(1)^{-1}\bmod N$. The last term of the product is obtained by modular inversion modulo $N$, using e.g. the half-extended Euclidean algorithm.
Note: that solution was found by the OP, based on a (strong) hint.

Given the server's limitation, we can get $\mathcal S(m)$ for any composite $m\in[4,2^{504}($, using three oracle queries (or just two when $m$ is a square). We can most often pull a factor $m_0$ using trial division, Pollard's Rho, ECM (all in GMP-ECM). We need GNFS in some difficult cases (e.g. CADO-NFS or Msieve, perhaps as packaged as FaaS).

With the "lengh" of a message counted in bits, I see no solution for prime $m$, or for $m=1$.

If the "lengh" of a message was counted in bytes excluding leading zero bytes, and for those $m$ such that $2m$ has the same length as $m$, then we can use $\mathcal S(m)\,=\,\mathcal S(2m)\cdot\mathcal S(1)\cdot\mathcal S(2)^{-1}\bmod N$ for $m>1$, and $\mathcal S(1)\,=\,\mathcal S(2)^2\cdot\mathcal S(4)^{-1}\bmod N$ for $m=1$. That still leaves quite a few problematic $m$, such as $131$ and $2^{504}-503$.
Note: We have $S(0)=0$ with no query for $m=0$.
Note: $k=F_9$ where $F_m=2^{(2^m)}+1$. The factorization of Fermat integers is well-studied, and it has been known since 1903 that $2424833$ divides $F_9$. But I do not see that it helps.


how to iteratively calculate a^emod n with modulus n sized 4096 bits In most sites the exponent of the RSA public key is 24 bits. But the modulus can get to 4096 bits size. I have an accelerator that can get max. 2112 bit size modulus. It calculates a^e mod n.

Is there a way to separate $n$ (maybe bit wise) and use the accelerator in several iterations to calculate the wanted a^e mod n?

Usually, RSA operations with the public exponent are fast, precisely because the public exponent is short. Hardware accelerators are meant to speed up operations with the private key, which are in much bigger need of it. In particular, hardware accelerators do not need to be "full width" because private key operations use the private key, which contains the factors $p$ and $q$, and allow for doing most of the work modulo $p$ and modulo $q$, both of which being twice shorter than the modulus $n$ (what the CRT is about).

A side note is that some implementation methods of exponentiations are fast but imply some fixed startup and wrapup overheads; e.g. Montgomery multiplication is popular to speed up exponentiations (which consists of many multiplications in a row), but requires converting source values into a special representation, and back at the end, both operations having a non-negligible cost. For a private key operation, the exponentiations used big exponents, and the savings implied by Montgomery multiplications dwarf these overheads, but this might not be true for a short exponent. Therefore, even if your accelerator did support a 4096-bit modulus, it is unclear whether this would have really provided some speedup for your public-key operations.

Anyway, I see no easy way to "split" a 4096-bit exponentiation into several exponentiations modulo smaller values, unless you factor the 4096-bit modulus, which should be infeasible.


Block cipher with key longer than block size When a block cipher key length is greater than the block length, is it the case that for some keys $k_0, k_1$ (with $k_0 \not= k_1$) and plaintext message $m$ that $E_{k_0}(m) = E_{k_1}(m)$?

A block cipher processes a single block of input and produces a single block of output, where the input and output blocks are the same size. By the pigeonhole principle, if the key size is larger than the block size then there must be some keys that will encrypt the same input block to the same output block.

More formally, a block cipher is defined as the family of encryption functions $E: K \times X  \to  X$ (and their inverse decryption functions), where:

$K$ is the set of possible keys with cardinality $|K|$.
$X$ is the set of possible block values with cardinality $|X|$.

The cardinality (number of elements) of these sets is $2^b$ where $b$ is the length of an element in bits. For example for a 256 bit key, $|K|$ is $2^{256}$ and for a 128 bit block, $|X|$ is $2^{128}$.

If you think of setting the key for the block cipher as fixing the value $k \in K$ to produce a function $e(X) \to X = E(k,X)$, then it's obvious that there are $|K|$ such functions.

It's then easy to see that if $|K| > |X|$, there are more possible encryption functions than there are possible output values, and so for any $x \in X$ there must exist (at least) two keys $k_0 \in K$ and $k_1 \in K$ where $E(k_0,x) = E(k_1,x)$. For a good block cipher, the number of such keys will be very low.


Using HMAC to secure a "widget" Let's say I have a web "widget" that a customer could include on their website. They would include the widget by adding an iframe that points to a URL on my site. I want to ensure that my widget can only be used by paying customers so I was thinking of using an HMAC (HMAC-SHA256 specifically) to verify the customer like so:

The URL would contain a customer ID (randomly generated 6 character hexadecimal number), a timestamp (the current time in seconds since UNIX Epoch), and the HMAC "signature". Since the widget is displayed in an iframe, all of these parameters would be sent clear-text (as a GET request).
The "signature" would be computed based on the URL (since there are multiple widgets), the customer ID, and the timestamp, with a (randomly generated) secret key that would be given to the customer.
On the server, the timestamp is checked to ensure that it falls within a specific window (15 minutes, for example) to prevent replays, and then the signature is checked by recomputing the HMAC and comparing.

I patterned my design off Amazon's web services, but Amazon's scheme requires that some of this data is passed via HTTP headers which would be encrypted over SSL. I don't have that luxury, since everything needs to be passed via GET parameters.

Does this sound reasonably secure? A coworker mentioned that it may not be very secure because all of the inputs to the HMAC algorithm are available in clear-text. An attacker would still need to figure out the way in which the URL, customer ID, and timestamp are combined to create an input to the HMAC algorithm, but, if they did, then they'd have both the input and output. My coworker worried that this information could be used to obtain the secret key via brute force or rainbow tables. Everything I've found via searching seems to indicate that our sun would explode before brute force would finish, and rainbow tables don't work on HMAC's, but the wide world of cryptography is very foreign to me. Plus, most of the answers I've found are 2+ years old and much can change... maybe some new vulnerability was found in the last 2 years or something...

So, is this reasonably secure? And, if not, what can I do to improve security?

Yes, this sounds secure to me.  HMAC, like any secure MAC algorithm, is designed to be existentially unforgeable under chosen-plaintext attacks: that is to say, even if the attacker was allowed to request from you the MACs for any set of messages they wanted, they would not be able to compute a valid MAC for any message they didn't request it for.

(Of course, this is only guaranteed to hold if the hash algorithm used to instantiate HMAC meets the security assumptions set out in the HMAC security proof.  In practice, though, secure cryptographic hash algorithms like the SHA-2 family are believed to meet these assumptions — and, in any case, HMAC is a very robust construction and seems to be very tolerant of even rather poor hashes like MD5.)

Of course, I'm assuming that all clients will be getting their own HMAC keys, so that you can revoke keys if they're compromised or simply if the client stops subscribing to your service.


Why should I export my private key instead of well known asymmetric crypto mechanism on openkeychain? I'm trying to use password-store as password manager under linux. I created a private github repo with my gpg files in order to use it with other devices. I installed android-password-store app for this end, which uses openkeychain as a openpgp client.(openkeychain paper).
My concern is that isn't using an private-public model (asymmetric crypto), you have to export your private key of your gnupg keyring and import it into your openkeychain keyring. I don't feel very safe exporting my private key when the public key exchange is a very good solution. What do you think about?
Thanks in advance.

It took me a bit to understand your issue. In summary, you want to use your passwordstore password manager on multiple devices, without copying the private pgp keys to multiple devices.
Yes, it can be done.
You need to create a separate key for each device, and configure your store to encrypt the passwords to multiple keys.
If you follow the steps at https://www.passwordstore.org/ it is mentioned at Setting it up:

pass init "ZX2C4 Password Storage Key"

ZX2C4 Password Storage Key  is the ID of my GPG key. You can use your standard GPG key or use an alternative one especially for the password store as shown above. Multiple GPG keys can be specified, for using pass in a team setting, and different folders can have different GPG keys, by using -p.

The man page details how it is used: you need to list the multiple keys on the .gpg-id file, one per line.
Each or your devices will need to have the public keys of all of the devices imported, so that they are able to encrypt the files for 'everyone'.


RSA-FDH Signature Scheme EUF-CMA I am aware of attacks whereby an attacker is able to forge a message IF the hash of the original message is the same hash as their current message. The question is, is it still possible for RSA-FDH to be EUF-CMA IF the hash function in question is collision-resistant. Lets take the case of $H(x) = 3x \mod N$. 3 is a prime number and N is always going to be prime as well. The function, in this case, is collision-resistant but despite this, is it still possible to break the EUF-CMA of RSA-FDH?

The function, in this case, is collision-resistant but despite this, is it still possible to break the EUF-CMA of RSA-FDH?

Yes, because the requirement for security is the hash function acting like a random oracle and not it being collision-resistant.

To illustrate this, consider the "hash function" $H(x)=x$ which is clearly collision resistant. Yet, RSA-FDH instantiated with this hash is not secure as it literally is textbook RSA, which suffers from the usual small-exponent and homomorphic attacks (which also apply when $H(x)=3x\bmod N$).

This could of course raise the question "why, do we need this stronger assumption?". And the main reason is that the "RSA problem" - extracting $x$ from $x^e\bmod N$ for appropriately chosen $N$ and $e$ - isn't always hard. It is only hard when $x$ is chosen uniformly at random, which is kind of what the hash function is supposed to do here.


I wrote this since it is too long to comment;
First the SageMath code
K =  GF(43)
E = EllipticCurve(K,[0,7])
print(E)
print(E.order())
print(E.abelian_group())

G = E(21,25)

With $K$ one can use different fields, the $[a=0,b=7]$ is for $y^2 = x^3 + ax + b$.
This codes give us a lot of information about the curve

print(E) : The curve information:
Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 43

E.order() : Print the number of the rational points on the curve:
31

E.abelian_group(): The group structure of the curve:
Additive abelian group isomorphic to Z/31 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 43

The last one is important since to exactly map a point $g$ and its multiples, they must have the same order in each group.
Actually, to map a curve to another, or a subgroup, one doesn't need the same $G$ to happen in both. The order is enough. We have to look for orders of the elements.
Let's look at your curves;

EllipticCurve(GF(17),[0,7])

Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 17
18
Additive abelian group isomorphic to Z/18 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 17

E = EllipticCurve(GF(31),[0,7])

Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 31
21
Additive abelian group isomorphic to Z/21 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 31

E = EllipticCurve(GF(43),[0,7])

Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 43
31
Additive abelian group isomorphic to Z/31 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 43

E = EllipticCurve(GF(67),[0,7])

Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 67
79
Additive abelian group isomorphic to Z/79 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 67

They are all isomorphic to $Z/18,Z/21,Z/31,$and $Z/79$, respectively.
The orders;
for i in (1..E.order()):
    print(E[i], E[i].order())

In the first curve, the orders of the elements are $1,3,2,6,9,18$
In the second curve, the orders of the elements are $1,3,7,21$

So, we have common order of $3$, then we can map these elements (5,8) and $(0,10)$ to each other.

A sample curve that is not isomorphic Z/n
E = EllipticCurve(GF(25, 'x'), [1, 1])

Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field in z2 of size 5^2
27
Additive abelian group isomorphic to Z/9 + Z/3 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field in z2 of size 5^2

Birational Equivalent is another story!


How many possible Enigma machine settings? I'm trying to calculate the amount of settings the enigma machine has. I have found several sites regarding this topic, but it seems like there are two answers to my question. The first answer is 158,962,555,217,826,360,000 and the second is 107,458,687,327,250,619,360,000. Where the difference is that in the second answer, it has been taken into account that the notched rings on the enigma could be set as well, giving 26 * 26 = 676 more settings than the first answer.

But which answer is the right one, and why? How many possible different Enigma machine settings are there and how can one determine this number?

Depends on the exact model. Wikipedia is your friend: "Combining three rotors from a set of five, the rotor settings with 26 positions, and the plugboard with ten pairs of letters connected, the military Enigma has 158,962,555,217,826,360,000 (nearly 159 quintillion) different settings."

More in detail: if you consider an Enigma with 3 rotors out of 5 rotors of model known to the cryptanalyst, and a plugboard with 10 wires

the 3 rotors out of 5 can be ordered in ${5!\over(5-3)!}=60$ ways.
for each rotor, the relative position of the wiring to the rest of the rotor can be set to 26 positions; for $26^3=17,576$ combinations.
each of the 20 extremities of the 10 wires can be plugged into any of 26 positions not otherwise occupied, with the two extremities of a given wire equivalent, as well as the 10 wires themselves; for
${26!\over(26-20)!\cdot2^{10}\cdot10!}=150,738,274,937,250$ combinations.

There are thus
$${5!\over(5-3)!}\cdot26^3\cdot{26!\over(26-20)!\cdot2^{10}\cdot10!}=158,962,555,217,826,360,000$$
possible settings, for a definition of that not including the initial rotor position, even though that's not initially known to the cryptanalyst.


Encrypt array of int for individual retrieval I have limited exposure to cryptographic terminology, so please bear with me.

My end goal is to encrypt integer IDs, before transmitting them to a web client in a list of search results, in a way that prevents enumerating IDs.

Only the transmitting authority should be able to decrypt them. The client will select a single ID from the provided encrypted list, and return it to the authority (in order to request details). This requested ID from the client should be verifiable as authentic. Also, multiple encrypted representations for each ID should be present (the decryption function should be "surjective" relative to a single ID, so that it is not possible to determine from looking at two encrypted IDs whether or not they represent the same decrypted value, thus preventing correlating multiple searches to discover valid IDs).

Here's an ugly example I've devised: Given an array of int32, prepend each with both a 16-bit constant (verified upon decryption, used as a MAC) and a 16-bit random value (discarded upon decryption, provides the surjective quality). Then perform 64-bit blocksize ECB encryption on the resulting array of int64.

My first problem with this example is that I'm not aware of any 64-bit ECB ciphers that are common enough to find in my library (.NET). My second is that I made it up - there's probably a much more direct and less naive route already supported by existing schemes/encryption libraries. My third (less important) issue is that I'm doubling the wire size of my result set (which could be reduced by, for example, requiring the surrounding IDs to be included in the request).

Note that I'd be willing to require client-application cooperation. For example transmit a separate signature, use CBC, and require both the desired ID and the previous one in the following client request. (Note a weakness here is that by varying only one of the IDs, all valid IDs are enumerated.)

Any help, even just correcting my terminology so I can try some new Google-fu, is appreciated.

As CodesInChaos comments, your basic idea seems sound, although a 64-bit block size leaves you with a rather low security margin.

Personally, I'd be more comfortable using a cipher with a 128-bit block size (like AES), zero-padding the IDs to 64 bits, appending 64 random bits and encrypting the resulting 128-bit block.  This means that:

even with the birthday paradox, an adversary must retrieve about 232 encryptions of a given ID in order to have even odds of finding one duplicate, and
the probability of a random encrypted block decrypting to a valid ID is N out of 264, where N ≤ 232 is the number of valid IDs in your database.

Now, you also ask whether there is a standard cryptographic scheme for achieving your goals.  In fact, there is: it's called authenticated encryption, and can be implemented either by combining a traditional encryption mode such as CBC, CTR or OFB with a message authentication code in the Encrypt-then-MAC construction, or by using a specialized authenticated encryption mode such as EAX, OCB or GCM.

Authenticated encryption provides IND-CCA2 security, which is short for indistinguishability under an adaptive chosen-ciphertext attack.  This is a rather strong security property, and, in particular, subsumes your goals that an adversary should not be able either to guess a valid ciphertext or to determine that two ciphertexts correspond to the same plaintext.

The main disadvantage of standard authenticated encryption modes, for your purposes, is that they normally impose an overhead of at least two whole cipher blocks: one for the IV and one for the MAC.  That said, their security margin is also correspondingly larger; for a standard AE mode using a 128-bit block cipher, the number of encryptions needed for a collision is around 264, and the probability of a successful forgery is at most one in 2128.

For some modes, it may be possible to reduce this overhead by making the IV implicit.  For example, with GCM (or, say, CTR mode with HMAC), you could just transmit a random initial counter value for the first item in your list, and then use successive counter values for the rest of the list.  Also, some modes support truncating the MAC to reduce the output length at the expense of the security margin.  Thus, combining an implicit IV with, say, a 32-bit truncated MAC, you could achieve security comparable to the 128-bit single block method described above (i.e. forgery probability less than one in 232) with a 64-bit output per item.


Does Java SunJCE Provider use AES for encrypting nonce in Poly1305? RFC 8439 states:

  AES is used there for encrypting the nonce, so as to get a unique (and secret) 128-bit string, but as the paper states, "There is nothing special about AES here.  One can replace AES with an arbitrary keyed function from an arbitrary set of nonces to 16-byte strings."

If an implementation like SunJCE uses AES, ChaCha20-Poly1305 may not have any performance advantage over AES in non-Intel architecture

If we look into the source code of the JDK 11 where this feature was introduced, we can see it is based on RFC 7539, not on RFC 8439. However, a quick look showed that they may be compatible none-the-less.

although the Poly1305 MAC is defined using AES, the AEAD cipher is not;
the AEAD construction is defined in section 2.8 and points to 2.6: Generating the Poly1305 Key Using ChaCha20.

So the nonce is taken directly as a parameter, and it is not generated by the application at all. However, the Poly1305 key is generated from this nonce. Note that a MAC does not require an IV or nonce otherwise, only a key. For Poly1305 that key needs to be unique, which is why it is calculated from the nonce used by the ChaCha20-Poly1305 AEAD cipher.

So the authentication tag is protected using a ChaCha20 block encrypt rather than AES:

    authenticator = new Poly1305();

    // Derive the Poly1305 key from the starting state
    byte[] serializedKey = new byte[KEYSTREAM_SIZE];
    chaCha20Block(startState, 0, serializedKey);

    authenticator.engineInit(new SecretKeySpec(serializedKey, 0, 32,
            authAlgName), null);

In other words, the ChaCha20Cipher class which implements the  ChaCha20-Poly1305 AEAD cipher (using the Poly1305 authenticator class) doesn't mention or reference the AES or any other block cipher.

Note that I've previously mentioned in a deleted answer that stream ciphers can generally not be used to perform this kind of key derivation from the nonce. This is correct; however, ChaCha20 operates on blocks underneath, which makes these kinds of operation possible none-the-less.

What was correct in the deleted answer is that the block encrypt for creating the key for Poly1305 is performed only once, so any speed difference between block ciphers to derive the key is inconsequential for larger messages. Only the Poly1305 calculation is performed over the whole message - that's the whole idea of these fast MAC implementations that enable "1.5 pass authenticated ciphers".


What is the difference between "Linkable" and "Traceable" Ring Signatures? In particular, both papers on Traceable Ring Signatures and Linkable Ring Signatures propose they are fit for the creation of ballots. The Wikipedia Article on Ring Signatures, though, suggests Linkable Ring Signatures can't be used for that purpose. Which is right?

The Wikipedia Article on Ring Signatures, though, suggests Linkable Ring Signatures can't be used for that purpose.

The Wikipedia article doesn't say or imply that. It lists possible applications:

Linkable Ring Signatures: "... One of the possible applications can be an offline e-cash system."
Tracable Ring Signatures: "... An e-voting system can be implemented using this protocol."

First, neither claims explicitly that you can create ballots with it, which is only a part of an e-voting system. And then if something is listed for one of them, it doesn't mean that you can create that only with this one.

And then, you have the wrong source for link signatures. Liu and Wong also wrote Linkable ring signatures: Security models and new schemes just one year later, which builds upon your linked paper but refines it. (although I can't find a publicly available version atm)


What is the minimum and maximum value of an RSA private exponent? Is it possible to calculate the minimum and maximum value of the private exponent for an RSA key, for example for a 1024 key size? In other words, what is the range of values in which the private exponent can occur?

In summary:

Modern practice is to fix a small public exponent $e$ such as $e=2^{(2^4)}+1=65537$, then choose a public modulus $N$ of $\text{nlen}$ bits (the key size) with large random prime factors compatible with $e$, then compute the RSA private exponent $d$ from that. With near certainty, that $d$ will be at least $\text{nlen}/2$-bit. That can be used as a minimum for other methods. For RSA1024, that's $d$ at least 512-bit.
If given a choice, compute $d=e^{-1}\bmod\lambda(N)$, and it's bit size will be strictly lower than the key size. For RSA1024, that's $d$ at most 1023-bit. See Carmichael function for the definition of $\lambda(N)$.
Otherwise, it is still recommendable to keep $d<N$ for compatibility with common software. For RSA1024, that implies $d$ at most 1024-bit.

Note: by the mathematical definition, a positive integer $m$ is $b$-bit when $2^{b-1}\le m<2^b$. Computer implementations often measure the size of integers differently: adding one for sign, or/and rounding up to the next multiple of some power of two, or/and adding more overhead for headers.

Caveat: RSA1024 might be vulnerable right now to well-funded and competent adversaries. For new applications, it has been deprecated for a decade at least, and RSA2048 is considered OK only till 2020 or 2030, depending on source (see the Keylength website).

Minimum value

Negative $d$ work, but at the price of an extra inversion modulo $N$ at each use, thus have little practical interest. We exclude negative $d$ in the following.

When $e$ is fixed or chosen then $d$ computed (as is modern practice), the lower bound for $d$ is commonly $d>2^{\text{nlen}/2}$ (e.g. in FIPS 186-4), or $d>0$, or just unspecified. In fact, $d$ will typically be few (if any) bit(s) less than $\text{nlen}$, and $d<2^{\text{nlen}-64}$ should seldom occur. $d>2^{\text{nlen}/2}$ is met with overwhelming probability for any sound key generation procedure that computes $d$ without attempt to minimize it, or in other words where:

$d$ is computed from the public exponent $e$ and the prime factors of the public modulus $N$ (these factors are noted $p$ and $q$ is the common case of $N=p\,q$; or more generally $r_i$, with $N=\prod r_i$, and $p=r_1$, $q=r_2$ ).
and $e$ and the $r_i$ are chosen independently of each others, except for meeting the requirements: the $r_i$ are suitably large random primes, $\gcd((r_i-1),e)=1$ (implying $e$ odd), and $e\ge3$.
Exceptions to the above:

Sometime it is additionally checked that the $r_i$ are suitably different from each others. For safely large $r_i$ and good random generator, such check never fails.
From a mathematical standpoint, $e$ can safely be chosen as $N$, in which case it depends on the $r_i$. That is the case in Christopher Cocks's 1973 cryptosystem, see here for bibliography.

In any case, $d$ must be much larger than $N^{0.292}$ in order to avoid an attack by Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999. A safer lower bound is $d>\sqrt N$, or the aforementioned $d>2^{\text{nlen}/2}$. That consideration is relevant at least when $d$ is chosen, as in in R.L. Rivest, A. Shamir, and L. Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystem (in CACM, 1978).

Maximum value

The upper bound for $d$ depends on context.

From a mathematical standpoint, there is no limit: any $d$ with $\lambda(N)$ dividing $e\,d-1$ is acceptable, where (for distinct $r_i$ ) $\lambda(N)$ is computed as the Least Common Multiple of the $(r_i-1)$. We can add any multiple of $\lambda(N)$ to any valid $d$, and obtain another valid $d$.
In a PKCS#1 context, we must additionally have $0<d<N$, which implies $d<2^{\text{nlen}}$. That leaves at least two possible $d$, sometime more.
Some definitions of RSA state that $d=e^{-1}\bmod\varphi(N)$, where (for distinct $r_i$ ) $\varphi(N)=\prod(r_i-1)$, see Euler's totient. This implies $d<\varphi(N)$, which implies $d<N$ and $d<2^{\text{nlen}}$. For usual RSA with two factors, that method of computing $d$ implies $d<N-2\sqrt N$, thus the upper bound is slightly lower than $d<N$ in PKCS#1.
In a FIPS 186-4 context, it is required that $d=e^{-1}\bmod\lambda(n)$. That is the smallest positive $d$, and it is often markedly lower than with the previous method. We get $d<\lambda(N)$, thus $d<\varphi(N)/2$, thus $d<2^{\text{nlen}-1}$, and for two factors $d<N/2-\sqrt N$.


Is perfectly secret key exchange provably impossible? We know that perfect secrecy in encryption is possible (one-time pad). Now, the concept of key exchange like Diffie-Hellman is that we can establish a shared key without an interceptor knowing, and with no previous communication.

Obviously, for Diffie-Hellman as such, an interceptor can actually find the shared key; it would just take them ridiculously long. But I'm wondering, is it possible to make it impossible for the interceptor to find out the shared key?

I know that no such key exchange currently exists, but is it proven that it's impossible for such a scheme to exist? Or is there a chance it could be invented?

Lets start with a set of basic assumptions.

The communication channel transmits a sequence of symbols with each symbol taken from a finite set, there is no weird quantum stuff going on.
The attacker can obtain a complete record of the symbols that were transmitted.
The end systems are finite sized computers fed from a finite sized random number generator and run for a finite amount of time.
The purpose of the key exchange algorithm is to establish a shared secret.
No secrets were known by the end points prior to the start of the key exchange process.

I believe that in this case an attacker with unlimited computing power can always crack the key exchange.

The attacker can simply enumerate all the possible outputs of the random number generator. Feed each one into the key exchange algorithm and compare the data that the algorithm generates with the data that was observed on the wire.

If the data exchanged on the wire matches then the shared secret must match.


How is the DUHK attack specific to the ANSI X9.31 RNG? Recently, the DUHK attack on bad RNG implementations of hardware devices has been published.

The attack is based on a (known or reverse engineerable) hardcoded key, which is used for a ANSI X9.31 based PRNG to create key material.

According to the blog post by Matthew Green, the attack is explicitely based on the X.931 generator: "ANSI X9.31 (and its cousin X9.17) is over twenty years old. It’s (fortunately) been deprecated as of 2016, but a huge number of products still use it. This algorithm should have disappeared ten years earlier"

But I keep wondering, how this attack is specific to ANSX X9.31. As far as I understand it, the very same problems would arise, if a hardcoded key would be used with any of the other keyed PRNG standards (like HMAC_DRBG or CTR_DRBG). What am I missing?

As far as I understand it, the very same problems would arise, if a hardcoded key would be used with any of the other keyed PRNG standards (like HMAC_DRBG or CTR_DRBG). What am I missing?

The issue is that, for X9.31, the key really is a long term key; it is never updated as a part of the RNG process.

That is, the state of X9.31 consists of a 'current state' (64 or 128 bits), and a 'key'; when you generate the next batch of outputs, you update the 'current state', but not the 'key'.  Hence, if you start with a fixed key, you'll end up using that for the life of the PRNG.

So, if we assume that the X9.31 has been used for a while (and so the attacker doesn't know the exact state; one of its input is the 'current time', that does act as a weak entropy source).  However, if X9.31 starts with a fixed key, that key is still in effect; if the attacker sees one output and has a guess of the current time, he can then predict future outputs (and previous as well, the state update function is invertible if you know the key).

In contrast, for the HMAC_DRBG or the CTR_DRBG generates, when they generate a batch of output, they update the 'current state', but they also update the 'current key'.  So, if the PRNG is used for a while (and so the attacker doesn't know the state of the PRNG), the attacker won't know anything about the HMAC_DRBG or CTR_DRBG key, hence the attacker has no advantage in predicting future (or previous) outputs.

Of course, if the PRNG starts off with no entropy (fixed key and state), and doesn't get enough entropy before the attacker observes the output, the attacker can easily recover the state (and predict outputs); this is true for any PRNG.  What is special about X9.31 with a fixed key is that this also holds even if the state has been given enough entropy.


How do I verify a message came from me? I have many clients and a single server, and on each of these clients I want to be able to verify a message did indeed come from my server. My idea was to send some sort of key with cryptographic significance.

For example, say I wanted to send a boolean from the server to the client, I could send a message like this:

{
    "boolean": true,
    "key": 30
}

In this trivial example, the significance of the key is that it is divisible by 3. So the client would perform a check like this:

if payload["key"] % 3 == 0:
    valid = True
else:
    valid = False

Is this a good idea provided I use a more secure algorithm? If so, what would you suggest?

If not, how should I go about verifying the authenticity of the message?

Thanks.

EDIT:

My understanding of the HMAC approach is as follows:

Firstly you generate a key which will be stored on the server and all of the clients. For example,

import random
key = bytes(hex(random.getrandbits(128)).encode("utf-8"))

Then, on the server when you want to send a message to a client, you generate a HMAC as follows and send it along with the message:

import hmac
import hashlib
h = hmac.new(key, str(payload["key"]).encode("utf-8"), hashlib.sha3_256).hexdigest()

Then on the client, you run this again with your key and if they match then it is a valid message.

I have two problems with this approach. Firstly, there are only two possible HMACs - one for true and one for false. Additionally, hardcoding the secret key into the client doesn't sound like the best of ideas.

Yes, this is a way to establish authenticity through the use of a so-called "shared secret".

In practice you could do it using the HMAC algorithm and a shared key between the server and clients.

Notice that here, there is a problem with shared keys: that is that the whole system is not secure as soon as one client is breached.
There are also other ways to establish authenticity of messages without this problem by the mean of public key cryptography.
In this case your server would be the only one knowing the secret key, and would sign its messages with it, so that the clients, knowing the public key of the server could verify the authenticity of the messages.
Typical algorithms to do so are ECDSA or Ed25519.

Edit

As requested, here are more details regarding how these would work in practice:

HMAC

This is almost exactly as you described in your own edit.

You create a secret HMAC key, which you store on both the server and the clients.
You have a message which you want to authenticate, so you just "HMAC" it on the server using the secret HMAC key, and you send both the message and the HMAC digest to your client(s).
The client receives the message and the HMAC digest and computes the HMAC digest of the message, and then verifies it matches the one it received.

There is just one slight caveat I have with your way:
you pass the value str(payload["key"]).encode("utf-8") as the msg in your HMAC call, but what is contained in your payload["key"] value?
You would rather have your payload itself being passed to the HMAC and then append the hexdigest to the message, thus you'd have a structure a bit like this for your messages:

{
"payload": {
    "boolean": true,
    },
"mac": {
    "hmac-digest": "6eb6a866856dc7ea74c0d6bd41993106f696cc5091f88f188efbb23def6d248b"
    }
}

Now, as you said in your edit, HMAC values being deterministic, if you authenticate twice the same message, you'd get twice the same digest.
But HMAC is about protecting authenticity of the messages, not confidentiality. (Notice that with HMAC, you get both authenticity and integrity of the message.)

Also, it is true that HMACed messages are trivially vulnerable to replay attacks, but so are public-key signed message.
Adding a replay protection to your protocol is not that easy, and usually requires being stateful.

To have replay attack protection, you'd typically need to have a message index value, and keep track (thus being stateful) of the said index on each clients. (And reject any message that does not increase the index value.)

{
"payload": {
    "boolean": true,
    "index": 12
    },
"mac": {
    "hmac-digest": "a1b0271d1eea012c81f06488645ce026914e095d9d770d7d213efbd968be3fe2"
    }
}

But notice that this is still vulnerable to replay attacks between clients, if all clients are not getting the same message at the same time...

Thus, you might want to include sender and receiver data in your payload, so that these are authenticated as well... as you can see the complexity of your protocol is increasing relatively fast!

Public key crypto

So, if you are to use public key crypto to authenticate your messages, the process would only differ slightly from the previous workflow:

You create a private key and its corresponding public key on the server and store them there.
You store the public key of the server on each of your clients.
You have a message which you want to authenticate, so you sign it on the server side using the private key, and you send both the message and the signature to your client(s).
The client receives the message and the signature and uses the public key of the server to verify that the signature was indeed produced by someone knowing the server's private key.

There a multiple algorithm to do so:
- ECDSA
- Ed25519
- RSA-PSS

Notice that the same caveats as with HMAC applies here: you might need to authenticate more than just the message to avoid replay attacks and any other abuse of your protocol.


Can the key-complement property of DES be used against 3DES? The comments in this recent question about the security of 3DES made me wonder if the key complement property of DES (which reduces its security by ~1 bit) can be used in the meet-in-the-middle attack on 3DES.

Can the complexity of the attack be reduced by 1-2 bits by making use of the complement property to rule out more keys than are being directly tested?

Sure, the difference between 112 and 110 bits probably does not matter in practice.

yes,it is possible because in meet in the middle attack on 3DES,see below

with Complementation Property of DES in red arrow,you can search $2^{55}$ key space instead of $2^{56}$,and for green arrow,you have $DEC_{K2}(ENC_{K1}(M))$ that without key Complementation Property,you need $2^{112}$ operations but with key Complementation Property of left ENC and middle DEC block,you need $2^{110}$ operation and in total you need $2^{55}+2^{110}\approx 2^{110}$ operations

NOTE: in green keyspace(arrow), you should calculate one encryption and then one decryption for your known plaintext,for both decryption and encryption of DES,if you test one pair key($K_{1}$ and $K_{2}$) and calculate the middle variable,because of Complementation Property of DES,you don't need to have a decryption and encryption for $K'_{1}$ and $K'_{2}$ so with every calculate of $DEC_{K2}(ENC_{K1}(M))$,you test 4=$2^2$ keys


Find collision in Ajtai's hash function using short vector Background

What is Ajtai's hash function?

Given a matrix $A \hookleftarrow U(\mathbb{Z}_q^{n \times m})$ and a column vector $\vec{m} \in \mathbb{Z}_d^m$, the hash of the message $\vec{m}$ is given by

$H(\vec{m}) = A\vec{m} \mod q$

Ajtai's SIS-lattice

The corresponding lattice for $A$ denoted by $L^{\bot}(A)$ is defined as all vectors $\vec{v}$ such that $A\vec{v}=\vec{0}$, in other words $L^{\bot}(A)$ is the kernel of $A$. Thus as far as I understand, to find a basis for $L^{\bot}(A)$ is essentially equal to finding a basis for the kernel of $A$.

The SIS-problem

The $\beta$-SIS problem is the problem of finding a non-zero vector $\vec{v}$ such that $A\vec{v}=\vec{0}$ and $\|\vec{v}\|\le \beta$. This problem is known to be hard.

Is the hash function collision resistant?

Finding a collision for the hash function is as hard as solving the $2d\sqrt{m}$ SIS-problem. That means, given a collision $(\vec{x}, \vec{y})$ we can easily compute a short vector in $L^{\bot}(A)$ as $\vec{x}-\vec{y}$.

Why does it work? We have a collision, i.e $A\vec{x}=A\vec{y} \rightarrow A(\vec{x}-\vec{y})=\vec{0}$, so the vector $\vec{v}=\vec{x}-\vec{y}$ is in the lattice. Next, due to triangle inequality we have that $\|\vec{v}\| \le \|\vec{x}\|+\|\vec{y}\|$. Since both $\|x\|_{\infty} \le d$ and $\|y\|_{\infty} \le d$, it follows that $\|\vec{v}\| \le 2d\sqrt{m}$.

Question

Now, my question is; is it possible to go the other way around? That is, is it possible to find a collision for Ajtai's hash function given a short non-zero vector found e.g using Lentra-Lenstra-Lovász lattice reduction algorithm?

It depends on the exact domain of the hash function and the quality of the SIS solution, i.e., its norm (and the choice of norm itself).

Suppose the hash domain is $\{-d, \ldots, d\}^m$, i.e., vectors of $\ell_\infty$ norm at most $d$. Then any nonzero vector in Ajtai's lattice having Euclidean norm at most $d$ collides with the all-zeros input. (Actually, $\ell_\infty$ norm at most $d$ suffices.) Thus, finding short enough lattice vectors yields collisions.

But now suppose $d=1$, say. (This is a typical choice.) For standard parameters, the shortest (in Euclidean norm) nonzero vectors in Ajtai's lattice have norm about $\sqrt{n \log q} \gg d = 1$.  Thus, short vectors in Euclidean norm (which is what typical lattice-basis reduction algorithms deliver) may not be sufficient to yield a collision.  Instead, finding a collision requires finding a shortest nonzero vector in the $\ell_\infty$ norm. But little is known about lattice-basis reduction algorithms for this setting.

More details on these issues can be found, e.g., in the paper "SWIFFT: A Modest Proposal for FFT Hashing" (I am a coauthor).


consequences of using fixed values with OAEP With DSA / ECDSA using a fixed $k$ means the private key can be trivially easily calculated from two different signatures. To remedy this RFC6979 Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) was developed.

OAEP / PSS, as described in PKCS#1 v2.0+, used randomized values as well.

For PSS I guess it isn't a huge problem since the only randomized element is the salt and the salt has a variable length with 0 being a valid length.

For OAEP my assumption is that the only issue with a fixed seed is that if the same message were encrypted twice you'd be see the same ciphertext each time. Or is there another more severe issue that the randomized seed protects against?

I note that the original encryption described in PKCS1 employees randomized padding as well.

If you encrypt something with low entropy but use a fixed seed for OAEP, it is trivial to brute force it, and verify your guesses with public key, while randomized all or nothing padding will make verifying a guess impossible.

In the context of signatures rather than encryption, it doesn't seem as severe, but you are supplying the attacker with a bunch of related plain text cipher text pairs which can't be a good idea.


Fractal Merkle Traversal I am studying Fractal Merkle Tree Traversal algorithm in the book “Post Quantum Cryptography” (PDF). On the [pag. 54] I don't understand this paragraph:

  We may determine the number of pebbles returned at these times by observing that a leaf is returned every single round, a pebble at height
  $ih + 1$ every two rounds, one at height $ih + 2$ every four rounds,
  etc.

Now, please look at Figure 4.1 of “Merkle-Tree Traversal Techniques” (PDF):

In round 1 is true that leaf $n_0$ no longer needed. Now in paragraph says "pebble at height $ih + 1$ every two rounds, ... " then for the second round, in the case of $i = 1$ and $h = 1$, we see that in the height $i*h+1=2$ should have a node that is no longer required. Which would be in this example that node?

Also, can someone explain the meaning of $A$ in the equation on page 55?
$$A+[A/2]+[A/4]+\cdots+[A/2^h] $$

First, the passage you refer to is on page 55, 2nd paragraph. And it would also be great if you'd announce that figure 4.1 is actually in a different document ;-) took me quite a while to figure this out. Now to your question.

So, I assume you understand the paragraph? You have to note that a round here corresponds to $2^{(i-1)h}$ "whole tree rounds". Now, the paragraph only says that every "round" a new node on level $ih$ is not required anymore, every two rounds one at level $ih+1$, and so on. Figure 4.1 is a bad example because the root of a subtree is never stored and hence there is no node on the second internal level of the subtree to discard. However, ignore everything green and red in the picture and assume this tree of height 3 is our exist subtree. Then, in the first round node $n_1$ is not needed anymore. In the second round, node $n_0$ and node $n_{23}$ can be discarded. So, Gustavo was right.

Regarding the $A$... it is simply $a$, I assume this is simply a typo, occured when harmonizing the notation of the different papers. You see, in round $a$ you discarded $a$ pebbles at level $ih$, $\lfloor a/2\rfloor$ pebbles at level $ih+1$, and so on.


convert $v-u \cdot s$ to centered representation as described here seems to work


Discrepancy between 3DES in OpenSSL and PyDES I'm trying to encrypt some data using triple DES ECB, but I get a discrepancy between OpenSSL and the pyDES library I'm using.

When trying to get a KCV value, I'm using a file consisting of 8 bytes each with value 0.

I'm using the following OpenSSL command (des-ede3 chosen based on this):

openssl enc -des-ede3 -pass pass:abcdefgh12345678abcdefgh -in empty8.bin -nosalt | xxd

which results in:

00000000: 17f7 b498 bd79 4d55 5e40 aa9c 2907 44bb  .....yMU^@..).D.

I'm using the following Python script, based on this question:

import binascii
import hashlib
import base64
from pyDes import *

key = 'abcdefgh12345678abcdefgh'

fileInput = open("empty8.bin", "rb")
data = fileInput.read()

print('key: ' + str(key))

k = triple_des(key, ECB)
d = k.encrypt(data)

print('KCV: ' + str(binascii.hexlify(d)[0:8]))

which results in:

key: abcdefgh12345678abcdefgh
KCV: b'37c92746'

I've also tried using http://online-domain-tools.com/ for a reference, which gives the same result as the Python code.

Can anyone offer any insights into why OpenSSL produces a different result?

In Python and on that website, you're entering a key. A 3-DES key consists of 24 bytes. You picked a key that's some nice printable text, but a key in general is binary, randomly generated.

With the OpenSSL command line, you're supplying a password (or passphrase, the two words are synonyms). A password is not a key: it's typically not fully random, consists only of printable characters, can have any length, ...

OpenSSL uses a key derivation mechanism to calculate a key from that password. To generate a key from a password, you need to perform stretching and randomize the process with a salt, which OpenSSL does, although not very well.

To get the same result with openssl en, tell it that you're supplying a key, with the -K option.

Generally speaking, the openssl command line is more of a demonstration tool than a tool for serious usage. This is especially true of commands like enc. Don't expect things to be secure unless you have a very precise of what you're doing.

In any case...

  triple DES ECB

Hopefully this is for learning purposes, and even then, neither 3DES nor ECB have any advantage for learning. 3DES is an obsolete algorithm with no benefit over the modern standard AES or modern alternatives such as Camellia and ChaCha20. ECB is not really a proper mode, it's “don't bother with a proper mode”, and it isn't secure (so why bother encrypting?). Use a mode such as CTR or CBC for encryption (and learn to use an IV, which is necessary for any mode), or a mode such as GCM or CCM for authenticated encryption.


What does the $e$ operation mean in cryptography research papers? I read a cryptography scheme that it include the following operation:
$$c= H(e(g_1,g_n)^t)$$
where H is a hash function.
I need to know what the operation $e$ means.

It's the pairing function. This bilinear map which takes as Input the set $\mathbb{G}\times\hat{\mathbb{G}}$ (in the common case, eliptic curves), and output a group element in $\mathbb{G}_T$ the group target.
In the symmetric case (Type 1), because $e$ is bilinear, you can deduce that $$e(g_1, g_n)^t= e(g, g)^{x_1x_nt}$$
with $x_1,x_n$ respectively be the discrete logarithms of $g_1, g_n$ in base $g$.
For more details check:
https://en.wikipedia.org/wiki/Pairing-based_cryptography


More than one private key for RSA In an RSA-encryption scenario, Bob's public key pair $(n, e)$ is $(143, 43)$. An attacker Mallory tries brute-force and comes to $d = 7$ as the private key.
The value of $φ(143) = 120$ is not known to Mallory.
However from $43 \cdot d \equiv 1 \bmod 120)$, one can calculate the first positive element $d = 67$ from multiplicative group $d = 120 + 67n$ and $n \in \mathbb{Z}$
$d = 7$ clearly doesn't fit in that multiplicative group, so how come it can successfully decrypt the encryption?

This question can be summarized: the attacker found a $d$ that did not satisfy $e \cdot d \equiv 1 \pmod{ \phi(n) }$, but it works; what's going on.
It turns out that $e \cdot d \equiv 1 \pmod{ \phi(n) }$ is not necessary (it is sufficient).
The necessary and sufficient conditions are:
$$e \cdot d \equiv 1 \pmod{p-1}$$
$$e \cdot d \equiv 1 \pmod{q-1}$$
If both of these hold, then $d$ will always work [1]; conversely if $d$ always works, then both of these hold.
These two conditions can be summarized as a single relation:
$$e \cdot d \equiv 1 \pmod{\text{lcm}(p-1, q-1)}$$
This $\text{lcm}(p-1, q-1)$ modulus is known as the Carmichael function of $n$.
In the specific example you have, $\text{lcm}(p-1, q-1) = 60$, and we have $7 \cdot 43 \equiv 1 \pmod{60}$, and hence $d = 7$ works

[1]: Assuming $p, q$ are distinct primes.


Is an AEAD the recommended method to add encryption + HMAC to a protocol? Assuming you are dealing with a competent developer/team, and you are advising on adding security to their protocol. Also for the time being lets not worry about the key establishment and validating the other end aspects of the protocol.

Would you recommend AEAD, specifically AES-GCM over AES 256 + HMAC with SHA2?

I ask because there are implementation/usage caveats with AES-GCM as mentioned here.

I think you're a bit unclear about the factoring and abstraction layers here.  A correctly designed AES + HMAC construction is AEAD.  This is because AEAD is about what interface and contract the cryptography should expose to its callers; while the choice between GCM vs. encrypt-then-HMAC is a choice between implementations.  Ideally, the code that calls an AEAD would do so through an interface that abstracts away the difference between the two implementations you propose, and the code that implements your AES + HMAC construction would expose the same caller interface as AES-GCM.

If you're looking cooking up your own AES + HMAC combination, I'd recommend you rather put some effort into finding a ready-made and well vetted third-party library.  Whether it uses AES-GCM or an AES + HMAC construction isn't the most important thing.  As the saying goes, don't roll your own.


Can the input to a one way function be pseudorandom? I know that normally a one-way function takes in a completely random input, but can a one-way function take in something pseudorandom instead of completely random? Will it still be a one-way function? Intuitively it seems like it would be, but I don't actually know why.

The definition of a one=way function, according to Wikipedia, is:

A function $f : \{0,1\}^* \to \{0,1\}^*$ is one-way if $f$ can be computed by a polynomial time algorithm, but any polynomial time randomized algorithm $F$ that attempts to compute a pseudo-inverse for $f$ succeeds with negligible probability. That is, for all randomized algorithms $F$ , all positive integers $c$ and all sufficiently large $n = \mathrm{length}(x)$ ,
$${\displaystyle \Pr[f(F(f(x)))=f(x)]<n^{-c},}$$
where the probability is over the choice of $x$ from the discrete uniform distribution on $\{0,1\}^n$, and the randomness of $F$.

The definition doesn't say anything about pseudorandom choices of $x$, and this means that we do not have to contemplate such choices when assessing whether $f$ is one-way.  So your question if $f$ would "still be a one-way function" if $x$ is drawn pseudorandomly has a trivial "yes" answer.

The question I think you're actually interested in is this: if $f$ is a one-way function but $x$ in the definition above is drawn from some pseudorandom distribution $D$ over $\{0,1\}^n$, could there exist a polynomial time randomized algorithm $F$ that finds a pseudo-inverse of $f(x)$ with non-negligible probability?  Well, if there is such an $F$, then we could use it to construct a distinguisher for $D$:

Accept an input $x$;
Output $1$ if $f(F(f(x))) = f(x)$, $0$ otherwise.

Now:

Since we assumed that $F$ succeeds with non-negligible probability for $x$ drawn from $D$, in that case the distinguisher will output $1$ with non-negligible probability;
Since we assumed that $f$ is one way, this means when $x$ is random $F$ outputs $1$ with negligible probability;
The difference between a negligible probability and a non-negligible one is non-negligible.

But that contradicts our assumption that $D$ is pseudorandom, so there cannot be such an $F$. In plainer English: feeding pseudorandom inputs to a one-way function is not significantly likelier in practice to pick "bad" (easy to invert) inputs than choosing inputs at random.


How to handle authenticated encryption for big files? First I need to mention that I can't use BouncyCastle to implement this solution.
I have to encrypt files into the file system. Those files are not going to be tranfered over the wire to any other location. They are only going to be stored in the server for later use by an application installed there. The file system may or may not be encrypted at an OS level, but that's something that I can't count on.
My files are going to be big files (say from several hundreds of megs to some times a couple of GBs). And they will be created on a regular basis, so I can expect to have a growing number of them. Also, sometimes some of this files are going to be deleted cause they may no longer be needed, and some other times files will be kept for years.
I already have the encryption in place, with AES/CBC/PKCS5Padding, using a 256 bit key and  I/O Cipher Streams. I have no authentication thought.
I don't think I can assume that it is safe to just encrypt and not use authentication as the server could be hacked I guess and the files stolen.
Also, by reading several questions it's clear that no authentication is just someting I shouldn't even think of.
So what are my options here then? I see 2 with some pro/cons analysis:
Option 1: AES/CBC + MAC (say with SHA-256)
Pros

Already have the encryption part working
Supported by Java with no extra libs

Cons

I have to deal with the computation of the MAC
I have to deal with appending the mac to the file and extracting it later
I will have to handle validation myself.
Lots of room for me not getting that right I'm affraid.

Option 2: Use GCM operation mode
Pros

Forget about handling tag computation / message authentication
Supported by Java (I'm using 1.8, so the default provider supports it)

Cons

I found that there are people who wouldn't recommend it.
Also this post seems to suggest that performance is somewhat an issue with Java8, but that's something I haven't verified (Update: @archie pointed to here and here that comfirm the performance issues).
It is badly broken in Java 1.7. I have yet to verify it works ok in Java 1.8 (update: this thread verifies that problems are still present in Java 8)
I'm using a single symmetric key for encryption. I'm worried about how to manage the nonce so I don't break the security properties of the algorithm (My current implementation gets the IV from cipher.getIV() after the Cipher is initialized. I'm not sure if that's good enough for GCM or if I need to take other special considerations.)

Are those options that I mention valid? What about the pro/con analysis? Is there any other suggestion you would have? Which approach would you choose?

If you definitely can't use other libraries such as Bouncy Castle, your best option is probably to just add an HMAC authentication tag (it should be easy to write a MacInputStream/MacOutputStream to chain it into your existing pipeline).

The primary reason is that the JDK 8 (at least up to 1.8.0_25) GCM implementation suffers from two problems that make it impractical for large files:

The implementation buffers the entire plaintext on decrypt (this is intended to prevent release of unauthenticated plaintext, but cripples the cipher implementation for uses that handle that at a higher level in the security protocol)
The performance is crippled (3MB/s on my server) due to a naive multiplier implementation and no hardware acceleration for the GCM calculations (AES in JDK 8 is AES-NI accelerated and very quick, but AES/GCM is completely dominated by the broken GCM performance). There are intentions to implement hardware acceleration, and there have been third party submissions to improve the performance with, but these haven't made it to a release yet.

If you go with the AES/CBC + HMAC option, you'll also want to make sure you have independent keys for the encryption and Mac (e.g. using something like HKDF to generate the two keys from a single master key).

If you can use Bouncy Castle (even using the lightweight API if your restriction is that you can't use another JCE provider) then the OCB, GCM and EAX implementations in that will give you better performance (and take away a bunch of the manual fiddling you'll have to do with the HMAC approach).


ECDSA: with knowledge of private key, can we make signatures with partially chosen content? In ECDSA, with knowledge of private key, can we make signatures with partially chosen content?
Detailing that: In ECDSA (with secp256r1 curve and SHA-256 hash), assume we know the private key, the message, and can choose the per-signature random. It that helps, assume we can choose the private key, and some of the message, so that it's hash is essentially random. Can we (more efficiently than by trial and error) make a signature $S=(r,s)$ valid for one key and message that, expressed as two 32-byte bytestrings concatenated, contains a bytestring that we can choose, or with certain characteristics?

Context: I'm helping (un-retributed) a standardization working group defining a cryptographically signed 2D code, and I try to make test cases where certain byte strings occur that could trigger incompatibilities between code generators and scanners. A simplified characterization is that there occurs in the signature a sequence of at least $u$ (like 3 to 7) bytes in a set of $v$ (10 to 13) values. That has probability about $(v/256)^u\,(65-u)$ to occur by chance, which gets tiny when $u$ increases. I'm not afraid of forgeries: The overall aim is testing out code encoders that could cause failures on the field (e.g. passengers blocked from boarding) because the combination of data and signature hits a corner case in some decoders.
Off-topic: there's rudimentary data compression built into most 2D codes. In Aztec aka ISO/IEC 24778:2008, encoders are encouraged to switch to Digit mode when long-enough bytestring segments consist of bytes in a set corresponding to ASCII  0123456789,. which get encoded as 4 bit/byte. When other bytes occur between two such sequences, it can be used Byte Shift that "can encode either isolated extended ASCII or control characters or long strings of byte data, possibly filling the whole symbol. At the end of the byte string, encoding returns to the mode from which B/S was invoked". In Digit mode there's no direct way to Byte Shift, this is done thru Upper/Lock or Upper/Shift (the later designed to insert a single uppercase ASCII letter in a sequence of digits). At the end of a Byte Shift entered from Digit mode thru Upper/Shift, decoders vary about if they return to Digit mode or Upper mode, and all hell breaks loose. Below is a minimal example that used to decode to ASCII 333j+33333 for ZXing (before version 3.2.2 of 8 Aug 2016) but 333j+ITIT for NeoReader and some others.
.

If the attacker has the ability of choosing the private key, then he can create a valid signature $(r,s)$ with a target value for $s$ for any message $m$. The attack works in the following way:
The attacker choose its target $s$, generates a random ephemeral key $k$ and computes the hash of the message $e = H(m)$.
Then the attacker computes the scalar multiplication $kG$ and takes $r$ as the x-coordinate of the result modulo $n$.
Then he computes the private key $d$ as:
$d = \frac{s - k^{-1}e}{k^{-1}r}$.
In this way $s$, when computed in the standard way: $s = k^{-1}(e+rd)$ will match the desired $s$.
In case the attacker can't choose the private key then I don't see how he can achieve his goal because in $k^{-1}(e+rd)$ he can control only $k^{-1}$ but that will pseudo-randomly influence the value of $r$.


Allowed key types in an SSL certificate What are the valid key types which can get signed (or generated and signed) by a CA to constitute an SSL certificate?
For the keys used in TLS, the key types I have seen are RSA and EC. Anything else?
For non-TLS use cases, are there any other key types that could be used? DH sounds like an option, but I don't think I have ever came across a certificate built upon DH public key.

RFC 5280 is the relevant standard for X.509 PKI certificates. Per section 4.1.2.7 of that standard:

The object identifiers for the supported algorithms and the methods
for encoding the public key materials (public key and parameters) are
specified in RFC3279,
RFC4055, and
RFC4491.

RFC 3279 specifies the following public key types:

RSA
DSA
Diffie-Hellman Key Exchange (DHKE)
Key Exchange Algorithm (KEA)
Elliptic curve DSA (ECDSA)
Elliptic curve Diffie-Hellman (ECDH)

RSA 4491 adds the following public key types:

GOST R 34.10-94
GOST R 34.10-2001

RFC 4055 adds some signature and other algorithms, but no additional key types.
Finally, section 4.2 of RFC 8692 adds that "certificates conforming to RFC5280 can convey a public key for any public key algorithm", so other types seem possible, although obviously certificates containing more exotic keys may not be interoperable.
Specifically for public-trust TLS certificates, the CA/Browser Forum Baseline Requirements restrict the key types to RSA and ECDSA (section 6.1.5), with additional restrictions appropriate to the type. For TLS more generally, the public key in the server certificate should be compatible with the selected key exchange algorithm.


Is scrypt a hashing function, encryption, or PBKDF? I have installed a python implementation of scrypt and noticed it has several functions, both an encrypt and hash function. Yet Wikipedia lists it as being used for PBKDF instead of PBKDF2. Is scrypt a hashing function for PBKDF2 or is it on its own an alternative?

Scrypt is most certainly a password-based-key-derivation-function.  So is PBKDF2, although it can be confusing since PBKDF2 is an eponym.  To add to the confusion, Scrypt uses PBKDF2 internally (which may be the hashing function you refer to), as well as the Salsa20/8 Core function (which may be the encryption function you refer to).  Further reading here.


Lagrange Interpolation for finite field GF(2^8), for Secret Reconstruction I'm using Lagrange's Interpolation technique to reconstruct the secret from a set of point pairs (x,y).
Since I only need the secret, not the whole polynomial, I have simplified the reconstruction process as follows:

  Let Secret $D = 10$, and we use a 3 out of 3 secret sharing scheme which generates 3 key pairs
      and all of them are needed to reconstruct the secret. We pick two random numbers as the coefficients.
      This gives us the polynomial $5x^2 + 2x + 10$.
      3 Points are generated from the polynomial: $(1, 17)$, $(2, 34)$, $(3, 61)$
      To get secret $D$, we only need to take care of the constant part of Lagrange's Polynomial.
  $$
\it{l}_{0} = \dfrac{(x-2)(x-3)}{(1-2)(1-3)} = \dfrac{(x-2)(x-3)}{2}
$$
  $$
\it{l}_{1} = \dfrac{(x-1)(x-3)}{(2-1)(2-3)} = \dfrac{(x-1)(x-3)}{-1}
$$
  $$
\it{l}_{2} = \dfrac{(x-1)(x-2)}{(3-1)(3-2)} = \dfrac{(x-1)(x-2)}{2}
$$

  By only considering the constant part of Lagrange's Polynomial (ignore $x$es),
      we can calculate secret $D$:

  $$
D = 17 \dfrac{(-2)(-3)}{2} + 34 \dfrac{(-1)(-3)}{-1} + 61 \dfrac{(-1)(-2)}{2}
= 10
$$

  which is our secret.

Now the same method should work for finite field GF(2^8) as long as the arithmetic are replaced with finite field arithmetic. However this is not the case:

unsigned int decodeByte(vector<pair<unsigned int, unsigned int>> keys) {
    int numKeys = keys.size();
    //extract the x's and y's from the vector
    vector<int> x;
    vector<int> y;
    for (int i = 0; i < numKeys; i++) {
        x.push_back(keys[i].first); //extract x
        y.push_back(keys[i].second); //extract y
    }

    GF256elm result(0);
    for (int i = 0; i < numKeys; ++i) {
        //calculate the constant term of lagrange interpolation polynomial
        GF256elm l(1);
        for (int j = 0; j < numKeys; ++j) {
            if (i == j)
                continue;
            GF256elm nxj = GF256elm(x[j]);
            GF256elm xi = GF256elm(x[i]); //xj
            GF256elm xj = GF256elm(x[j]); //xj
            GF256elm ximxj = xi - xj;  //xi - xj
            GF256elm prod = nxj / ximxj; // (-xj)/(xi-xj)
            l *= prod;
        }
        GF256elm product = GF256elm(y[i]) * l;
        result += product;
    }
    return result.getVal();
}

Basically what I'm doing here is I'm calculating $\dfrac{-2}{1-2}$, then multiply it with $\dfrac{-3}{1-3}$, then multiplying everything by 17, (which is the y value from the first point $(1, 17)$). This is the first term in D's equation above. I then go on and calculate the other two terms.

Problem is, instead of 10, I get 14 as my answer.

My Questions

In finite field arithmetic, negating x ($-x$) is really $0 - x$, which is actually $0 \oplus x$ (XOR), and it ends up being $x$ itself, am I right?
Is there anything wrong with my approach to finding the Secret $D$?

Additional info:

My division and multiplication is implemented using table look up. This part of the code has been tested and its results are the same as other sources.

GF256elm& GF256elm::operator*=(const GF256elm& other) {
    int temp = (_logTable[val] + _logTable[other.val]) % 255;
    val = _expTable[temp];
    return *this;
}

GF256elm& GF256elm::operator/=(const GF256elm& other) {
    int t = _logTable[val] - _logTable[other.val];
    int temp =  ((t % 255) + 255) % 255;
    val = _expTable[temp];
    return *this;
}

I now see your problem; it's more fundamental than what my previous answer assumed.  You state:

Now the same method should work for finite field GF(2^8) as long as the arithmetic are replaced with finite field arithmetic. However this is not the case

where you interpret "should work" as "coming up with the exact same answer".
Actually, that's not the case.  Your original example appears to be designed in the infinite field $Q$ (or some superfield); you then use the exact same shares, reinterpret them as $GF(2^8)$ points (in some unspecified representation), and then are confused that answers you get aren't precisely the same.
$Q$ and $GF(2^8)$ are both fields, but they are about as unlike as fields can get.  For example:

$2+2=4$  (in the field $Q$)
$2+2=0$  (in the field $GF(2^8)$)
$3 \times 3 = 9$  (in the field $Q$)
$3 \times 3 = 5$  (in the field $GF(2^8)$, in the most common representation)

Your original shares $(1, 17)$, $(2, 34)$, $(3, 61)$ were computed in $Q$; if they were computed in $GF(2^8)$, they would have lhad different values.  Therefore, it is not suprising that if you reconstruct them in a field other than what they were computed in, you'll come up with a different answer.  I recomputed your shares using the original polynomial (assuming a polynomial representation of $GF(2^8)$), and came up with the values $(1, 13)$, $(2, 26)$, $(3, 29)$
To test your code, you'll need to come up with your own shares, computing in the field you're using to reconstruct.
(You'll also need to fix up your multiplication logic, in case one of the shares happen to be the value 0)


Where can I read about DER certificate structure - fields and its registered values? Where is an official documentation for ASN1 structure and values of x509 certs?
Using OpenSSL command like openssl asn1parse -in server.der -inform DER I can see how the cert is structured, but, for example, value OBJECT :sha256WithRSAEncryption is HEX 2A 86 48 86 F7 0D 01 01 0B, or countryName identifier is 55 04 06 - where are all this values documented?

ASN.1 is defined by the International Telecommunication Union (the ITU). ASN.1 stands for Abstract Syntax Notation One, and is a schema definition language. DER, as well as its base form BER, are serialization formats of the data defined by the ASN.1-specified schema.
ASN.1 and DER/CER/BER are specified in ITU-T-X series standards, available at the official ITU website. Information about OIDs are available at http://oid-info.com/


Difficulty deciphering the RSA algorithm $d = 27, e = 3, n = 40$

For encryption, I have the letter T converted to 084 by the ASCII table, which encrypts to $24$ by $84^3\bmod 40$, for example.

To decrypt, I believe it would be $24^{27}\bmod40$ however this gives me 4.4342649e+38 which clearly does not fit into my ASCII table.

How does one decrypt using the RSA algorithm in relation to ASCII?

Further question: Is ASCII converter the best way to convert plaintext to numerical value?

EDIT: this is purely for a high school maths project; thank you for all the answers

You have two problems. The first is that you tried encrypting a value which is too large. If you are doing all your math mod n you have no hope of ever getting a result larger than n.

The second is in tthe implementation. You seem to be working in an environment which treats large numbers as floating points (JavaScript? ) and are not using efficient modular exponentiation.
https://en.m.wikipedia.org/wiki/Modular_exponentiation

24^27 is a fairly large number. It doesn't fit in a normal int or long variable. So you need to either have a special big integer to handle such large numbers. Or Preferably avoid them in the first place by applying the moduls in intermediate steps while calculating the power operation, preventing the nunbers you are handling from getting out of hand.(In full size implementations you need both).


Why RSA must make sure that $\gcd(e,\varphi(n)) = 1$ instead of $\gcd(e,n) = 1$? By Euler's theorem, if $\gcd(e,n) = 1$, then $e^{\varphi(n)} \equiv 1 \pmod n$. But why does RSA need to make sure that $\gcd(e,\varphi(n)) = 1$?

You want to be able to encrypt a message and decrypt it, that is translated to:

$m^{ed} \equiv m^1 \equiv m \pmod n$

But why does this work? Since $ed \equiv 1 \pmod{\varphi(n)}$

If $\gcd(e,d) \neq 1$ then $e$ and $d$ are not coprime then $ed \not \equiv 1 \pmod{\varphi(n)}$. So $e$ must be coprime with $\varphi(n)$ to have a modular multiplicative inverse.

Also $\gcd(e,n)=1$, since the public key is presented as $(e,n)$. Then you trivially can compute a factor of $n$ if $e$ is not coprime.


AES: Is it safe to encrypt same cleartext with same key but with million diferent IV? The encryption mode that I am using is CBC. Algorithm is AES and the key size is 128bit.
I will be encrypting a 36 byte string over 1.3 million times with the same key but with a random IV.

My question, as the title states, is it possible to reverse engineer the key for 1.3 million cypher texts without knowing the key nor the IV but with the knowledge that all the clear texts are the same.

From experience I know, it would not be easily possible to decrypt the first block without the right IV but how would the security of the rest of the block be impacted ?

Edit:

Situation 2: will knowing some portion of the clear text make it easier to guess the key ? Suppose the data is padded using PKCS7 specifications effectively making, lets say, the last 12 bytes of the clear text to be "0c 0c 0c 0c 0c 0c 0c 0c 0c 0c 0c 0c" as the string is 36 byte long.

An easy solution would be to fill the last 12 bytes with pseudorandom data. However, I am interested in knowing the consequences of not following such an approach.

No, for the same reason that you can't crack 1.3 million ciphertexts knowing they use the same key but different plaintext.

As long as the CSPRNG you use to get your IVs is strong, you're safe.

You are correct in that decrypting the first block without the right IV is not possible. If it were, we wouldn't be using CBC. But yeah, if he could somehow guess the right IV and key for a certain block, he'd be able to decrypt all the following.

For situation 2 take a look at this question.


MDC-2 recommended IV values? I'm currently reading Menezes' "Handbook of Applied Cryptography", and in it, when describing the MDC-2 cryptographic hash function, has the following line:

  Choose the 64-bit non-secret constants $IV$, $\widehat{IV}$ (the same constants must be used for MDC verification) from a set of recommended prescribed values. A default set of prescribed values is (in hexadecimal): $IV = 0x5252525252525252, \widehat{IV} = 0x2525252525252525$.

My questions are firstly, is it OK to use these "default" values more than once (as implied by the word "default")? And secondly, is there a full list and reasoning for these prescribed values? I cannot find the MDC-2 specification and so was hoping someone here would know more about it.

You can use those values more than once and there isn't much of a reason to choose another pair – except longer values for a cipher with a larger block size.

The only real requirement for the values is that they differ. However, if someone found a fixed point or other cycle for MDC-2 with a given block cipher, they could choose that point as an IV and be able to generate collisions for any string. That's why using a pair of non-suspicious nothing-up-my-sleeve numbers is better.


Fairness in cryptography Two users A and B decided to share a file of same size and transfer data bit by bit. And at the end of exchange, A will have B's data and B will have A's data.

Assuming, A starts to transfer the first bit, is the protocol considered fair?
If both of them do not know in real world, should trust issue be put into consideration when we determine fairness in protocol?

Fairness is, loosely speaking, the property of secure protocols that guarantees that either all honest parties will receive their output or no party will receive output. We know that this property can not be achieved for all functionalities unless when a majority of parties are honest.*

As I recall your question is a classic example of fairness not being achievable in general for two-party protocols. If we assume B could be actively corrupt, the protocol does not have fairness.

To see this note that when B gets the final bit of his output he can just abort the protocol. I.e, stop all communication with A. In this way B receives his full output but A never gets her output.

*This does NOT mean that fairness can never be achieved when there is a dishonest majority. It just means we can not get fairness for ALL functionalities in this setting.