Security effects of the seed's length in OAEP In the OAEP scheme for asymetric encryption padding a random seed is used, whose length can be chosen. The paper which introduced OAEP in 1994 just states, that the seed's length $k_0$ should be chosen such that the adversary's running time is significantly smaller than $2^{k_0}$ steps.

I am wondering, what the securiy effects would be, of choosing a very small or very large $k_0$.

NOTE: I am asking about the generic OAEP, not RSA-OAEP, which fixes $k_0$ to the length of the hash function used.

Let's start with the preliminaries. The basic scheme has encryption defined as follows:

$$\mathcal{E}^{G, H}(x) = f(x \oplus G(r) || r \oplus H(x \oplus G(r)))$$

Some definitions:

$f: \{0,1\}^k \rightarrow\{0, 1\}^k$ is a trapdoor permutation where $k$ is the security parameter
$x$ is the message to encrypt
$n = |x|$ is the bit length of the message
$k_0 = k - n$ (the value of interest in out case)
$G: \{0,1\}^{k_0} \rightarrow\{0, 1\}^n$ is a "generator" from $k_0$ bits to $n$ bits
$H: \{0,1\}^n \rightarrow\{0, 1\}^{k_0}$ is a "hash function" from $n$ bits to $k_0$ bits
$r \gets \{0, 1\}^{k_0}$ is a randomly selected $k_0$ bit string

The general idea behind setting $2^{k_0}$ to be much larger than the adversaries run time is to prevent the adversary from having a non-negligible chance of brute forcing the value of $r$. Recall that $r$ is a random $k_0$ bit string so there are $2^{k_0}$ possible values of $r$.

Suppose that $k_0$ was selected to be only a couple bits, in this case $\mathcal{E}^{G, H}$ is not secure under a chosen plaintext attack (IND-CPA). For an intuition of how to prove IND-CPA see this graphic. Briefly, if an adversary submits messages $m_0, m_1$ to be encrypted by $\mathcal{E}^{G,H}$ and gets back $c$ it needs to determine if $c$ is the encryption of $m_0$ or $m_1$. Here's how it does that:

$G$, $H$, and $f$ are all public , so the only unknown in the equation is $r$, which was randomly sampled. If $r$ is small enough (i.e. if $k_0$ is small) then an adversary can compute $\mathcal{E}^{G, H}(m_0)$ and $\mathcal{E}^{G, H}(m_1)$ for all possible values of $r$. Once it computes a value that matches $c$ the adversary knows that $c$ is the encryption of whichever message was input into $\mathcal{E}^{G, H}$, which means it has a non-negligible advantage in the IND-CPA game (i.e. the scheme is not IND-CPA).

So naturally we want to pick a $k_0$ that is large enough such that an adversary is unable to brute force the value of $r$. This implies the definition that $k_0$ be chosen such that the adversary's running time is significantly smaller than $2^{k_0}$ steps.

So to conclude, for values $k_0$ that are very small the results are catastrophic as you lose semantic security. For values $k_0$ that are very large there's no security drawback, but your permutation $f$ needs to be bigger which generally translates to a slower scheme (think RSA2048 vs RSA4096 for example).


Does make sense utilize TLS and Noise Protocol in the same application? Nowadays I work maintaining an web application written in Node.js and we use HTTPS with TLS 1.2. We have to implement a new feature related to security on this application, all HTTP messages must be encrypted, and we will have all messages encrypted two times ultimately, one time using TLS and another through the new feature. We are studing the Noise Protocol to know if makes sense use it on this new feature, but from what I understand so far, the Noise Protocol would be an alternative to TLS. I'd like to know if makes sense use both protocols together, or if they are
mutually exclusive.

We don't know how to utilize the Noise Protocol yet, if we simply pick up an implementation and include on the project or if the Node.js should offer an implementation like TLS. I found this implementation on GitHub: Noise-c.

Any clarification or help is welcome, thanks.

Using two transport protocols is not a good idea. You would double-encrypt your data. However, the symmetric ciphers are generally rather secure if applied correctly.

Besides double encrypting your data you would also get: double the security warnings to react to, double key management, double the initial handshake processing, double the latency.

If you want to encrypt twice it is probably better to perform additional end-to-end encryption / decryption on top of the point-to-point encryption that the TLS security offers. That way you can keep your messages secure over multiple point-to-point connections and after receiving them at the end points. For this you could device your own protocol or you could use web-security.

Generally it is better to perform encryption well once, instead of performing it badly twice. Bullet-proofing your TLS connection makes the most sense if you just require transport protocol security. Encrypting things twice should not be your goal. The goal is simply to secure your messages to the best of your ability.

The noise protocol seems to be in draft stage. Besides that, it seems a rather generic sum of possible algorithms more than an actual protocol. It seems that it mainly has been setup to explain the security behind WhatsApp rather than to be a protocol that you should consider. Just the formatting of the messages is already ill-defined, and it is unclear which kind of authentication method you should be using.


General idea for storing public/private keys? What are the general ideas for storing keys in order to make sure no one else has access to it?

It's not a good approach to hash the keys, since you are going to need them later.

The requirements for storing public keys and private keys are quite different. Public keys need to be in a trust store in order to be able to trust them. Care should be taken that an attacker cannot replace them or trick the system into using a different trust store. Public keys - as the name implies - do not have to be confidential.

The requirements for private keys obviously do require confidentiality. Furthermore, the access to use the private keys should be restricted. Note that it is possible to open up access to use the private key while keeping them confidential; an example of this is storage of the private key in a smart card, which then offers a signing / decryption service.

The handling of public keys / certificates and private keys is known as key management. Entire books have been written about that subject so we won't be able to discuss all of them.

For storage in software a common method is to store the private keys in key stores. Examples of key stores are PKCS#12 key stores and PGP key containers. These containers are files for which the contents of the entire store and / or the key entries themselves are in turn protected by a passphrase.

For generic solutions I'd take a good look at PKCS#12 which is for instance used by OpenSSL. Mind that the default password handling may still require work (e.g. increasing the work factor for the decryption key that unlocks the PKCS#12 contents). Just choosing PKCS#12 is not key management on its own.

Symmetric (data or session) keys are often derived - using a Key Derivation Function or Key Agreement protocol - rather than stored.


What was the problem in the SSL version 2.0? What is the main reason (attacks) the appearance of the protocol SSL version 2.0 to replace version 3.0?

RFC 6176 lists four reasons why SSL 2.0 must not be used, in its section 2:

  Message authentication uses MD5 [MD5].  Most security-aware users
    have already moved away from any use of MD5 [RFC6151].
  Handshake messages are not protected.  This permits a man-in-the-
    middle to trick the client into picking a weaker cipher suite than
    it would normally choose.
  Message integrity and message encryption use the same key, which
    is a problem if the client and server negotiate a weak encryption
    algorithm.
  Sessions can be easily terminated.  A man-in-the-middle can easily
    insert a TCP FIN to close the session, and the peer is unable to
    determine whether or not it was a legitimate end of the session.

However not all reasons are equivalent in gravity. The main security issue with SSL 2.0 is that it has no notion of verified closure: the SSL 2.0 connection ends when the underlying TCP connection is closed. An active attacker can force that, and neither client nor server can know whether the closure is really what the peer wanted. This is a problem when the protocol within the SSL tunnel uses the closure in a semantic way; e.g., with HTTP when there is no Content-Length header or chunked encoding (a rarity nowadays).

The three other reasons are less imperious, and can be debated:

Though MD5 is thoroughly broken with regards to collisions, it still is quite strong when used in other ways, e.g. to build a MAC (as long as you do it properly). You should not use MD5 in new designs, but that does not mean that MD5, as it is used in SSL 2.0, can trivially be broken (or even non-trivially).
Through the lack of protection of the handshake messages, attackers can force client and server to use a weaker cipher suite than what they could have used -- but one could say that the real issue here is that the client and server agree to use a weak cipher suite at all.
Indeed, when the negotiated encryption is weak (a 40-bit "export cipher"), the MAC key is equally weak. But, there again, if the client and server agree to use weak crypto, they only get what they deserve.

Apart from that, SSL 3.0 is more extensible and offers extra features:

SSL 3.0 supports more generic key exchange mechanisms, such as Diffie-Hellman (SSL 2.0 is RSA-only). In particular, this opens the possibility of ephemeral Diffie-Hellman, which grants forward secrecy, a nice thing to have.
SSL 3.0 allows for re-handshake: doing a new handshake within the context of the first. This allows for things such as requesting certificate-based client authentication conditionally, based on what was previously exchanged over the connection.
SSL 3.0 supports optional compression (not always a good idea, but sometimes a nice thing to have).
SSL 3.0 is extensible with room to put extensions in the ClientHello and ServerHello. This has been used extensively, e.g. to fully support elliptic-curve cryptography.


Single roundtrip authentication I have a server and a client that need to authenticate to that server.
The idea is that we have user/pass and the authentication generates a token that can later be used.

An important factor here is that I want to reduce the number of network round trips as much as possible.
I came up with the following scheme:

Client generates a single use public key / private key
Client sends the server the following:

user
public key
hash(public key + pass)

The server load the relevant user and computes hash(public key + pass)
It then generates a token that the client will use, and encrypt that token using the public key.
Client decrypt the token using the private key, and can then use it.

The issue of token security is not relevant here. It is expected that most users will use this over HTTPS, but we need to avoid sending the password on the clear for cases where users use HTTP internally inside the organization.

As I figure, we prevent replay attacks using this approach because only the client can decrypt the token.

I'm aware that if an attacker can listen to the network they can just sniff the token on the next request after authentication, but that isn't the concern here.

Are there any holes that I'm missing?

public-key, H(public-key||pass) seems open to offline password guessing. Other than that seems to achieve what you want under the adversarial assumptions.


Assumptions on one-way functions What are the assumptions we make to propose a one-way function? I only know of some number theoretic assumptions, but what are the other assumptions you can possibly make, which if true, would imply that $f$ is a one-way function?

(Considering pre-image resistant hash functions, what is the assumption there? Hashes as far as I know do not rely on any assumption other than the fact that it seems to  be hard)

Edit:

Example: Say we assume factoring a semiprime $N = pq$ is hard. Then we can say that the function $f(p,q) = p*q$ is one-way. What other assumptions exist?

General
The existence of a "perfect" one-way function is not proven. Such a function would prove that P $\ne$ NP, which is still an unsolved problem in mathematics / computer science.
One-way functions are per definition hard to invert, but easy to check. One example, that are assumed that they are one-way, are hash-functions:
You can easily create a hash of a given input, but you can't get the input from a given hash in a reasonable amount of time, assuming the input is long enough.
Some properties of a one-way function:

Easy to compute, but infeasible to compute the inverse of the function in the average case
Preimage resistant

