ECDSA over $\mathbb{F}_{p^n}$ for $n>1$. How to calculate $r$ and $s$ I'm having some trouble understanding how to calculate $r$ and $s$ as specified in the wikipedia page for ECDSA (https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm)

We can see on step 4 of the signature generation algorithm that they calculate the following:

$r = x_1 \text{mod}\ n$, where $n$ is the order of the group.

However, $x_1$ is an element of $F_{p^m}$, which for $m > 1$ it doesn't make sense to compute it's remainder over an integer.

Similarly on the next step they calculate $s = k^{-1} * (z + r d_A)\ \text{mod}\ n$. However, here I also do not understand what operation they are refering to when they write $z + r d_A$, since $z$ is a number and $rd_A$ is a curve point.

Surely I must be missing something very obvious but I cant figure out what. For $r$ it occurs to me that you could just take the modulus over the corresponding field element to $n$, since all the elements of $F_p$ are also in $F_{p^n}$.

For calculating $z + rd_A$ I'm at a loss though, how do you calculate the sum of an Integer and an element of $F_q$?

However, $x_1$ is an element of $\mathbb{F}_{p^m}$, which for $m>1$ it doesn't make sense to compute it's remainder over an integer.

True; when they defined ECDSA, they did not consider curves over extension fields.  This means that ECDSA just isn't defined in that case.

Now, it wouldn't be unreasonable to extend ECDSA to cover that case; the requirement for the $kG$ to $r$ mapping is that it $r$ be computationally uncorrelated to $k$; you might (once you've defined the field representation) treat $x_1$ as an $m$ digit number in the base $p$, and then take that value modulo $n$ (which might be what you suggested...).   Of course, any such extension would need to be analyzed before usage...

Also, as for your objection "$r d_A$ is a curve point", no, it is not.  $d_A$ is the private key, which is an integer between 0 and $n-1$


Creating a secure key Imagine that your lecturer and the undergraduate office have conducted a key exchange protocol after which both of them hold the string $X$. Yet, it is possible that a curious student sitting next to the lecturer in the bus may have gained some information $E$ about $X$. (Un)fortunately, the student eavesdropper Eve has gained only $1000$ bits of information $E$ about $X$ from the quick glance. If $X$ contains 1 million bits and was chosen randomly beforehand, describe how the lecturer and the undergraduate office can produce a fully secure key $K$ from $X$ to encrypt the final exam for electronic transmission, such that student eavesdropper Eve knows essentially nothing about the key $K$.

I think that it's more proper  for your title to be named "Why hashing the shared value to get session key?" Next I'll answer your question in my understanding.

The basic problem is to establish a shared key between Lecturer  and undergraduate office securely. In the original Diffie-Hellman key-exchange protocol, Alice and Bob use the $g^{ab}$ as their session key. This basic DH protocol is based on CDH assumption, but CDH assumption alone can not ensure that we can use all the bits of $g^{ab}$ securely, it can only make sure that we can obtain  a hard core bit which is unpredictable. So the straight idea is to run the protocol $k-times$ to get secure $k$ bits. But it's undesirable and inefficient. So, in order to make the weak bits of $g^{ab}$ as strong as others, usually we hash the shared value to get the final session key.

But another problem you need to consider is the key-exchange protocol's security, so  that you can establish a session key between  lecturer and undergraduate office. I think key-exchange protocol's security is more important. And it's vulnerable to kinds of attacks.As your question is not about it, so I just answer you question in my view.


Sensitivity on differential privacy I want to verify my knowledge of sensitivity. So in $\epsilon$-differential privacy, the noise is added with the Laplace mechanism depending on the sensitivity and the privacy loss parameter. Laplace takes into account the global sensitivity and the noise is scaled on the L1-norm, ιn $\epsilon-\delta$ differential privacy the noise is added with Gaussian mechanism which considers the local sensitivity and uses the L2-norm as a metric am I right or did I miss something? I think that maybe I have confused somehow the concepts.

The differential privacy book is the typical reference for the area, and it is quite useful here. Since this answer essentially amounts to quoting from that book, I'll walk through how to find the right things to quote.
Ctrl+F-ing "Laplace", we find Theorem 3.6, which states that the Laplace mechanism is $(\epsilon,0)$-differentially private.
This mechanism adds i.i.d. $\mathsf{Lap}(\Delta f/\epsilon)$ noise to the output, where (as you mention):
$$\Delta f = \max_{\substack{x, y\in\mathbb{N}^{|\mathcal{X}|}\\\lVert x - y\rVert_1 = 1}} \lVert f(x) - f(y)\rVert_1$$
So this is the $\ell_1$ version of sensitivity.
Ctrl+F-ing "Gaussian", we see that it works for sensitivity defined via:
$$\Delta_2 f = \max_{\substack{x, y\in\mathbb{N}^{|\mathcal{X}|}\\\lVert x - y\rVert_1 = 1}} \lVert f(x) - f(y)\rVert_2$$
This is an $\ell_2$ notion of sensitivity (although note that "neighboring datasets" $x, y$ are still within 1 of eachother in the $\ell_1$ norm, meaning they still differ in at most one row).
Theorem 3.22 then shows that to be $(\epsilon, \delta)$ differentially private, the Gaussian mechanism adds i.i.d. noise $\mathcal{N}(0, 2\ln(1.25/\delta) \Delta_2(f)^2/\epsilon^2)$ to the output of the function.


using a hashed IV for AES128-CBC I would like to minimize the encrypted packet size.
Is it possible to derive the IV from a non-repeatable counter?
For example, take a 32 bit counter, hash it with a key (different from the AES key), and then use the result as a 128 bit IV.
The counter will increment on each packet, and not recycle during the lifetime of the key.
Then I could send the 32 bit of the counter, instead of the whole 128 bit IV, and if the transmitter and receiver are in sync, then there is even no need to transmit the counter at all.

Is it a reasonable solution?

For CBC, the IV must be chosen uniformly at random¹. Furthermore the IV must be independent of the plaintext: if you start sending a message encrypted with CBC, and then an adversary can submit some plaintext that will go in a later part of the message, they may be able to decrypt the whole message.

The output of a cryptographic hash function isn't necessarily uniformly random, but it may be close enough. Your method is very close to encrypting a counter, which is considered safe. But you're still saddled with the downsides of CBC: you must not allow the adversary to inject message content after they've seen the IV, and you must be very careful with padding.

I recommend using CTR instead of CBC. CTR is a lot easier to use correctly. All you need is that the counter does not repeat ever. It doesn't need to be random or unpredictable. Just remember that the counter is incremented with each block, not with each message.

In addition, consider whether you need to authenticate the message. If you don't have a good reason why it isn't necessary, then you definitely need to authenticate the message. To encrypt and authenticate the message, use an authenticated encryption mode such as GCM or CCM. Most authenticated encryption modes use CTR for encryption, but they may have different constraints on the IV due to the way they use it (and the IV for the authenticated encryption mode is not always used directly as the initial counter value for CTR).

¹  Exception: if the key is only ever used once then the IV can be anything.


Computational Complexity - When is it really exponential time? I'm currently working on the discrete logarithm problem and the relevant attacks. I'm fine on the mathematical side of things, but when it comes to estimation of running times I run into problems. More specifically: if we take a generic square algorithm like Baby Step Giant Step for a cyclic group of size $n$, we usually arrive at $O(\sqrt{n})$ necessary operations to find a discrete logarithm. With the argument that the input of the algorithm is measured in bits, we arrive at a running time of $O(2^{b/2})$ where $b$ is the bitlength of $n$. So far so good.

But this argument does not work for say, matrix multiplication. Let's take $A,B \in Mat(n \times n, \mathbb{Z})$, so computing $A \cdot B$ obviously takes $n^2$ operations in $\mathbb{Z}$. This is, in contrast to the above, considered efficient. So why can't I argue as above and say that matrix multiplication takes exponential time as well?

