Memory hardness of key derivation function through XOR-ring multiple matrix values For theoretical purposes in order to enhance my own understanding, and NOT in order to create my own cryptography, I am asking a question about the memory-hardness of a key derivation function achieved by a more intense shuffling of the matrix.

If I were to create a matrix with N elements with pseudorandom values:

for i=1 to N
    matrix[i] = HASH (some input)

and then hash over all elements of the matrix:

for i=0 to N
    result = HMAC (SHA512, result XOR matrix[i], matrix[N-i])

It was pointed out to me here that this was not especially memory-hard, since an attacker can trade twice the computation for half the memory use. This is done by only storing the second half of M. Then for the first N/2 iterations of the loop, one only calculates the i'th element from the i-1'th, then recalculate the first half of M instead and continue as earlier.

Greater memory-hardness would therefore seem to be achievable through a more intensive XOR-ring of matrix values in the second loop.

One could e.g. generate a matrix of a size N * x, which is then hashed N times, but each hash made up of XOR-ring multiple different matrix values. The example below (PHP code) shows it for x=4 (^ is the PHP XOR operator):

for i=1 to N*4
    matrix[i] = HASH (some input)

for i=1 to N
    result = HMAC (SHA512, result +
            (matrix[$i] ^ matrix[(N*2-$i)] ^ matrix[N*2+i] ^ matrix[N*4-i]),
            (matrix[N-i)] ^ matrix[N+i)] ^ matrix[N*3-i] ^ matrix[N*3+i)]))

For 8 rounds, a matrix size 8*4 = 32 would be created, and then hashed with XOR combinations in the loop shown. The output below shows, which matrix index values (the i in matrix[i]) would be combined in each HMAC round:

Computing 1 ^ 15 ^ 17 ^ 31 AND 7 ^ 9 ^ 23 ^ 25
Computing 2 ^ 14 ^ 18 ^ 30 AND 6 ^ 10 ^ 22 ^ 26
Computing 3 ^ 13 ^ 19 ^ 29 AND 5 ^ 11 ^ 21 ^ 27
Computing 4 ^ 12 ^ 20 ^ 28 AND 4 ^ 12 ^ 20 ^ 28
Computing 5 ^ 11 ^ 21 ^ 27 AND 3 ^ 13 ^ 19 ^ 29
Computing 6 ^ 10 ^ 22 ^ 26 AND 2 ^ 14 ^ 18 ^ 30
Computing 7 ^ 9 ^ 23 ^ 25 AND 1 ^ 15 ^ 17 ^ 31
Computing 8 ^ 8 ^ 24 ^ 24 AND 0 ^ 16 ^ 16 ^ 32

One concern there is the question of whether that many XOR operations would create a lot of collisions and thus compromise security, even though each result is HMAC hashed. The lines "computing 4/8" show same matrix values being XOR-ed, although one could remove these lines (only two in total) from the second loop or alternate the respective values. It would be interesting to get people's comments on that, with the reasons behind it.

Collisions are not much of a concern, since you have to compute them to know they happen, and assuming your values are a typical hash size (256+ bits) they will never happen randomly anyway. But yes, having identical computation that use the same data is wasteful if you don't store the intermediate values.

However, the main problem your function has is that the XORs can be computed ahead of time for multiple iterations of the second loop. For example, here:

Computing 1 ^ 15 ^ 17 ^ 31 AND 7 ^ 9 ^ 23 ^ 25
Computing 2 ^ 14 ^ 18 ^ 30 AND 6 ^ 10 ^ 22 ^ 26

The attacker can compute both of these by going through the matrix once and only maintain four values where they XOR the appropriate elements of the matrix. In fact, they can choose exactly the amount of memory they do have and calculate that many iterations' worth of XORs in one go. (Concatenation would be better than XOR since it would take more space. But it would still be less than the whole matrix, so trade-offs would be possible.)

The way scrypt and other memory hard hashes accomplish their memory-hardness is by having a large state that they update instead of just reading. Your two loops where one generates and one "collects" the data will always let the attacker store only parts of the matrix and recalculate as needed. If the second loop took many passes over the data while also changing the matrix, it would no longer be as easy since calculating any dropped values again would take longer and longer the further along the algorithm is.


Is AES-Keywrap (NIST SP 800-38F) quantum-safe? Having looked at the paper "Breaking Symmetric Cryptosystems using Quantum Period Finding", I'm unsure as to whether the AES-Keywrap as defined by NIST SP 800-38F is safe against the described attack or not.

I also came up empty handed on google.

Does anyone have any information on this?

The Kuwakado-Morii attack (the attack of Kaplan et al. is a nice adaptation of this) relies crucially on Simon's algorithm, which essentially says that on the group $(\mathbb{Z}/2)^n$, the hidden shift problem is easy.  That is, from quantum access to $H(\cdot)$ and $H(\cdot\oplus s)$, it is possible to recover $s$ efficiently.

On the other hand, the Key-wrap algorithm of NIST SP 800-38F does not use group structure.  Well, at least not much: while some constants are XORed during the execution of the algorithm, no adversarially-controllable data are ever XORed during the computation: the whole process is mostly built using shuffling and blockcipher evaluation.

Of course, we cannot really know whether it would be secure until we prove the security, but some constructions not relying on group structures (not even XOR) are known to be quantum-secure: for example, Zhandry proved that the GGM construction is a secure PRF, and, it happens that GGM uses only function composition, not group structure.

At the least, I think this suggests that Kuwakado-Morii is not really applicable here.


Key derivation with implicit certificates The big advantage of implicit certificate is their small size and fast processing. This article presents a way how to compute implicit certificates.

In the end Alice is able to derive both her public and private key ($\alpha$, $Q_A$).

Does this mean that the usage of implicit certificates implies the generation of a new key pair each time such a certificate is issued? Traditional explicit certificates (e.g. X.509) can be issued unlimited often for the same public key.
How do you prevent somebody else to derive Alice's private key? I don't see any secret information that is only possessed by Alice. Initially, I thought this was $\alpha$, but apparently this random integer is send in plain text to the CA. Even if it was encrypted, the CA would know $\alpha$ and consequently Alice's private key.

Yes, the certificate $cert$ and the private key are linked. For $cert' \ne cert$, the private key will be different (except for a negligible collision probability).
Alice's secret $\alpha$ is known by herself only (only $\alpha G$ is sent in the first step of the protocol). This prevents a third party from deriving her private key.


Using negative values / unsigned integers to implement SHA-2 What happens if we allow implementation of SHA-2 using negative values?

What happens if a negative value was used in the first round? Would the algorithm still result in a secure value?

I have a basic understanding of how the maths work. However, before I go writing my own function - could somebody indicate if they have any experience using negative values?

The 32-bit values in SHA-256 are unsigned integers, which means the only values they are allowed to have are between 0 and 4,294,967,295, there are no negative values allowed.

If you look at the 4th initial value (0xa54ff53a), that has an integer value of 2,773,480,762. Implementing SHA-256 in programming languages that do not have the a 32-bit unsigned integer, but rather a signed integer, results in that value being interpreted as -1,521,486,534, but the bits of the value are still the same.