Hashes
We assume that there exists a perfect one-way hash function: Hash functions are a special kind of one-way functions, since they reduce a possible large input to a fixed length smaller hash value, the term is a one-way compression function. This means that there is a data-loss and also means that mulitple different inputs can have the same hash value (pigeonhole principle). Data-loss here means, that it's impossible to retrieve the unknown original input from a given hash-value.


Functional Encryption (for Non Experts) I recently stumbled across "How to Run Turing Machines on Encrypted Data".

Given that it's now possible to run turing machines on encrypted data, what open problems remain in the realm of Functional Encryption?

(It seems like for every problem in Functional Encryption, one would just say: well, design a TM to compute the function, encrypt the data, then use the above scheme.)

Some general categories that come to mind:

Same functionalities from less extreme assumptions; in particular, from falsifiable ones. For example, the FE for Turing machines in GKPVZ requires SNARKs and extractable witness encryption, both of require less plausible "knowledge-type assumptions." See Gentry/Wichs
Or taking the above further: Succinct-ciphertext functional encryption without obfuscation. Obfuscation is likely to be slow in practice for a long time. Wouldn't it be nice if we could have, say, a practical, compact-ciphertext functional encryption scheme for P/poly from (say) the NTRU problem alone?
Stronger notions of security, directly. Currently, iO-based functional encryption schemes are proven selectively secure, boosted to full security by complexity leveraging, and then boosted to SIM security by De Caro et al's compiler. Being able to prove the strongest possible notions of FE security from 'first principles' would be nice.
Anath, et al defines a notion of delegatable functional encryption. It could be interesting to explore how far this can be taken in general.
Boneh, et al gives one example of a definition of function privacy for functional encryption. "Full" function privacy for all P/poly is impossible, since VBB cannot exist for all P/poly in the real world, but restricted notions may be possible for all functions (or 'full privacy' for restricted classes of functions)
(Disclaimer: my work) You could also consider functional encryption in a setting where the function is represented by, say, Java code: AFKLSZ


Forgery attack against Textbook RSA with simple redundancy I know how to forge vanilla Textbook RSA message signatures (easy).

I've learnt that by adding a good redundancy to the message, it cannot be forged anymore.

How can one add redundancy so that the message could be recovered from the signature (RSA with message recovery), and cannot be forged (meaning the redundancy function is "good")?

For example, a redundancy function which adds a 00...0 sequence in the beginning

of the message is considered not secure because it's easy to forge. (How?)

The usual methods of RSA signature with message recovery (that is, embedding a part of the message in the signature, known as the revoverable message) are those in ISO/IEC 9796-2:2010 (partial preview). There are three:

Scheme 1; it is an ad-hoc scheme that essentially concatenates the recoverable message, the hash of the whole message, and a little fixed data (about two bytes when there's more to the message than the recoverable part), forming the padded message; to which the raw RSA private function is then applied. This scheme is insecure if the adversary can obtain the signature of many chosen messages, see Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi and Ralf-Philipp Weinmann, Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures, in proceedings of Crypto 2009; or full PDF
Scheme 2; in addition to hashing, it uses salting and an unbalanced two-rounds Feistel construct using a Mask Generation Function, so that the input of the raw RSA private function is indistinguishable from random (except for about two bytes, and without knowledge of the salt assumed random). It aims at demonstrable security similar to (and by the same means as) the Probabilistic Signature Scheme introduced in version 2 of PKCS#1, and pioneered by Mihir Bellare and Phillip Rogaway: The exact security of digital signatures - how to sign with RSA and Rabin, in proceedings of Eurocrypt 1996; or better PDF.
Scheme 3; that's precisely scheme 2 with no salt. It is deterministic (when the size of the recoverable portion of the message is fixed), and has the same message embedding capacity as scheme 1. It has the demonstrable security of Full Domain Hash; see Jean-Sébastien Coron, On the Exact Security of Full Domain Hash, in proceedings of Crypto 2000, or better PDF.

Noticing that left-padding a message $M$ with zero bits leaves its value unchanged when bitstrings are assimilated to integers using big-endian conventions (as customary), the last paragraph of the question asks how to attack the trivial RSA signature scheme giving message recovery where

the signature of message $M$ is defined as $\mathcal S(M)=M^d\bmod N$ (just as in vanilla Textbook RSA message signature), restricted to $M$ of (perhaps: at most) $m$ bits with $m$ fixed, positive, and such that $m\ll \log_2N$;
the verification procedure recovers $M$ from $\mathcal S(M)$, as $M=\mathcal S(M)^e\bmod N$, then checks that $M<2^m$ (that is, checks the padding consists of zero bits).

Another way to look at this is: vanilla Textbook RSA message signature, with the message omitted (as it can be recovered from the signature), and restricted to be exactly (or at most) $m$ bits.

Just as in vanilla Textbook RSA message signature, it is easy to make an existential forgery out of nothing, in the sense that the message consisting of $m$ bits at zero has signature $0$, and the message consisting of $m-1$ bits at zero followed by a single bit at one has signature $1$. Also, if the public exponent $e$ is small, for any positive integer $S$ less than $2^{m/e}$, $S$ is the signature of message $M=S^e$.

Just as in vanilla Textbook RSA message signature, it is easy to make a forgery for a large fraction of valid messages $M$ one wishes to obtain a signature for, when having access to a signing oracle (that is, mean to obtain signature of any desired valid message, except for the messages subject to forgery). One method is to try to factor $M$ into $M_0\cdot M_1$ for $1<M_0\le M_1$, which is possible for a large fractions of messages $M$ (including all even $M\ge4$, and more generally all $M$ divisible by a small prime and larger than this prime). It holds that $\mathcal S(M_0)\cdot\mathcal S(M_1)\bmod N=\mathcal S(M)$, and that allows computing the signature of $M$ from that of $M_0$ and $M_1$.

Note: a former version of the present answer explained how to forge a slightly less vulnerable trivial RSA signature scheme giving message recovery, which (it turned out) did not match that intended in the question.


When a DER format RSA private key is extracted from an encrypted PEM file, is it still encrypted? Let's pretend we create a passphrase protected PEM file using openssl:

$ openssl genrsa -aes256 -passout pass:password -out sample.pem 2048

And then extract the private key in DER format:

$ openssl rsa -in sample.pem -out sample.prv.der -outform DER

Is sample.prv.der still encrypted using the passphrase?

No, it will output the PKCS#1 compatible encoding of the private key, try this:

openssl asn1parse -inform DER -in sample.prv.der

it will output an ASN.1 sequence of:

a version number (00);
the modulus;
the public exponent;
the private exponent;
the CRT parameters.

It did ask you for the password, right?


Implementing Secure multi-party computation for online website I need to know if the following is feasible:
I want that any two users of my website have a private key such that the private key is divided into three parts one for website owner and one each for the two users.

I understand that the private key can be divided into 3 parts such that two of them can generate the full key using "Shamir's Secret Sharing" , however I want to know if it is possible to independently generate and distribute the key parts to each party, so that the users do not need to fear that the website or other user may have the private key.

I think it may be possible using multi-party computation but could not find any such implementation.

Thanks

What exactly constitutes the "private key"?

If the key is the private part of an asymmetric encryption key pair, such as for RSA, and you'd hence also like all three parties to know the public key, then what you're looking for is called distributed key generation. You can then also use threshold cryptography and let the parties compute private key operations – decryption and signatures – without any single party needing to have access to the full key.

If the key is any random string of bits (e.g. the key for a symmetric block cipher), and you want a secret sharing of this random value, what you want is called correlated randomness (see e.g. this paper by Ishai et al. from 2013 for its uses in multiparty computation). In this 2-out-of-3 case, you can simply let each party $i \in \{1, 2, 3\}$ generate a random $k$-bit string $r_i$ and send their value to the "next" party (i.e. party $i$ sends $r_i$ to party $i+1 \bmod3$). Define $r = r_1 \oplus r_2 \oplus r_3$ to be your random key. Then any single party has only two of the values $r_i$, and hence does not obtain any information about $r$, but any two parties can reconstruct $r$.


Updating the secret key used for HMAC I am designing a distributed system, composed by a set of physically distributed embedded devices (8 bit cores with less than 1 KB of RAM). The devices need to be able to authenticate the originator of the commands they receive, and for that purpose I chose HMAC.

Each device has a secret key, and a central server knows all of the keys (somewhat similar to a RADIUS server). When a user wants to send a command to a device, it first sends the message to the central server which will append the correct HMAC to it. The user then sends the authenticated message to device, the HMAC is sucessfully verified and the message processed.

My question: is it possible to update the secret key on the device using only this scheme? Since there is no encryption, the new key would be sent in plaintext. I was wandering if a secret sharing mechanism would work for this case.

Does your embedded device have access to a random input source and a bidirectional channel?

If not, then there will only ever be as much entropy on the chip as you put on it to begin with, so there's no purpose in updating the key.

If so, then just do an authenticated key exchange and generate a new shared symmetric key occasionally.  ECC is best for bandwidth starved devices and lattices are best for computation starved devices.


Why do we need multiple adversaries in a game-based definition? Consider we have a protocol, where multiple algorithms of it are run by an adversary.
When we want to define a game for that protocol (or its security properties), I have seen that an adversary is defined as $A=(A_1,A_2,...A_n)$. Then each of them (e.g. $A_1$) calls a certain algorithm and outputs something (in other words its role is one-off).
Question: Why do we need multiple adversaries instead of a single one? why cannot always use only one adversary (like here)?

It is a way of formalizing a security definition as an interactive game played against an adversary.
In an interactive game between an adversary and challenger, the adversary outputs some value, then the challenger responds, then the adversary chooses another value, etc etc. It's possible to define things at this level of formality (by using phrases like "adversary outputs a value and gets another value in response"). But sometimes you also want to introduce some precise notation about this interaction.
One way to do this is to think of the adversary (and challenger) as "next message" functions. This paper is considering $A_1$ to be the algorithm that outputs the adversary's first thing, $A_2$ is the algorithm that takes the challenger's response as input and outputs the adversary's second thing, etc. This kind of notation is formal and precise, but clunky. It's often also necessary to allow $A_1$ to pass its internal state ahead to $A_2$, etc. In the paper that you link, the goal is to apply to literally any interactive security game, thus the more formal style.
Here's an example for chosen plaintext security for public-key encryption. A perfectly reasonable way to define it would look like this:

Challenger chooses $b\gets \{0,1\}$, generates a keypair $(pk,sk)$, and gives $pk$ to the adversary
Adversary chooses plaintexts $m_0,m_1$
Challenger encrypts $m_b$ and gives the result to the adversary
Adversary outputs a guess $b'$, and wins the game if $b'=b$

A more "formalistic" way of defining the same interaction might read:

$b \gets \{0,1\}$ [challenger chooses random bit $b$]
$(sk,pk) \gets \textsf{KeyGen}$ [challenger chooses key]
$(m_0,m_1,\textsf{state}) \gets A_1(pk)$ [adversary gets public key and chooses two plaintexts]
$c \gets \textsf{Enc}(pk,m_b)$ [challenger encrypts one of the plaintexts]
$b' \gets A_2(\textsf{state}, c)$ [adversary gets ciphertext and outputs a bit $b'$]
declare the adversary winner if $b = b'$