On a more general level, I often encounter the argument that some algorithm requires $O(p(n)$ (p(n) being some polynomial) operations that themselves can be computed efficiently and thus the whole algorithm is considered efficient. This runs counter to my intuition I gained from looking at Pollard's Rho etc.

I know I'm probably making a stupid mistake somewhere, but I'm not seeing it at the moment.

Thanks for any help!

The names of complexities normally refer to $b$, not the bitlength $n$.

$\mathcal{O}(log\ n) = \mathcal{O}(b)$ is polynomial time, $\mathcal{O}(n) = \mathcal{O}(2^b)$ is exponential time.

Matrix multiplication of a matrix of length $n$ would involve more operations than multiplying all elements of your group with all others. It has complexity of $\mathcal{O}(n^3) = \mathcal{O}(2^{3b})$ which is exponential time - it is not considered effective.
In $\mathcal{O}(n^2)$, you could create the multiplication table of your group, which is basically a lookup table. If you have that, you're basically done with the DLP, so it should be obvious, that solving the DLP should be less complex than matrix multiplication.

Also, this does not seem to be consistent. In some cases (like crypto) it makes sense to say that $\mathcal{O}(n)$ is exponential time since the thing that grows is the bitsize, and thus $n$ grows by $2^b$. In other cases, when we're talking outside of crypto $\mathcal{O}(n)$ might be considered polynomial, since n is the thing that grows (like sorting algorithms).


Is it feasable to combine ECB and CTR block modes of operation? Both ECB and CTR block modes have advantages over other block modes. They both support parallel encryption and decryption and random reads/writes. Yet both have major disadvantages: (I'm assuming AES block sizes)

ECB produces repeating patterns for the same 16 bytes of cleartext
ECB can be shuffled in 16 byte blocks, which results in the cleartext to become shuffled the same way
CTR xors the clear text to an encrypted nonce+counter. If nonce and key are reused, you can create an XOR key for encrypting/decrypting any AES-CTR encrypted file/message which uses the same key and nonce (This is mainly useful when you can encrypt data, but not read the key/nonce back from the HW AES)

Combining ECB and CTR (By first encrypting the data with ECB,then the ciphertext with CTR) will still allow parallel encryption/decryption and random reads/writes. Yet if you shuffle the blocks, the blocks that changed locations are completely broken. Plus you can't just create an xor key using the same key/nonce, as the data is then still encrypted with a different key. This will also double the key size.

My question is: Does this block mode exist? What are the main problems with an block mode like this?

EDIT:
The keys for both encryptions are different, which makes it unlikely that both the ECB and the counter encryption produces the same ciphertext.

Yet if you shuffle the blocks, the blocks that changed locations are completely broken.

This may be true, but you'd have to define what you have achieved if you do. What you are trying to do here is to change the error propagation of the mode of encryption. ECB however has very limited error propagation; it only extends to one block. If you change one bit then the whole output changes. But if your input may have a high amount of possible values, then the change won't be detected. Now you could introduce a crib, a known plaintext, but you'd still have to create yet another pass of e.g. a cryptographically secure hash to protect all the blocks using only one crib.

Error propagation was once an important topic for block ciphers. Nowadays however we tend to rely on CRC's or schemes like PAR2 to avoid damaged (cipher)text. And we tend to rely on message authentication codes (MAC's) to create cryptographically secure authentication tags. Finally we have schemes such as OCB and GCM that provide 1 to 1.5 pass authenticated encryption, making your scheme rather inefficient.

  Plus you can't just create an xor key using the same key/nonce, as the data is then still encrypted with a different key. This will also double the key size.

Encrypting twice often does not double the key size due to meet in the middle attacks. You'd have to prove that this is the case.

But given the inefficiency and only partial error propagation and ineffective authentication, I don't think you'd have to delve into that topic.


What is wrong with simple concatenation in salted password hashes? I once heard that if implementing a password hashing scheme, simply concatenating the password and salt together before hashing could lead to some subtle vulnerabilities, and I'm trying to figure out if this is actually the case.

According to this anecdote, the following should not be used:

hash(salt + password)
hash(password + salt)

And instead, something similar to an HMAC, like the following, should be used:

hash(hash(password) + salt)

Even though simple concatenation is vulnerable to length extension, I can't think of a way that could ever be useful to an attacker.

Is there any merit to this anecdote?

One difference is that with simple concatenation two different salt-password pairs could lead to the same hash input. For example: H('abcd'||'example@example.com') = H('abcde'||xample@example.com). This cannot happen between your password hashes if you use a constant width salt, but could still happen between your password hashes and those of some other service using the same hash.

With HMAC or another construction that handles the password and salt differently you avoid such collisions. Collisions still exist, of course, if the number of possible passwords and salts is long enough, but they never happen in practice.

If you generate a long enough random salt you avoid the issue even with simple concatenation, and that is usually a good idea in any case, so the practical effect may not be significant in many applications.

In practice the issue should not crop up other than in algorithm design. The best practice is always to use a real password-hashing function, such as bcrypt, scrypt or argon2, and those expose an iterface where you input the salt and password separately.


Difference between HMAC-SHA1(key, msg) vs SHA1(key + msg) Is there any practical difference from using HMAC-SHA1(key, msg) vs SHA1(key + msg) as a way to verify the authenticity/integrity of a certain message? Note that the plus sign means string concatenation in this context

Am I losing out on some esoteric detail that the HMAC-SHA1 offers in terms of mathematical immunity to cryptanalysis? Or do both approaches basically do the same thing?

Ive looked through the basic descriptions of both algorithms. And although HMAC-SHA1 seems to do some fancy things with padding and other stuff, I fail to understand any importance. To me both HMAC-SHA1(key, msg) & SHA1(key + msg) carry essentially the same strength/resistance against attacks aside from superficial details

How am I wrong, What am I missing?

Right off the bat, SHA1(key + msg) is vulnerable to length extension attacks. That is, if I know SHA1(key + msg) I can use that to compute SHA1(key + msg + anything I'd like to add here) without having to know the key.


Where and how to store private keys in web applications for private messaging with web browsers I am working on a web application enabling users to communicate over private messages which is just one part of the whole system. The main focus during my development process is to protect the privacy of my users, I think this should be one of the main responsibilities for every software developer. Especially when you think about the harmful data leaks over the last years.

I've read a lot of articles about end-to-end encryption and that famous messaging apps like Whatsapp use end-to-end encryption to protect their users privacy. I want to achieve that my server and my application have zero knowledge about the contents of messages being transmitted.

When you have applications which are installed on the users device I know theoretically how to store and protect the private keys on the users device. But in my special case, there is going to be no executable installed on the users device. They are accessing the web application over their browsers and a secured https connection. This fact causes me quite a headache. I can't even imagine how to store the private key permanent and secure in this client side environment. So I thought about storing the keys in a secure way on the server, but this is a contradiction to my mind, when thinking about that I have to assume that a potential adversary takes over the control of my server, database, ... the whole machine while everything is running and the "key vault unsealed".

I opened a question on StackOverflow a couple of days before if you want to read more about my way to desperation. Protecting application secrets like encryption keys and other sensitive data. After a long discussion I was referred to this Cryptography Forum of StackExchange.

So I want to ask you without focusing on any special programming language: "Where and how to store private keys in web applications for private messaging with web browsers?". Thanks in advance!

You may want to consider using the Web Cryptography API for client-side cryptography in the web browser.  Then, you can create a keypair using the webcrypto api, and store the CryptoKey object, containing the user's private key, with the .extractable property set to false, using Indexed DB storage.  This way the private key can only be used for decrypting and/or signing messages within the browser - but can not be read (even by client-side scripting in the browser).

For more info, see:

https://pomcor.com/2017/06/02/keys-in-browser/
https://www.w3.org/TR/WebCryptoAPI/
https://developer.mozilla.org/en-US/docs/Web/API/Web_Crypto_API
https://www.w3.org/TR/IndexedDB/
https://www.boxcryptor.com/en/blog/post/building-an-app-with-webcrypto-in-2016/
https://gist.github.com/saulshanabrook/b74984677bccd08b028b30d9968623f5
https://blog.engelke.com/2014/09/19/saving-cryptographic-keys-in-the-browser/


Enforcing Randomness in Malicious Setting I was going through some lecture notes where it said that if we have a 2-party protocol that requires both the parties to generate random integers during the course of protocol, then if we migrate the protocol and tweak it to make it work in Malicious setting, then we need to ensure that both parties instantiate random numbers which are indeed random.

It said that this can be achieved by using the following protocol:

$P_1$______________________________________________________$P_2$
commitment($s_1$) -------------------------------------------------->>
<<------------------------------------------------------commitment($s_2$)
$s_2'$----------------------------------------------------------------------->>
<<---------------------------------------------------------------------------$s_1'$

Now, both parties can find their random number $r_i$, $i\in \{1,2\}$ as
$r_i = s_i \oplus s_i'$.
I had a doubt that how does a party ensure that the other party will find $r_i$ as $s_i \oplus s_i'$ and not as just $r_i = s_i$?
How is this ensured that both parties will find their $r_i$s in the exact same way as the protocol says?

The way that this is used is that each party proves in zero-knowledge during the protocol that it sent the correct message based on its committed input, the randomness defined by the committed $s_i$ value and the clear $s'_i$ value, and the series of incoming messages. This proof forces the party to not use any other randomness.

However, in order for this to work formally, you can't use plain commitments. Rather, the commitment must be something that we call ``extractable'' by a simulator.

In any case, you should read more about this as the GMW compiler. You can read about it in the 2nd volume of Goldreich's textbook.


Deterministic ECDSA signatures? ECDSA signatures depend on parameter k that is chosen by the signer. As a result, there are many signatures for the same private key d and message m.

What I want to achieve is a deterministic signature. That is, given private key d and message m, there should be only one valid signature. I could go with RSA (with deterministic PKCS#1 v1.5 padding) but would prefer ECDSA if possible as it is almost as widely deployed and has smaller key and signature sizes.

RFC 6979 describes how k can be generated deterministically but it doesn't solve my problem because those who verify the signature can't verify that the signer did actually follow RFC 6979 (I'm not aware of any such method).

I'm thinking about imposing some additional requirements on signers that others can easily verify.

For example, what if I require that all signers derive k using a formula like this:

k = H(m) * d

where d is private key, and H is hash function. Then in signature (r, s), r is x-coordinate of

k x G = H(m) * d x G = H(m) * Q

where G is generator, Q = d x G is public key, and x denotes EC multiplication.

Unless I'm getting EC math wrong, this choice of k derivation function has the  advantage that it can be easily verified by multiplying public key point by H(m) and comparing the x-coordinate of this point with r from the signature. At the same time, it seems, all the security requirements for k are still satisfied: it is private since it is derived from private key and it is different for each message as it depends on message hash.

Will it work? Any other ways to create deterministic signatures?

DSA relies on $k$ being independent from $d$. You define $k$ as:

$k=z^\prime d\mod n$

Substituting $k$ in the signing equation you get:

$s = k^{-1} (z+rd) \mod n$

$s z^\prime d = z + rd \mod n$

$d=z (sz^\prime -r)^{-1}  \mod n$

The attacker knows everything on the right side and can recover the private key.


How to prove if a Hash Function is collision resistant Say we have the following Hash Function, H(x) = 4x mod N where N is a number generated by multiplying two prime numbers and x={0,1,2,3,...,N-1}. So lets assume that N=15 where 15 is made from 3 and 5

How would we prove whether it is collision resistant or not? I tried manually doing it like below:

x=0; 4(0) mod 15 = 0
x=1; 4(1) mod 15 = 4
x=2; 4(2) mod 15 = 8
x=3; 4(3) mod 15 = 12
x=4; 4(4) mod 15 = 1
x=5; 4(5) mod 15 = 5
x=6; 4(6) mod 15 = 9
x=7; 4(7) mod 15 = 13
x=8; 4(8) mod 15 = 2
x=9; 4(9) mod 15 = 6
x=10; 4(10) mod 15 = 10
x=11; 4(11) mod 15 = 14
x=12; 4(12) mod 15 = 3
x=13; 4(13) mod 15 = 7
x=14; 4(14) mod 15 = 11

As you can see in the example, there are no collisions but how do you prove it Mathematically without providing numbers?

For the function $F(x) = ax \bmod n$, where the inputs are limited to the range $[0, n)$, this function will be a bijection (that is, no collisions) if and only if $a$ and $n$ are relatively prime.

Here is a proof in the direction you're asking about:

Suppose there exists a collision, that is, we have a pair $x, y$ with $0 \le x < y < n$ where $F(x) = F(y)$.  This implies that $a(x-y) \equiv 0 \pmod n$, that is, there exists an integer $k$ with $a(x-y) = kn$.  $x-y$ is not a multiple of $n$ (it is not zero, as $x < y$, and we know that $|x - y| < n$, hence it is not a larger multiple of $n$), hence there exists a prime power $p^k$ where $n$ is a multiple of $p^k$, but $x-y$ is not.

We know that $a(x-y)$ must be a multiple of $p^k$, hence $a$ must be a multiple of $p$, and hence $a$ and $n$ are not relatively prime.

The other direction is easier; suppose $a$ and $n$ are not relatively prime, that is, there exists a prime $p$ for which both $a$ and $n$ are a multiple.  Then, we have $F(0) = F(n/p)$, hence there exists a collision.


Is there an encryption algorithm, which is a magnitude faster than AES (with weaker guarantees)? There are current state-of-the-art encryption algorithms, which considered absolutely safe currently, like AES. Their speed is around the 100MB/sec ballpark on current PCs (note: this is the speed when AES instruction set is not used - I'm interested in the general case, not when HW acceleration is available).

And there are fast, non-safe, obfuscation-only algorithms, like for example, xoring with some fast general-purpose, non-cryptographic random. Their speed can be very-very fast, possibly in the 10GB/sec range. But they can be broken easily (if a little part of the clear-text is known, they can be broken immediately).

Are there any algorithms, which are between these? Like, it has speed of ~1GB/sec, and it can be broken, with some computational effort (like the key can be found in a week/month/year of bruteforce searching on a current PC)?

It can be used in a scenario, when speed matters, but the data is not that sensitive, so it would not worth to break the encryption.

A classical table-based AES implementation would achieve about 160 MB/s on my current computer (a fairly recent MacBook Pro). However, one can do better; of course there are the AES-NI instructions, that easily bump up speed on that machine to the 5 GB/s mark (with a parallel mode such as AES-CTR; AES-CBC encryption is much slower). But even without these instructions, the Käsper-Schwabe implementation of AES-CTR would offer more than 400 MB/s, a substantial improvement.

Looking outside of AES, there is ChaCha20, as specified in RFC 7539. Using my own implementations, the purely generic, 32-bit plain C code (chacha20_ct) encrypts or decrypts data at 385 MB/s on my laptop; the SSE2-enhanced implementation (chacha20_sse2) offers a 584 MB/s.

Generally speaking, block ciphers like AES are versatile primitives, and it can be argued that, by forfeiting versatility and concentrating on the encryption/decryption role, better performance may be achieved. This is what stream ciphers like ChaCha20 are about.

About ten years ago, there was the eSTREAM project which resulted in a portfolio of stream ciphers. On my laptop, SOSEMANUK achieves about 1.64 GB/s, which is not bad for a design from ten years ago. Notably, it is 10 times faster than the table-based AES. (I wrote part of the code; I don't know who packaged it as a Zip archive with modified file names that break compilation.)

Among more modern designs, one may cite NORX. I encountered an implementation on small ARM systems that was consistently trouncing ChaCha20. I suppose it would also clear the 1 GB/s mark on a modern PC.

Summary: 1 GB/s is actually highly feasible with existing algorithms, on standard hardware, without using the AES instructions, and without sacrificing security: all of the above are currently unbroken, despite extensive exposure to vindictive cryptographers.

Of course, excluding the AES-NI instructions is rather artificial: it makes relatively little sense to make benchmarks on a modern CPU without using the features of that CPU. Performance on smaller, embedded systems without an hardware AES implementation may be more relevant.


Is this MAC correct and secure? Let $m \in \{0, 1\}^{2n} = m_1 || m_2$. Let's also assume that $F_k$ is a PRF and $G$ is a PRG defined as $G: \{0, 1\}^n \rightarrow \{0, 1\}^n$. Now, Let's define the $MAC$ scheme as follows:

$$MAC(m) = F_{m_1}(k \oplus G(k\oplus m_2))$$

Where $k \in \{0, 1\}^n$. I think it's correct, but I have not seen much examples of using the message itself as PRF's key. That is why I am getting confused. Is it correct and/or secure?

No. The construction is not secure!

The security property of MAC says that, every poly-time adversary who has access to a MAC oracle (the oracle outputs MAC on input message) cannot come up with a MAC on a message of his choice (without querying the oracle) with non-negligible probability. In your construction, suppose you know that $G(x) = G(x')$ for some known values $x, x'$. Then an adversary can query for MAC on $m_1 || x$ (for any message $m_1$) and then obtain MAC for $m_1 || x'$.

Note: It's easy to construct a PRG $G$ such that $G(x) = G(x')$. Take any PRG $G'$ and pick any two values $x,x'$. Construct $G$ as follows. $G(y) = G'(y)$ if $y \neq x$. $G(y) = G'(x')$ if $y = x$. Note that $G$ is a PRG if $G'$ is a PRG.


Special-purpose witness encryption without multilinear maps In Witness Encryption and its Applications Garg et al describe "witness encryption" which allows one to encrypt some specified data to a NP problem, such that another party can decrypt iff they present some witness to the NP problem.

They give general construction using multilinear maps based on a reduction of NP from CNF predicates to subset-sum problems.

Are there any examples of witness encryption on a smaller class of problems (say, inner products, or preimages of point functions, or discrete logarithms) that are provably secure without multilinear maps?

One obvious example would be the factorization problem, with the Rabin encryption system.

One way of stating the factorization decision problem is: given $x, M$, does there exist integers $y, z$ such that $1 < y < x$ and $yz = M$?  The witness would be the values $y, z$.

If we constrain the values of $M$ to be Rabin modulii (product of two prime factors, with both factors $3 \bmod 4$), then Rabin is provably equivalent to the factorization problem.  Hence, if you can decrypt, then you can produce a witness (as you can factor), and if you can produce a witness, then you can decrypt (as you can factor).


Which sub operation is more expensive in the AES encryption process? In the AES encryption process, there are various sub-operations, like SubByte, MixColumns, ARK etc. My question is which of these operations is more expensive?  In a video lecture by Dan Boneh, it is mentioned that the lookup table implementation of AES is faster than the implementation where the MixColumns function is performed using finite field multiplication.
I do not find any information on how much faster it is? Also, is there any relation between the individual sub-operations in terms of individual CPU time?

The table lookup implementations usually combine the SubBytes and ShiftRows steps with the MixColumns step.
Different implementations/hardware/etc make general statements impossible, but this paper gives some  benchmarks and information on a table-lookup implementation.
It won't necessarily be quicker across all systems.  As per this paper:

It must be noted, anyway, that using a large amount
of memory for the look-up tables is too expensive for small systems, like for
instance smart cards, and is considered unsafe, as monitoring the accesses to the
look-up tables may in some cases allow to infer the key.

As an aside, another (better) way to speed up AES is to have the instructions built into the hardware


Proving the security of a one-way function with partially known input Let's say we have a construction like in this question: We have a OWF $h(.)$, a secret salt TXT, and a counter starting at 1, and we compute

H1 = h(TXT || 1)
H2 = h(TXT || 2)
...
Hn = h(TXT || n)

According to the linked question, this scheme is secure. However, I was wondering how to formally proove this.

My first attempt was to try to formalize the scheme a little: Given the OWF $h(x)$, we construct $h'(x) = h(TXT\ ||\ x)$. Now, we can do the usual dance of "Assuming $h'(x)$ is no OWF, a PPT algorithm A exists that inverts it with non-negligible probability." We now have to use $A$ to construct a PPT attacker $B$ that inverts $h(.)$.

However, $h'(x)$ clearly does not even properly represent what the scheme above is doing (we know that TXT is fixed, but have no guarantee that $x$ is increasing monotonically). Since the function does not match the problem, it's not interesting if it is an OWF.

In fact, since the scheme does not even have any parameters, any attempt to put it into the form of an OWF is doomed. It's more of a PRNG, with TXT being the seed. So, one way to phrase the security requirement of this scheme would be "no algorithm $A$ exists that can determine TXT in PPT with a non-negligible probability, given any number of consecutive outputs of the PRNG".

This is where my ideas end. I am not sure how one would go about prooving this, or if there is a more elegant way to perform this proof. I'd be interested in how you would solve this problem (and if it is even possible).

(Note that this is no homework assignment, just me being curious about how one would proove this. It's also related to another question of mine, where the security of the scheme could be prooven in the same way)

You are right, it does not seem as if a reduction from OWF works here. Indeed it rather seems like a separation is possible. This is what @RickyDemer describes in his comment, i.e. showing that there exists at least one OWF $h$ for which the above use case is insecure. This would show that a reduction from OWF is impossible.

You definitely can get a proof if you assume $h$ is a pseudorandom function family. In that case $TXT$ would have to be treated as key and the counter as message. Finding the (secret) key used for a PRF would allow to distinguish it from a truly random function with high probability and hence learning $TXT$ from the above inputs means breaking the PRF property of $h$... In practice you can for example use any HMAC as PRF.


Zero knowledge proof of equality of discrete log and hash preimage So my question is as follows: We know that we can prove in zero-knowledge equality of discrete logs, for example to prove equality of committed values we can prove in ZK for $g^xh^y$ and $g^{x'}h^{y'}$ that $x = x'$ using a Sigma protocol.

Is there a way to prove equality when one committed value is the output of a hash function? This means prove in ZK for $g^xh^y$ and $H(x')$ that $x = x'$. (the tricky part here is that the Hash function doesn't necessarily have homomorphic properties as the commitment does)

This paper (here also in case of a academic barrier) solves exactly the problem you have; just instantiate the garbling scheme with the hash function.

To prove the relation of the hash, they use a garbling scheme with the garbler being the verifier and the evaluator being the prover. Since the garbler has no inputs to provide into the garbled circuit, the verifier can 'open' the complete circuit to the prover after the prover has commited to the output key, which makes the performance comparable to garbing schemes secure against semi-honest adversaries (which is a lot faster than security against malicious adversaries) This paper (here also in case of a academic barrier) describes that in detail. The paper cited above now only combines that idea with 'common' commitment schemes.


Master keys for decrypting? I'm not a Cryptography expert, but i've seen this topic sometimes on the Web: Master decrypt keys.

Most of the people said that "Master decrypt key" does not exist.

This makes sense if you developed your own Cryptography software.

But if a company releases a cryptography software, where the user must enter the content (string or file), and a password, and then he gets the output, wouldnt the company be able to include the user password in another string encrypted with the company's password in somepart of the file? so no matter the user has encrypted the file with 30 keys, the company could decrypt it's part of the file and get the user key to decrypt the entire file

does it make any sense? I was wondering this for security reasons

In theory, someone could do this, but in practice nobody really uses random, sketchy third party cryptography software. Most, if not all, of the commonly used cryptography functions are well understood and tested. Most of them also openly reveal precisely how they work so anyone can implement them. This means lots of people can analyse the algorithms for built in weaknesses like the one you described.

The case you described is a good reason to stay away from unknown and untrusted third party cryptography software.


Different tools return different ciphertext value for equal input I have a Luna G5 Safenet HSM and I want to encrypt a text file containing testtest with 3DES-ECB algorithm. So in the first step I generate a 3DES key on the HSM:

A view of the key generator tool:

Select type of key to generate
[ 1] DES     [ 2] DES2   [ 3] DES3             [ 5]  CAST3
[ 6] Generic [ 7] RSA    [ 8] DSA   [ 9] DH    [10]  CAST5
[11] RC2     [12] RC4    [13] RC5   [14] SSL3  [15]  ECDSA
[16] AES     [17] SEED   [18] KCDSA-1024   [19] KCDSA-2048
[20] DSA Domain Param    [21] KCDSA Domain Param
[22] RSA X9.31                                 [24] ARIA
[25] DH PKCS Domain Param [26] RSA 186-3 Aux Primes
[27] RSA 186-3 Primes
> 3

Enter Is Token Attribute [0-1]: 1
Enter Is Sensitive Attribute [0-1]: 1
Enter Is Private Attribute [0-1]: 1
Enter Encrypt Attribute [0-1]: 1
Enter Decrypt Attribute [0-1]: 1
Enter Sign Attribute [0-1]: 1
Enter Verify Attribute [0-1]: 1
Enter Wrap Attribute [0-1]: 1
Enter Unwrap Attribute [0-1]: 1
Enter Derive Attribute [0-1]: 1
Enter Extractable Attribute [0-1]: 1

Generated DES3 Key handler: 14

After that I checked its attributes:

G:\LunaG5> Cmu.exe getattribute -password 1234567

Select object to query

Handler Label
14      Generated DES3 Key

Enter handler (or 0 for exit) : 14
class=secretKey
token=true
private=true
label=Generated DES3 Key
value=86016e6572617465642044455333204b6579000000000000
keytype=3DES
id=
sensitive=true
encrypt=true
decrypt=true
wrap=true
unwrap=true
sign=true
verify=true
derive=true
startdate=
enddate=
extractable=true
local=true
neverextractable=false
alwayssensitive=true
modifiable=true

As you see above, the value of my generated 3DES key is:

86016e6572617465642044455333204b6579000000000000

Well, in the next step, I encrypt my text file using 1-my HSM, 2-OpenSSL, 3-this online tool. The weird thing is that the output of all are different with each other!

1-My HSM:

Enter your choice : 40
[ 1] DES-CBC       [ 2] DES3-CBC      [ 3] DES3-CTR      [ 4] CAST3-CBC
[ 5] DES-ECB       [ 6] DES3-ECB      [ 7] AES-CTR       [ 8] CAST3-ECB
[ 9] RC2-ECB       [10] RC2-CBC       [11] CAST5-ECB     [12] CAST5-CBC
[13] RC4           [14] RC5-ECB       [15] RC5-CBC       [16] RAW-RSA
[17] DES-CBC-PAD   [18] DES3-CBC-PAD  [19] DES3-CBC-PAD-IPSEC
[20] RC2-CBC-PAD   [21] RC5-CBC-PAD   [22] CAST3-CBC-PAD [23] CAST5-CBC-PAD
[24] SEED-ECB      [25] SEED-CBC      [26] SEED-CBC-PAD
[27] AES-ECB       [28] AES-CBC       [29] AES-CBC-PAD   [30] AES-CBC-PAD-IPSEC
[31] ARIA-ECB      [32] ARIA-CBC      [33] ARIA-CBC-PAD
[34] RSA-PKCS      [35] DES3-CFB8     [36] DES3-CFB64    [37] DES3-OFB
[38] AES-CFB8      [39] AES-CFB128    [40] AES-OFB       [41] ARIA-CFB8
[42] ARIA-CFB128   [43] ARIA-OFB      [44] AES-GCM       [45] XOR-BASE-DATA-KDF
[50] RSA-OAEP      [51] ECIES         [52] ARIA-CTR      [53] SEED-CTR
Select mechanism for encryption: 6
Enter name of file to encrypt: plain.txt

Enter key to use (-1 to list available objects) : -1

Handle 14 -- label: Generated DES3 Key

Enter key to use (-1 to list available objects) : 14

Encrypted data stored in file ENCRYPT.BIN
Status: Doing great, no errors (CKR_OK)

HSM output file content:

2-OpenSSL:

D:\GnuWin32\bin>openssl.exe enc -des-ede3 -e -in in.txt -out out.bin -K 86016e6572617465642044455333204b6579000000000000 -iv 0

OpenSSL output file content:

3-Online tool&Output:

Why I have different outputs?

Let me try to provide an answer for your question (despite the answers in the comment section). Some research showed that a recently discovered vulnerability allowed to extract the keys from SafeNet HSM (which the Luna G5 is). Therefore it should under normal circumstances NOT be possible to extract any private keys from the HSM.

To your question in the comments:

  I checked getattribute command for RSA Keypairs on the the HSM. It
  seems that the device show the Modulus and public Exponent. Is it
  unusual and strange too?

Compared to 3DES, RSA is an asymmetric encryption scheme, meaning that you have a public and a private key. While data is ENcrypted with your private key, it can be DEcrypted with your public key. The modulus and public exponent are the public key of the private key which is stored in your HSM.

To sum it up: The purpose of a HSM is that no one should be able to extract any keys from it. In this case you may have to trust the implementation of the vendor.


Authentication without decrypting the password? To my knowledge it works like this:

The server receives the username-password values over a secure & encrypted channel.
The username-password values are decrypted in the server and are present as plaintext.
With the username the according salt gets retrieved for the user.
The salt is appended to the plaintext-password and is finally hashed.
The hash is compared to the stored hash and depending if the hashes match or not the user gets logged in or receives some sort of a message that says that the username / password is wrong.

Hypothetical problem: If for example we have a vicious programmer "Mallory" that works as a programmer for the company he could write a piece of code inside the authentication process to receive the plaintext password:

private bool Authentication(string username, string password)
{
    // Some code ...

    log($"{username}, {password}"); // Logs the plaintext username & password for Mallory

    // Some more code ...
}

For this example we assume that the company fully trusts Mallory and that nobody else ever checks the source code.

My questions are:

Is it possible to change this authentication mechanism in a way so that the password is never present as plaintext?
Is it possible to prevent this without changing the effort for a user, like introducing two-factor-authentication or something similar?

This can be done with a cryptographic protocol called Password-Authenticated Key Exchange (PAKE). It comes in a few flavors:

Plain PAKE is a good fit for peer-to-peer connections. Both participants know the password in the clear, and use it as input to the PAKE protocol. If they both agree on the password, then they establish a shared secret key, safe from eavesdroppers. If the passwords disagree, they fail to establish a key.
Asymmetric PAKE (aPAKE) is a good fit for client-server connections. The client knows the password in the clear and the server holds only a "hash" of the password. (In practice, it's not exactly a hash but something more involved. The point is that the server doesn't know the password in the clear.) The two participants will establish a shared secret key only if the connecting client uses the correct password.

A good, accessible introduction to the state of the art can be found in this talk by Hugo Krawczyk earlier this month at the Real World Crypto symposium. Among other things that you can do with PAKE, he explicitly talks about aPAKE as a replacement for password-over-TLS (the typical approach for authentication that you described).


The magic box puzzle: How to implement a verifiable self-contained secret system? Imagine we have a magic box that will open only if we pronounce the secret words. Everybody at the beginning of the game have some verifiable proof of the correct secret words.
During the first phase all contestants will say their guesses for the secret words.
On a second phase the magic box will open if any of the contestants said the secret words. And using the proof provided and the beginning of the game you will be able to verify the secret words are the same, and the box is not trying to trick you. If none of the contestants guessed the secret words the box will tell the secret words and the game will start again resetting the secret words and offering a new proof.

My own guess
Based on my limited cryptography knowledge my implementation will be as follows: The proof provided at the beginning of the game would be a hash of the encrypted secret. When the secret is revealed on the second phase, a key and method to encrypt the secret is also provided, so contestants will be able to encrypt themselves the secret and compared the hash to the proof provided at the beginning. I would use a simple symmetric encryption method and a md5 hash for the proof.

Please let me know of your thoughts and if you get a better approach of the problem.

HMAC is what you need:

The HMAC of the secret is provided at the start of the round
The box gives out the HMAC key at the end of the round
If someone guessed the word correctly in the round, then the box gives the HMAC key out to all the contestants, so everyone can verify that the box is telling the truth that a contestant was correct
If no-one gets the answer by the end of the round, then the box can share the key, and the contestants can then verify that the secret is in fact what the box claimed it to be, and that the box isn't lying.

HMAC is hash based, and relies on a symmetric key, which satisfies your requirements


Cryptographic data structure: sparse array without membership test I would like a data structure supporting two operations: $\mathsf{set}(k,v)$ and $\mathsf{get}(k)$, with the following properties:

$k$ can be any number between $0$ and something impressively large, like $2^{256}-1$.
If there is some $v$ such that $\mathsf{set}(k,v)$ has been called then $\mathsf{get}(k)$ returns the most recent such $v$.
There is no way to learn anything about which $k$ and $v$ are such that $\mathsf{set}(k,v)$ has been called (but it might be possible to determine information that does not have to do with specific $k$ and $v$, e.g., it might be possible to learn how many times set has been called or on how many different $k$ it has been called).
Space and time complexity are bounded by reasonable functions of the total number of calls to set and get (or better yet by a reasonable function of the number of keys set has been called on).

An attacker would learn everything I know, so the solution cannot be based on me retaining any secrets.  But an attacker would not see the sequence of $\mathsf{set}$ and $\mathsf{get}$ operations since that would allow knowing what $\mathsf{set}$ has been called on.  An example of a data structure that would meet all my demands except for the computational complexity ones is to create at time zero an array of size $2^{256}$ populated by random data and then update and query it as a normal array.

I assume a fixed field length for $v$ and also that the data being stored in $v$ is effectively random.  The meaning of the last statement is a bit subtle.  If $v$ is a 256-bit field then storing all zeros in a place in the array will effectively give away that it has been set.  If $v$ is a 1-bit field then storing any particular value in any particular place will not give anything away, but other patterns, like storing more zeros than ones might.  Imagine that the attacker has a correct guess about what the set of set keys is.  Depending on how the array was used, he might be able to become more certain of his guess by querying the array.  I simply want a data structure that doesn't give up any more information than strictly necessary beyond the infeasible full array of length $2^{256}$ initially stocked with random data.

Obviously it will have to give up a little more information because it will get bigger depending on how much data it has in it (compare black holes), but ideally the approximate number of keys set is all the information it will leak.  Actually, it will not have to progressively give up more information if the maximum amount of data the structure can contain is fixed at creation time.  And the partial solutions to the problem that are given below by otus and myself require the size to be fixed in this way anyway.

Is there such a data structure?  Also, what is a good reference for this kind of question?

The attacker only gets to see the final data structure. The concept of history-independent data structures looks really interesting, but I am skeptical that literature will help with my problem. Among other things, the couple of papers I looked at seemed to use a threat model where the attacker has infinite computational resources, but it is impossible to solve the problem under that threat model.

This answer builds on the answer supplied by @otus.  There is also an important worry about whether the main solution works at all as advertised.  I am posting it now to make clearer to @otus a question I asked in a comment.  I will eventually either delete it or substantially revise it.

First off, let me emphasize that if the table is going to be used to store arbitrary data, then an attacker who suspects k is a key may be able to test the suspicion by checking whether get(k) is data-like.  So the natural guarantee in this case is just that an attacker cannot recover any information from the table without possessing the key to that data.  If this guarantee is all we require, the problem can be completely solved using the @otus's idea of hashing the keys and using the hash as a symmetric encryption key.  Let me explain this solution as a preliminary.

Assume, as @otus does, that an initial hash has been performed.  (Questions: do standard cryptographic hash functions actually come with a guarantee that the hashes are indistinguishable from draws from the uniform distribution?  Also, if we are willing to hash to a larger space than the domain, can we be guaranteed that the hash function is injective?)

A simple version of the data structure is as follows.  We maintain a list of data items.  Each item in the list is of the form $E_k(k,v)$ for a $k$ that is unique in the list.  To retrieve the value associated with $k$, we decrypt the list members using $k$ and check for one that returns to $(k,v)$.  To store $(k,v)$, we first check if $k$ already has a value associated with it and, if so, remove the corresponding data item from the list.  Then we add $E_k(k,v)$ to the list.

The simple version has linear time overhead, but it is straightforward to eliminate that inefficiency by using hash tables with collision resolution.

Now back to the full version of the problem, which is mainly interesting in the case where the stored data will be indistinguishable from random bit strings.

@otus gives a solution to this problem, but it has three drawbacks: it is probabilistic, it requires super-quadratic space to have low error probability, and it the eventual size of the data structure must be known in advance.  The first and third drawbacks seem to me inescapable, though I have no proof of this conjecture.  I have an idea about how to eliminate the second drawback, but it depends on the existence of a certain kind of error-correcting code.

The data structure is an array of $N$ bits initialized to random values.  To store $(k,v)$, we use $k$ to seed a pseudo-random number generator to generate a sequence of indices into the table.  We blow up $E_k(v)$ to double its original size using an error-correcting code, and we store the successive bits of this blown up version of $E_k(V)$ at the successive pseudo-random indices into the table.  This code can correct errors in up to half bits, so as long as the probability of a collision at any bit is significantly less than a half, we can be virtually certain of recovering the data.  If the table is four times size of the data stored in it then the expected number of bits stored at each index will be 1/2.  We can think of the number of collisions at a location as following a Poisson distribution with mean 1/2, so the probability of no collisions at a location will be about .61.  Assuming the data is long, there will be an overwhelmingly high probability that we can recover it from the code.  And the total space requirement is only four times the amount of space we need to hold the data.

The only problem is that with normal error-correcting codes, it is easy to tell whether an bit string is a code or not, and it is probably also easy to tell if a bit string is close to being a code in the Hamming metric.  So an attacker in possession of $k$ would be able to confirm that $k$ was likely a key, precisely what we don't want.  I am not sure if this problem dooms the whole approach I am contemplating here or whether there are special codes that do not have this problem.  Now with any code there will be some bit strings that it is easy to see are not code words because they have short Hamming distance to bit strings that decode to something different.  But maybe such bit strings could be rare, or even impossible to find, and bit strings that do not have that property would be indistinguishable from codes.


Is it possible to combine digital signature to provide message addition? Let's assume we are using the textbook RSA where $Sig(x)=x^d$. Alice has public key $(e,N)$, and private key $(d,p,q)$.

Now, if Alice sends $Sig(5)$ and $Sig(10)$ to Bob, where $5$ and $10$ is just numbers, is there a way to combine them on Bob's side to get $Sig(15)$?

If this is not possible in RSA, is it possible in other schemes like, for example, ElGamal) ?

Please note that I'm looking for a solution to handle this via "addition", not "multiplication".

No, in textbook RSA signature with $\operatorname{Sig}(x)=x^d\bmod N$, there is no method to deduce $\operatorname{Sig}(15)$ from $\operatorname{Sig}(5)$ and $\operatorname{Sig}(10)$.

It is possible to deduce $\operatorname{Sig}(50)$, by using the general fact that in textbook RSA signature, if $x$ and $y$ are positive integers (with $xy$ below the limit for messages that can be signed, if any), then $\operatorname{Sig}(xy)\;=\;\operatorname{Sig}(x)\operatorname{Sig}(y)\bmod N$. But notice that being able to obtain an admissible signature for a message from the signature of other messages is considered a break of a signature scheme. That's why textbook RSA signature with $\operatorname{Sig}(x)=x^d\bmod N$ is not a secure signature scheme (rather, it is a building block towards one).

Further, if we have a signature scheme such that $\operatorname{Sig}(x+y)$ can be deduced from $\operatorname{Sig}(x)$ and $\operatorname{Sig}(y)$, then the signature of any message $x>0$ can be deduced from $\operatorname{Sig}(1)$ with $O(\log(x))$ deductions. That's why the literature tends to consider such additively homomorphic signature schemes only to repel them.

If we really want an additively homomorphic signature scheme, we can define one related to RSA, as $\operatorname{Sig'}(x)=\operatorname{Sig}(g^x\bmod N)=(g^x\bmod N)^d\bmod N=(g^d\bmod N)^x\bmod N$ for some fixed public $g$ generator of the groups $\mathbb Z_p^*$ and $\mathbb Z_q^*$ (it is easier and best that $(p-1)/2$ and $(q-1)/2$ are primes). In order to verify the alleged signature $s$ of $x$ per this system, it is checked that $s$ is the textbook RSA signature for $g^x\bmod N$, that is $0\le s<N$ and $s^e\bmod N\,=\,g^x\bmod N$. For all non-zero $a$ and $b$ and messages $x$ and $y$ it holds that $\operatorname{Sig'}(ax+by)\;=\;\operatorname{Sig'}(x)^a\operatorname{Sig'}(y)^b\bmod N$. This is comes at the price of extreme insecurity: revealing the signature of $x$ and $y$ allows the efficient computation of the signature of any multiple of $\gcd(x,y)$.


Given 2 Digital Signature generated by $S=D\times k^r$ how do you solve for $k$? Given 2 signature $(D_1, r_1, S_1)$ and $(D_2, r_2, S_2)$ and the Signature is generated as $S=D\times k^r \mod N$ where $N$ is a product of 2 primes and $r_1$, $r_2$ is co-prime. How do you solve for $k$?

I got the following equations :

\begin{align}
S_1 &= D_1 \times k^{r_1} \mod N \\
S_2 &= D_2 \times k^{r_2} \mod N
\end{align}

I get that the hint should come from the co-primes of $r_1$, $r_2$. But I can't see why.

Given that $\gcd(r_1, r_2) = 1$, using the extended Euclidean algorithm we can find $a,b$ such that $a \cdot r_1 + b \cdot r_2 = 1$. If $D_1$ and $D_2$ are invertible $\mod N$ (which is quite likely; they only have to be coprime to the two large primes that make up $N$), we can compute $$k^{r_1} = S_1 \cdot {D_1}^{-1}$$ $$k^{r_2} = S_2 \cdot {D_2}^{-1}$$

Then we can compute $$(k^{r_1})^a \cdot (k^{r_2})^b = k^{a \cdot r_1} \cdot k^{b \cdot r_2} = k^{a \cdot r_1 + b \cdot r_2} = k^1 = k$$


Computing power function with BGW scheme Is it possible to use BGW scheme, to compute (private value) power of  some other private input?

I believe that it's not possible, because this scheme allow only multiplication and addition. Where here we need to know the number of multiplication operations in front of the protocol.

Is there any other MPC (more efficient than Yao's GC/ or extension to BGW), that I can use to compute a "gate power"?

Thanks.

The exact solution will depend on the specific setting you have in mind, but yes, it should be basically feasible. Suppose for example that Alice has a private input $a$, and Bob has a private $t$-bit input $b = b_0b_1\cdots b_{t-1}$ (the length $t$ is public; we always have to assume some public bound on the values of the parties anyway, whatever the protocol we plan to run).

A simple solution would be the following: Alice computes $a_i \gets a^{2^i}$ for $i=0$ to $t-1$. Then, both parties run any MPC protocol to securely compute $$\prod_{i=0}^{t-1} \left((a_i-1)\cdot b_i + 1\right) = \prod_{i=0}^{t-1} a_i^{b_i} = a^{\sum_i 2^i b_i} = a^b.$$

This requires $t$ secure multiplications and $t$ secure additions.

In this simple, setting where both parties hold one of the inputs (instead of, say, shares of the inputs),  you can also use the following natural ElGamal-based solution:

Alice encrypts her input with an ElGamal encryption scheme over a group of prime order $p$, and sends the ciphertext to Bob;
Bob can homomorphically compute an encryption of $a^b \bmod p$ from this ciphertext and sends it back to Alice;
Alice decrypts the result and get $a^b \bmod p$.

The protocol can be repeated multiple time with different primes $p_i$ until $\prod_i p_i > a^b$, and $a^b$ can then be reconstructed over the integers via CRT. There are a few details to take care of in this solution (e.g. if Alice's input is $0$, she would have to encrypt some arbitrary non-zero value instead, set her output to $0$, and ignore the content of the ciphertexts sent by Bob), but that should work.

There are alternative, more complex solutions that would be more suited in other scenarios (e.g. if $b$ is very large, and if the inputs are not known to each party but secretly shared between them, etc), see for example my paper on encryption switching, or this paper.


Handshake SSLv2, SSLv3, TLS Can someone confirm that SSLv2, SSLv3, and TLS have the same Handshake process (ClientHello/ServerHello, ..., ClientKeyExchange ...)?

If not, can you tell me the main differences between theses three protocols?

I am asking this because, as you can see in the image below, I can see ClientMasterKey (SSLv2) instead of ClientKeyExhange(TLS1.2).
ClientKeyExhange must contains the Premaster secret, and I have never seen ClientMasterKey in handshake process.

Handshake differs greatly between SSLv2 and SSLv3. All versions of TLS (1.0, 1.1, 1.2) use the SSLv3 format and although they add some new options and features they don't alter the basic flow relevant to DROWN. Although formatted differently, the security content of SSLv2 ClientMasterKey is the same as SSLv3/TLS ClientKeyExchange when using RSA keyexchange, in that both contain an RSA (specifically PKCS1v1.5) encryption of the only secret information needed to determine the keys, which is exactly why DROWN works.

The critical difference is SSLv2 ServerVerify. Quoting from the DROWN paper:

  2.2 SSL and TLS ...
  The SSLv2 handshake protocol. ...
    The server responds with a ServerVerify message
  consisting of the challenge $r_c$ encrypted with
  the server_write_key. ...
    Our attack exploits the fact the server always decrypts
  an RSA-PKCS#1 v1.5 ciphertext, computes the
  server_write_key, and immediately responds with a
  ServerVerify message. The SSLv2 standard implies
  this message ordering, but does not make it explicit. However,
  we observed this behavior in every implementation
  we examined.

  The TLS handshake protocol. ... or SSLv3, ...
  The two main details relevant to our attacks are: ...
  * After receiving the ClientKeyExchange message,
  the server waits for the ClientFinished message,
  in order to authenticate the client.

This is why SSLv2 provides the Bleichenbacher-style oracle but SSLv3 or TLS does not, so DROWN can use the SSLv2 oracle to break SSLv3 or TLS sessions.


Subexponential algorithms for DLP in $\mathbb{Z}_s \times \mathbb{Z}_t$ Consider the accepted answer to the question: Why are elliptic curves better than cyclic groups?

It seems to suggest there are subexponential algorithms (i.e., algorithms with running time
$$
L_n[\alpha,c]=e^{(c+o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}},
$$
where $\ln n$ is the input size, $c > 0$, and $0 < \alpha < 1$) for solving DLP in $\mathbb{Z}_s \times \mathbb{Z}_t$ in general.

Are there such algorithms?

If not, perhaps someone could explain the following sentence that appears in the answer:

"And working only with the representation $\mathbb{Z}_s \times \mathbb{Z}_t$ will weaken the discrete logarithm so useful for cryptographic purposes."

First of all, DLP is only defined for cyclic groups. The $\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$ you are talking about is not cyclic, since (say) $s$ divides $t$. But you can define a "generalized" DLP by considering the cyclic subgroup generated by an element $g$.

Next, DLP in any subgroup of $\mathbb{Z}_t^+$ is trivial. Figuring out why is a nice exercise. It follows that any "generalized" DLP in $\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$ will be trivial. So there's no need to consider subexponential algorithms.

(If we were talking about $\mathbb{Z}_t^*$, not $\mathbb{Z}_t^+$, subexponential algorithms would be interesting and important.)

An elliptic curve has a group structure that is isomorphic to $\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$ (for some $s$ and $t$), which means that abstractly, the two mathematical objects have the same structure. But they have different representations.

Representation is extremely important for DLP. As far as anyone knows, "generalized" DLP is hard when the representation is a suitably chosen elliptic curve, but it is extremely easy when the representation is $\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$. Abstractly, they're the same, but in practice, they are very different with respect to what we can compute.  For instance, recovering the isomorphism that connects the elliptic curve to $\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$ (that maps from one representation to the other) is computationally hard: it is as hard as the discrete log problem on that elliptic curve.

PS. The above contains many mathematical subtleties, so please consider this as an invitation to study mathematics, and not as an answer to your questions.


Can combining two secure block ciphers be insecure? Let's say we have two secure block ciphers FOO and BAR. Will a new block cipher built by combining them into a single new block cipher result in any insecurity?
$$\begin{align}
\operatorname{BAZ}_K(x)&=\operatorname{FOO}_K(\operatorname{BAR}_K(x))\\
\operatorname{BAZ}^{-1}_K(x)&=\operatorname{BAR}^{-1}_K(\operatorname{FOO}^{-1}_K(x))
\end{align}
$$

It depends on what you mean by "a secure block cipher", but under a strong enough definition (which is thought to hold in practice), the answer is "no" for boring reasons. If we had some block cipher $F_k$ such that $F_{k}^{-1}$ was also a secure block cipher, then the composition:
$$(F_k\circ F_k^{-1})(x) = x$$
Would trivially not be a secure block cipher.
Therefore, if we want to justify this (contrived) counterexample, we would need $F_k$ being a secure block cipher to imply that $F_k^{-1}$ is as well.
This does not hold for the "standard" notion of security of block ciphers (distinguishing the PRP from random), but does hold if you also allow the adversary to query the "inverse" function.
Most block ciphers in practice are thought to satisfy this stronger definition, but this kind of insecure construction (composing a block cipher with its inverse) is a "dumb" attack on your idea, and relies on the two block ciphers ($F_k$ and $F_k^{-1}$) sharing a great deal of structure mathematically.


Advice for a high schooler intending to read about post-quantum crptography I'm a high schooler who is interested in learning about post-quantum cryptography.

I would like to read some papers of post-quantum public key algorithms, shortlisted by NIST: https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions.

I have a basic understanding of abstract algebra, number theory, etc. I'm more than willing to learn more mathematical topics as necessary in order to understand the mechanics behind the algorithms I read.

Which paper(s) from the 17 shortlisted post-quantum public key algorithms would members of the Cryptography Stack Exchange Community consider the most accessible for a post-quantum newbie?

The overall aim of my personal project is to implement the algorithm on Python (that's the only language I know), then test it against a quantum computer stimulator.

I'd really appreciate the community's thoughts on the feasibility of my undertaking.

Up to and excluding the point "test it against a quantum computer stimulator (sic)", the question is about a feasible endeavor, though first implementing a more classical algorithm could be a useful warmup.

But I see a giant gap at said point: a quantum computer simulator attempts to simulate a quantum computer running a quantum algorithm, which (in the context) would be one attacking a cryptographic algorithm of the NIST PQC Round 2 (intended to run on classical computer). And by standard definition of security in PQC, there should be no known (sub-exponential or otherwise practical) algorithm that can attack a PQC algorithm. Therefore, finding an algorithm that is interesting to simulate would be extremely difficult. It's also very unlikely that the simulator would be powerful enough.

Among the NIST PQC Round 2 encryption algorithms, my feeling is that Classic McEliece is not the harder to grasp; but I've not studied them all, and on PQC I'd rather follow poncho's feelings than mine. As he pointed in comment, signature algorithms are also worth consideration.

If you do not have a clear understanding of the difference between encryption and signature, well I suggest to deffer working on PQC until you know more about asymmetric cryptography as currently practiced. That's hard enough.


Proving set membership in less than $\log{N}$ bandwidth I have an unchanging set of unique items, and I want my server to show one of those items to a client, then cryptographically prove that the item is part of the set.

How I do this currently:

Generate a Merkle tree containing all of the items.
Give the client the Merkle root, (32 bytes) out of band.
Give the client the item, then the branch leading to the Merkle root.
The client hashes the item, then hashes each Merkle branch, starting at the bottom.
If the hash at the end equals the Merkle root, the item is in the set.

The problem with this is that it takes $2\cdot 32 \cdot \log_2{N}$ bytes of bandwidth (where $N$ is the number of items in the set.) Is it possible to do this is in a smaller space?

The scheme needs one additional property, which is that once you have all of the items, it must be possible to determine that you have all of the items in the set.

Other factors:

The set isn't private - it's okay if the scheme reveals information about other members of the set.

Depending on your trust assumptions about this server, you might be able to use cryptographic accumulators which provide constant-sized (non)membership proofs.

However, as far as I know, no efficient strong accumulator scheme has been developed yet. Most accumulator constructions rely on the RSA assumption where the server knows the factorization $n = pq$ of the modulus $n$ and, as a result, can compute fake membership proofs for any element $x$ by taking the accumulator $acc$ and computing a fake proof $mem = {acc}^{x^{-1} \pmod {\phi(n)}}$. The proof is verified by checking that ${mem}^x = acc$, which is true because the server faked the proof by inverting $x$.

This happens because the server can easily compute $\phi(n) = (p-1)(q-1)$ and invert $x$.

To fix this problem, a trusted setup phase is necessary that generates a modulus $n$ of unknown factorization and gives it to the server, without giving the server the factors $p$ and $q$.

Also note that pairing-based accumulators need a trusted setup phase. However, I suspect they would be faster in practice than RSA, if you want non-membership proofs!

You might find the following accumulator papers useful:

One-way accumulators: A decentralized alternative to digital signatures
Collision-free accumulators and fail-stop signature schemes without trees
Cryptographic accumulators: Definitions, constructions and applications
Universal Accumulators with Efficient Nonmembership
Proofs
Accumulators from Bilinear Pairings and
Applications to ID-based Ring Signatures and
Group Membership Revocation

The following paper proposes using a certain kind of group called a class group to construct a strong accumulator. I am not sure how it constructs (non)membership proofs though.

Secure Accumulators from Euclidean Rings without Trusted Setup


Secret IV MAC with weak hash function Assume there is a secret-IV (hash-based) MAC scheme, i.e. $MAC_k(m) = H_k(m)$, where $H$ is a hash function, $k$ the secret key that initializes the hash function, and $m$ the message to protect with the MAC.

When using a Merkle-Damgård construction, length extension attacks can be performed trivially.

Let us further assume the MAC is instantiated with a weak hash function that has several weaknesses. I would like to focus on MD4. There exist several practical collision attacks, some semi-practical (second-)preimage attacks and obervations on MD4's onewayness.

Are there more critical attacks on the MAC in this case due to the weakness of the MD4 hash function? In practice, the above mentioned length extension attack can be mitigated by including the length of $m$ in $m$ itself.

I guess the most powerful attack would be to recover the secret-IV $k$ (maybe by exploiting weaknesses in MD4 onewayness). But I do not know if this is even possible.

Yes, there are attacks. Hash functions aren't designed for massive related message first preimage attacks. In an ideal scenario. Where the attacker can get a MAC for any string he wants that's what the hash has to stand up against. The one way function inside MD4 has to resist being reversed even when fed with lots of attacker controlled message blocks. This isn't something it was designed to do.
MD4 is similar to most of its successors (MD5 SHA1, SHA2) in that it's built from a Davies–Meyer compression function. There's an internal 128 bit state. To process a message block, the state is encrypted using a 128 bit block cipher keyed with the message block (512 bits --> 32bits x 16 words). To make the function one way, the input value is added to the output before processing the next block.

So, consider this a sort of fault injection attack. We get to flip bits of the round keys and see the resulting cipher-text (with the plaintext as an offset) we can vary the other message blocks to vary the plain-text that will be encrypted and then added to the result before we get it. The goal is to recover the plain-text.
The block cipher here has 48 rounds. There's about 200 nonlinear operations, with pretty good mixing between rounds. This sounds pretty horrible right?
Well the rounds are actually split into three groups of 16 rounds and the key schedule isn't too complex. Each of the 16 rounds in a group uses one of the 32 bit words in the current message block as a round key. Any bits we flip in a message cause a bit flip in three of the round keys.
Let's say we flipped two bits, one in one round key and another in a later round key. It's possible that the first bit flip would be cancelled by the second. Its also possible for this to repeat itself for the same bit flips in the second group of rounds. That would leave only the bit flips in the final group of rounds which are close enough to the final value we see that we might be able to distinguish that case.
Taking a look at section 3.4 of the MD4 spec, pairs (5,9) and (6,10) look promising. They aren't used too far apart in the first and second round groups while also being close enough to the end in the third round group not to have the differences spread too much before the end
(11,14) would be better but are more limited since 14 is part of the padding (the message length) which limits the bit flips we can do.
So we need the differences to cancel in the first and second round groups. We detect the lack of significant change in the hash output. This gives us information about the internal state where the cancellation happened.
Once this happens, we can make a slight change in the area of the first cancellation and then make further changes afterwards until there's a cancellation in the second round group. This gives more information. As our information improves we become limited by the probability of the second cancellation since getting that to happen is blind luck. Eventually though, we would have the full state in the area of the first collision. Just work backwards from that to get the input, the thing we were trying to get.
What does this get you?
Case 1: The secret key is the initial hash state.
The attacker can recover the initial state used as the MAC key. They can now MAC any message they want.
Case 2: the secret key is prepended to the message data and the message and key fit in a single block.
This complicates the attack but likely not that much. This would directly recover the secret key.
Case 3: The secret key is prepended to the message but padded to take up the whole first block.
Now the attacker can't recover the key but , like with case 1, can recover the secret internal state required to MAC arbitrary messages.
Case 4: The minimum message size is several blocks.
Now the attacker can't recover the key. They can only work backwards 1 block at a time. Every output value used in attacking the second to last block has to be gotten by repeating the whole attack process for the last block. If attacking one block takes N queries, attacking two takes N^2 and 3 N^3 queries. They'll likely be able to change the last block but nothing else.
Is there any way to mitigate this without using HMAC?
Yes! Add 55 bytes (64 byte block - (8 byte length + 1 byte min padding)) of constant value padding to your message before hashing. This is enough to keep all message data out of the last block. Now the attacker can't get access to the output value of the last block for which they supply message data. None of the interesting behaviour is visible to them except through an entire block of nasty behaviour.
That other statistical attack
There is one other failure mode worth mentioning. Thanks to the birthday paradox, submitting on average 2^64 plain-texts where a single block is tweaked will yield a collision. If they do the same for a second block they'll also get a collision. The important point is, this is a collision in the internal state so where A and A' are the first set of colliding blocks MAC(AB)=MAC(A'B)=MAC(AB')=MAC(A'B'). The internal state after processing block A is the same as after processing block A'. This is known as a multicollision and generalizes to multiple chained blocks. Using MD4-HMAC does not help with this since this is a fundamental statistical weakness of Merkle–Damgård construction.
What about other hash algorithms (MD5, SHA1, SHA256 ...)
They would be a lot harder to attack if not impossible. The same properties that make this kind of attack function also make it easier to find collisions. MD5 has four round groups with more shuffling of sub-keys. All other variants have a real key schedule with messy nonlinear operations used to expand the message block into multiple round keys. The probability of touching something deep inside and not completely changing the output is negligible.


Benchmarks for second round CAESAR competitors I'm interested in how the second round CAESAR competitors stack up in terms of software performance against each other and against chacha20-poly1305 with both small and large messages. Sadly the only numbers I can find are on their individual websites, and due to most likely different testing methods and hardware those aren't really comparable. Are there any comparison tables or something similar that I just haven't been able to find?

Benchmarks for 2nd-round candidates are now available at the eBACS website. There is also an independent report comparing candidates' performance.


Question on Simplest Oblivious Transfer Protocol In the paper The Simplest Protocol for Oblivious Transfer, in the scenario where the receiver chooses $c=1$, then $B$ is calculated as $Ag^b$.

Then $k_1$ is calculated as $H( (B/A)^a)$.

That means that the receiver can calculate the same encryption key, and decrypt message $M_1$ (because it's encrypted with $k_1$.

Does this imply that $H( (B/A)^a ) = H( Ag^b)$ ?

I don't understand how it works in this scenario (receiver choosing $c=1$)

As you have said, let's say the receiver chooses $c = 1$. Then his $B = Ag^b$. So In Alice's case, the $k_0 = H(B^a) = H((Ag^b)^a) = H(g^{a a} g^{a  b}) = H(g^{a a + a b})$. Similarly, $k_1 = H((\frac{B}{A})^a) = H(g^{ab})$. Receiver's own key $k_R$ is also, $H(A^b) = H(g^{ab})$. So you see, his key is similar to the senders key $k_1$. That is why, even though the sender is sending both encryptions, the receiver can only decrypt one of these. The one for which the keys are the same, i.e. message 1!


Strongest collision resistance test? An administrator is testing the collision resistance of different hashing algorithms.
Which of the following is the strongest collision resistance test?

A. Find two identical messages with different hashes

B. Find two identical messages with the same hash

C. Find a common hash between two specific messages

D. Find a common hash between a specific message and a random message

I am studying for Security+ and I find this question repeated with the same answer: A without explanation which I believe wrong.

I thought pre-image resistance is when given a hash output h, it is difficult to find the input m such that h(m) is irreversible.

While a weak collision test is when given a specific m1, it is difficult to find a random m2 such that h(m1) = h(m2)

And a strong collision test is when given a random m1 and a random m2, it is difficult to output the same hash digest such that h(m1) = h(m2)

So I believe the answer is not even listed. Since that A does not correspond to any of the collision tests definitions and B is typically the characteristic of a hash function, C implies identical messages which also a paraphrase of B and lastly, D closely refers to a weak collision test a specific m1 and random m2.

How could possibly the answer be A? Is this question missing something or am I misguided somehow? Can someone explain to me please.

I believe the answer should be E. Find a common hash between two random messages

A. Find two identical messages with different hashes

This is fundamentally impossible, assuming you're talking about a regular hash and not a keyed hash (like HMAC). As hashes are deterministic, two identical messages will always result in an identical hash.

  B. Find two identical messages with the same hash

This is not only possible, but guaranteed. Two identical messages will always have the same hash.

  C. Find a common hash between two specific messages

Assuming "specific message" refers to a message that you generate, this would be a collision attack. Such attacks are done against the hash function itself, not any existing message. A collision attack generates two messages which differ but which result in the exact same hash output.

  D. Find a common hash between a specific message and a random message

This implies a preimage attack, which is similar to a collision, but you only get to control one message. It's also far harder to exploit than a collision attack because you do not have as much freedom.


What's the difference between digest algorithm and signing algorithm? I'm reading rfc5652, there are different references of the two algorithm identifiers.
For example in this ASN.1 structure:
SignerInfo ::= SEQUENCE {
        version CMSVersion,
        sid SignerIdentifier,
        digestAlgorithm DigestAlgorithmIdentifier,
        signedAttrs [0] IMPLICIT SignedAttributes OPTIONAL,
        signatureAlgorithm SignatureAlgorithmIdentifier,
        signature SignatureValue,
        unsignedAttrs [1] IMPLICIT UnsignedAttributes OPTIONAL }

There're two types of identifiers: DigestAlgorithmIdentifier and SignatureAlgorithmIdentifier.
When using RSA for signing; isn't the digest algorithm represents the hash function used to compute the hash value, that's encrypted using the private key?
What's the signing algorithm in this case?

This is specific to PKCS7/CMS.
See rfc3370 3.2 and rfc5754 3.2,
noting that the referenced versions of PKCS1v2.0 rfc2437 and 2.1 rfc3447 have been formally superseded by 2.2 rfc8017 but the content relevant here hasn't changed. Bear in mind that the original versions of both PKCS1 and PKCS7 (which became CMS) were written in the early 1990s, before it became understood that describing signature and verification as 'encrypting' and 'decrypting' the hash with the private and public keys, or 'backwards', is misleading; PKCS1 is only descriptive has been corrected but PKCS7/CMS has this mistake baked into the ASN.1 and can't be fully corrected without introducing incompatibility.
For "RSA" signature, more exactly RSASSA-PKCS1-v1_5 from PKCS1v2.0 up, with SHA-1 the 'digest' OID is 1.3.14.3.2.26 and the 'signature' OID is 1.2.840.113549.1.1.5. For e.g. SHA-256 they are 2.16.840.1.101.3.4.2.1 and 1.2.840.113549.1.1.11. Although represented by two OIDs in different parts of the message, these actually use the standard hash,pad,modexp scheme with only one hash operation. Don't use MD5, it's broken for collision and thus signature in any setting where the adversary can affect the data (e.g. certificates), so as a result people no longer trust it for anything. SHA-1 also is broken (more recently, see other Qs and https://shattered.io) for 'high-resource' attackers like a government or google, and most people have stopped trusting it.


Algorithm for computing square roots in $GF(2^n)$ Short question: is there an algorithm for efficiently computing square roots in $\mathbb{F}_{2^n}$?

Yes, there is an algorithm for efficiently computing square roots in $GF(2^n)$.

I don't know if this is the most efficient known, but the existence of an efficient algorithm can be shown by observing that squaring within $GF(2^n)$ is a bitwise linear operation, hence it is equivalent to taking the bit representation of the value, and multiplying it by an $n\times n$ matrix in $GF(2)$ to obtain the bit representation of the sequence.  Hence, it can be inverted by computing the inverse matrix, and multiplying by that.

Also, you have tagged the question with the "quadratic-residuosity" tag; however the field $GF(2^n)$ has the special property that all elements are quadratic residues; that is, for any element $x$, there will exist a unique element $y$ with $y^2 = x$.  Hence, in this field, the quadratic residuosity question is uninteresting.


Trying to understand the constant factors (19 and 38) in Ed25519 ref10 function 'fe_mul' I would like to transpose the Ed25519 ref10 implementation to a similar twisted Edwards curve that is based on another prime, in order to have the same speed optimizations in place for the new curve. Most of the code is not too hard to understand.

However, I don't understand what is going on in the function 'fe_mul', where there are several multiplications by constant factors like 19 and 38.

Can somebody please give me a hint where these constants are coming from? Many thanks!

The section 'Radix-$2^{64}$ representation' on page 11 of the Ed25519 paper ("High-speed high-security signatures" by Bernstein et al.) actually explains the technique. I should have read the paper more carefully.

As pointed out by CodesInChaos, the order of the field is $p=2^{255}-19$ and the 38 corresponds to $2p=2^{256}-38$.


How can we get CA's public key? To get a public key of some organization or someone we want to send an encrypted message to, we need to make a request to CA asking that organization's public key. CA then returns X509 certificate. It contains CA's signature. To decrypt it we need to have a CA's public key. How can we securely obtain CA's public key?

Related:
- How can we get CA's public key?
- I've got my private key compromised. How does CRL work?
- What happens when a root CA has its private key compromised?

You can search for root certificates of a given CA.

E.g.:

http://www.symantec.com/page.jsp?id=roots, but this page is served over plain HTTP so maybe you shouldn't trust it!
or https://www.mozilla.org/projects/security/certs/included/.

From there when you want to check a certificate you can check whether it belongs to/was signed by a root CA you trust. If you trust it, then you can get its public key.

More commonly as CodesInChaos said, trusted certificates are shipped with your OS/browser.


Homomorphic multiplication by a scalar Few homomorphic encryption schemes like Paillier , Ring-LWE support homomorphic multiplication operation by a scalar apart from additive homomorphic property.

Loosely they could be defined as below

$ Additive : Dec(Enc(a)+Enc(b)) = (a+b) $
and
$ MultiByScalar:  Dec(Enc(a)\times b) = a \times b $

Is this any class of homomorphic encryption schemes that supports only these two functions ?

Not sure if they could be called Partial Homomorphic Encryption(PHE) or Some What Homomorphic (SHE) schemes.

Side notes: I saw that few papers are referring $MultiByScalar$ as $absorb$ function too.

I'm not sure I completely understand the point of your question. First of all, the property Additive implies the property MultiByScalar. Indeed, to multiply a ciphertext $E(a)$ by a scalar $b$, you can simply use a square and multiply algorithm, adding a ciphertext to itself to multiply its plaintext by two, which allows to multiply in polynomial time $E(a)$ by $2^k$, for all the positions $k$ corresponding to a $1$ in the bit decomposition of $b$, then summing all those ciphertexts to get $E(ab)$.

Note that the additive variant of the ElGamal ciphertext does also satisfy this property, but unlike Paillier or LWE/RLWE, the decryption is not efficient.

Ciphertexts with the additive property have automatically this multiplicative property; they are sometimes called partially homomorphic. Somewhat homomorphic encryption schemes refer to schemes in which you can both add and multiply encrypted value (and not just an encrypted value and a scalar), but you can do so a limited number of times (say, lots of additions and a few multiplications).

So, every additively homomorphic encryption scheme (Okamoto-Uchiyama, Goldwasser-Micali, Benaloh, ElGamal, LWE/RLWE...) satisfies your two properties (and only these two properties, regarding homomorphism: only some very specific lattice-based encryption scheme are both additively and multiplicatively homomorphic).


Why is plain-hash-then-encrypt not a secure MAC? It seems that even in MAC-then-encrypt systems like SSL, something like HMAC is used rather than a plain hash. Why?

Suppose we use some stream cipher; then why can't we use $Encrypt(m | H(m))$ as the MAC-then-encrypted version of the message? Assuming no bad relations between $Encrypt$ and $H$, what are the possible weaknesses? It seems that in this case we are encrypting the hash with part of a secretly keyed stream cipher keystream, and the hash is secure; does this not fulfil an approximation of the ideal MAC?

This must be somehow bad, since no secure protocol seems to use it. Why?

$\operatorname{Encrypt}(m\|H(m))$ is not an operating mode providing authentication; forgeries are possible in some very real scenarios. Depending on the encryption used, that can be assuming only known plaintext.

Here is a simple example with $\operatorname{Encrypt}$ a stream cipher, including any block cipher in CTR or OFB mode. Mallory wants to forge an authenticator for some message $m$ of his choice.

Mallory intercepts a cryptogram $\operatorname{Encrypt}(m_0\|H(m_0))$ of the form $IV\|C_0$, with $m_0$ known and at least the size of $m$; $C_0$ is the size of $m_0\|H(m_0)$ and the eXclusive-OR of the later with keystream $K$ function of $IV$.
Mallory computes $K$ as $C_0\oplus(m_0\|H(m_0))$, truncated to the size of $m\|H(m)$ if $m$ is shorter than $m_0$.
Mallory computes $C=(m\|H(m))\oplus K$.
Mallory replaces the cryptogram by $IV\|C$, which will pass the authentication check of the receiver, and decipher as $m$.

Another example: assume $\operatorname{Encrypt}$ is AES in CBC, CFB, or OFB mode with random $IV$; and $H$ is SHA-256. Mallory wants to forge an authenticator for some message $m$ of his choice, with size $s$ blocks of 16 bytes (the block size of AES).

Mallory computes $m_1=m\|H(m)$, of $s+2$ blocks.
Mallory manages to insert $m_1$ into some message $m_0\|m_1\|m_2$ sent by a legitimate holder of the AES key, who chooses $m_0$ and $m_2$, with $m_0$ non-empty and of size multiple of the block size known by Mallory.
Mallory intercepts the cryptogram $IV\|C$.
From $C$ Mallory removes one less block than in $m_0$; keeps the next block, forming $\widetilde{IV}$; then the next $s+2$ blocks, forming $\widetilde{C}$.
Mallory replaces the cryptogram with $\widetilde{IV}\|\widetilde{C}$, which will pass the authentication check of the receiver, and decipher as $m$.

That scenario is not far fetched: if Mallory is in a position to choose some file in a CD-ROM image, like a movie he pretends will be a promotion, then he can make a fake enciphered-and-authenticated CD-ROM image, which will appear as an authentic CD-ROM image and decipher to something Mallory chooses arbitrarily.

If $m_0$ can be empty (which is less realistic), an even simpler attack works: $\widetilde{IV}$ is $IV$, $\widetilde{C}$ is the first $s+2$ blocks of $C$.

The title of the question asks if $\operatorname{Encrypt}(m\|H(m))$ is a secure MAC, which to a Vulcan means that $\operatorname{Encrypt}(m\|H(m))$ is appended to $m$ sent in clear. This is does not provide authentication either, and succumbs to trivial variants of the above.


Separate Read and Write Keys in TLS Key Material Why does the TLS protocol use different symmetric keys for receiving and sending data?

Isn't it enough to have a single key used for both reading and writing?

Well, whether it would be safe to use the same keys to encrypt and to decrypt depends a great deal on the ciphersuite.  In particular, TLS supports ciphersuites where it would cause a serious security problem; hence TLS was designed to have different keys in two directions (so that it could use those ciphersuites safely).

In particular, the RC4 encryption algorithm would be insecure if the same key was used in both directions.  This is because, if both directions used the same key, then the same keystream would be used to encrypt both sides; that means if the attacker heard both sides of the communication, and exclusive-or'ed the corresponding bytes from both directions, he would get the exclusive-or of the two plaintexts.  This is a serious security problem; at the simplest level, if he could guess one side's half of the communication, he can recover the other side.

For one trivial example, consider a TLS-protected communication where the server sent the fixed string "Enter password:" (or the XML equivalent), and the client then sent the password, well, the attacker could exclusive or the two together, and recover the password.

Obviously, this is not acceptable.  By using two different keys for the two directions, both directions are encrypted using independent keystreams, and so the attacker cannot do this.


Is cryptography an interesting field for research? I am now styding for first year bachelor's degree in Mathematics for IT. In the future I would like to major in the same field and possibly continue trying to get a Ph.D. But I still have options to take a different path.

Even though I have a long journey ahead, I am thinking about trying to write a "scientific bachelor's thesis" (that's how we call bachelor's thesis with scientific results on my university in my language) when the time comes.

Is cryptography a field with interesting and imporant problems to solve? I know about some interesting problems like P=NP and some stuff about (post-)quantum cryptography, but surely that's not what majority of problems are like.

So, is cryptography a field where it is easy to find meaningful and interesting problems to solve?

(I am not sure if this is the right place to ask this, so please inform me if I should ask somewhere else.)

Cryptography is a nice field in which not only problems to solve are a-plenty, but it is also one of these fields where individuals can make significant discoveries in a relatively short time. A PhD student in cryptography will typically write three or four articles during his thesis; by comparison, a "pure mathematics" PhD student will generally produce a single article in the same time. Informally, to make new advances, you have to first learn the existing science; in cryptography, this means getting up to date with about 40 years of research. In mathematics, that's closer to 200 years, hence the comparatively higher effort to reach the "publishable" state.

Moreover, cryptography is an applied field, by which I mean that it has immediate practical applications. This means money: you can make a very nice living out of cryptographic expertise. A PhD is a very good key to unlock such things (I have a PhD and I am a consultant in cryptography, and my experience is that both facts are related). Intellectual fulfilment is of primordial importance to a balanced life, and money does not make happiness; but money is still some super useful stuff, and being able to live out of doing intellectually rewarding things is a nice combination to achieve.

In any case, mathematics are always useful for anything related to computers. A lot of computer users and developers can get along with a very low understanding of the underlying principles, but the maths are what explains why computers work that way. Mathematics allow to look beyond the magic.