For modular addition that is not an issue, (see two's complement), but can be an issue for the shifting and rotations, which need to be performed across all 32-bits, and not just the lower 31. XOR also does not care if the numbers are signed are not, and since SHA-2 only uses addition, XOR, and shifting (and thus rotation), implementing SHA-256 in a programming language that only supports unsigned integers is possible, just maybe a little slower if you have to deal with rotation through shifting of a signed integer, like in Visual Basic 6.


Why the symmetric key layer in PGP? I've been familiarizing myself with the basics of PGP. If I understand correctly, PGP symmetrically encrypts the data of interest using a random single-use key, then encrypts the encrypted data and its symmetric key using the public key of the intended recipient.

What benefit does the inner layer of symmetric key encryption provide? I am having trouble understanding how this layer adds security over simply encrypting the data with the recipient's public key straight away.

I think you misunderstood a detail of PGP encryption. Only the random symmetric key is encrypted under the recipient's (asymmetric) public key. This way to encrypt stuff is quite common and is called KEM/DEM paradigm: Key Encapsulation Method/Data Encapsulation Method oy Hybrid Encryption. Some refs: en.wikipedia.org/wiki/Hybrid_cryptosystem and en.kryptotel.net/encryption.html.


RSA cipher wrong use Why is it foolish if you decide to use an RSA cipher to encode some message by first converting each letter of the message to an integer? So for exmaple Space=0, a=1, b=2,...

After the conversion I encrypt the integer $k$ as $k^e \mod N$.

I do not see why is there any difference?

As a first note: No one would use RSA encryption to directly encrypt some (possibly large) plaintext message and RSA must not be used without a secure padding scheme  (see below in the "practical advice"). Anyways, lets look at it:

As I interpret it from your question, you suggest that you use RSA to encrypt a message $m$ interpreted as a string of characters? Then, for instance, an encoded message $k=12$ could either be $m=ab$ or $m=\ell$? You need an unambiguous encoding.

Edit

From your comment another interpretation is that you interpret your message $M$ as a string of $n$ characters $M=M_1\|\ldots\|M_n$ and treat every character $M_i$ as a single message and produce $n$ RSA ciphertexts. Issues:

Bad performance: Modular exponentiation produces non-negligible overhead and thus encrypting the message $M$ with this approach leads to $C=(C_1,\ldots,C_n)$ and costs $n$ RSA encryption operations (in comparison to a single one when encrypting $M$ as a single message - where I assume that $M$ fits into one integer of $Z_N$). Consequently, it also costs $n$ RSA decryption operations. Why should one do that?
One can efficiently do "trial encryptions" when using textbook RSA, i.e., without a secure padding scheme, to determine the message hidden when given a ciphertext, since textbook RSA is deterministic.
Apart from that, even if you use RSA-OAEP which provides IND-CCA2 security and thus non-malleability, i.e., modification of ciphertexts can be detected, in this scenario an adversary could simply drop/replace/reorder/insert any ciphertexts from/into $C$ and thus your so obtained construction does no longer provide non-malleability as single block RSA-OAEP does. However, this is a theoretical issue, since, as @fgrieu points out in his answer, public key encryption alone does not provide authenticity.

/Edit

What is done in practice is quite similar to your idea, but one interprets the entire encoded message (which is typically the result of some padding scheme) as an element of the set $Z_N=\{0,\ldots,N-1\}$, and one
uses standardized (unambiguous) encoding functions to map strings to elements of $Z_N$ and back. These are denoted as OS2I(octet string to integer) and
its inverse is denoted I2OS (integer to octet string).

For an encoding x=OS2I(M), one treats a string $M$ of $\ell$ octets, i.e., $M=M_{\ell-1}\|\ldots\|M_0$ (which you want to encrypt) as an integer $x$ in base 256 (each octet is interpreted as a non-negative integer to the base 256, where the leftmost bit is the most significant one). More precisely, one sets $x_i = M_i$ and thus

$x=x_{\ell-1}\cdot 256^{\ell-1}+\ldots+x_1\cdot 56+x_0$.

The inverse (which you call after decryption) then takes an integer $x$ and a lenght parameter $\ell$ and outputs an octet string $M$.

Practical Advice

Note that if your string $M$ you want to encrypt does not fit into $Z_N$ you need to divide it into blocks that fit into $Z_N$. But in practice no one would do so,
since RSA is used to encrypt only a very short key, e.g., 128 bits, that fits in one block (element of $Z_N$) and uses this key with a secure symmetric encryption scheme to
encrypt the (larger) message. This is what is caled hybrid encryption.

Furthermore, textbook RSA must never been used in practice for encryption and one should use standardized and secure versions of RSA
with appropriate padding schemes such as RSA-OAEP. Look for instance here. The above mentioned encoding is then applied to the padded message.


Signing different types of messages with the same asymmetric key I want to be able to sign different types of messages with the same asymmetric key. (For completeness, I am using Ed25519 for my signatures).

Why do I want to do this?

The same key is used to sign different types of messages. If I didn't use some method to differentiate between message types, an attacker might be able to ask me to sign one message of one type, and then use it as a message of another type.

Example crude solution

For a quick prototype, I used the following crude method.

To sign a message of type 1:

$\operatorname{Sign}[\text{key}](\text{"type1" }||\text{ message}_1)$

To sign a message of type 2:

$\operatorname{Sign}[\text{key}](\text{"type2" }||\text{ message}_2)$

I have a feeling that this is not the best way to get good separation between message types. This is especially true if one type string is a substring of another type string. I remember for example, that HMAC and hkdf use a more sophisticated mechanism (They don't just concatenate).

I don't want to reinvent the wheel here. Is there a common practice to solve this problem?

As long as the prefixes type1 type2 etc.. are distinct, of equal size, and consistently inserted before everything signed, what's proposed is perfectly fine, and common practice.

That prefixes are distinct and of equal size is a simple and foolproof (thus good) way to implement the necessary and sufficient requirement: no prefix shall be the start of another prefix.

If for some reason prefixes must be of different size, possible conventions insuring that this requirement is met include:

The size in byte of the prefix is before the prefix, on 1 byte (Pascal string convention).
A special terminating byte is at the end of all prefixes, and not used elsewhere in a prefix. Common choices include the byte 0x00 (C string convention) or a separator like :
Using the hash (SHA-512/256) of distinct string prefixes, as proposed in comment. Since that's constant-size, the requirement boils down to using string prefixes that do not collide, and we do not even know how to make otherwise.

At the upper end of the complexity spectrum: everything signed could be per an appropriate ASN.1 grammar. Watch out for the complexity degenerating into interoperability issues, or even exploitable flaws.


Why are the bit lengths of keys and digests equal in Lamport signatures? In Lamport's one time signature scheme:

One way function to convert a pseudo random number private key to a public key takes $\{0,1\}^n$ and returns $\{0,1\}^n$.
Cryptographic hash function to convert message into message digest takes $\{0,1\}^*$ and returns $\{0,1\}^n$.

Why are these two not independent? Why do they need the same number of bits $n$?

The security level of a hash function is determined by its output size. In general, a hash function is considered cryptographically secure when it is collision resistant and provides security level $b = n/2$. Hence, it is not wrong to describe Lamport's scheme that way. However, the description probably was done that way to abstract away some details:

If you want to get $b$ bits security and do a classical message digest, you will need a hash function with $m = 2b$ bit outputs for the digest. However, for the "internal" hash function used to map secret key elements to public key elements you are fine with $n = b$ bit outputs as you just need one-wayness for this function. Now, if you change the message digest to a randomized message digest using $h = H(R,M)$ for randomness $R$ and message $M$, you can get away with $m = n = b$ bit output length for the message digest (if you do everything correctly). This is more about the message digest than about the hash function used inside of Lamport and hence distracting from the actual topic: How does Lamport's scheme work.


Does any problem arise when the order of an elliptic curve is equal to its prime field modulus? Regarding cryptographic schemes in elliptic curve cryptography, is there a problem with having the order of an elliptic curve being equal to its prime field modulus?

That is, an elliptic curve where $\#E(\mathbb{F}_p) =p$ for some prime $p$?

As I understand it, this seems to be an optimal curve because by the lagrange's theorem the order of an elliptic curve's subgroup must be divisible by the order of the elliptic curve. But if the order of an elliptic curve is prime, that then that means that any point in this curve is a generator that produces all of the points in $E$ and has a cofactor of $1$. For example, this curve here.

So, is there some kind of 'gotcha' with this sort of elliptic curve? Something that might allow an attacker to easily solve it by some math trick? Of course, assume for an elliptic curve some large prime $p$ but with the same properties.

Found an answer: Why Smart's attack doesn't work on this ECDLP?

Smart's attack seems to be what I was looking for.


Difficulty to find any preimages $a$ and $b$ for given $V$ so that $H(a) \oplus H(b) = V$? Suppose I have the values $a$, $b$, and $V = H(a) \oplus H(b)$ with inputs $a \neq b$ and $H$ being SHA-224. None of these values are a secret.
How secure is it to assume that no other possible values $a'$ and $b'$ (except the case of $a'=b$ and $b'=a$) can be generated that result in the same $V = H(a') \oplus H(b')$?

Are there recommended procedures to combine two hashes into a single value and meet the following properties:

$V$ has same (or nearly same) size as each of both input hashes
Any single unknown value ($V$, $H(a)$, or $H(b)$) can easily be deduced from two known values.
Cryptographically hard to obtain different pre-images $a'$ and $b'$ with same $V$

$ Pr(H(a) \oplus H(b) = V)$ is independent of $V$ For a good hash, as pointed out in the comments. Pick your input space to be the output space of SHA-224 so with probability $1/2$ (1) holds.

The range of $H$ is a group under $\oplus$. So (2) holds.

3 won't hold by the same group property. Another $2^{112}$ trials will likely yield $a',b'$ satisfying (3) with probability $1/2$.


Scalability of homomorphic tallying Whenever I look at online voting schemes, the idea of homomorphic encryption being a key concept, specially in the form of homomorphic tallying, appears to be universally accepted. The accepted answer for this question, for instance, suggests that it is one of the two most important technical approaches to online voting (the other one being mixnets).

The general approach for homomorphic tallying that I have found so far (supported on different additively homomorphic encryption schemes) is to define the tally as a single number, assigning some bits to the part of the tally corresponding to each voter. For instance, assuming that we have 4 voters and 3 candidates, the tally can be represented by the bit string ABCDEF, such that the candidate 1 has AB votes, the candidate 2 CD votes and the candidate 3 EF votes. In the general case, getting the values for each candidate given the integer representing the tally should be a trivial set of bit operations.

The problem is that it doesn't seem to scale: if I had 50 candidates and 256 voters, I'd need a tally of size 8*50=400 bits. It is my understanding that homomorphic schemes and big integers are not a very efficient combination. However, I cannot find a scenario that addresses this problem and shows that it is feasible in a country wide scenario (where voters can be hundreds of thousands, or even millions, and candidates can get up to a few hundreds), or, quite the opposite, clearly states the practical limits of homomorphic tallying.

Am I missing something? Is homomorphic tallying as restricted as it seems? If so, why is it regarded so highly as a building block for online voting?

I am not sure why you think that "homomorphic schemes and big integers are not a very efficient combination". In most homomorphic public-key cryptosystem, the message space is very large. For example, the Paillier cryptosystem (probably one of the most used for secure voting) has a plaintext space size of $2^{2048}$ with current security parameters. This allows for elections with a million voters and a hundred candidates. Moreover, the plaintext space of Paillier can be increased if necessary (interestingly, it can even be increased "on-the-fly" if the plaintext space size seems too short, without having to ask the voters to re-vote). With $4096$ bits, you can support twice more candidates, or a billion of voters.


Does key renewal increase complexity of MAC forgery? Suppose I have encrypted messages sent to a device authenticated with a MAC keyed with a strong shared cryptographic key. This device can only process so many messages per unit of time. This cryptographic key is renewed every few seconds: a new key is independently created and the previously one is destroyed.

Does this actually have any effect on the difficulty of an attacker to forge a message with a valid MAC? I originally thought it did since any computational effort spent for a key would be wasted once the key is renewed, but it occurred to me that it's not really possible to attack a MAC in a structured way (otherwise it would be broken); tags are just tried at random until a valid one is found, independently of the key.

Am I right in saying that constantly changing the key does not help with increasing the strength of a MAC? If not, can I shorten the MAC for these messages and achieve equivalent security against forgery to a larger MAC length due to the use of short-lived keys?

This depends on the MAC because there are different kinds of attacks to consider.

If the best attack is randomly trying authentication tags, then the key does not matter.
If the best attack is brute forcing the key, then key renewal does mean that the attacker has to "start anew", but as long as the key space is large enough that the probability of finding the key is small, that probability does not decrease all that much.
If the MAC is broken and admits other attacks, then key renewal may make attacks more difficult (e.g. if a large number of known MACs are needed) or easier (e.g. if some keys are weak).

MACs such as SipHash or many AES-256-based MACs fall under the first case. It is much faster to randomly guess a correct MAC value than guess a correct key, because the key space is larger than the tag space.

On the other hand, HMAC is sometimes used with a key that is shorter than the output (e.g. 128-bit key and HMAC-SHA-256). If the MAC tag is not truncated, then the fastest known attack is brute forcing the key. This is the second case.

Regarding the third case, one example is MAC misuse, such as CBC-MAC with variable length messages, which becomes secure if you renew the key on every message. A short AES-GCM tag is also secure as long as you do not reuse the key too many times.


In RSA, why does $p$ have to be bigger than $q$ where $n=p \times q$? In openSSL – during RSA key generation – if $q$ is bigger than $p$, they exchange them. Why is that?

There's no real difference between $p$ and $q$ in RSA. It looks like OpenSSL just has the agreement "$p$ has to be bigger than $q$" for conveniences. One of the numbers has to be bigger than the other (otherwise they would be the same number, and $p = q$ is very bad in RSA).

Just use two examples: $p = 13$ and $q = 11$. $p$ is bigger than $q$, all right. What about $p = 11$ and $q = 13$? In RSA, there is no difference between the two prime numbers, so you can exchange them at will. Both are the same prime pair for RSA, even when the two numbers for $p$ in the examples are different, and "the same prime pair" means in praxis the same key.


Multilinear Pairing in Cryptography I want to create 2 Bilinear Pairing $e_1$,$e_2$ such that
$$e_1:G_0 \times G_0 \rightarrow G_1$$
$$e_2:G_1 \times G_1 \rightarrow G_T$$

and use this to encrypt a message $M$ in the form  $$M e_2(e_1(g,g),e_1(g,g))^{xy}$$ To decrypt the message, first one has to retrieve $e_1(g,g)^{x}$ and $e_1(g,g)^{y}$ using linear secret sharing scheme. Then, can calculate $$e_2(e_1(g,g)^{x}, e_1(g,g)^{y})=e_2(e_1(g,g), e_1(g,g))^{xy}$$ Ultimately one can retrieve $$M=\frac{M e_2(e_1(g,g),e_1(g,g))^{xy}}{e_2(e_1(g,g), e_1(g,g))^{xy}}$$
My question is whether it is possible to user this to create a cryptographic scheme? And also is it practical to implement using any existing crypto library? One idea is if it were possible to define $e_1$ as $e_1:G_0 \times G_0 \rightarrow G_0$, then we could define $e_2$ as $e_2:G_0 \times G_0 \rightarrow G_0$. And that serves our purpose. Since I am new in Pairing based cryptography, I do not know whether the solution is practical. It would be great if I get any help or lead from any of you guys. Thanks in advance.

Pairings, or bilinear maps, have indeed found a great deal of applications in crypto; hence, researchers have soon pointed out that further "degrees" of linearity (trilinear maps, etc.) would provide even more powerful applications.

Nowadays, multilinear maps are one of the most powerful cryptographic primitives. They are at the heart of indistinguishability obfuscation, witness encryption, multiparty key exchanges, among many other applications. As one can expect, building such a powerful primitive is not an easy task. The story of multilinear maps, which schemes have been created, which have been broken, etc., would be really long to tell (although I could try to look for some survey if you're interested). To make it short:

-The last thing you've described, $e: \mathbb{G}_0 \times \mathbb{G}_0 \mapsto \mathbb{G}_0$, is referred to as an ideal multilinear map. I know of a single paper which proposed such a scheme, and it was broken within a few months.

-There are currently two major constructions (and many variants of each of them) of graded encoding schemes, which are close variants of multilinear maps and are associated to some degree, which corresponds to its degree of linearity. The first scheme is usually called the GGH scheme and is based on ideal lattices; the second one relies on the hardness of factorization and is usually called the CLT scheme.

-The expected security of a graded encoding scheme is defined through a set of assumptions on the scheme which are conjectured to be intractables. The assumptions might require some particular components to be made available (one important case for multilinear maps is whether it provides encodings of the zero value). Different applications require different assumptions, so there's really a patchwork of schemes whose security is related to some assumption on some multilinear map. Essentially, most assumptions have been broken. Multilinear maps have suffered from a collection of very powerful attacks, denoted zeroizing attacks (a recent result seems to indicate that a new, an even more effective way of attacking multilinear maps has been discovered; it was introduced under the name of annihilation attacks). Zeroizing attacks have broken most assumptions on major candidate constructions, and I don't think many cryptographers would confidently advocate the use of these constructions as a safe choice.

However, it should be mentioned that this is not a full break. In particular, these attacks do not rule out several constructions of indistinguishability obfuscation from multilinear maps, which is one of the most important applications.

This was regarding security. Regarding efficiency, things are not better: even if they were really secure, current candidates are very slow. For multilinear maps of small degree (say, less than 10), an optimized implementation in a very simple setting might allow you to execute a protocol using them in a few minuts, but when parameters grow, the running time will soon make this solution entirely impractical. Indeed, building multilinear maps (or graded encoding schemes) with a better-understood security, and a better efficiency, is one of the major goals in theoretical cryptography.


Given hash(x) and y, can I verify z = hash(x + y)? Here's the problem I'm trying to solve:

y is public, it's a timestamp
there is A who knows x - it's a file
A can send B some information about the file (a hash?), but not the full file (it's too big)
A then sends the file x to C

The role of B now, is to periodically verify that at given time y C still has the file x. C could send something like hash(x, y) to B, and B (who doesn't have the full x) needs a way to verify that C indeed has the full file x at time y.

Here's the original question I've asked (it includes the solution approach I've been trying to take):

Say I only know hash(x) and y.

I receive z that is supposed to be hash(x + y)? Is there any way I can verify that without knowing x?

I'm interested in any mechanism that could make such check possible rather than particular hash and + operations.

The technical term for what you're looking for is "publicly verifiable proof of retrievability". Here is a question on crypto.SE that discusses existing implementations of PoRs.


Best choice out of these six TLS cipher suites I have a small embedded platform that supports 6 TLS ciphers. Is there a good/better/best one to chose?

I was looking around on the web for some kind of rating system or list of ciphers that have known weaknesses, but I couldn't find much.

Back to my project, I used the Wireshark tool to capture the "client hello" when authenticating with the server, and my (slim) options are as follows:

TLS_RSA_WITH_RC4_128_SHA (0x0005)
TLS_RSA_WITH_RC4_128_MD5 (0x0004)
TLS_RSA_WITH_AES_128_CBC_SHA (0x002F)
TLS_DHE_DSS_WITH_AES_128_CBC_SHA (0x0032)
TLS_RSA_WITH_3DES_EDE_CBC_SHA (0x000A)
TLS_DHE_DSS_WITH_3DES_EDE_CBC_SHA (0x0013)

I have heard triple DES, RC4, and MD5 are insecure, so should I be avoiding ciphers with those algorithms? Does this leave me with cipher suites TLS_RSA_WITH_AES_128_CBC_SHA and TLS_DHE_DSS_WITH_AES_128_CBC_SHA?

Ideally, you should not use any of them. At all.
Here's why.

RC4, MD5 and DES should not be used anymore. Old crypto. Toss it.
CBC mode in AES sometimes suffers from implementation problems (cf. Padding Oracles). Thus, CBC should be avoided.
SHA1 is considered insecure and is not be accepted as a certificate signing hash since January 2017 by major browsers.

So, if you absolutely have to stick with one of these ciphers, I agree with @otus here, and would recommend TLS_DHE_DSS_WITH_AES_128_CBC_SHA.

IF ever you have a chance to add other ciphers to your embedded platform, know this :
Symetric ciphers :

AES and ChaCha20 are the best symmetric ciphers to use, as of the
beginning of the 21st century. The difference between them is, simply
put, being a block and stream cipher, therefore being different in
speed.
AES often takes advantage of AES-NI, a hardware acceleration, found on many processors in current laptops and servers.
ChaCha20 is to be preferred on mobile and embedded platforms, where
AES hardware acceleration is rare, because it is really faster.
Poly1305 is de facto the best buddy for ChaCha20, so they go in pair.
For AES, consider AEAD compatible modes, like GCM.
Chose a hash algorithm like SHA2 or above (SHA384, SHA512,...). The higher, the more secure. But this is overkill, will take more time and is heavier in terms of size. So stick with SHA256.

Asymmetric ciphers (for key exchange) :

Today's trend and best use is Diffie-Hellman. Even better, Ephemeral Elliptic-Curve Diffie-Hellman (ECDHE), because it is smaller, faster (you can generate 384bit parameters in a couple of milliseconds, corresponding to 7680 non-EC bits that would take hours to generate on your embedded device).

Certificate Signing :

Nobody uses DH.

RSA was good. To be avoided from now on. is still good.
It's even really faster for validation than DSA - take a look with
openssl speed (up to you to determine whether this matters for your use).

Best use : ECDSA. DSA is new, and coupled with Elliptic curves, it is smaller and really faster than RSA - take another look at openssl speed. Considered more secure. Just a shame that Edwards curves are not supported in OpenSSL as for now.

(Sorry if I missed details or am not being clear, wrote this on lunch break.)
EDIT : Added clarification on choice between ECDSA and RSA. Thanks @Dreadlockyx and @otus for having me have a second look !


Sliding windows implementation (Exponentiation by squaring) I am conducting a research on cpu-cache based info leak caused by using Sliding window in the diffie helman key exchange.

For my research I am looking for a real-world implementation of sliding window,I have read the source of BouncyCastle and Gnu-TLs and came out empty.

Can someone share some light on the real world use of this algorithm and where, if at all I will be able to find implementation of it?

Serious cryptography software today does not use sliding windows for exponentiation by secrets precisely because it leaks the secrets through array indexing.  You might find it older versions of OpenSSL, libgcrypt, etc.  In modern software, your best bet is probably libgmp (mpz_powm, not mpz_powm_sec) or other generic bignum libraries optimized for speed, not for security.


What is the Peer Signing digest on an OpenSSL s_client connection? For a little background, I am trying resolve an issue with an ISAM (reverse proxy) appliance not being able to connect to a server due to it failing to complete a TLS connection.

A server that is connecting just fine is using ECDHE-RSA-AES256-GCM-SHA384, with peer signing digest of SHA512. This is on a tomcat server.

The on that's having trouble is using ECDHE-RSA-AES256-SHA384, with a peer signing digest of SHA1. This is on Microsoft IIS.

Based on my research, Windows doesn't support ECDHE-RSA-AES256-GCM-SHA384 as a cipher suite (which is fine), but what I don't understand is what the peer signing digest is and why, even with SHA1 hashes disabled on windows, is SHA1 being used.

This may not solve my server issue, but I would like to understand what the peer signing digest is.

Peer Signing Digest is the hash algorithm used by the peer (i.e. the server from the perspective of the client) when signing things during TLS handshake. You will find these places by looking for the term digitally-signed in the TLS RFC.  See for example the details of the ServerKeyExchange message in wireshark:

  .. even with SHA1 hashes disabled on windows

SHA1 is not disabled on Windows in general. It is disabled only for use within the issuers signature of a certificate.


Why does DSA require that a new $k$ be chosen and the algorithm restarted if $s=0$? DSA is an algorithm used to generate a digital signature, which consists of a pair of values $(r,s)$. The algorithm computes $r$ first and then $s$. However, if we calculate $s=0$, it says to restart the algorithm choosing a different pseudorandom integer $k$ as our starting point.

What is the purpose of this? Is a digital signature $(r,s)$ invalid if $s=0$? If so, why?

The algorithm needs to be restarted because the private key $x$ can be obtained when $s=0$.
From:

$s=[k^{-1}( H(M) + xr)] \mod q$

We can solve for $x$ and get:

$x=\frac{-H(M)}{r} \mod q$


How does OAEP improve the security of RSA? The heart of OAEP algorithm used for RSA encryption are the cryptographic hash functions $H$ and $G$.

Does everybody (so also an adversary) know these functions?

If YES: How does it help the security, if he just can decode the padding and read the message?
If NO: What knowledge is needed for these functions? Are keys or something priorly exchanged? Are they related to the receivers private key?

Well, yes, everyone (or, at least, everyone who can use the public key) knows the hash function H and G; so we can assume that an adversary knows them as well.

You ask:

  If YES: How does it help the security, if he just can decode
  the padding and read the message?

Well, he can't decode the padding; the ciphertext has been encrypted using RSA, and he doesn't have the private key; so he can't get at the padded version.

Here's how OAEP works; you take the plaintext message $m$ to send, you pick a random value $r$, and compute the function:

$Padded = OAEP(m, r)$

(with H and G as parts of OAEP).  Then, once we have that, we encrypt it using the base RSA public operation (using the public key):

$Ciphertext = RSA(PublicKey, Padded)$

The $Ciphertext$ is what's actually sent; because it is encrypted using RSA, the attacker cannot recover $Padded$.

So, if the OAEP operation doesn't prevent an attacker from decrypted the ciphertext in this straightforward manner, why is it there at all?

Well, raw RSA has some nastly properties (called an homeomorphic property), namely:

$RSA(k, A) \times RSA(k, B) = RSA(k, A\times B)$

(where $\times$ is implicitly modulo the public key modulus).

Because of this property, using raw RSA to directly encrypt plaintexts is almost always the wrong thing to do; there are clever ways to use this homeomorphic property to recover plaintext.

What the OAEP function does is try to mimic a random function between plaintexts and padded versions; because we present the raw RSA operation with effectively random texts, these homeomorphic properties are no concern.


How can two UProve token holders prove to a 3rd party that they aren't the same user? Suppose I have two users who are issued two different UProve IDs.  The Issuer has guaranteed that one UProve token bearer will never have more than one UProve token ID.

How can I use UProve to guarantee that two users are "different" without disclosing their actual private ID?

Here is a scenario:  An online voting system wants to use UProve to anonymously collect votes.  They decide to trust an Issuer who has full knowledge of the end user, but the relying pary has to accept the fact that they will know nothing about the end user at all.

The polling station (relying party) only needs to know that the same UProve ID wasn't used to cast a second vote.  The only UProve scenario I know of that would work here is proving the user's SSN (or similar fixed ID).

In this case I don't want to disclose anything.

Is this possible?

The U-Prove Technology Overview V1.1 shows that this can be done. The issuer knows who the individual is but can't correlate that with verifier or prover use.

Upon setup the issuer can have extra attributes available that upon request of authorization from the prover the verifier can have access to. The verifier could use such an attribute and only successfully verify if it hasn't seen that attribute before.


DLP-based keyed one-way function I am trying to understand if it possible to use DLP to build a keyed one-way function with the following properties:

$H_a(H_b(M)) = H_c(M)$, where $a$ and $b$ are the keys, and $c=a*b$
The output of the function is relatively small - e.g. 256 bits

The function itself could be $h_a=M^a$ mod $p$, where $p$ is a 256-bit prime. However, I'm not sure how secure this would be given that the prime is pretty small. Specifically, I want to understand if the following would hold:

Given $h_a$ and $p$, it would be impractical to compute $M$
Given $h_a$, $M$, $c$, and $p$, it would be impractical to compute $a$

The messages I need to process are relatively small (256 - 512 bits), but can be padded if that would increase security.

An adversary who can compute discrete logs modulo $p$, given oracle access to $H_a$ for unknown $a$, can compute $\log_2 H_a(2) \equiv \log_2 2^a \equiv a \pmod p$ with a single query to the oracle.

After that, given $h = H_a(M)$ for unknown $M$, they can compute $$h^{a^{-1}} \equiv (M^a)^{a^{-1}} \equiv M^{a\cdot a^{-1}} \equiv M \pmod p,$$ where $a^{-1}$ is the inverse of $a$ modulo $\phi(p) = p - 1$.

If $p$ is 256 bits, adversaries can compute discrete logs modulo $p$ today.  You need $p \gg 1024$ to be safe, among other criteria.

It might be helpful to go into more detail about why you need these properties, and what you are trying to achieve more generally.


How can i verify a certificate to root? I write some certificate Authority that has it's own private/public cert keys .
This CA signs public keys of user.
If for example i have user that has a public cert that signed by the CA.
How I can verify later that the user's certificate as indeed signed by that CA if he has the public cert of the CA ?
I'm using cryptography module in Python, and there are some functions that i can use but I'm not sure how:
The representation of both certificates is X.509 , which means that one can grab the public key of the user and use verify method, this is how i used it :

caCert.public_key().verify(clientCert.signature,clientCert.tbs_certificate_bytes,padding.PSS(       mgf=padding.MGF1(hashes.SHA256()),salt_length=padding.PSS.MAX_LENGTH),clientCert.signature_hash_algorithm)

But i still get invalid signature error

Your code should work.

However you (implicitely?) assume the certificate uses PSS padding for the RSA signature. While this is possible, it is extremely rare in practice, you should try validation using PKCS#1 v1.5 signature padding instead.

Converted my last comment to an answer because it apparently solved the problem.


SSL - encrypt with private key and then with public key? Say there are 2 sides that wish to communicate: side A and side B. Let's say we are looking at side A sending messages.

When establishing connection in SSL protocol, does the protocol always require that the message is first encrypted using side A's private key (so side B knows that only A could have encrypted it) and then is encrypted with B's public key ? So that only B could decrypt it ?

In what case would side A encrypt the message only with B's public key and then just send it ?

You cannot "encrypt" with a private key.

Encryption provides confidentiality of the encrypted message.

If the public key performs decryption, and the public key is public, then anyone can decrypt the message. So "encrypt with the private key" is not possible.

This notion may be popular, but it is incorrect.

It stems from the fact that signing a message with textbook RSA is equivalent to public key encryption done in reverse. However, there are many problems with this:

Textbook RSA does not provide a secure signature/encryption scheme, and is not used
Padding and hashing ensure that the signature process is in fact not the same as the encryption process done in reverse.
Few, if any, other algorithms even operate in a similar manner. E.g. there exist signature schemes that you cannot encrypt with, and therefore signatures being "encrypting with the private key" is not even a vaguely correct analogy.

So your questions can be translated to something more accurate:

  When establishing a connection in the SSL protocol, does the protocol always require that the message is first signed using side A's private key (so side B knows that only A could have signed it) and then is encrypted with B's public key so that only B could decrypt it?

When establishing a connection, it is assumed that A's public key is already signed by a certificate authority (that has vetted A's identity). First the certificate and public key are presented to B. B has the public verification key of the certificate authority pre-installed, and can use it to verify the signature on the certificate and public key. There is a nice outline of the process on our information security sister site.

  In what case would side A encrypt the message only with B's public key and then just send it?

Situations where the message is not signed include:

Broken protocols vulnerable to man-in-the-middle attacks
When A and B already share public keys with each other

The initial key exchange could use signatures, but the actual messages sent back and forth may only use MACs rather than signatures.

When A desires deniability about having sent the message to B


Why does Openssh use only SHA1 for signing and verifying of digital signatures? I am learning SSH protocol. With my current understanding of SSH protocol, I think that message digest algorithms for using in digital signature should be derived from Key Exchange. But Openssh implementation uses only SHA1 for signing and verifying of digital signatures. SHA1 is hard coded in these two functions, ssh_dss_sign() and ssh_dss_verify().

I am wondering, does all the implementations of use SHA1 as hash algorithm for signing and verifying digital signatures.  And why don't we use SHA-256 as it's better than SHA1?

Is there any specific reason for doing so..? If yes, could someone please provide some references.

Thanks in advance.

Because the RFC says so.

  Signing and verifying using this key format is done according to the
    Digital Signature Standard [FIPS-186-2] using the SHA-1 hash
    [FIPS-180-2].

It says the same for RSA half a page down.

Apparently the signature algorithm is a defined part of the public key method's specification, rather than being negotiated separately like the MAC algorithm is.

At a guess, SHA-1 was considered good enough at the time SSH 2 was being written almost a decade ago (the RFCs were published in 2006), and no one wants to bother changing it now.

Notice that ECDSA keys, published in RFC 5656 in 2009, use SHA-2:

  Signing and verifying is done using the Elliptic Curve Digital
     Signature Algorithm (ECDSA).  ECDSA is specified in [SEC1].  The
     message hashing algorithm MUST be from the SHA2 family of hash
     functions [FIPS-180-3] and is chosen according to the curve size as
     specified in Section 6.2.1.

You can see it in action in ssh_ecdsa_sign() in ssh-ecdsa.c and key_ec_nid_to_hash_alg() in key.c.

(I'm not an expert on SSH, so please take this answer with a grain of salt.)


Why is it recommended to hash passwords with a secret salt? NIST recommends doing an additional round of hashing using a secret salt:

  In addition, verifiers SHOULD perform an additional iteration of a key derivation function using a salt value that is secret and known only to the verifier. This salt value, if used, SHALL be generated by an approved random bit generator [SP 800-90Ar1] and provide at least the minimum security strength specified in the latest revision of SP 800-131A (112 bits as of the date of this publication). The secret salt value SHALL be stored separately from the hashed memorized secrets (e.g., in a specialized device like a hardware security module). With this additional iteration, brute-force attacks on the hashed memorized secrets are impractical as long as the secret salt value remains secret.

Questions about this:

Is it safe to ignore this advice? Are there any known vulnerabilities if we don't do this additional iteration?
How should we implement this additional iteration, if the secret salt must be stored separately but need to be available when hashing a password? Should we use a dedicated server for the secret salt, transferred to the verification server using a secure protocol? The secret salt may stay in the verification server's memory, does this matter?

NIST document section 5.1.1.2 Memorized Secret Verifiers.

That section is a "SHOULD" not a "SHALL".

It is standard practice not to keep the salt secret but to save it with the password hashed verifier.

If the salt is not secret a brute force search is possible if the password is weak such as being on a list of frequent passwords. One example source of such frequent passwords is SecLists.

If the salt is secret such a brute force search will not succeed. Note: stored separately from the hashed memorized secrets (e.g., in a specialized device like a hardware security module) and such a device is generally not available.


Randomness and reversibility of a sequence generated by taking sha256 hashes of an predictably-changing input? Let's say we generate a sentence in a way like for example this: Fix an initial seed. Attach '1' at the end of the seed and compute sha256 of such a string. This hash is our first number. Now attach 2 at the end of the seed(instead of 1 like in the previous step) and compute sha256 to get our 2nd number. And so on.

Will this sequence behave randomly? Would it be possible to extract any information about the inital seed if enough numbers of the generated sequence are known? Does anything in this matter change if we decrease the size of the generated numbers by, for example, truncating the hash to a couple of the initial bytes or taking the hash modulo a very small number?

This is basically how KDF1 and KDF2 work: use a secret, add a (constant sized) label + possible other values such as a salt and then use this as input for a hash value.

Another way to look at it is to view the seed + number as a new number and then reduce the problem to the problem that Richie Frame pointed at.

So:

yes it will behave randomly
no, no information about the seed can be retrieved
truncation of hashes is a well known method, and will not leak any more information


Which algorithm is the simplest reversible fixed-size length-preserving symmetric "cryptography" with low probability of collision? I am not a mathematician/cryptographer, so I could not take much advantage of this other question, and it seems (?) to have more requirements than me (SAC).

I say simple, because I need it to be have a fast implementation and also because security is irrelevant in my use case.
However, a low collision probability is an important requirement. By low I mean something comparable to the odds of MD5(textA + keyB) = MD5(textC + keyD), for different texts and keys. Both text and key have  a fixed size, e.g., 16 bytes. Plus sign here means concatenation.

For instance, AES would be suitable for this task, but it is 100x slower than MD5.
Of course, MD5 is irreversible, so I can't use it.

Another requirement is that it should also be non-commutative, i.e. encrypt(textA, keyB) != encrypt(keyB, textA) otherwise I guess I could just use the XOR bit-wise operation.

EDIT

What I have done so far was to implement the following 128-bit "cryptography" in Python. However, with many collisions:

def pepper(msg):
    bit = (msg & 0b1111111) % 120 + 8
    return msg ^ (2 ** bit)

def rev_hash(msg_int, key_int):
    """A "reversible hash", the nightmare of cryptologists."""
    lshift = (((msg_int & mask_127ones) << 1) | (msg_int >> 127))
    result = lshift ^ key_int
    return pepper(result)

def rev_unhash(encrypted_msg_int, key_int):
    xor = pepper(encrypted_msg_int) ^ key_int
    rshift = (xor >> 1) | ((xor & 1) << 127)
    return rshift

What's asked is fulfilled by a block cipher with 128-bit key and block size (but notice that it's trivial to make collisions when one of the keys is known). We can't use a stream cipher (collisions would be trivial even with both keys secret), nor OAEP padding as used in RSA encryption (as practiced it is not length-preserving, and not exactly simple).

AES-128 is one suitable block cipher, and is not slow . It commonly runs at over 1 million 16-byte encryptions per second per core in pure software, sometime 20M (for repeated use with the same key), or even 200M with AES-NI hardware. Sure, that's not for AES implemented in pure python.

But using AES from python is easy, even if we use the question's message-as-int interface.

from Crypto.Cipher import AES

def rev_hash(msg_int, key_int):
    return int.from_bytes(AES.new(key_int.to_bytes(16,'big'),AES.MODE_ECB).encrypt(msg_int.to_bytes(16,'big')),'big')

def rev_unhash(encrypted_msg_int, key_int):
    return int.from_bytes(AES.new(key_int.to_bytes(16,'big'),AES.MODE_ECB).decrypt(encrypted_msg_int.to_bytes(16,'big')),'big')

Try it online!

That might be acceptably fast. It would be hard to beat if we used the native bytestring interface (avoiding to_bytesand from_bytes), and modified the interface to reuse the AES instances across calls with the same key.

It is possible to make a block cipher that's simple, fast, secure: pick at most two of these features. Here, one of the requirement can be read as: making collisions must be comparable in difficulty to making collisions between MD5 hashes with different (secret) keys appended, even with many plaintext/ciphertext pairs at hand for both keys. Combined with reversibility, that means 64-bit security, since MD5 remains that strong against collisions under these conditions. With this requirement, it's hard to make something simple and fast, especially in pure python.

Without any claim of security, here is a very simple self-contained 128-bit block cipher

def rev_hash(msg_int, key_int):
    for x in [305065944875308933,445871615361279994733287202953785,859072698151683073,893999628687995393356516725455569]:
        msg_int = (((msg_int>>64)^msg_int^key_int)*x+1)&((1<<128)-1)
    return msg_int^key_int

def rev_unhash(encrypted_msg_int, key_int):
    encrypted_msg_int ^= key_int
    for x in [409772003941621297,679237006192346672534347824675841,229702291678999561,786310896237332493342854003018061]:
        encrypted_msg_int = ((encrypted_msg_int*x-x)&((1<<128)-1))^key_int
        encrypted_msg_int ^= encrypted_msg_int>>64
    return encrypted_msg_int

Try it online!

Rationale: there are 5 rounds, each reversibly acting on the whole state. Each round uses XOR with the key, and (except for the last round) modular multiplication by a constant (which gives left diffusion) with addition of 1 modulo 2128, and XOR of the left half into the right one (which gives right diffusion, and alternates addition and XOR to break linearity). The constants are pre-computed as four 18-digits random primes selected among about a million for having 33-digit modular inverses, alternating with the inverses. Such use of round-dependent constants hopefully partially compensates for the total lack of key schedule. Things are arranged so that the encryption is compact. Decryption is even so slightly more complex, because it needs to proceed in reverse order. The addition avoids a stationary point at zero with key 0.

Speed is only marginally better than in first example using AES (like by a mere factor of two), at the expense of security. And again the first example would be much faster with a rethought interface.


Parsing of X.509 certificates I'm working on a firmware for a platform with limited resources with C as programming language.

There are a set of cryptographic primitives to be implemented, including AES, GCM/GMAC, ECDSA, ECDH. Our hardware allows to handle all these algorithms (it is more or less a crypto controller) and all the mentioned things beside ECDH are already implemented and tested.

For a future firmware release certificate handling (only for ECC with P256/SHA256, including also certificates in the validation chain) is needed as an additional requirement.

What is the best approach to parse certificates into its atomic constituents. E.g. I need access to public key material, like expiration date, issuer, subject , ...

Of course, I know about openSSL, but this is too heavy and would blow up far too much. So I tested mbedSSL (under Apache license). This open source project would do it, but I'm not allowed to use it because of internal reasons. Similar for woolfSSL. Anyway, I would only use a very small part of such library (just parsing of certificates)...

Is there some recommended way to parse a PEM X.509 certificate? Any third party product I can use? Is it complicated to write such parser on my own? Where is the structure described? My biggest concern is about writing a good ANS1 parser together with a base64 decoder on my ow, but maybe it is not that complicated as I expect from now.

Is there some recommended way to parse a PEM X.509 certificate?

Well, this site is not for software recommendations (Software Recommendations is, who would have thought), but if the certificate is well-behaved it is possible to generate code for the ASN.1 constructs. You need a parser/generator for ASN.1.

  Any third party product I can use? Is it complicated to write such parser on my own?

There are various ASN.1 and X.509 libraries online. Is it hard to write on your own? Yes, expect a low minimum of 3 months work to write something pretty OK, if you already understand ASN.1 / DER.

  Where is the structure described?

ASN.1 and DER are described in the ISO/IEC 8824 and 8825-1 specifications respectively. X.509 certificates and CRLs are described in RFC 5280. The appendix of the RFC contains the ASN.1 module.

  My biggest concern is about writing a good ANS1 parser together with a base64 decoder on my ow, but maybe it is not that complicated as I expect from now.

Creating a base 64 decoder is absolutely peanuts compared to the parsing of ASN.1 structures. You may however get away with just DER encoding and looking up paths within the certificates (if you want to live dangerously). You may run into some trouble when converting between implicit and explicit input for the signature algorithm, just to name one issue with the ASN.1 structures.

Note that ASN.1 BER/DER codecs are very vulnerable against stack overflow attacks (especially in non-managed languages like C of course), and that the decoding of the certificate comes before authentication.


Is using the same HTTPS cipher suite as Google a good idea? I'm searching for a cipher suite for my HTTPS website, running on the Apache 2 web server, that would offer a good compromise between compatibility with users and security. One idea I had was to simply using the same cipher suite that Google uses, i.e.:

Accepted  TLSv1  256 bits  ECDHE-RSA-AES256-SHA
Accepted  TLSv1  256 bits  AES256-SHA
Accepted  TLSv1  128 bits  ECDHE-RSA-AES128-SHA
Accepted  TLSv1  128 bits  AES128-SHA
Accepted  TLSv1  112 bits  DES-CBC3-SHA
Accepted  TLS11  256 bits  ECDHE-RSA-AES256-SHA
Accepted  TLS11  256 bits  AES256-SHA
Accepted  TLS11  128 bits  ECDHE-RSA-AES128-SHA
Accepted  TLS11  128 bits  AES128-SHA
Accepted  TLS11  112 bits  DES-CBC3-SHA
Accepted  TLS12  256 bits  ECDHE-RSA-AES256-GCM-SHA384
Accepted  TLS12  256 bits  ECDHE-RSA-AES256-SHA384
Accepted  TLS12  256 bits  ECDHE-RSA-AES256-SHA
Accepted  TLS12  256 bits  AES256-GCM-SHA384
Accepted  TLS12  256 bits  AES256-SHA256
Accepted  TLS12  256 bits  AES256-SHA
Accepted  TLS12  128 bits  ECDHE-RSA-AES128-GCM-SHA256
Accepted  TLS12  128 bits  ECDHE-RSA-AES128-SHA256
Accepted  TLS12  128 bits  ECDHE-RSA-AES128-SHA
Accepted  TLS12  128 bits  AES128-GCM-SHA256
Accepted  TLS12  128 bits  AES128-SHA256
Accepted  TLS12  128 bits  AES128-SHA
Accepted  TLS12  112 bits  DES-CBC3-SHA

Presumably, Google has chosen their cipher suite to be compatible with most people's browsers, while also being very secure, so it seems that this should be a good choice for a cipher suite in general. But since I'm only running a small website, I'm not entirely convinced that what's good for Google is also good for me. So my questions would be:

Are there any ciphers in the suite above that I should not use? And if so, why?
Are there any other ciphers that I really should allow, even though Google doesn't?

But since I'm only running a small website, I'm not entirely convinced
  that what's good for Google is also good for me.

You're right with this assessment. Google has far more ressources for this than you probably have and this is why they can do things like roll-out ChaCha20-Poly1305 before it's standardized or the new post-quantum key exchange they're using, especially since they largely control development of Chrome which has an insanely large userbase.

  Are there any other ciphers that I really should allow, even though
  Google doesn't?

Yes.
For some reason, Google offers only ECDHE and (static) RSA cipher suites. While they reach the most people with this, you probably don't need to reach those ancient browser who don't understand either DHE or ECDHE (it's 2016, come on!). So the recommendation here would be to add the DHE variants of the cipher suites (although with lower priority than the ECDHE counter-parts).
Additionally you should consider adding (the now standardized) ChaCha20-Poly1305 cipher suite(s) into that list if supported by your TLS implementation, because of the high perfomance on mobile platforms.
Note though: If you can, disable parameter (as in the private key) re-use with the (EC)DHE cipher suites and generate your own DH parameters (and use them) once (using OpenSSL or something like that).

  Are there any ciphers in the suite above that I should not use? And if
  so, why?

Yes.
All the cipher suites that lack "ECDHE" or "DHE" in their name should be gone. Those are a) removed from TLS v1.3 anyways and b) if your server key ever gets leaked (heartbleed anyone?) an attacker can decrypt all the traffic that has ever been recorded while this key and these cipher suites have been used. This doesn't happen with the (EC)DHE suites and the property for them is called "forward secrecy".
Additionally you can (and should) drop the 3DES cipher suites because you don't need the backwards compatibility they provide (probably) and because they have quite a small block size, making them vulnerable to attacks like Sweet32.


Client and server using same SSL certificate - any issues? I'm working on software where multiple components will communicate with each other using SSL.

There would be one central component acting as a server, which would also require the clients to present a certificate. So there is mutual trust between the clients and server. The software will be deployed internally within organisations.

To avoid the pain of creating and distributing multiple SSL certificates, can a single certificate be generated once for each organisation, and then used by all of the components within that organisation?

If all the components share the same certificate, then they share the same private key. This raises the two following points:

When a secret is shared by more than two people, can it still be considered really secret ? Secrecy dilutes fairly fast. If all components share the same secret value, then breakage of any single component reveals the private keys and endangers the whole system. Similarly, every single client or server has the power to impersonate every other client or server in the system.
If client and server share the same secret value, why would you use certificates at all ? Certificates make sense when every entity has its one private key which never travels around. If client and server contain the same secret sequence of bits, then they could use pre-shared key cipher suites, which will use no certificate at all, and might be faster as well.


Do you need to MAC an ECIES message? Normally, when decrypting messages, you need to check if the message is authentic and integral (aka, never decrypt before checking the MAC).

With ECIES, this seems to be done internally. Is it necessary to include a MAC on your messages you encrypt when using ECIES?

From the original paper[1]:

  DHIES is a Diffie-Hellman based scheme that combines a symmetric encryption method, a message authentication code, and a hash function, in addition to number-theoretic operations, in a way which is intended to provide security against chosen ciphertext attacks.

So the MAC is in this case already part of the scheme. If implemented correctly encryption should result in an ephemeral public key, a ciphertext, and a MAC / tag for the ciphertext being generated. So there's no need to generate another MAC.

[1] The distinction between DHIES and ECIES is simply the type of group being used for the underlying algebra, it isn't important in this context, much like the distinction between DH and ECDH


Homomorphism with subtraction for Pedersen Commitment I was trying to use Pedersen's homomorphic property for some privacy preserving mechanism, and to the best of my knowledge

$Com(x1,r1)\cdot Com(x2,r2)^{-1} = g^{x1-x2}h^{r1-r2}$

That is, if we commit $x1-x2$ with blinding factor $r1-r2$ we should get the commitment with value $Com(x1,r1)\cdot Com(x2,r2)^{-1}$.

However, I'm only getting this if $x1-x2>0$ and $r1-r2>0$. I believe this should hold whatever the values of $x1-x2$ or $r1-r2$.

I am taking the mod of all values i.e., $(x1-x2) mod\ p$ for some prime p, so none of the numbers are negative. So does Pedersen commitment not support homomorphism for subtraction?

You used the wrong modulus when verifying the result.

Note that although the computation is modulo $p$, i.e. you compute $g^xh^r \bmod p$, the exponents $x,r$ are in $Z_q$. And so the operations among the exponents are modulo $q$. That means, after the homomorphic operation, you get a commitment of $x_1-x_2 \bmod q$, not $x_1-x_2 \bmod p$ .


How to compute negative point in EC-DSA? Assuming we have a valid EC-DSA signature $\sigma = (r,s)$. We can then easily create another valid signature without the knowledge of the secret key by negating $s$. That is, $\sigma' = (r, -s)$ can still be verified. The verification algorithm of ECDSA works the following

$e = H(M)$
$w = s^{-1 }\mod p$
$u = ew \mod p$ and $v=rw \mod p$
$Z=(z_1,z_2)=uG+v\cdot pk = uG+v\cdot xG$
If $z_1=r\mod p$ return TRUE, otherwise FALSE

I'd like to understand mathematically why $\sigma'$ is still valid. If we fully extend the forth step of the verification algorithm, we get the following:

$Z = (x,y) = uG+v\cdot xG=G\cdot(ew+rwx)=G\cdot (e\cdot s^{-1}+r\cdot s^{-1}x)=G\cdot s^{-1}(e+rx)=G\cdot k\cdot(e+xr)^{-1}\cdot(e+xr)=G\cdot k $

Negating $s$ in $\sigma'$ essentially means, that we compute $Z = G\cdot (-k)$ instead of $Z = G\cdot k$. However, I see two ways to interpret $Z = G\cdot (-k)$, but obviously only one can be correct.

Recall that EC-DSA is applied on a finite field $\mathbb{F}_p$ with $p$ prime. $Z=G\cdot (-k) \mod p $ means that we first set $h = -k \mod p$. This is $h=p-k \mod p$ (For instance, $-3 \mod 17 = 14$.). We then calculate $Z = G\cdot h$. However, $G\cdot h$ does not equal $G\cdot k$ and thus, $\sigma \neq \sigma'$. This contradicts the assumption.
$Z=G\cdot (-k)$ can be written as $Z=-G\cdot k$. We then compute $Y=G\cdot k$ and eventually get $Z=-Y$. We simply have to negate the point $Y$. As $Y = (y_1, y_2)$ is a point on an elliptic curve, we get $Z = -Y = (y_1, -y_2) = (z_1, -z_2)$. The negation only affects the second point component and thus $\sigma = \sigma'$.

Question

Obviously, the first interpretation is not correct. But why? Is $\sigma = (r, -s)$ a valid signature, because it is only mirrored at the x-axis? The fifth step of the verification algorithm would still return true, because it takes only the x component of $Z$ into consideration? What prevents me to interpret $G\cdot (-k)$ like in the first way?

Your second point is the correct interpretation.

Due to the negation map automorphism on (Weierstrass form) Elliptic Curves we have for all affine points that if $P = (x,y)$ belongs to the curve then also $-P = (x,-y)$ belongs to the curve.

This is due the curve's symmetry with the respect to the $x$ axis, as you said.

You can view it as $-k \cdot G = k \cdot (-G)$ but you can also see it as $k\cdot G$ and $-k\cdot G$ are symmetric with respect to the $x$ axis just like $G$ and $-G$.
In fact, how would think of the negation of $(k\cdot G)$ if not with $-(k\cdot G)=(-k)\cdot G$ ?

Now the two point differs. But in the ECDSA verification only the x coordinate is checked, and this will be the same for $k\cdot G$ and $-k\cdot G$


Why are elliptic curves constructed using prime fields and not composite fields? I come across this:

  Numbers mod composite number does not form a field rather it forms a ring

and

  every number has a multiplicative inverse under integer mod prime

Maybe these are the reasons why prime field is preferred? By the first above fact it means that construction of a composite field is not possible. But I have seen some research articles about multiplication algorithm using composite fields…

Why are elliptic curves constructed using prime fields and not composite fields?

For a prime $p$ and an integer $n\geq1$, the ring $\mathbb{Z}/p^n\mathbb{Z}$ is a field if and only if $n=1$. There are fields with $p^n$ elements, usually denoted $\mathbb{F}_{p^n}$ or $\operatorname{GF}(p^n)$, but they are constructed differently. For $n\ge2$, they are commonly called extension fields (as opposed to prime fields for $n=1$), as they can be viewed as extensions of $\mathbb{F}_p$.

There are examples of elliptic curves over extension fields. For example, every cryptographically secure curve in characteristic two is defined over a field of the form $\mathbb{F}_{2^m}$, i.e. a field with $2^m$ elements. There is also the Four$\mathbb{Q}$ curve, which is defined over $\mathbb{F}_{p^2}$ where $p=2^{127}-1$.

Doing things over extension fields can get a bit more tricky. There are attacks which can exploit the fact that $n\ge2$, which lead to faster algorithms for the discrete logarithm problem, on which elliptic-curve crypto is built. This gets complex pretty quickly, but some of it is explained in Galbraith's book (see $\S15.7$ and $\S15.8$). These attacks do not apply to every curve over an extension field, but show that you'll have to be more careful.


How cryptographically secure was the original WW2 Enigma machine, from a modern viewpoint? If cryptanalysts today were to crack the original Enigma machine, “how fast” or “how easily” could they do it? What methods would they use?

The original cracking was significantly helped by operator mistakes, like always including the same header, always including a weather report, and finally, a long message of LLLLLLLL… being sent. Let's assume no such operator mistakes happened.

What methods would they use?

Since WW2, we know the security of Enigma machines was weakened by the reflector, resulting in two problems:

No difference between en- and decryption, which means that if K ↦ T, then T ↦ K.
No letter can be encrypted by itself because electricity can not travel the same way back, which results in a reduction of encryption alphabet.

Also, history has shown that Enigma had another security problem: the contradiction to Kerckhoffs' principle "The security of a system should not depend on the privacy of the algorithm. It should only be based on the secrecy of the key.".

Enigma got it wrong because:

Security of Enigma depended on wiring of rotors,
Wiring was part of algorithm and not part of key, and
Wiring never changed from 1920s until 1945.

(source: https://www.infsec.cs.uni-saarland.de/teaching/SS07/Proseminar/slides/maurer-Enigma.pdf)

Since you're asking about today, I will therefore assume the fact that we know about the internal workings of Enigma since WW2.

Based on your assumptions and the known Enigma weaknesses, one of the well-known attacks to break Enigma is using the Index of Coincidence (short: IC), a statistical measure of text which distinguishes text encrypted with a substitution cipher from plain text.

Let's put Enigma into the formula: $IC = \frac{{\textstyle \sum_{i=0}^{25} } f_i(f_i-1)}{n(n-1)}$ where $x_1,...,x_n$ is the string of letters and $f_0,...,f_{25}$ the frequency of the letters in that string. For a random string that boils down to $IC ≈ 0.038$ and for a natural language $IC ≈ 0.065$.

I'll skip the details and simply give you some raw numbers while summing up how IC can be used for an attack on Enigma:

Find the rotor order
Trying all rotor orders and positions searching highest IC takes $60*26^3 ≈ 2^{20}$ operations.
Approximation to rotor start positions
Starting with a rotor order from step $1$ and $w$, trying all rotor positions and ring positions for 1st ring only, again searching highest IC. That takes $26^4 ≈ 2^{19}$ operations.
Find ring and rotor start positions
We have the 1st ring and 1st rotor start positions, approximations
for other rings and starting positions from 1 and 2. First search positions for the 2nd ring and rotor, then use the same procedure for last remaining rotor. This will take $26^2 ≈ 2^9$ operations.
Find the plug settings
We have the rotor order, position and ring positions. Now we can use IC as statistical test again, deriving of the trigram information of the underlying language.

  how fast/ how easily could they do it?

Generally, that's hard to say without having any specific information about available resources you are assuming an attacker would have.

A single computer might take a little while depending on how old it is (in terms of CPU power), but things like distributed networks will probably make you cry by successfully attacking Enigma in a few blinks of an eye. If you happen to have any specific computing setups in mind, you can take the provided number of operations mentioned above and simply do the related maths to calculate the related speeds.

And last but not least - to answer the title of your question too...

  How cryptographically secure was the original WW2 Enigma machine, from a modern viewpoint?

Totally insecure. The weaknesses described above provide ample proof to that claim.

On the other hand, we can't really compare today with the situation during WW2. They used machines that were mainly mechanical (eg: Bletchley Park Bombe), while we have computers with powerful CPUs. WW2 cryptanalysts  would probably have killed to get their hands on such a futuristic "wunder Maschine" which we use to do simple things like surf the internet.

Nota Bene: If you're interested in the maths behind Enigma, you might want to check on "The Cryptographic Mathematics of Enigma" by Dr. A. Ray Miller, The Center for Cryptologic History – National Security Agency.

The above publication certainly provides more insights related to the internals and maths behind Enigma than the usual NSA "freebee" stuff (PDF) which tends to restrict itself to talking about the history instead of cryptography.

Edit: The last two links are now offline and seem to have been removed from the nsa.gov website. As they are still available via web.archive.org, the links have been updated point there.


Key Exchange vs Key Encapsulation From what I understand, the steps of a key exchange protocol are

Alice and Bob each encrypt something using their public key and private key and send the result to each other
Alice and Bob each do some mechanism with their private key and the result sent by the other
They should agree on the secret.

Key encapsulation is

Alice generates a secret key and public key and sends the public key to Bob.
Bob generates his own secret key and encrypts it using Alice's public key. He sends the result to Alice.
Alice decrypts the result using her private key and ends up with Bob's key.

Is this correct and if not, could someone clarify which parts I am misunderstanding or missing?

Looking at the Known Answer Tests for NIST PQC KEM Submissions, when a seed is provided, each algorithm returns the secret key, public key, cipher text, and shared secret.

Is the shared secret Bob's private key and the cipher text what Bob sent to Alice? If not, how does the terminology work? How can the seed guarantee the correct public/secret key generation?

Key exchange: I'll use ECC as an example. Alice and Bob generate ephemeral key pairs and sign their ephemeral public key with their static private key, and then send their signed ephemeral public key to each other.

Both parties receive the others signed ephemeral public key and verify it using the others static public key, stored by a CA or in a PKI. Now they combine their own ephemeral private key with the other's ephemeral public key, using EC Point Multiplication (for this example). Now they both have a shared secret, as both multiplications give the same result.

This is then run through a quick hash like SHA2/3 into the correct length for symmetric encryption. For example with AES-256, the shared secret goes through SHA(3)-256 to get a key of the correct length.

Key encapsulation: I'll use the RSA KEM for this example. Bob knows Alice's public key $(e,n)$. He creates the symmetric key $M$ from a CSPRNG , where $0<m<n$, and converts it into a symmetric key with a KDF ie symmetric key $M=KDF(m)$. The Ciphertext $$C = m^e (mod \ n)$$ This is transmitted from Bob to Alice, and she can decrypt it by computing $$P = m^d (mod \ n)$$ Alice now has $k$, and derives the symmetric key $M$ with $M = KDF(m)$

Side note: I've seen that you tagged post quantum cryptography, so you could use NTRU for KEM; ECC and RSA can be broken with a powerful enough quantum computer running Shor's algorithm. The NTRU KEM works differently to the RSA KEM however. I'm not familiar with a quantum safe version of the ECC key exchange, though I'm sure one exists.


Is it ok to store the plaintext hash of encrypted data Is it ok to create and store the hash (unkeyed hash function) of a plaintext before encryption or does it lead to vulnerabilities?
If it is ok are there requirements for the used hash function and encryption algorithm?

Important to mention is that the hash should not be used for integrity checks or something like that.

This will be less secure than storing only the encrypted data or storing also the hash of the encrypted data.

In your scenario, you give more options to an attacker, because it is possible to attack both the cryptosystem and the hash. For instance, think of an attacker that found a preimage attack to the hash...

Moreover, since the hash is deterministic, it allows some kinds of inference attacks, because if two stored hashs $h_1$ and $h_2$ are equal, then, they are probably hashs of the same message. This is the reason we use probabilistic encryption schemes.


Cryptographic hasing functions init-update-final Does anyone care to explain what is the idea behind the init-update-final functions of cartographic hash functions (e.g. SHA*_Init, SHA*_Update, SHA*_Final from OpenSSL)?

Many libraries, like Java and OpenSSL, provide an Init-Update-Final model for transformations. It's used to minimize memory requirements.

Let's suppose all you have is a single shot SHA-1 function which requires the input to be available.

Then, for example, with a 1GB RAM system, how would you hash a file of 2 GB ?

You simply cannot as the SHA-1 function will require to have the whole input in RAM and you simply can't do it.

What you can do, instead, is to call SHA_Init, read 1MB of the file into RAM, SHA_Update that 1MB, read the next 1MB of the file (overwriting the previous one), call SHA_Update on that 1MB, repeat 1998 more times and then call SHA_Final.

This requires only 1MB RAM to hash a 2GB file.


Cryptographic algorithms compromised and alternatives? After Edward Snowden's release of top secret information we have seen clues that the NIST certified crypto-algorithms like AES might be compromised.

  Although not as fast as AES, we prefer Twofish because we are suspicious of anything NIST certified (we explain why here.) We’ll also go with the Whirlpool hash algorithm for the same reason (see the full documentation for more info on this subject)

From https://www.bestvpn.com/blog/18538/veracrypt-how-to-basics/

Also from another article on the same site: https://www.bestvpn.com/blog/4147/pptp-vs-l2tp-vs-openvpn-vs-sstp-vs-ikev2/.
If you scroll down to the NIST section they discuss this built-in back doors in NIST certified crypto-algorithms with different sources of evidence.

So they recommend using Twofish, but compared to AES, Twofish algorithm strenght isn't as good as AES. Also AES is "pretty" post-quantum computer algorithm proof, but is Twofish too?

My question is: in for an example Veracrypt you can choose between different algorithms. Should you pick AES, Twofish, AES(Twofish) or Twofish(AES). Also if you should choose Twofish, is it post-quantum computer algorithm proof? Even a little?

Should you pick AES, Twofish, AES(Twofish) or Twofish(AES)?

You should pick AES.

  Also if you should choose Twofish, is it post-quantum computer
  algorithm proof?

There's no current publicly known attack that breaks Twofish any faster than Grover's algorithm (using quantum computers), so it is as secure as AES in that regard. However it is likely much more difficult to securely implement Twofish than it is to securely implement AES (due to the large secret S-Boxes) and the last meaningful cryptanalysis result against Twofish is more than one and a half decades old because research focused on AES.


Revoke a GPG key using previously generated revoke certificate after renewd (change expiration date) I have few sub-questions

Do secret keys get expired, or just the public key gets expired?
Do I have to back up the master sec key each time I renew it?

For an example:

Let's say I generate gpg keypair and ssb for signing, encrypting, and a revoked certificate. And I backup the master sec key, revoked certificate and place them somewhere safe, and remove master sec from the key-ring.

Then the pub and sub keys get expire so, I get a copy of master sec key from the safe place and re-import it to the key-ring for the sake of key renewing process. After that, can I just safely remove and delete that copy of master sec key from the key-ring? If so, is master sec key that I saved at the first place aware of these new renewed pub and sec keys, shouldn't I re-backup the sec key after using it for renewing process? and replace to the old sec key that I saved in the safe place?

What would happen If I generate a new ssb key for authentication after that renewal process? Is my master sec key that I saved in the safe place at the first aware of the newly generated ssb key? If so, how is my revoked certificate affect to these new keys? (new ssb keys, and renewed pub keys)
Do I have to re-generate revoke certificates each time after I renew the secret key, or can I just use the previously generated revoke certificate after renewing the key?

For an example:

First I generate a seckey and a revoked certificate, then I generate ssb key.

Then sec and ssb both get expire and I renew it for a next 6 months, then I lose my master sec key, so Is my revoke certificate still valid? can I revoke the key by importing the revoked certificate?

For 3:

I did a simple test and the results showed that after revising the private key, the old revocation certificate can still revoke the gpg public key.

Test steps:

Delete a uid
Export private key
Import the old revocation certificate, the public key is revoked


Brute-force attack on OAEP Assume $M_1$ is $\operatorname{OAEP}$ padded and encrypted and the ciphertext is 1024 bytes as an example. If an adversary somehow gets around the encryption and manages to get half of the bits of $\operatorname{OAEP}(M_1)$, and although infeasible, assume that it was somehow possible to loop through all combinations of the missing 512 bytes. At some point the $\operatorname{OAEP}$ decode will succeed and give $M_1$.

Will the decode operation succeed more than once to give other plaintexts, and if so, how many times?

Skipping over the OAEP details, considering only the probability that a random ciphertext will have a valid all-zero pad.

For a $t$ bit pad, the random probability is $1/2^t$. Brute forcing 512 bytes or $512\times8$ bits will result in on average $2^{512\times8}/2^t$ valid padding. Assuming a $128$-bit zero pad this is$\dots$

$$3.069183e1194$$

As you said this is impossible. Information theoretically we know the message is one of the $2^{512\times8}/2^t$. If you have any additional structure of the message, you may reduce the candidates further.

Another way to look at this is the birthday bound. Where it'll take on average $2^{t/2}$ random samples to find a valid padding.


3DES Modes EED or EDE? Can we use EED with 2 keys $(k_1, k_1, k_3)$ rather than EDE $(k_1, k_2, k_1)$? We measure the strength of DES by the effort (in terms of the number of tries) in finding some $k_1$ & $k_2$ to match a known plaintext and ciphertext pair.

Will EED have the same strength as EDE? Which one is stronger?

Concerning $(k_1, k_2, k_1)$ vs. $(k_1, k_1, k_2)$

$(k_1, k_1, k_2)$ can be split into $(k_1, k_1)$ with $2^{56}$ possibilities and $(k_2)$ with $2^{56}$ possibilities, so the meet-in-the-middle attack has cost $2^{56}$.

$(k_1, k_2, k_1)$ can be split into $(k_1, k_2)$ with $2^{112}$ possibilities and $(k_2)$ with $2^{56}$ possibilities or into $(k_1)$ with $2^{56}$ possibilities and $(k_2, k_1)$ with $2^{112}$, so no matter how you split it, the attack costs $2^{112}$.

=> $(k_1, k_2, k_1)$ is much stronger than $(k_1, k_1, k_2)$

Why is triple-DES using three different keys vulnerable to a meet-in-the-middle-attack?

Concerning EDE vs EED

Choosing encryption vs. decryption for the three steps has no effect on security.

By setting all keys to the same value you can emulate DES using 3DES with EDE and EED but not with EEE. Not sure if EDE offers any advantages over EED, except looking nicer due to being symmetric.

Why do we use encrypt-decrypt-encrypt (EDE) in 3DES, rather than encrypting three times?

Encryption-Decryption-Encryption


What does it imply if in RSA pow(m, e, n) is same as the m So, Let's assume we have n which is made up of 2 strong primes which cannot be factored & e which is textbook value of e that is 65537.

Now, I have a message1, first I convert that into decimal and then do

(msg1^e)%n and this turns out to be exactly same as random1 . Now, I generated a lot of messages and performed the encryption same way and I found one of the message (let's call it msg2) generates same output after encryption as it is in plain.

So, usually RSA formula is c=pow(m,e,n) . In my case pow(msg2,e,n) gives output exactly same as msg2. That implies for an edge case of a message the encryption provides same ciphertext as plaintext.

Does this means, that this RSA system for n is broken/buggy?

Not necessarily.  With the (not so strong) primes p=211 and q=311, we have n=65621.  Using e=157, I came up with the following messages that encrypt to themselves:

1
5908
5909
11197
11817
17105
17106
23013
23014
28922
36699
42607
42608
48515
48516
53804
54424
59712
59713
65620

Finding such a message with strong primes would be extremely difficult, but I can't think of a reason it couldn't occur.

At this point I don't have an explanation for the consecutive numbers in the list.


Are IVs and salts the same and usable for each other uses? I'm new in the crypto world and I've just discovered PBKDF (I used to use typed passeword as symmetric key).

When using some crypto mode, you're required to generate an IV which must be completely random and not predictable, the best length is the length of a block size. PBKDF (and hashing functions in general) needs a salt which must also be random, I don't know the best length for a salt.

I'm thinking that an IV and a salt seems to be exactly the same but with a different name, they're random and are made to avoid getting the same output for the same input(s).

So I wonder if it would be secured to generate an IV, derive the password with this IV as salt, and use these to encrypt data?

No.

A salt for a PBKDF is to prevent a bruteforce search to be able to target multiple passwords at once. You generally choose one salt for a password per user, and store it. So you do not keep generating salts, only when the password is set/changed.

The role of an IV depends strongly on the mode. In some modes it is only required for semantic encryption (the same message encrypted twice is still different). For other modes such as CTR it's absolutely required for security. In general the IV should change for every message, which is the most important difference.

Note that "generate an IV which must be completely random and not predictable" is not always true. For example the IV, or nonce, for the ChaCha cipher does not need to be random nor predictable - just always different.


How to submit a new method of encryption? I came up with a truly new method of applying modulo-2-addition encryption function in stream ciphers which is inspired by a mechanism used to prove a mathematical theorem. How can I determine whether my method is cryptographically correct and considerable? If so, how can I officially submit or formally register it in my name? And finally, can I make money thorough this method just by selling it to an encryption company or organization?

EDIT

Hi everyone, thanks for all answers and comments. It seems quite heartening.
I know that modulo 2 operation is equivalent to XOR (exclusive OR operation in Boolean Algebra) gate in electronics. As you all know, the overriding issue concerning the security of stream ciphers is how to generate truly random key streams, and actually my newly-inspired method mainly deals with this issue. I mean this method can produce or generate random key streams in an entirely new way for either stream or block ciphers. I finally decided to publish my workings on this topic very soon for gaining cryptographic credits rather than just making money.

Write documentation / a paper:

An overview

What kind of cipher it is and an outline of how it works.
Advantages of your algorithm

Why should somebody use it, over existing designs? Possible advantages include:

A simple and elegant design
Being faster or cheaper on certain platforms
Having features or security properties other designs lack

Specification of the cipher

It should be possible to implement your cipher from the specification, without looking at the reference implementation.
Security claims

There are many security definitions, which of those apply to your design?

For a block cipher you might aim for a strong pseudo-random-permutation. For a stream cipher you might claim that its output is indistinguishable from truly random data. Make sure to use the standard names and definitions for those properties, not just an informal description.

One important purpose this section has is to show that you're aware of and aiming for strong modern security definitions. Too many beginners argue that their cipher isn't broken because the attacks don't demonstrate full plaintext recovery in a ciphertext only scenario.
Benchmarks

How fast is your algorithm on different platforms? For symmetric algorithms this is typically given as CPU-cycles per byte (cpb). Make sure to disable Turbo Boost on Intel CPUs and to mention that you did so.
Design rationale

Why does your algorithm look like it does?
Your own crypto-analysis, if you did it.

For example you might describe how to break a round-reduced version of your cipher
Test vectors

Example tuples containing key, plaintext and ciphertext, to help implementers check if their implementation is correct.
Typeset it properly, using LaTeX. People will see if you did it in Word and that will leave a bad impression.

Implement it:

A reference implementation which focuses on clarity
An optimized implementation, which you use to determine the performance of your algorithm

For symmetric algorithms I recommend including a C implementation.

Now the hard part is getting somebody to look at it:

If there is an upcoming competition, submit it.
Upload the paper to https://eprint.iacr.org.
Submit it to a peer reviewed conference or journal.
Make a name for yourself, for example by attacking other people's ciphers

You won't make any money selling or patenting a cipher. There are too many good and free algorithms available. Even great designs like OCB mode weren't adopted due to being patented.


Role of lHash field in RSAES-OAEP The RSA encryption padding of RSAES-OAEP has a lHash field set to the hash of a label. That label is typically the empty string, or some public description of the intended use of the message.

Does the lHash field play some role in the security (confidentiality of M under IND-CCA2 or similar), or security reduction to RSA? Does that depend on lHash being checked on decryption? On lHash not leaking on decryption of malformed cryptograms?

Would removing lHash and accordingly increasing the maximum size of M harm security?

Update: Squeamish Ossifrage answers, essentially by yes. Accordingly, PKCS#1v2.2's EME-OAEP decoding wants lHash to be checked, as well as other padding, and that it be done in constant time:

  Care must be taken to ensure that an opponent cannot distinguish the different error conditions [on 00, lHash, PS, 01], whether  by  error  message or timing, or, more generally, learn partial information about the encoded message EM. Otherwise an opponent may be able to obtain useful information about the decryption of the ciphertext C, leading to a chosen-ciphertext attack such as the one observed by Manger [35].

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, essentially shows that decryption implementations leaking if the leading 00 is present can be converted into a decryption oracle.

I believe $\mathit{lHash} \mathbin\Vert \mathit{PS} \mathbin\Vert \mathrm{01}$ serves the rôle of the zero-padding in $s = (m \mathbin\Vert 0^{k_1}) \oplus G(r)$ from the formulation of RSAES-OAEP in the standard reference for its security reduction, on p. 5.  Verifying that it matches exactly what you intend is critical for the security reduction to work, in particular where it figures into Game 6 on p. 14, to provide the bounds involving $k_1$ in Theorem 1 on p. 9.

Using a label perhaps provides some kind of domain separation for different applications, in case, e.g., two application's entropy sources are both broken.


Lack of usage of secrets in ZK Bitcoin ownership proof I read the paper "Provisions: Privacy-preserving proofs of solvency
for Bitcoin exchanges" which is available for download on http://crypto.stanford.edu/~dabo/pubs/abstracts/provisions.html and have some questions about it. For discussing the single question I want to address here, having read the entire paper is not necessary as it is limited to what the authors describe in section 4.1.

The authors claim:

  Now, to prove that $Z_\text{Assets}$ computed in (2) is a commitment to (a lower bound of) the exchange’s assets, the exchange proves knowledge of quantities:

  $s_i \in \{0, 1\}$ and $v_i, t_i, \hat x_i \in \mathbb{Z}_q$

When you read the definitions of these symbols right before that claim, you notice (or at least I think I did) that none of these values require knowledge of any secrets to be computed.

$x_i$ describe the private keys, $y_i$ the public keys. As $y_i = g^{x_i} \forall i \in [1, n]$, knowing the values of $x_i$ is not required to commit to the values of $x_i \cdot s_i$ when using Pedersen commitments.

I don't see how any secrets were used when computing the values the exchange is going to prove ownership of and therefore not how proving knowledge of these values proves knowledge of the $x_i$. Yet in their protocol 1 (page 9), these values constitute the entire input of the prover (apart from the publicly available data on the blockchain).

As this is a published paper, I assume that they're right with that this is sufficient and I'm wrong. But what am I missing?

Yes, $\Sigma$-protocol is described at section 4.1 of the paper referenced. This is a 3-move protocol, with the last message "response" computed from second message "challenge" and a secret. In particular, 4 responses are computed at step 1(d) of the protocol presented. Coin private keys $x_i$ held by exchange is the input for computing the last response, selected by binary mask $s_i \in \{0, 1\}: \; \hat x_i = x_i s_i$.


What is keyId in Signal Protocol JavaScript library? I'm trying to implement the Signal Protocol JavaScript library for a school project. On this page, the generatePreKey function takes as parameter a keyId. I can't find what that is in the specifications. Can somebody tell me where do I have to get it from or if it's just a random number I have to generate myself?
KeyHelper.generatePreKey(keyId).then(function(preKey) {
    store.storePreKey(preKey.keyId, preKey.keyPair);
});

Usually you use these identifiers only for permanent storage. Those keys you will have to look up again, and normally you'd do that using a unique identifier (e.g. a label). Those are generally not random, and if they are random, then they should be 128 bits or higher to avoid collisions (i.e. two keys possibly sharing the same number).
After some advanced Internet searching, I found the following tidbit:

After the account is created, the user can upload the keys to the server. The identity_key and public_keys are both Curve25519 Base64 encoded public keys with a size of 33 bytes. A client will publish 100 pre-keys when registering, see figure 4.2, however, this is not a restriction. Along with these keys, a signed pre-key will be sent with a signature over the public_key. The key_id is an identifier of 3 bytes.

After that there is a code example that clearly shows it is a 24 bit sequential number, presumably unsigned, so you can supply it a non-random number [0, 2^24).