Is DES secure under CBC? I know DES is outdated, but will is is secure in CBC mode? Can anyone help me understand why not?

No, it will be insecure. There are two reasons;

Due to the smaller key size 56-bit; DES was tested for brute-force attack since published.

DES_CHALL, 96 days to find the CES challenge key in 1997.

EFF DES cracker 56 hours to find the CDES challenge key in 1997.

COPACOBANA, an FPGA hardware built for attacking by brute-force for DES, can successfully find the key on average 6.4 days in 2006.
4 . Hashcat; running with two p3.16xlarge instances on AWS, one probably will find the key on average in about 0.9 days. Because that's 46G tries/second per GPU and 16 GPUs.

crack.sh can search the key in ~26 hours with a single machine.

crack.sh also produce a chosen-plaintext attack utilizing a rainbow table to recover DES key in 25 seconds in 2017.
There is a nice secret message in the DES Challange II-2 about this;

$$\text{The secret message is: It's time for those 128-, 192-, and 256-bit keys.}$$

Due to the Small 64-bit block size; DES is not secure under any modes of operation. If the attacker collects blocks encrypted under the same key in total the square root of the possible blocks, there $%50$ chance that the clock will be the same. This will leak information even CBC and OFB.For a 64-bit block cipher as DES, $\sqrt{2^{64}} = 2^{32} \times 8 \text{ B} = 32 \text{ GiB}$ space will be enough.
In our community, there are two nice questions more about the block size;

How does blocksize affect security?
Is a small size block cipher usable?

and a website Sweet32: Birthday attacks on 64-bit block ciphers in TLS and OpenVPN.


Does pairings based cryptography inherently require a CRS/trusted setup? In all algorithms I've seen that rely on pairings-based cryptography (some examples: snarks without PCPs, more snarks, sublinear ring signatures), a common reference string is required. Is this always the case? If so, what is it about pairings (or the algorithms that use them?) that means the CRS is needed?

I know ZCash got around this by using MPC to emulate a TTP as described here, here, and here, but I'm more interested in understanding why the CRS is necessary. To clarify, I don't mean why the party that generates it needs to be trusted, as I understand that the public parameters of the CRS cannot be generated without use of the 'private' component that must later be destroyed, but I would like to know why the public parameters are required?

(I've looked at is pairing based crypto ready for productive use thinking it might answer this question but it doesn't)

No. For example, these pairing-based protocols don't require trusted setup:

BLS signatures;
tripartite Diffie-Hellman, as mentioned in Elias' answer;
some identity-based encryption schemes (when users are their own PKGs, e.g. when using IBE for forward-secure encryption);
the Bünz–Maller–Mishra–Vesely polynomial commitment scheme. (This could in principle be used for NIZK arguments of knowledge, although it has $\Theta(\sqrt{N})$ verification and so is not fully succinct.)


Prevent replay attack without storage I am designing a set of low-power sensing motes. Each mote will communicate to a central base over RF.

I want the mote to be able to authenticate itself with the base, and send its data without being vulnerable to replay attacks while not using a lot of processing power.

Are there major flaws in the following algorithm?

Mote A sends a 'hello' message to Base. This message contains the ID# (public key of the mote) and a random nonce [R] (HW generated) encrypted by the base's public key.
Base decrypts the 'hello' and verifies the ID# against a whitelist.
Base sends an 'ack' message to Mote A. This message contains [R+1] and is encrypted by the ID# (mote's public key)
Mote A decrypts 'ack' and verifies received [R+1] matches stored [R+1].
Mote A sends ID#, data and [R+2] to base encrypted by Base public key.
Base decrypts and sends an 'ack' and [R+3] and is encrypted by the ID# (mote's public key)
Mote A verifies 'ack' and Communication is Complete.

The random nonce [R, R+1, R+2, R+3] will only be valid for a short period of time (< 1 second) as the base has no memory for session storage.

This protocol doesn't authenticate the mote at all.  Consider this attack:

Mote B sends a 'hello' message to Base. This message contains the ID# of Mote A and a random nonce [R] (HW generated) encrypted by the base's public key.
Base decrypts the 'hello' and verifies the ID# against a whitelist.
Base sends an 'ack' message. This message contains some gibberish that Mote B cannot understand.
Mote B sends ID#, data and [R+2] to base encrypted by Base public key.
Base decrypts and sends more gibberish that Mote B cannot understand
Mote B ignores the ack.

Here, the base has accepted data as coming from Mote A, even though it actually came from Mote B.

In addition, it does nothing to prevent a replay attack (as someone just replaying the two messages that the mote sends to the server would cause the server to accept the replay).

For this general idea to work, then either:

The base needs to send some data to the mote encrypted by the mote's public key, and the mote must use that data as a necessary part to continue the exchange; or
The mote needs to sign something with its private key (which the base validates)

In addition, then if the server cannot store state about the messages it has already received, then it is the one that needs to pick the random number (nonce), and inject that into the protocol.


How to find generator $g$ in a cyclic group? As generator $g$ is used in DH how do you find a combination of prime $p$ and $g$? eg: if we choose $p=23$ and its generator is $7$ (given in the book) how do we find the generator?

Mike gave you the answer for the specific question you asked.  I'll try to give you an answer to the question you should have asked:

  For Diffie-Hellman, what criteria should I use to select a secure $p$ and $g$?

This question is important, because not every large cyclic group is actually secure.  It turns out that, for the group $\mathbb{Z}_p^*$, the factorization of $p-1$ is critical.

If $p-1$ has a factor $q$, and $g^{(p-1)/q} \ne 1$, then given $g$ and $g^x \bmod p$, we can determine $x \bmod q$ in $O(\sqrt{q})$ time.

What does this mean?  Well, if we pick a $p$ where $p-1$ has a bunch of small factors $q_1, q_2, q_3$, and we give $g$ to be a primitive element (so $g^{(p-1)/q} \ne 1$ for any $q > 1$), then we transmit $g^x \bmod p$ as a part of the DH exchange, the attacker can efficiently derive $x \bmod q_1q_2q_3$; we're effectively giving him $\log_2 q_1q_2q_3$ bits of our secret exponent.  This means that, with a random prime $p$ and either a random $g$, or a primitive $g$, we have a good possibility of leaking quite a bit of information.

So, what do we do?  Well, first of all, we make sure that $p-1$ has a large prime factor $q$ that we know.  There are two common practices:

Select a prime $p$ with $(p-1)/2$ prime as well (often called a safe prime).  If we do that, then $q = (p-1)/2$ is certainly large enough (assuming $p$ is large enough).
Select a prime value $q$ (perhaps 256 to 512 bits), and then search for a large prime $p = kq + 1$ (perhaps 1024 to 2048 bits).  This is called a Schnorr prime

Once we have our values $p$ and $q$, we then select a generator $g$ that is within the subgroup of size $q$.  Members of this subgroup have the property that $g^{(p-1)/r} = 1$ for any factors $r$ of $p-1$ other than $q$ (and $p-1$ itself), hence the above observation does not apply.

One easy way of selecting a random generator is to select a random value $h$ between 2 and $p-1$, and compute $h^{(p-1)/q} \bmod p$; if that value is not 1 (and with high probability, it won't be), then $h^{(p-1)/q} \bmod p$ is your random generator.

An alternative method of finding a generator $g$: if you selected a safe prime, and if your safe prime also satisfied the condition $p = 7 \bmod 8$, then the value $g=2$ will always be a generator for the group of size $q$.  It won't obviously be a random generator, however, we can also show that, with a safe prime, if you can solve the computational Diffie-Hellman problem with $g=2$, you can solve it with any $g$ (with a polynomial number of queries), hence $g=2$ cannot be weak.


Salsa20 in Davies-Meyer mode with a fixed key (message): is it one-way? Say I have a function that calculates a pseudo random permutation and this function is easy to invert.

For example $P(i) = AES_k(i)$ where $k$ is a publicly known key. So anyone can compute $P(i)$ and also get back $i$ if $P(i)$ is known.

Would the following function be hard to invert?

$$F(i) = P(i) \oplus i$$

I am trying to understand why the Salsa20 construction is secure and would like to know if any construction like this will be secure provided that $P(i)$ is a good pseudo random permutation, or if there is more to it.

If you take a pseudo random permutation permutation you usually get a hard to invert PRF.

AES with its 128 bits is a bit narrow, but Salsa's 512 bits are certainly wide enough.

Commonly used compression functions are built from block-ciphers with similar techniques:

For example Davies–Meyer (used in popular hashes such as MD5, SHA-1 and SHA-2) uses:

$H_i = E_{m_i}(H_{i-1}) \oplus H_{i-1}$

The $\oplus$ operation prevents solving for $H_{i-1}$ given $m_i$ and $H_i$. Without this one-way operation a narrow-pipe hash-function would be vulnerable to meet-in-the-middle attacks.

With Matyas–Meyer–Oseas the $\oplus$ is even more crucial:

$H_i = E_{H_{i-1}}(m_i) \oplus m_i$

This construction directly relies on $\oplus$ turning a permutation into a one-way function for its pre-image resistance.

The only different between Matyas–Meyer–Oseas constructions and Salsa is that salsa is lacking the chaining value/block cipher key which it doesn't need.


Is post-quantum Oblivious Transfer possible If I’m not mistaken classical OT is not regarded quanum-safe. However I’ve been reading (not really understanding) some papers [1,2] and some reviews[3] on quantum OT and/or post-quantum OT, it seems to be possible.

I do have an engineering background, so that’s the reason why I don’t get quantum cryptography papers.

Can you please explain briefly in layman (engineer) terms if and how post-quantum OT is possible?

[1] https://www.computer.org/csdl/proceedings/phycmp/1994/6715/00/00363696.pdf

[2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.650.385&rep=rep1&type=pdf

[3] https://www.quantiki.org/wiki/oblivious-transfer

Post-quantum oblivious transfer protocols are possible. If you base the security of the OT in a post-quantum assumption, this should give you an OT conjectured to be robust to quantum attackers. Besides the already mentioned OT based on supersingular isogeny (in comments), I can give you some other examples:

Code-based: https://eprint.iacr.org/2008/138.pdf , https://ieeexplore.ieee.org/document/6089575

Lattice-based: https://eprint.iacr.org/2018/530

There are also some constructions for OT ,secure in the Universally Composable framework and based on post-quantum assumptions, such as

https://link.springer.com/chapter/10.1007/978-3-319-12280-9_10

based on the LPN assumption, and the ones that can be instantiated using the frameworks of:

https://eprint.iacr.org/2007/348.pdf

and

https://eprint.iacr.org/2017/993.pdf

using post-quantum encryption schemes.


Is it safe to reuse the same random session number r in the Guillou-Quisquarter protocol? I basically use the method below, one difference is that after receiving the first proof the verifier asks the prover to create a proof for another challenge d and this several times without having the prover generate a new random value r.
Is this safe? I was not able to find indications in the literature about it and r is never defined as a nonce but I am afraid this could leak the provers secret key A.

  Guillou and Quisquater ([link][1]) present a zero-knowledge proof of
  an RSA signature. Basically, the scheme is as follows:

  Public knowledge: RSA modulus $n$, public RSA exponent $v$, preimage
  $X$.

  Secret knowledge for prover: $A$, such that $A^v = X \mod n$.

  $$ \begin{matrix} \mathcal{P} & & \mathcal{V} \\ r \xleftarrow{\$}
 \mathbb{Z}_n^* \phantom{\mod n} & & \\ T \leftarrow r^v \mod n & & \\
 & \xrightarrow{\quad{}T\quad{}} & \\  & & d \xleftarrow{\$}
 \{0,1,\ldots,v-1\} \\  & \xleftarrow{d} & \\  t \leftarrow A^dr \mod n
 & & \\  & \xrightarrow{\quad{}t\quad} & \\  & & t^v \stackrel{?}{=}
 X^{d}T \mod n \end{matrix} $$

  In this diagram, $\leftarrow$ denotes assignment of a value to a
  variable and $\xleftarrow{\$}$ denotes uniformly random selection from
  a finite set.

  [1]: http://dl.acm.org/citation.cfm?id=88372

Is this safe?

No, it is not.  Here is how it would be easy to recover $A$:

The prover generates $r$ and publishes $T$, and the verifier selects an arbitrary challenge $d$.  The prover responds with $T = A^d \cdot r$
The prover generates the same $r$ and publishes the same $T$.  The verifier selects the next $d' = d+1$ as his challenge, and the prover responds with $T' = A^{d'} \cdot r$

The verifier can then compute $T' \cdot T^{-1} = (A^{d+1} \cdot r) / (A^d \cdot r) = A$, thus recovering the secret.

  I was not able to find indications in the literature about it and r is never defined as a nonce but I am afraid this could leak the provers secret key A.

Actually, it's not a nonce; calling something a nonce implies that the only requirement it has is that values never repeat,  In this case, you can devise ways to exploit related $r$'s as well; for example, if it's a simple incrementing pattern, that is, $r' = r+1$, then the attacker just selects $d = d' = 1$.  There might be nonrandom update patterns that are safe, but why risk it?

In general, using nonrandom challenges (either repeating or related) within a zero knowledge protocol does leak the secret.


Can an encrypted message be derived from only keys? I recently started teaching myself cryptography, and had an idea while reading up about basic ciphers. Instead of passing ciphertext between Person A and Person B, which can be broken if intercepted by Person C, what if they passed keys between them for a ciphertext they both possessed with multiple messages encrypted in it? If Person C intercepted multiple keys, could they derive the ciphertext from them?

No, you cannot derive the plaintext from keys if the plaintext nor the ciphertext is ever transmitted. However, to break a cipher you don't need to do that. You only have to show that you can get any kind of information about the plaintext (other than information about the message size, which is hard to avoid if any size message can be present).

Now if you see repeated "keys" then you know that the same message is being targeted, and the scheme would be considered broken. This is why ECB mode is considered broken: you cannot decrypt any message, but you can see repeated blocks.

Now in your case you don't seem to have any cryptographic keys, as keys cannot be shared with everyone - what you seem to be doing by sending them over a unsecured channel. Your lookup scheme doesn't really use cryptography in that sense. They may be database keys, but database keys are a different concept.


blake2b length extension attack approach I understand that a completion flag parameter with Boolean value of 1 is used by Blake2 when it’s compressing the final block of the digested message.

This ensures that one cannot load the state of a blake2 implementation with a blake2 digest and continue on (length extension attack).

However I was just thinking, given that blake2 is open source, couldn't one just create a variant of blake2 that doesn't contain the completion flag, run the original message through it to obtain a non 'completed' digest and then use this as the state to mount a length extension attack through the standard version of blake2?

Which seems so trivial, I'm surprised we consider it length extension proof.

Surely loading the state of SHA-256 is only slightly more hassle than forking blake2, modifying and loading the state.

BLAKE2 is not open-source. BLAKE2 is a specification.

The state is shuffled one last time after having set the final bit, ensuring that a small change, even a single bit, yields a completely different output, that cannot be reverted.

A length extension attack means that knowing M and Hk(M), you may be able to compute Hk(M||E) without knowing the key k.

But with BLAKE2, in order to compute Hk(M) before the finalization, you would need to know the key k. If you somehow know the secret key, you can already forge tags for arbitrary messages.


Public points in SIDH I was going through a presentation titled "SIKE in Hardware" by professor Reza Azarderakhsh. On the page $10$ of the presentation he introduces a variable $w$. Could you please explain what the variable is in layman's terms? I am a master student with a background in software engineering and little to none background in algebra.

Coordinates of points on the curves in SIDH are in a finite field $\mathbf F_{p^2}$.

First, $\mathbf F_p$ are integers mod $p$. Some polynomials on this field does not have roots, and what we can do about it is extend the field so it has a root. The same way $X^2 + 1$ does not have a root in real numbers, so we introduce $i$.

On this case, let's say we have an irreducible (it has no roots) polynomial of degree $2$ in $\mathbf F_p$, so we introduce a root $w$ and that's how we can create $\mathbf F_{p^2}$. Then, any element $z$ in this new field can be written $z = a + bw$ for $a$ and $b$ in $\mathbf F_p$.

Again, think of the complex numbers: anyone of them can be written $a + bi$ for $a$ and $b$ two real numbers.


Clarification needed in TLS 1.2 key derivation process Reference to TLS 1.2 standard documentation section 6.3 regarding the key generation here:

  To generate the key material, compute

  key_block = PRF(SecurityParameters.master_secret,
                  "key expansion",
                  SecurityParameters.server_random +
                  SecurityParameters.client_random);

  until enough output has been generated.  Then, the key_block is
  partitioned as follows:

  client_write_MAC_key[SecurityParameters.mac_key_length]
  server_write_MAC_key[SecurityParameters.mac_key_length]
  client_write_key[SecurityParameters.enc_key_length]
  server_write_key[SecurityParameters.enc_key_length]
  client_write_IV[SecurityParameters.fixed_iv_length]
  server_write_IV[SecurityParameters.fixed_iv_length]

I assigned them the the following variables:

$kc_{mac}$= client_write_MAC_key[SecurityParameters.mac_key_length]
$ks_{mac}$= server_write_MAC_key[SecurityParameters.mac_key_length]
$kc_{data}$= client_write_key[SecurityParameters.enc_key_length]
$ks_{data}$= server_write_key[SecurityParameters.enc_key_length]

In a DHE key-exchange, where the client and server exchanged the keys and both have $\mathit{premaster} = g^{xy}$.

The client and server compute the master secret:

$$ms = \operatorname{hkdf}(\mathit{premaster},\mathit{nonce}_\mathrm{client}+\mathit{nonce}_\mathrm{server})$$

Then both compute the session keys:

$$\mathit{kc}_\mathrm{mac}, \mathit{ks}_\mathrm{mac}, \mathit{kc}_\mathrm{data}, \mathit{ks}_\mathrm{data} = \operatorname{hkdf}(\mathit{ms}, \mathit{nonce}_\mathrm{client} + \mathit{nonce}_\mathrm{server})$$

The $ms$ is used in the Finished MAC computation as follows:
$\operatorname{MAC}(\mathit{ms}, \operatorname{hash}(\mathit{handshake}))$

The Finished messages are encrypted with the $\mathit{kc}_\mathrm{mac}$, e.g. the client Finished MAC:

$$\operatorname{enc}_{\mathit{kc}_\mathrm{mac}}(\operatorname{Finished}(\operatorname{MAC}(\mathit{ms}, \operatorname{hash}(\mathit{handshake})))$$

The data from client to server is encrypted as in:

$$\operatorname{enc}_{\mathit{kc}_\mathrm{data}}(\mathit{data})$$

My questions are:

Is my interpretation for the TLS 1.2 key generation and usage correct?
Are the master key $\mathit{ms}$ and the four session keys: $\mathit{kc}_\mathrm{mac}$, $\mathit{ks}_\mathrm{mac}$, $\mathit{kc}_\mathrm{data}$, $\mathit{ks}_\mathrm{mac}$ computed in in two consecutive steps, that is: after the Client Key Exchange and before the client Change Cipher Spec and Finished messages? or is there any other messages sent/received between them?

There are a few things off in your description.

First, you use the term "hkdf". There is such a thing as HKDF, which is a key derivation function that internally uses HMAC; however, HKDF is not used in TLS. TLS defines its own key derivation function, which it consistently calls "PRF". It is described in section 5 of the standard. That function is also based on HMAC, but with a different structure. The PRF has three input parameters:

the "secret";
the "seed";
the "label".

Exactly what goes into each of these parameters depends on the context. Normally, the "label" is a constant string that qualifies the usage point (e.g. "client finished" when computing the client's Finished message). The "seed" is made of elements from the handshake, that are normally observable, i.e. non secret. The "secret" input is where goes any actually secret data. The PRF will mix all these values together with a fair dosage of HMAC invocations, into a sequence of bytes of arbitrary length.

In TLS, a key exchange mechanism is used, that results in a "pre-master secret". When RSA key exchange is used, the "pre-master" is generated randomly by the client and encrypted with the server's RSA public key. When using Diffie-Hellman key exchange, the "pre-master" is the encoding of the integer that results from DH ($g^{ab} \pmod p$). When using ECDH (Diffie-Hellman over an elliptic curve), the pre-master secret is the $X$ coordinate of the computed DH point ($abG$). Note that there is no question of hashing at this point: the pre-master secret is a sequence of bytes whose length and contents depend on the used key exchange method.

The master secret is computed from the pre-master secret using the PRF. This is described in section 8. The label is "master secret" and the seed is the concatenation of the client random and server random (these two values are 32-byte each, generated randomly for each handshake, and exchanged in the ClientHello and ServerHello messages). The master secret has length 48 bytes, exactly.

From the master secret are derived the keys and IV needed for symmetric encryption. This is the "key block" that you show. Note that the sizes for the various keys in the key block depend on the negotiated cipher suite. For instance, if the cipher suite uses AES/GCM (e.g. TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256), then there is no MAC key (or, equivalently, the MAC key length is 0), since GCM mode ensures both encryption and integrity check with the same key. Key block computation uses the PRF, with this time the master secret as "secret" input; the "seed" is the concatenation of the server and client randoms. Mind the order! This time, the server random comes first.

The Finished messages have contents which are computed with, again, the PRF. The contents of the Finished message are 12 bytes obtained by invoking the PRF with, as "secret" input, the master secret; the "seed" is the hash of all previous handshake messages. The "label" differs depending on who, between the client and the server, sends that specific Finished message. Since the Finished messages are sent after the ChangeCipherSpec, they are encrypted and MACed, using the algorithms and keys which have just been negotiated. In that sense, the keys and nonces (the client and server randoms) are involved multiple times.

Thus, in your description, use of "hkdf" terminology is spurious, as well as the MAC usage, in particular with regards to the Finished messages.

A nice summary of the SSL handshake is this diagram, which is part of the TLS 1.2 standard:

  Client                                               Server

  ClientHello                  -------->
                                                  ServerHello
                                                 Certificate*
                                           ServerKeyExchange*
                                          CertificateRequest*
                               <--------      ServerHelloDone
  Certificate*
  ClientKeyExchange
  CertificateVerify*
  [ChangeCipherSpec]
  Finished                     -------->
                                           [ChangeCipherSpec]
                               <--------             Finished
  Application Data             <------->     Application Data

         Figure 1.  Message flow for a full handshake

Note that after the ClientKeyExchange message from the client, and before the ChangeCipherSpec, there may be a CertificateVerify message (this is sent by the client when the server requests a client certificate, and the client sends one, and this is not full-static DH or ECDH).

The "hash of all previous handshake messages" that is used as an input to the PRF for the computation of the Finished messages really includes all previous messages for this handshake, starting with the ClientHello. Notably, when the server responds with its own Finished message, the hash used in that second Finished message will include the contents of the first Finished message. Also note that the ChangeCipherSpec message is not formally a handshake message (though it may occur only at very specific times within the handshake) so its contents are not used for these hashes.

The complete TLS handshake is quite complicated, mostly for historical reasons. If you want to formalize its use of cryptographic algorithms, you have little choice but to invest a few hours of reading time to get through all the details. I suggest starting with this answer.


In a additive group is it hard to calculate $bg$ given $ag, g, abg$ The ECDH problem defined that given $g,ag,bg$ it is difficult to calculate $abg$. But it is also difficult to calculate $bg$ given $ag,g,abg$. where $g$ is generator and a,b are elements of group.

Yes, it is equally as difficult; if we assign:

$$g' = ag$$
$$a' = a^{-1}$$
$$b' = b$$

Then the restatement of your problem is: given $g' = ag$, $a'g' = g$ and $b'g' = abg$, compute $a'b'g' = bg$, which is exactly the ECDH problem.

Now, this assumes that $a$ has an inverse; this is not a problem if the curve order is a prime, and is easy to work around if the curve order is a prime times a small cofactor.


Is it safe to use pairing-based cryptography in a commercial product? My findings don't show any standardization(NIST, FIPS?) of pairing-based cryptography. Would this mean that it is a bad idea to incorporate pairing-based cryptography(bilinear groups) within a commercial product?

Pairing-based cryptography has been and is currently used in commercial products sold by Voltage Security, which was recently acquired by HP Enterprise. They seem to have sold the products with a fair amount of success, so there is at least some evidence that a product using pairing-based crypto can work. However, there are two pretty major caveats:

Intellectual property restrictions. HPE owns many patents related to pairing-based crypto, and if you use them without paying a licensing fee you could be the target of a lawsuit.
Cryptanalysis. The hardness assumptions underlying pairing-based crypto are still pretty new and haven't received as much cryptanalytic scrutiny as, say, factoring or ECDLP. This means that choosing parameters for the cryptosystem you're planning to deploy is tricky. For example, a parameter regime you think is offering 128 bits of security could be shown to only offer 80, which is not a very comfortable margin. Changing the parameters after you already have paying customers is difficult at best, and choosing large parameters to account for cryptanalytic advances can make your system slow.

The threat of cryptanalytic attacks is not an abstract one - the situation I described above happened recently to the Zcash anonymous cryptocurrency. If you really want to use pairings in a product I would recommend hiring a consultant who knows the area well to choose the parameters.


ElGamal with elliptic curves I've searched some information on ECC, but so far I have only found Diffie-Hellman key-exchange implementations using ECC, but I don't want to exchange keys, I want to encrypt & decrypt data like in ElGamal.
I know that ElGamal with elliptic curves should be possible (Since ElGamal is based on DH), but I have no idea how.
So, could anyone tell me how to implement ElGamal using elliptic curves.
I think I do not need to much background information,

What is the private, what is the public key?
How to encrypt messages? and
How to decrypt messages?

should be enough.

Your answer is in the paper Elliptic curve cryptosystems from Neal Koblitz:

Set up an elliptic curve $E$ over a field $\mathbb{F}_q$ and a point $P$ of order $N$ just the same as for EC-DDH  as system parameters.
You need a public known function $f : m \mapsto P_m$, which maps messages $m$ to points $P_m$ on $E$. It should be invertible, and one way is to use $m$ in the curve's equation as $x$ and calculate the according $y$.
Choose a secret key $x \in_R [1,N-1]$ randomly, publish the point $Y=x P$ as public key.
Encryption: choose random $k\in_R [1,N-1]$ , then calculate $C=kP$ and $C'=kY$ and calculate $P_m = f(m)$. The ciphertext is the tuple $(C, C'+P_m)$.
Decryption: From a ciphertext $(C,D)$ calculate $C' = xC$, and retrieve the point $P_m$ with $P_m = D-C' = (k(xP)+P_m)-(x(kP))$. Then calculate the message $m$ with $f^{-1}(P_m)$.


Verification of Pinocchio (verifiable computation) I am reading the Pinocchio paper. The calculated result $y$ is a part of the verification input, but it seems to me, the verification procedure does not utilize the result $y$. Can anyone can help me to understand this?

$y$ is the values of the output wires, so it is used to compute $g_v^{v_{io}(s)}$, $g_w^{w_{io}(s)}$, and $g_y^{y_{io}(s)}$. (Remember that $c_k$ is the value of the wire with index $k$.)


Is the strength of RSA over quadratic or other cyclotomic fields as strong as over the integers? If we assume the strength of RSA is based on the difficulty of factoring (which I know we can't guarantee) and we compose the modulus of some other quadratic ring that is a unique factorization domain like the Gaussian integers, what is the resistance to attacks based on factoring with classical computing techniques?

As far as I know they are still vulnerable to quantum computing attacks as factoring in most (all?) of these rings is reducible to the hidden subgroup problem for finite Abelian groups, but for classical attacks involving number field sieving, are these rings as difficult to factor as the integers?

For instance, if I composed a key in classical RSA of 2048 bits, is 1024bits of the real part and 1024 bits of the quadratic coefficient equivalent? (1024bits a + 1024bits bi for example for Gaussian integers?)

Are there any tricks to make it easier to factor or do discrete log in these fields, like there are in polynomials?

There are three distinct computational problems related to RSA. They are:

FACTORIZATION: given an RSA modulus $n$, find its prime factors $p$ and $q$;
ORDER: given an RSA modulus $n$, find the order $\lambda$ of the multiplicative group modulo $n$;
RSA Problem: given a ring element $a \in \mathbb{Z}_n$, a public exponent $e$ and an RSA modulus, find an element $b \in \mathbb{Z}_n$ such that $b^e = a \mod n$.

For the integers, the following reductions are known:

Given the factorization of a number $n$, it is easy to find the order: $\lambda = \varphi(n) = \varphi(p) \varphi(q) = (p-1)(q-1)$.
Given the order of the multiplicative group modulo $n$, it is easy to find the inverse exponent (if it exists): $d = e^{-1} \mod \lambda$. Given the inverse exponent, it is easy to solve the RSA problem: $b = a^{d} = b^{ed} = b^1 \mod n$.
Given the order $\lambda$ of the multiplicative group modulo $n$, there exists an efficient way to calculate the prime factors of $n$.
However, no algorithm is known that can turn an RSA problem solver into an algorithm that either finds the order $\lambda$ or factorizes $n$.

We can write these relations concisely as FACTORIZATION $\equiv_p$ ORDER $\geq_p$ RSA Problem.

Note: RSA is secure based on the assumption that the RSA problem is hard. This assumption implies, in turn, that factorization is hard. This assumption is weaker than the assumption that factorization is hard.

You correctly note that it is possible to define an analogue of RSA on other unique factorization domains (UFDs). However, on all the UFDs, factorization is either easy, or equivalent to factorization over the integers.* For example: there is a polynomial-time algorithm for factoring polynomials in one variable (see this survey). Factorization over the Gaussian integers reduces to factorization over the real integers (see this stackexchange answer).

*: I should qualify this statement by saying that not all UFDs are known. Perhaps there does exist a UFD where factorization is harder than it is for the integers. But finding this would be a scientific breakthrough because its applications to cryptography would be great.

Lastly, I should not that quantum computers might not be able to factorize efficiently in just any UFD. Shor's algorithm for factorization first finds the order $\lambda$ of the muliplicative group modulo $n$, and then uses this value to find the prime factors of $n$. The quantum algorithm to find the order will translate to any group. However, the reduction from FACTORIZATION to ORDER might not hold for all UFDs.


What prevents a padding standard to cause a data loss? In here different byte padding standards are listed as ANSI X.923, ISO 101.26, PKCS7, ISO/IEC 7816-4 and zero padding. All of them seems to apply padding to the last byte blocks. Odds are rare but what happens if the actual data is an integer product of the block size and last bytes conflict with a padding scheme.

For example, for PKCS7 let last 8 bytes be

FF FF FF FF FF FF FF 01

01 may actually be original data or padding. How do we know this? How do we avoid a data loss? (It seems trivial but image formats may become corrupted, because original data size changes.)

Padding is always added, even if the plaintext is a product of the block size. This way the algorithm look for the last byte(s) and can safely interpret it as padding data. In case of alignment to the block size, a full block is added just for padding purposes.

So if your example shows 8 bytes of data and you are using a 64-bit block cipher, a block of eight 08 would be added as padding.


What are the advantages of CBC over ECB? From this question I understand that, for a block cipher, using CBC is better than ECB. It seems that if one only has part of the cipher text, then decryption is difficult because the decryption depends on the previous cipher block.

But, what if one does have the whole cipher text? Is CBC then better? It seems, that in this situation one can just first XOR each cipher block with the previous cipher block and then convert the cipher text into what would have been the output using ECB (I assume that the IV is known). Is that correct? If so, what other advantages does CBC have over ECB?

The reason why CBC is considered better than ECB has nothing to do with situations involving an attacker with a partial ciphertext; we always assume that any attacker has full access to the ciphertext.

Instead, the problem with ECB is that it leaks information.  Specifically, if you encrypt two messages which has two blocks of plaintexts in common, then with ECB mode the corresponding ciphertext blocks will be the same.  The attacker can see that, and can immediately deduce the relationship between the plaintext blocks; even if this doesn't give him immediate information about what the plaintext block might be, it tells him something about the plaintext, and that something is more than what we'd like to give him.

This doesn't happen with CBC mode; the previous ciphertext block (or IV) is effectively random (and independent of the plaintext block), and so what is presented to the block cipher is an effectively random string; a collision there is no more likely than it would be if we were encrypting random blocks.

Here is a famous example of this; here is the original image, the image encrypted in ECB mode, and the image encrypted in CBC mode:

As you can see, you can still visually see the image in the ECB mode encryption (it helps that the image is a cartoon, and so there are large areas with the exact same color); you can't see anything in the CBC mode encryption.

Now, if we were encrypting random blocks of data, it turns out ECB mode actually does work out; with random data, you are quite unlikely to run into the exact same block of data twice, and so this 'leaking when two blocks are the same' is not an issue.  However, in the real world, we often encrypt things that are quite nonrandom; we need our cryptosystem to be able to deal with it.


Is there something wrong with using a hash function as a PRG? I need to create cryptographically secure pseudorandomness in JavaScript. However, when I googled for PRGs, all I found was very sketchy.

My idea is as follows (in pseudocode):

seed = "0x1a29fd..." // long number I always get passed (impossible to guess but used in a different context as well)
hashedAndSaltedSeed = sha256sum("seed: " + seed)
purpose = "..." // my current function's name (no spaces)
usageIndex = 1; // will increment this each time

randomness = myPrg(hashedAndSaltedSeed, purpose, usageIndex)

function myPrg(hashedAndSaltedSeed, purpose, usageIndex, numberOfBytes) {
    if(numberOfBytes > 32) {
        fail()
    }

    input = purpose + " " + usageIndex + " " + hashedAndSaltedSeed
    return sha256sum(input).binary2hex().slice(0, 2*numberOfBytes).hex2binary()
}

I only need a small amount of randomness (at most 32 Byte at a time, very few times), so the speed difference won't matter. But is there anything else wrong with this approach?

The randomness I need doesn't need to be distributed perfectly randomly but it needs to be infeasible to guess the resulting randomness when only given purpose and usageIndex but not seed nor hashedAndSaltedSeed.

Edit: I'm sorry that I forgot to mention an important requirement. I'm sure it was in my question at some point as I wrote it but I seem to have deleted that part accidentally. I need to be able to reproduce the same randomness when given the same seed. That's why I can't just use something that gives me randomness but doesn't let me control the seed.

This is fine, although you should avoid these conversions to and from hexadecimal, that are no needed and may introduce side channels.

Now, since you are using JavaScript, you can simply use the WebCrypto API. Specifically crypto.GetRandomValues, which can fill an array up to 65536 bytes.


Random Masking of Padded RSA Ciphertext through homomorphism I had asked a question related to this before:
Oblivious Decryption: Decrypting with a private key, without knowing the message

@rikhavshah has an answer, which I would like to discuss the security of.

Simply put:

Alice has an RSA public key $(e, N)$ and a private key $(d,N)$
There's a ciphertext $x$, padded and encrypted using Alice's public key.
Bob doesn't know what the padded plaintext $m_p$ is, but has the ciphertext $x$.
Bob randomly chooses a mask $r$ from $\{1,\cdots,N-1\}$, calculates $x\,r^e\bmod N$ and sends it to Alice.
Alice decrypts $x\,r^e$ by computing $(x\,r^e)^d\bmod N$, which is also $x^d\,r\bmod N$, and sends it to Bob
Bob multiples the value by $r^{-1}$ (the modular multiplicative inverse of $r$ modulo $N$, which with overwhelming odds is well-defined) to extract $x^d\bmod N = m_p$. And later on removes/decodes the padding to extract $m$.

This way, Alice decrypts $x$, without knowing what $m_p$ is. Bob knows the value of $m_p$ without knowing the value of Alice's private exponent $d$

Is there a known attack, that this scheme is vulnerable to? Can the choice of $r$ make this more or less secure? Or simply, how can we approach this scheme and make it secure?

Note: as @rikhavshah has also mentioned in their answer, this has a potential attack where Bob can get Alice to decrypt anything encrypted with her public key. But this is actually what the scheme requires. So I wouldn't consider this as a vulnerability. And please assume, they are using a signature scheme to verify each-others identity.

In the last bullet of the question, Bob computes $x^d\bmod N=m_p$. This the padded message $m$. Padding must be removed from $m_p$ by Bob to get back $m$. And serious problems can occur if Bob leaks at what step the padding check fails, just like in James Manger's A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0 (in proceedings of Crypto 2001).

If Bob leaks where the padding fails (e.g. by timing), and allows that to occur often enough (some thousands times) for different $x$ chosen by an adversary, then an active adversary can decipher a message, unbeknown to Bob, even though Alice would have refused to decipher the message should the adversary have asked Alice directly (because Alice authenticates who she accepts messages from).

There is no proof that having $(N,e)$ and the capability to raise to the power $d$ modulo $N$ (by querying Alice) does not allow Bob to factorize $N$ and get at $d$ (or an equivalent). That's only widely conjectured.

It should also be emphasized that Bob does not have $d$, but has access to something almost as good: the capability to raise to the power $d$ modulo $N$. And he can share that capability (by forwarding requests to Alice and her answers, or just revealing his credentials w.r.t. Alice).

Also: even with secure padding such as OAEP verified by Bob without leaking anything other than success/failure, Bob should still be careful that messages deciphered with the help of Alice that pass the padding check are in no way authenticated. For example, if a (genuine) message $x$ has deciphered to "the winner is Carol", and Bob later gets a message $x'$ that decipher to "repeat: winner is Malory", Bob should not leak that he is surprised, for that would reveal that the winner is not Malory to whoever (e.g. Malory) generated the bogus $x'$.

Aside of these, and standard implementation attacks on Alice and Bob (e.g. side-channel leakage), I see no other attack specific to the protocol.

Per comment: I do not see that the protocol is sensitive to minor imperfection in the generator for $r$, including w.r.t. Alice trying to get at $m$.


How do I multiply a Twisted Edwards point in Montgomery space? EdDSA (and ed25519) signatures require a scalar multiplication.  Currently, I do this directly in Twisted Edwards space.  (The code can be found in my crypto library.)  My research and my tests suggest it would be quite a bit faster to do that multiplication in Montgomery space instead.  This would mean 4 steps:

Convert the Twisted Edwards point to Montgomery space.
Perform the Montgomery ladder.
Recover the Y coordinate.
Convert back to Twisted Edwards space.

Steps 1, 2, and 4 seem pretty simple (even straightforward).  Step 3 is more complex, but is documented in this paper, which I have followed.  Here is my attempt, which unfortunately gives the wrong result:

typedef i32 fe[10]
typedef struct { fe X; fe Y; fe Z; fe T; } ge;

sv ge_scalarmult(ge *p, const ge *q, const u8 scalar[32])
{
    // convert q to montgomery format
    fe x1, y1, z1, x2, z2, x3, z3, t1, t2, t3, t4;
    fe_sub(z1, q->Z, q->Y);  fe_mul(z1, z1, q->X);  fe_invert(z1, z1);
    fe_add(t1, q->Z, q->Y);
    fe_mul(x1, q->X, t1  );  fe_mul(x1, x1, z1);
    fe_mul(y1, q->Z, t1  );  fe_mul(y1, y1, z1);
    fe_1(z1); // coherence

    // montgomery scalarmult
    // The same ladder is used for x25519,
    // it comes from the ref10 implementation.
    // Field elements are modified in-place
    x25519_ladder(x1, x2, z2, x3, z3, scalar);

    // recover the y1 coordinate
    fe_mul(t1, x1, z2);  // t1 = x1 * z2
    fe_add(t2, x2, t1);  // t2 = x2 + t1
    fe_sub(t3, x2, t1);  // t3 = x2 − t1
    fe_sq (t3, t3);      // t3 = t3^2
    fe_mul(t3, t3, x3);  // t3 = t3 * x3
    fe_mul973324(t1, z2);// t1 = 2a * z2
    fe_add(t2, t2, t1);  // t2 = t2 + t1
    fe_mul(t4, x1, x2);  // t4 = x1 * x2
    fe_add(t4, t4, z2);  // t4 = t4 + z2
    fe_mul(t2, t2, t4);  // t2 = t2 * t4
    fe_mul(t1, t1, z2);  // t1 = t1 * z2
    fe_sub(t2, t2, t1);  // t2 = t2 − t1
    fe_mul(t2, t2, z3);  // t2 = t2 * z3
    fe_add(t1, y1, y1);  // t1 = y1 + y1
    fe_mul(t1, t1, z2);  // t1 = t1 * z2
    fe_mul(t1, t1, z3);  // t1 = t1 * z3
    fe_mul(x1, t1, x2);  // x1 = t1 * x2
    fe_sub(y1, t2, t3);  // y1 = t2 − t3
    fe_mul(z1, t1, z2);  // z1 = t1 * z2

    // convert back to twisted edwards
    fe_sub(t1  , x1, z1);
    fe_add(t2  , x1, z1);
    fe_mul(p->X, x1, t2);
    fe_mul(p->Y, y1, t1);
    fe_mul(p->Z, y1, t2);
    fe_mul(p->T, x1, t1);
}

Can someone tell me what I did wrong?

I finally got the answer from Hacker News.  My mistake came from the conversion code.  I used a formula from Wikipedia, which is slightly different from the correct one. Simply put, I missed a multiplication by a constant (specifically, the square root of -486664,  or 6853475219497561581579357271197624642482790079785650197046958215289687604742 —the other square root also works.)

The correct code for converting to Montgomery format is this (note the inversion, needed to ensure that z1 == 1, which allows a faster Montgomery ladder):

// sqrt(-486664), in 26/25 bit limbs.
fe K = { 54885894, 25242303, 55597453,  9067496, 51808079,
         33312638, 25456129, 14121551, 54921728,  3972023 };

// Actual conversion
fe x1, y1, z1, x2, z2, x3, z3, t1, t2, t3, t4;
fe_sub(z1, q->Z, q->Y);  fe_mul(z1, z1, q->X);  fe_invert(z1, z1);
fe_add(t1, q->Z, q->Y);
fe_mul(x1, q->X, t1  );  fe_mul(x1, x1, z1);
fe_mul(y1, q->Z, t1  );  fe_mul(y1, y1, z1);
fe_mul(y1, K, y1);  // missing multiplication
fe_1(z1);

(Even though we use projective coordinates, the Montgomery ladder is faster when it can assume z1 is equal to one.  This compensates the cost of the inversion.)

The correct code for converting back to Twisted Edwards format is this:

fe_sub(t1  , x1, z1);
fe_add(t2  , x1, z1);
fe_mul(x1  , K , x1);  // missing multiplication
fe_mul(p->X, x1, t2);
fe_mul(p->Y, y1, t1);
fe_mul(p->Z, y1, t2);
fe_mul(p->T, x1, t1);


Zero Knowledge and Computational Indistinguishability Having some trouble understanding the following line:
“Alice conveys zero knowledge to Bob if Bob can sample
from a distribution of messages that is computationally indistinguishable
from the distribution of messages that Alice would
send.”

From Page 122, https://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf

Could someone give a practical example of this sentence?

Suppose in some protocol Alice is supposed to send an encryption of her special secret $s$ under a public key $pk$. She is sampling from the distribution of encryptions of $s$.

Bob can choose a random plaintext $r$ and encrypt it under $pk$. He is sampling from the distribution of encryptions of random plaintexts.

Even though Bob doesn't know Alice's special secret $s$, these two distributions are computationally indistinguishable (that's the basic definition of security for the encryption scheme). So this message (Alice's encryption of $s$) is zero-knowledge.

In a real example, you would have to simulate the entire exchange of all messages (called the transcript). It doesn't really work to simulate just one at a time, you have to capture correlations along messages if there are many rounds in the protocol.

Imagine Alice wants to prove to Bob that she is a good archer. The protocol to convince him is for Bob to paint a target on the wall, then Alice will fire an arrow into the bullseye. The "transcript" (the information that Bob leaves with) is a target painted on a wall with an arrow in the bullseye.

But Bob can generate the same distribution of transcripts without Alice's help! He can just put an arrow into the wall first and then paint a target around it. Hence, the protocol is "zero-knowledge."


What is the recommended minimum key length for ECDSA signature I want to identify the proportion of certificates that use unrecommend ECDSA key length for TLS certificates based on some data I collected.

By looking at a standard like NIST for example, I find this in this website:

My data shows use of ecdsa-with-SHA256.

My question is: Which if the following key algorithms the ECDSA is based on? Since ECDSA stands for (Elliptic Curve Digital Signature Algorithm) my understanding is that it is based on Elliptic Curve. So since we are in 2018/2019, I assume the recommended length is 224 bits?

You are already well on your way if you've found keylength.com. It references the documents that the recommendations are based on, so if you need a more clear reason to go for a specific key size then you could simply dig deeper. Yes, you need to look at Elliptic Curve sizes for ECDSA.

Using different key sizes for different purposes is spot on. Kelalaka pointed to an interesting document NIST Special Publication 800-57 Part 3
Revision 1: Recommendation for Key Management
Part 3: Application-Specific Key Management Guidance.

For application for non-repudiation I would go for P-384 or P-521 though, not P-256 or P-384 as indicated in that document. These are signatures that should be made to last. I also think the recommendation to choose an RSA 2048 bit key - a key that has significantly less security than the EC P-256 counterpart in that document - is dangerous practice.

Maybe after 2030 we should worry about quantum computers. You'd better store it at a notary or another third party who can additionally sign the document with post-quantum crypto once (and if) that starts to become a requirement.

For real time authentication - the other major use case of ECDSA - you could go for P-256 or a similarly sized curve. However, if your systems can handle it, you might as well use a larger key size - if just to give you some leeway.

Beware: in the end the protocol and implementation security are endlessly more likely to be an issue than key size. Too often the key size debate is only important to the sales department and management - mainly because it is really the only thing they kind-of understand.


Exchanging keys via third party In many symmetric key ciphers sender and receiver have to exchange a single key. They may also do it through 3rd party who distributes it to both of them. since 3rd party can read all messages exchanged between them It can have disastrous impact on them in terms of capital, forgery etc. so In this case how is the privacy between the two ensured ?

Yes, if you are using 3rd party key exchange, the 3rd party can read the messages. If that is not the security feature you want, use something else. There are many legitimate scenarios where users are fine with trusting the third party, however. For example, a system setup by my employer to allow encrypted chat between myself and our clients. My employer has legitimate reasons to want to be able to access those messages if necessary and so would want to set it up with (possibly) third party key exchange. I, as an employee, might be fine with that as I would be conducting official company business using the system.

Older protocols might have done this before public-key crypto was invented in order to keep key management reasonable.


How exactly are public and private keys used to encrypt and the decrypt data? In asymmetric encryption schemes, a public key is used by an outside source to encrypt data to be sent to the holder of the private key.

It's my understanding that public keys are generated from the private key using a one-way, or trapdoor function, rendering it computationally infeasible to reverse-engineer the private key from the public key or its encrypted message.

My question is not why private keys can't be reverse-engineered, or how public/private keys are generated.

My question is exactly HOW the public key is used to encrypt the data, and the process by which the private key can decrypt it. Can anyone give an example of a very simple public and private key, and how exactly they're used to encrypt, and then decrypt some data?

For the sake of simplicity and ease of understanding, perhaps an example could utilize multiplication as the one-way function to frame the keys, and a small string of ones and zeroes could be used as the data to be encrypted and then decrypted.

Here is a numerical example with RSA.
(Edit and warning: as fgrieu notes in the comment, these values are strictly for illustrating the math involved; all of the parameters are unsuitable for actual use. See the answers here for discussion about how to properly choose the primes $p$ and $q$, and here about secure RSA key sizes.)
Quoting the relevant parts:

The first step of RSA encryption is to generate two primes, $p$ and $q$.
$$p = 257$$
$$q = 337$$
The product of $p$ and $q$ is $n$, in our case:
$$n = 257\cdot 337 = 86609$$
The euler totient, $\phi(n)$ is calculated below:
$$\phi(n) = (p-1)(q-1) = 256\cdot 336 = 86016$$
Now we have to chose an exponent, $e$ that is relatively prime to $\phi(n) = (p-1)(q-1)$. The pair $(e, n)$ is our public key that is used to encrypt messages.
$$e = 17$$
$17$ is relatively prime to $86016$ because they share no factors. We know this because $17$ itself is a prime number, so its only factors are $1$ and $17$. $9113$ is not divisible by $17$, so the numbers are relatively prime.
Our next step is to calculate a value for $d$. If you recall from the RSA algorithm, $d$ must be chosen so that it is the inverse of $e$, modulo $n$. So for our example, we must find a number such that:
$$e\cdot d \equiv 1 \mod \phi(n)$$
$$17 \cdot d \equiv 1 \mod 86016$$
To solve for d we use the Extended Euclidean Algorithm which can be used to find multiplicative inverses.
Using the Extended Euclidean Algorithm, we can calculate one possible value for $d$ is $65777$. We can check the algorithm by computing  $e*d \mod \phi(n)$ and ensuring it equals $1$.
$$e\cdot d \mod \phi(n) = 17\cdot 65777 \mod 86016 = 1118209 \mod 86016 = 1$$
$d$ is our private key and is used to decrypt our messages. Now that we have both a public key and a private key, we can encrypt and decrypt messages.
$$\hbox{Pub } = (e,n) = (17, 86609)$$
$$\hbox{Priv } = (d,n) = (65777, 86609)$$
To encrypt a message m, we first convert it into a large integer. Then we calculate m^e \mod n. The result is the encrypted message, or ciphertext, $c$. Let’s send the text “Hi”. In order to do this, we must convert the message into an integer. We’ll use the integer $18537$ to represent our text.
$$c = m^e \mod n$$
$$c = 18537^{17} \mod 86609 $$
$$c = 12448$$
Now, can we decrypt $12448$ back into the original message, $18537$? To decrypt a message we use the private key, $(65777, 88609)$
$$m = c^d \mod n$$
$$m = 12448^{65777} \mod 86609$$
Here we use the Chinese Remainder theorem, an easy way to solve $a^b \mod n$
$$m = 18537 \mod 86609$$
Indeed, when we perform decryption on our ciphertext, we are left with the original message.

One more thing:

It's my understanding that public keys are generated from the private key using a one-way, or trapdoor function

Not always. In Diffie-Hellman key exchange, you start with a private value $x$ and generate $g^x \mod p$ as a public key, given suitable $g$ and $p$ (and are known to the public). However, for RSA, you pick secret primes $p$ and $q$ and from that generate the public key $(N=pq, e)$, such that $\gcd(e, (p-1)(q-1)) = 1$. And from that you can derive the decryption exponent (private key) $d$, such that $ed \equiv 1 \bmod (p-1)(q-1)$.


Is phi-hiding assumption as hard as integer factorization? Phi-hiding assumption can be simply stated as (wrt hardness)

It is difficult to find small factors of $\varphi(m)$ where $m$ is a number whose factorization is unknown and $\varphi$ is Euler's totient function.

Is the hardness due to this assumption comparatively higher than than the hardness of integer factorization?
My intuition says that finding prime factors of $\varphi(m)$ is simpler than finding the prime factors of $m$. So I believe that the hardness of the phi-hiding assumption is at most equal to the hardness of integer factorization.

Firstly, the phi-hiding assumption [CMS,KK] states that it is computationally-hard to distinguish the cases $(e,\phi(N))=1$ (where $(\cdot,\cdot)$ denotes the GCD) and $e|\phi(N)$ for a given RSA modulus $N$ and "small" prime $e>2$ ($e\ll N^{1/4}$, to be precise). In the former case, the exponentiation map $x\mapsto x^e\bmod{N}$ is injective (i.e., the RSA permutation), whereas in the latter case the map is lossy. Therefore, one could rephrase the assumption as assuming that the lossy and injective modes of the exponentiation map are computationally-indistinguishable [KK]. Note that this is stronger than simply assuming it to be hard to find small factors of $\phi(N)$ (the same way DDH is a stronger assumption than CDH is).$^*$
The assumption is clearly at least as strong as the factoring assumption as given an efficient algorithm that factors $N$, it is easy to compute $\varphi(N)$ and therefore decide whether a given prime $e$ divides $\varphi(N)$. Moreover, it is claimed in [KK] to be at least as strong as the RSA assumption. I couldn't find a proof of this anywhere, but the following reduction seems to work: given $(N,e)$ where either $(e,\phi(N))=1$ or $(e,\phi(N))=1$ and access to an oracle $A$ that computes $e$-th roots:

Sample $x_1,\cdots,x_n$ uniformly at random from $\mathbb{Z}_N^*$
Send $x_1^e\bmod{N},\cdots,x_n^e\bmod{N}$ to the oracle $A$ to obtain $x_1',\cdots,x_n'$
Return "$(e,\varphi(N)=1)$" if $x_i=x_i'$ for all $i\in[1,n]$

Showing the converse statement -- i.e., that the factoring assumption is at least as strong as the phi-hiding assumption -- is, as far as I know, an open problem.$^{**}$ This would require factoring $N$ (or find $e$-th root for that matter) given access to an oracle that on input $(N,e)$ decides whether $(e,\phi(N))=1$. Settling this problem would require first settling the equivalence between RSA problem and factoring (which is an easier question).
Finally, it is worth pointing out that for "large" value of $e$s ($e\geq N^{1/4}$, to be precise), the phi-hiding assumption does not hold as given such an $e|\phi(N)$ it is possible to factor $N$ using Coppersmith's attacks. You can read more about this in [CMS,KK]. Some moduli where the assumption does not hold are. discussed in [SF]
$^*$The definition in this Wikipedia article is also wrong: computing $\varphi(N)$ given $N$ is known to be equivalent to factoring $N$.
$^{**}$ Although it is believed that the equivalence holds: see discussion in [KK,§1.1].
[CMS]: Cachin, Micali and Stadler, Computationally Private Information Retrieval with Polylogarithmic Communication, Eurocrypt'99
[KK]: Kakvi and Kiltz, Optimal Security Proofs for Full Domain Hash, Revisited, JoC'18
[SF]: Schridde and Freisleben, On the Validity of the Phi-Hiding Assumption in Cryptographic Protocols, Asiacrypt'08


How do AES and DES ensure data integrity? I have been trying to study for cryptographic symmetric algorithms (AES,DES) and came up with a question whether these two on their own ensure integrity (i.e data has not been altered). Do these two need message digests in order to ensure it?

I have also seen this paper, but it does not show 'how' these two algorithms ensure integrity.

Answer to your question title: they don't.

Answer to your inline question: yes (or something similar to it).

Longer answer:

Both DES and AES are examples of block ciphers, and block ciphers do not have any inherent integrity protection. Thus, in order to also ensure integrity you would need to add something more, for example a message authentication code (MAC) or a digital signature.

However, note that you would probably never want to combine DES and AES directly with, say, a MAC. Instead, you would want to use DES and AES in a dedicated mode-of-operation that provides both confidentiality and integrity for you (which together is called authenticated encryption).


Why is RSA easily cracked if N is prime? This question was part of an assignment.
Here's my reasonning:

If N is prime and N=p*q, then p=1 and q=N (or the opposite).
e * d ≡ 1 mod ((p-1) * (q-1)), but ((p-1) * (q-1))=0 here.
e * d ≡ 1 mod 0, so e=d.
We now have the private key.

Is this correct?

Is this correct?

Sadly no.

First here's a simple counter-example: $n=11,e=3\Rightarrow d=7\neq 3$, also note that $(5^3)^3\equiv 9\not\equiv 5\pmod {11}$ and $(5^3)^7\equiv 5\pmod {11}$.

Concretely the mistake in the calculations is finding the order for exponent (e.g. the totient function of the modulus), which the calculations hard-code to $\varphi(pq)=(p-1)(q-1)$ which is only true for $p,q\in\mathbb P$.
The fix is to use the proper formula which obviously is $\varphi(1\cdot q)=q-1$. Now you can proceed normally in calculating $d$ as solution to $e\cdot d\equiv 1\pmod{q-1}$.


Digital Signature Attack In a typical digital signature scheme in which in order to sign we compute:

hash of the message: $h(m)$
resulting hash signed with the private key $[h(m)](private key)$

If there were a collision on the hash, what an adversary could do?

Solution (?)

An adversary can find a different message $m_2$ with the same hash of $m_1$.
The user (good guy) signs $m_1$. The adversary can claim that $m_2$ has been signed by the user because $m_1$ and $m_2$ have the same signature.

Is this the correct answer? How can the adversary claim that? I mean… the hash of the message is signed with the user's private key. The adversay does not know that key.

If the adversary gets a signature on $m_1$, then it's true that the adversary could claim the signature is a signature on both $m_1$ and $m_2$, if $h(m_1) = h(m_2)$ (i.e., there is a collision). The adversary does not need the private key to make this claim, anyone holding the public key should be able to verify the signature.

The reason the adversary can successfully make this claim is that the signature does not actually sign the message, it signs the hash. So since $h(m_1) = h(m_2)$ the resulting signature is in fact both a signature of $m_1$ and $m_2$.

The reason why this is not usually a problem is that the hash function $h$ will be chosen as a cryptographic secure hash function meaning that it should be (practically) impossible for the adversary to find such a collision.


Proof by reduction definition in "Serious Cryptography": Cipher reduced to hardness problem or other way around? In Serious Cryptography by Jean-Philippe Aumasson on p. 46, paragraph "Provable Security", it says:

  Provable security is about proving that breaking your crypto scheme is at least as hard as solving another problem known to be hard. [...] This type of proof is called a reduction [...]. We say that breaking some cipher is reducible to problem $X$ if any method to solve problem $X$ also yields a method to break the cipher.

I am wondering if this is the right direction. Assume we reduce the problem of breaking a cipher $P$ to some problem $X$, $P \leq_m^p X $, as suggested by the book (if I understand correctly). Then if we have a polynomial-time algorithm for $X$, we also have a polynomial algorithm for $P$. But this does not guarantee that if no polynomial algorithm for $X$ exists, there should be no polynomial-time algorithm for breaking $P$. In fact, there could still be a polynomial-time algorithm breaking $P$ in some way unrelated to problem $X$.

So shouldn't the reduction be the other way around $X \leq_m^p P$. That is, if we can break $P$ in polynomial time, we can also solve $X$ in polynomial time? This way, if $X$ is hard (not polynomial-time solvable), then by contraposition $P$ must also be hard, thus $P$ is at least as hard as X?

What am I missing here?

The definitions come from Turing Reduction of Wikipedia

  In computability theory, a Turing reduction (also known as a Cook reduction) from a problem A to a problem B, is a reduction which solves A, assuming the solution to B is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve A if it had available to it a subroutine for solving B. More formally, a Turing reduction is a function computable by an oracle machine with an oracle for B. Turing reductions can be applied to both decision problems and function problems.

which can be simplified as $A$ is reduced to $B$;

If $A \leq B$ then, if you were given a subroutine for $B$ you could solve $A$.
This can be also mean that $A$ is no harder than $B$.

  I am wondering if this is the right direction. Assume we reduce the problem of breaking a cipher $P$ to some problem $X$, $P \leq_m^p X $, as suggested by the book (if I understand correctly). Then if we have a polynomial-time algorithm for $X$, we also have a polynomial algorithm for $P$. But this does not guarantee that if no polynomial algorithm for $X$ exists, there should be no polynomial-time algorithm for breaking $P$. In fact, there could still be a polynomial-time algorithm breaking $P$ in some way unrelated to problem $X$.

So we have $P \leq X$, which means we use $X$ as a subroutine and $P$ is not harder than $X$.

Yes, the reduction doesn't say about a polynomial-time algorithm exists or not. If one can prove that there is no polynomial-time algorithm for $X$ than this doesn't mean that there is no for $P$. Because the reduction is just a useful upper bound.

If there is a polynomial-time algorithm for $P$ this can be used to solve $X$ if one can show that $X \leq P$. Otherwise, as stated in the second bullet, the reduction provides only the upper bound.

  So shouldn't the reduction be the other way around $X \leq_m^p P$. That is, if we can break $P$ in polynomial time, we can also solve $X$ in polynomial time?

Not exactly, the reduction gives the upper bound. To use a polynomial-time algorithm for $P$ to solve $X$ one needs to show that $X \leq P$.

  This way, if $X$ is hard (not polynomial-time solvable), then by contraposition $P$ must also be hard, thus $P$ is at least as hard as X?
  What am I missing here?

Assuming that one showed a reduction of $X \leq P$, then the information we have $X$ is no harder than $P$ with $P$ is solvable in polynomial-time. If you show that $X$ is hard ( assuming NP-hard here) then one must look at either the reduction or the hardness of solving $P$ again.


In Pedersen Key Distribution, can the public key be persistent? I am implementing a key distribution protocol described by Torben Pedersen in A Threshold Cryptosystem without a Trusted Party (EUROCRYPT'91). In the protocol, the $n$ parties distribute a public key for the ElGamal cryptosystem, where each party ends up with "part of" the private key and can work together to decrypt a message.

In the paper, Pedersen states that the parties all agree on the two primes $p$ and $q$, and the generator $g$ of $\mathbb{G}_{q}$. $h$ is then computed based on the individiual's choice of the private key $x_{i}$ (so that $h_{i} = g^{x_{i}}$ and $h = \prod_{i}^{n} h_{i}$).

If $p$ is sufficiently large, can the public parameters $p$, $q$, and $g$ be reused? It seems to me that if in each round of encryption, each party selects a new $x_{i}$, thus resulting in a new $h$, that the values of $p$, $q$, and $g$ can be persistent.

I ask this because finding a random safe prime of 1024 bits can be slow, and finding a generator of $\mathbb{G}_{q}$ can take a very long time. If these could be agreed upon well in advance and then reused, it makes the protocol more practical.

If $(p, q, g)$ can be reused, is this true for ElGamal in general?

This question probably goes much deeper than what you actually aimed for. Simply speaking: If you use $(p,g,h)$ just a couple of times, where $x$ is not revealed in any way, then yes you can reuse it. If you reuse it very often you might run into trouble. However in a general ElGamal-like encryption system, you can use a single public key as often as you want.

The tricky part in the security proof is, when you have to deal with security under "selective openings", where you consider a larger number of private/public keys, and grant the attacker the ability to open some of them and want to know if the remaining ones are still secure. A paper about this is e.g. "Encryption Schemes Secure under Selective Opening Attack" (Bellare, Yilek, 2009) or "Possibility and impossibility results for encryption and commitment secure under selective opening" (Bellare, Hofheinz, Yilek, 2009)


When adding two points on an elliptic curve, why flip over the x-axis? Every introduction to elliptic curves that I've read hasn't explained this.

If you have two points P and Q on an elliptic curve, to find P+Q, you draw a straight line through the points, find the third point of intersection with the elliptic curve. To get P+Q, reflect across the x-axis. Why reflect across the x-axis?

For example, towards the bottom of this blog post they explain how to add two points on the curve, but not why you want to reflect across the x-axis.

Please ELI(someone who has taken a university crypto class that didn't cover ECC).

If we did not make the final reflection, point multiplication would not be associative, we would not have a group, and we thus could not define a scalar multiplication the way we do, with the property $n\cdot A+m\cdot A=(n+m)\cdot A$ .

If operation $+$ is a group law, the operation $\boxplus$ defined on that group by $A\boxplus B=-(A+B)$ (which is what removing the reflection does) is generally not associative, because $$(A\boxplus B)\boxplus C=-(-(A+B)+C)=A+B-C,$$ while $$A\boxplus(B\boxplus C)=-(A-(B+C))=-A+B+C.$$ The only groups where $\boxplus$ is associative are those with 1 or 2 elements.

Associativity of point addition on an elliptic curve in fact is a non-trivial and fragile property. Messing with how we do point addition in almost any way (changing sign as proposed, using a curve with a different equation like an astroid..) breaks that property.

Comments by entrop-x and Rosie F provide an intuitive explanation: if three points $A$, $B$, $C$ on the curve are such that "point addition of $A$ and $B$ without final reflection yields $C=A\boxplus B$", then that statement holds for all 6 permutations of $A$, $B$ and $C$, and it can be reworded as "$A$, $B$ and $C$ are collinear" without consideration of the order of the points. In a group with law $+$, the simplest relation between 3 variables with that invariance under order is: $A+B+C=0$, and then we have $A+B=-C=-(A\boxplus B)$ (where the $-$ sign designates taking the opposite for law $+$ ), hence the final reflection to change $\boxplus$ into a group law $+$.

That intuitive explanation can be extended to justify that full point multiplication is associative!