Is AES + RSA Encryption of individual log entries with the same key but different IVs secure? I have sensitive logs that needs to be encrypted using AES-256 and RSA. Due to the nature of the logging system, the entries (rows) need to be encrypted one-by-one.

My approach was to reuse the same AES-256 key and IV (and also the same RSA pubkey) per run of the application. I would save the unencrypted IV and the RSA encrypted AES key together with each log entry. I figured out that this is not secure as two identical log entries in the same application run would yield the same cipher text, making inference possible (please correct me if this is not true).

What I'm thinking of now is encrypting each log entry using the same AES key but with different IVs . This will remove the need to perform the expensive RSA encryption for each log entry, while not allowing inference weakness. Is this approach secure?

Yes that would work; that's exactly what the IV is for. In this case the IV is really required to obtain confidentiality over multiple log entries. Note that public key operations are relatively fast for RSA (but nowhere near so fast as AES encryption, generally).

Mind though that there are many other possible leaks of information: size of ciphertext, time of logging, change of encrypted AES key (i.e. change of run). If those leak any info depends on you.

Also note that encryption by itself does not allow to detect change, duplication, removal etc. So you should make sure that this is acceptable to you as well. Signatures generation and sequence numbers can be part of a solution to create a cryptographically secured, auditable log file.


Prove you computed $hash^r(input)$ for some cryptographic hash function What is the most efficient way to prove that a person computed $r$ rounds of some cryptographic hash function (ex. SHA256) on an input? Specifically, I'm trying to optimize (1) the running time of the verifier and (2) the size of the proof (in that order).

The trivial solution seems to be to show all $r$ hashes, where $v_i = hash(v_{i-1}), \space \forall i \leq r$, but this seems very space inefficient.

Though a formal proof eludes me at the moment. I believe I can make a compelling argument this can't be done.

If what you want is for a prover to supply the output and some extra evidence. And the verifier should be able to convince himself with high probability it is correct with effort orders of magnitude less then computing the hash himself.

Even if the prover provides the full chain, a forger will be able to swap just a singls hash and compute any additional stuff on the forged chain. Other then checking the single forged hash( 1 in r) there is no way for the verifier to catch this. If the verifier checks even half of the steps at random that still gives the forger a 50% chance of succeeding(going undetected). You presumbly want the verifier to check only a handfull of hashes but that would give the forgery excellent chances of going undetected.

In order to get high confidence the verifier would have to do almost all the work of computing the r hashes himself.


CPA Secure Chosen plaintext scheme The example for IND-CPA secure schemes given is generally:

for a random r,

  Enc_k(m) =(r|| E_k(r) XOR m) where E is a PRF

But does the role of r and k really matter--i.e. isn't this equally secure?

  Enc_k(m) =(r|| E_r(k) XOR m) ?

No, it is not equally secure.  Consider an instantiation where $E$ is instantiated with AES, and where the message is always 128 bits long.  Can you find an attack on this particular version of the scheme?

This smells like homework (I'm guessing?), so to avoid ruining the problem and give you a chance to learn from it, I'm just going to leave it at that.  I think you'll find the process of working out the rest of the details to be instructive: for instance, it might help you understand IND-CPA security a bit better and how a scheme can fail to meet this security definition.


Is it possible to permute a binary vector obliviously? Lets say A has a binary vector of length n, B has a permutation matrix of size n. Is there a way for B to permute A's vector so that A only learns about the result of permutation and B does not learn about the original vector?

Using an encryption scheme that is rerandomizable (such as ElGamal for example), A can just send n ciphertexts encrypting her values, then B shuffles those ciphertexts and rerandomize them. B never learns anything and the rerandomization destroys information about the original ciphertexts so that A cannot trace back the permutation.


why inverse in diffie-hellman protocol will not give same value? Security of diffie hellman protocol is $K=g^{ab}$.if sender want to calculate value of $b$(given $a$) he can do $g^{{{ab}^b}^{-1}}$(where K=$g^{ab}$) which will give $g^{a}$ as we are cancelling value of $b$ by finding its inverse. but it is not cancelling the value of $b$ and not give the output $g^a$. can any one explain why, while in ElGamal decryption in same way give plain text ($m=c2 *g^{ab}^-1$)

In DH if you want to compute $g^a$ from $K$ you have to know $b$ (which the legitimate receiver of $g^a$ clearly knowns, so this does not really make sence). This party can compute the inverse of $b$, namely $b^{-1}$, and then compute $g^a=K^{b^{-1}}$. Note that this is not the same as $(K^b)^{-1}=(g^{ab})^{-1}$ (as I will discuss below). But that is not related to the security of DH.

The security behind DH is the computational DH problem, i.e., an eavesdropper learning $g^a$ and $g^b$ cannot compute the shared secret $K=g^{ab}$. But clearly the two parties doing the exchange can, as they hold $b$ and $a$ respectively. So for instance the party holding $a$ and received $g^b$ can compute $(g^a)^b$. Both parties holding $K$ can then use this shared secret to derive some symmetric key for encryption of any messages they want to communicate.

Note that in ElGamal (which may be seen as a non-interactive DH using the public key as static DH key of the receiver) you have $(c_1,c_2)=(g^k,mg^{xk})$ as a ciphertext and $h=g^x$ as the public key and $x$ as the secret key. This means that you encrypt a message using the DH key. Then you decrypt as $m=c_2\cdot (c_1^x)^{-1}$. Note that $(c_1^x)^{-1}=(g^{xk})^{-1}$ which is the inverse of $g^{xk}$ and will cancel out in the decryption as $g^{xk} \cdot (g^{xk})^{-1}=1$.

Note that nobody would use ElGamal to directly encrypt messages, but one will use hybrid encryption, i.e., use ElGamal to encrypt a random symmetric key and use the symmetric key to encrypt the messages.

Why is it a different thing to compute either $(g^{ab})^{b^{-1}}$ or $((g^{ab})^b)^{-1}$? Well, I think your problem is that you should write the parenthesis as I have done it above, since these are two different things.

Now, $K^{b^{-1}}=(g^{ab})^{b^{-1}}=g^{abb^{-1}}$, i.e., here you exponentiate $K=g^{ab}$ with the element $b^{-1}$ (the invese of $b$) and since $bb^{-1}=1$ you obtain $g^{a}$. In the second case you have $(K^b)^{-1}=((g^{ab})^b)^{-1}=(g^{abb})^{-1}$, i.e., you exponentiate $K=g^{ab}$ with $b$ and then compute the inverse of the resulting element, which does not give you $g^a$ as a result, but $(g^{abb})^{-1}$ which is not equal to $g^a$.

For a concrete setting, if you work in the group ${\mathbb Z}_p^*$ with $p$ being prime and use a generator $g$ of  ${\mathbb Z}_p^*$, then arithmetic is done modulo $p$. So inverses of elements, e.g. $(g^{ab})^{-1}$, are computed in ${\mathbb Z}_p^*$. But, be careful, operations on elements in the exponent of $g$ ($g$ generates the group of order $p-1$), e.g., computing $b^{-1}$ (if you want to compute $(g^{ab})^{b^{-1}}$) are done modulo $p-1$. This clearly requires that $b$ is co-prime to $p-1$, i.e., $\gcd(b,p-1)=1$, that the multiplicative inverse $b^{-1}$ of $b$ exists.


Would Triple DES-X with 7 keys be much slower than standard Triple DES? Since a single hardware pass of an XOR with a 64 bit key is very fast, would Triple DES-X using seven 64 bit keys used in the following manner be virtually identical in terms of code size, memory consumption, and execution speed to 3DES?

You have four 128 bit keys and three 64 bit keys.

You take a 128 bit block of plaintext.

You break it into two 64 bit block-halves in the following columnar transposition based fashion.

The bits at even indexes go into one half and the bits at odd indexes go into the other half, so the halves are intermingled.

You take the first 128 bit key and XOR the entire 128 bit block.

You take the first 64 bit key and encrypt each 64 bit half-block with DES independently of each other.

You treat the result as that round's 128 bits of ciphertext and repeat the 128 bit columnar transposition, importantly inter-mixing both half-blocks again based on odd-even indexing.

You take the second 128 bit key and XOR the entire block as one.

You then take the second 64 bit key and DES both 64 bit half-blocks independently.

You then repeat the columnar transposition-XOR-DES process for the third time.

Finally, you XOR the entire 128 bit block with the 7th 128 bit key.

Additionally, would it be significantly stronger?  Would it still suffer from the same block size based vulnerability of DES-X?

Well, there's a fairly obvious CPA attack that uses circa $2^{34}$ or so chosen plaintexts, and about $2^{120}$ trial DES operations. Because of that, the cryptographical strength is not significantly higher than standard 3DES.
As for code size and memory size, it'd certainly be larger than standard 3DES (you do more, and have more keying material lying around) - but it's hard to make a guess as to how much.
The scheme would likely be somewhat slower than 3DES. For 3DES, you can omit the intermediate IP/FP permutations between DES operations. In the scheme you've defined you would have to have them in there, and you would have to perform the columnar transposition as well. Now, it looks plausible that you could combine the FP/transpose/IP between DES operations into a single operation, which would reduce the cost somewhat, but it still wouldn't be as cheap as omitting them entirely.
On the plus side, this is effectively a 128 bit block cipher, so you do avoid the vulnerabilities that come with a 64 bit block size.


SHA-256-based stream cipher Can anyone comment if the stream cipher described  here is safe? The author claims it to be unbreakable, but does not provide any evidence or proof to support this. For completeness, I have reproduced the algorithm below.

Encryption routine (Alice$\to$Bob)

Calculates a shared secret:
$s=$Curve25519(Alice_private_key, Bob_public_key)
Calculates N seeds $s_1,\dots,s_n$:
$$s_0 = \mathrm{SHA256}(s);\quad s_n = \mathrm{SHA256}(s_{n-1})$$
Calculates N keys $k_1,\dots,k_n$:
$$k_n = \mathrm{SHA256}(\overline{s_n})$$
(where $\bar{s}$ is the bitwise compliment of $s$)
Encrypts the plaintext via xor:
$$c_n = p_n \oplus k_n$$

Upon receipt Bob decrypts the ciphertext by repeating the identical steps, except he derives the shared secret $s$ using his private key and Alice's public key.

Some brief thoughts:

Shared secret Generation:
$$s=E_a(B)=E_b(A)$$
The shared secret is generated by encrypting the other users public key with your private key. This is effectively an ECDH step, which is very reasonable, and one of the key aims of C25519$^{[1]}$.

Key Generation:
$$s_0=\mathrm{SHA256}(s); s_i=\mathrm{SHA256}(s_{i-1})$$
First, using the definition above, they generate seeds. This doesn't seem an unreasonable way of expanding one seed into many.
$$k_n = \mathrm{SHA256}(\overline{s_n})$$
Yes, I'm happy that the $k_n$ should look pretty random.

Xor combinator:
This isn't at all unreasonable, and most stream-ciphers use this technique for combining their stream with the plaintext.

Overall?
Assuming the relation required in the first step holds, which I'm unsure and sceptical about, then first impressions are that this scheme should be ok. At the end of the day it's basically using ecdh to seed a $\mathrm{SHA256}$-based stream cipher. Cryptographically, this means it will at best have the security bounds from the weakest of those primitives. Whilst this is certainly not genuinely 'unbreakable', it should be computationally secure. However, there are some far more significant issues with it that won't be addressed by 'is it secure'? I'll note some of them now...

Key reuse
As noted by the original author, this scheme only generates a single key-stream, seeded by the two public keys through the ECDH step. The dangers of reusing an xor keystream are severe - it leaks the xor of the plaintexts, which is often sufficient to allow a total break:
$$c_a=m_a\oplus K;c_b=m_b\oplus K \implies c_a\oplus c_b = m_a\oplus m_b$$
This could be resolved by adding a nonce to the original step, which is arguably the biggest issue of the scheme. That is,
$$s_0=\mathrm{SHA256}(s||N)$$
Where $N$ is a nonce, although it does not have to be unpredictable.

Why should I care?
This is the biggest issue with most homebrew schemes. Unless a scheme can demonstrate some advantage over the other schemes in existence, then why on earth wouldn't I just use those? In this case, it won't be particularly quick given the number of SHA calls made, won't be very nice to parellelise due to the recursive nature by which the stream is generated, and after all that it's just an xor-based stream cipher. See this question for why you should always think at least 3$^{[1]}$ times before using an encryption algorithm rather than an authenticated encryption algorithm.

[1]: Thanks to DrLecter for clarification on this point.

[2]: In the old days, people used to be told "think twice before doing $x$". However, as we are all aware, lots of people still did $x$. As such, I'm pushing for raising the number of "think's" required. Obviously as a cryptographer I'd like to go for at least 64-bit security, but for now 3 will have to do.


Why are the IV (constant) values fixed for HMAC/SHA? Why do HMAC/SHA IV's have a fixed value? I refer to the arbitrary H constants which are included in the algorithm prior to any data being fed in.

Why aren't they exposed to the user, so one can decide on an IV and modify it accordingly (for example, in java they are provided at hash function specification, instead of being supplied by the user at init)?

How does modifying these IVs affect the algorithm?

The hash IV values aren't provided to the user for the simple reason that they are not required.

The whole idea of a hash function is that you get a practically unique value that is irrevocably linked to the input message without exposing any details of the message. Using an IV would go against this idea: it would give you a different value each time the IV is changed.

This is not the case for ciphers, which require randomization to be CPA secure. If they wouldn't then repeating messages would be identical for the same key. You could for CBC of course start with an in the plaintext, but that would mean that the ciphertext would always have to be expanded. This could be wasteful as there is no requirement that the IV is send with the ciphertext.

This shows another reason why not to include an IV in the interface of a hash function. If a unique value is required you can simply include it with the message. It will only be included in the hash calculation rather than expanding the output of the hash.

Now there are actually reasons where having different constants is beneficial.

One is when a shortened hash value could leak information about the full or less shortened hash. For instance, if an adversary has a SHA-512/256 hash then the adversary would also have the first part of the SHA-512/384 or SHA-512 hashes. For that reason these hashes do actually have different constants.

Another reason is when hashes are used 1. with the same input and 2. for different purposes. In that case it could be beneficial to have some differentiating bits included in the hash. This is a scheme that is actually present in SHA-3, where a KMAC algorithm and the SHAKE functions use a few different bits than the raw hash algorithm.

HMAC doesn't have this kind of protection. It does however use the key in two different ways so you'd have to create a pretty weird scheme to ever get into trouble by hashing a key, message and duplicate a HMAC result.

Modifying these constants should not affect the algorithm at all. If you however use your own constant values then people might get suspicious that you know more about the algorithm than themselves. You're better off using the original constants as "nothing up-your-sleeve" values.

If you need additional input of some kind, just make it part of the message, making sure that the encoding of the message is canonical. That is, make sure that different fields in the message can be distinguished, e.g. by prefixing the length before each field.


Encrypted Hash vs MAC I (believe I) am aware of the general difference between a hash and a MAC; the former is used for integrity and the latter for integrity and authentication as it also takes a secret key as an input in addition to the message.

But what if I hash the message, encrypt it using the secret key (one that is separate from the one used to encrypt the message), and send that instead of the MAC? Does it not hold the same properties as sending a MAC?

In both cases, we input a message and a secret key to compute an encrypted hash / MAC, so it seems like both integrity and authenticity are provided.

If not, in what way would an adversary be able to break the authenticity of a scheme that sends, along with each encrypted message, an encrypted hash (using a separate secret key)?

Edit:

As mentioned in a comment below, this has already been answered here and here but I am unable to mark it as a duplicate as it is on a separate StackExchange.

Assuming you mean EK1(m) || EK2(H(m)) or EK(m || H(m)), it is not an approved MAC scheme in any standards and may have issues. Instead, you should probably use an HMAC, which involves taking the message and the key and hashing them together. An HMAC is defined by RFC 2104 as HMACK(m) = H((K ⊕ opad) || H((K ⊕ ipad) || m)) where opad and ipad are constants. An HMAC is a keyed hash function, which means the digest depends on both the message and the key.


How is original plain text length reconstructed after decryption under RSA? So far I know the ciphered output length of RSA equals the modulus N.

If I have only a small block of data significantly smaller than N, is the rest of the input to RSA just zero padded?

How can deciphering be unique then?

For instance if I get back as a plaintext

P="XXXXXXXXXXXX000000000000000000000000000000000000000000000000000000....",
how can I know, how many zeros had been in the original plain text:
It could be

"XXXXXXXXXXXX" or also "XXXXXXXXXXXX000000" as well as "XXXXXXXXXXXX0"

All those plaintexts would give the same ciphered text after padding.

Most importantly, note that for almost all practical applications textbook RSA should not be used to encrypt something. It does not yield an encryption scheme which provides the guarantees one would expect in practice. In particular it does not even provide security against chosen plaintext attacks (IND-CPA).

Instead one would use some padding scheme such as optimal asymmetric encryption padding (OAEP).

Despite the fact that the usage of RSA you describe should not be used in practice, you would typically not pad "XXXXXXXXXXXX" as "XXXXXXXXXXXX000000....". Instead, you would encode "XXXXXXXXXXXX" as a number between 1 and N and use this upon encryption (i.e., you only implicitly prefix it with zeroes).


RSA: How to get ciphertext in decimal from an encrypted base64? I was given the ciphertext as base64 just like that:

ADknbLUTEh1NBT80tH57H7B44DZOWao67c8I8+AQwuSwnUUxiJUidAedSaOGceVjC4tVF3sfnj0b
1akQiMMXO7YPj+0MFFN09WqE0Jz36ZtY695Esp3DoErjnK8=

How can I convert it to decimal?

Base 64 is an encoding of bytes, not numbers. Of course, bytes can be used to represent a number. The output of RSA encryption consists of bytes (or octets, the term used in the RSA PKCS#1 stancard). So the base 64 decoding has come after RSA encryption in your protocol. This all means that the conversion is a two step process.

How to decode base 64 to bytes is not a question we're going to answer here, there are plenty of libraries that will do this for you.

Before the conversion happens it is important to validate that the value is precisely as long as the modulus (the key size), when encoded to a minimal number of unsigned byte. The real second operation, both for RSA that uses OAEP- and RSA v1.5 padding, is the conversion from bytes to the integer. This operation has a name: OS2IP, or the Octet String to (2, gedit?) Integer primitive. Very basically, this interprets the bytes as an unsigned, big endian integer.

    a.  Convert the ciphertext C to an integer ciphertext
        representative c (see Section 4.2):

         c = OS2IP (C).

This points to the following text in Section 4.2 of PKCS#1 v2.2:

  OS2IP converts an octet string to a nonnegative integer.

   OS2IP (X)

   Input:  X octet string to be converted

   Output:  x corresponding nonnegative integer

   Steps:

      1.  Let X_1 X_2 ... X_xLen be the octets of X from first to last,
          and let x_(xLen-i) be the integer value of the octet X_i for 1
          <= i <= xLen.

      2.  Let x = x_(xLen-1) 256^(xLen-1) + x_(xLen-2) 256^(xLen-2) +
          ...  + x_1 256 + x_0.

      3.  Output x.

Do not try and implement this as a mathematical function using multiplication and calculating things to the power of two; it is just a mathematical description of the decoding of an unsigned integer.

After the trick is to find a good big integer library for your language and use the right method to convert or at least interpret. In Java it is simply new BigInteger(1, <the byte array>) where the 1 is the sign bit, which is of course always positive (or zero). Java copies the value represented by the bytes to the internal interpretation but other languages may leave the number where it is and simply reference it as an unsigned big integer.

Beware that other languages such as C# are commonly little endian. You may need to find the right method that explicitly mentions the endianess. Otherwise you may need to reverse the location of the bytes within the representation before parsing the bytes that now represent a little endian integer.


How many unique elements are generated by a variation on the equation in DSA for r? How many unique elements are generated from the following equation?

$$i = (g^x \bmod p) \bmod n $$

where:

$g$ has order $q$
$q$ and $p$ are prime numbers
$q\mathop{|}p-1$
$n$ is integer number more than 2 (could be even or odd number)

In part $g^x \bmod p$, it will generate $q$ unique numbers. But I am getting confused when the value is modulus-ed by $n$. Can someone help me?

If $n > p$, then this will yield $q$ distinct results, since $g^x$ takes on exactly $q$ distinct values all below $p < n$ and ‘modulusing’ by $n$ has no effect in that case.  This is the largest number of values it can take on, no matter what $n$ and $p$ are.

Suppose $q = 2$ and $n = g < p$.  Then there are two distinct values of $g^x$, namely 1 and $g$, and two distinct values of $(g^x \bmod p) \bmod n$, namely 1 and 0.  This is the smallest number of distinct values it can take on, no matter what any of the parameters are.

It can also take on intermediate numbers of values.  For example, with $g = 2, p = 17, n = 13$, we have $q = \operatorname{ord}(g) = 8$, and $(g^x \bmod p) \bmod n \in \{0,1,2,3,4,8,9\}$, which has 7 possibilities, which lies between $2$ and $q$.

It's possible there is some nice formula relating $p$, $n$, $q$, and the cardinality of $\{(g^x \bmod p) \bmod n \mathrel| x \in \mathbb Z\}$, but it's not obvious to the tiny brain in this feathery skull—which is spending more brain cycles wondering: Why do you want to know the number of possible values this can take on?  It is not actually the formula for $r$ in DSA, unless $n = q$.

On the other hand, if $n = q$, one might be wondering about the security of DSA.  Curiously, if one follows the references, what appears to be the standard reference for reduction of DSA security to discrete log security has only this to say on the subject:

  Indeed, it is very unlikely that the $“x \mapsto (g^x \bmod p) \bmod q”$ map has $(\log q)$-multi-collision.

(§6.1 ‘DSA–II Variant’, p. 289)

Here ‘$(\log q)$-multi-collision’ means a set of about $\log q$ (exactly which integer near that real number is not clear) elements sharing a common image under that map; the paper demonstrates a reduction of DSA forgery to calculation of discrete logarithms under the model of the message hash function as a random oracle and under the assumption that the map $x \mapsto (g^x \bmod p) \bmod q$ is $(\log q)$-multi-collision-free.  If, indeed, it is $(\log q)$-multi-collision-free, then since there are $q$ possible inputs in the domain and $q$ possible outputs in the codomain, there are at least $q/\log q$ possible values of $(g^x \bmod p) \bmod q$.

Thus, I'm afraid I must leave it as an exercise for the reader to trawl the number theory literature for wisdom on the question of the cardinality of the image of $x \mapsto (g^x \bmod p) \bmod q$, since the field of cryptography seems to lack an answer.


Constructing public key encryption schemes with desired ciphertext expansion I would like to know if

given a public-key encryption scheme (PKES) with ciphertext expansion close to 1, and an integer N greater than or equal to 2

there exists a method for constructing a PKES with ciphertext expansion:

size(ciphertext) = size(plaintext) x N

Preferably, the constructed PKES would be similar to the given PKES in terms of security and efficiency.

Thank you.

Edit [about padding][@poncho]: I work with two different entities represented as bitstrings. Let's call them large and small.

size(large) = size(small) x N

Let encryption and decryption functions of the PKES be (E,D).

I receive many large bitstrings, and there is a need to store the small bitstrings which are derived as follows:

smallInstance = D(largeInstance)

At a later point, largeInstance should be recoverable using the public key:

E(smallInstance) = largeInstance

The problem I see with padding here is that it is not possible to use a constant padding for all the associated small bitstrings, and it is not desirable to store all the different paddings $pad_i$ obtained from:

smallInstance_i || pad_i = D(largeInstance_i)

From your expanded comments, it appears that you hope to use encryption to do data compression; that is, you have an $N$ Megabyte input, and hope to store it in a 1 Megabyte storage, and later recover it in toto.

Sorry, but that's (probably) impossible.  If there are $2^n$ possible largeInstance's, then you cannot store them in less than $n$ bits, and be able to recover it later.

The only case where it might be achievable is if the largeInstance's have a great deal of redundancy (and so that even though they are $n \times N$ bits long, only $2^n$ values are actually possible); if so, you'd be better off looking at a data compression method, rather than an encryption method.


Operation modes of block ciphers how are used? I am studying about different operation modes of block ciphers my question isn't something specific to that, but is how these operation modes are used in cryptography?

I have this picture here (OFB-mode):

(source)

I would like to know how these operations are combined with a block cipher algorithm? For example we have the DES encryption, while the DES has it's own encryption method where does these operations intersect with the algorithm? I mean when these operations are used in the actual DES algorithm? And why we need them if we know that the DES itself is an encryption method?

DES would be the box in your diagram that's labeled "Block Cipher Encryption", and it participates in the encryption mode you show in two ways: the output is XORed with the plaintext, and the output is used as the input to the next block's use of DES (the second "Block Cipher Encryption").

In this mode, you're using DES to generate a sequence of random blocks based on the IV and key, so it's operating as a stream cipher (which means you must NEVER use the same IV and key more than once, in other words you need to use a new unique IV for each new set of message blocks as long as the key stays the same). OFB turns a block cipher such as DES into a stream cipher.

The requirements for an IV can be different for different modes, as are the consequences of re-using an IV with the same key.

Using the "raw" encryption algorithm on each block is known as ECB, Electronic Code Book.  The reason you don't normally use ECB is that any time you encrypt the same block with the same key, you'll get the same output.  This can easily yield a lot of information about the message, something that you don't want.  There's a nice image showing how much information can leak using ECB mode in the Wiki link above.

The different chaining modes have different requirements, before using one you need to understand what the pitfalls, advantages and drawbacks are.  In particular, most of the modes need to have some form of message authentication to prevent an attacker from changing parts of the encoded data.  The way to do this with the common chaining modes is called a MAC, a Message Authentication Code.  An example of a MAC is called HMAC (Hash-based message authentication code)(which, itself, is a mode of operation using some underlying hashing algorithm).

The problem with not using any message authentication (which is not the same as authenticating WHO you're talking to) is that an attacker can do many nasty things, depending on the chaining mode.  This can lead to them being able to change messages or determine part or all of what's in a message.


Any implication of a Yale result to security of quantum cryptology? Quantum key distribution depends, if I don't err, on (irreversible) damages done by MITM's measurements on qbits. Now news.yale.edu/2013/01/11/new-qubit-control-bodes-well-future-quantum-computing says:

"The Yale physicists successfully devised a new, non-destructive measurement system for observing, tracking and documenting all changes in a qubit’s state, thus preserving the qubit’s informational value."

Wouldn't the new technique, if not immediately practically, at least in long term render the security of QKD questionable?

No.  The Yale result describes a method of partial measurement that is not completely destructive to the quantum system's coherence, which is tied to its physical representation.  It is not a refutation of quantum indeterminacy, which is the basis for (provably secure) quantum key exchange.  In other words, the Yale team measured a qubit in such a way that it doesn't "fall apart" (decohere) when it's measured - in the author's words, "the measurement record faithfully reports the perturbation of the system after the fact." However, the act of measurement still affects the qubit's information content in accordance with the mathematics of quantum mechanics.


Is there any bias whatsoever in modern hash function outputs? The following is a representative example of a common hash function:-

The asymmetry is clear, and I would  expect additional edge effects  in the A and E output words. So I'd be surprised if the probability distributions between words A to E are identical to the nth degree. The same asymmetric construction argument clearly applies to all other hash architectures.

In general cryptography and as NIST does, it's common to treat a bias $\epsilon < 2^{-64}$ as negligible.  So an $\epsilon$ is expected of some degree as our constructions are imperfect.

The question therefore is: is there any estimate of the theoretical bias across the block width of hash function outputs? Assume the limiting case of an infinite number of hash inputs. Would the output probability distributions be (say for the above example) $P_{\infty}(A) = P_{\infty}(B) = P_{\infty}(C) = P_{\infty}(D) = P_{\infty}(E)$ exactly, and $\epsilon = 0.0$?

I won't be accepting the current answer as that deals with empirical measures, but I'm asking about theoretical expectations. There is no computationally bounded adversary.  I'm just curious.

NB. I take "bias" to mean the standard NIST definition (SP 800-90B) as "A random process (or the output produced by such a process) is said to be biased with
respect to an assumed discrete set of potential outcomes (i.e., possible output values) if
some of those outcomes have a greater probability of occurring than do others."

I'm really not sure if Is any group of bits in a SHA-1 hash more/less unique than another? is similar or not.

If there were any detectable bias, I wouldn't be posting about it on a forum of pseudonymous wackos like me on the internet—I would be getting top billing (or beaking, as the case may be) in a top-tier cryptography conference, and the champagne would be popping, and Twitter would be abuzz with speculation, and Hacker News would be extra insufferable.

Specifically, with the exception of 2-pass Snefru[1][2], no major hash function with advertised preimage and collision resistance has ever seen its preimage resistance broken[3] (archive).  (Yes, there's a paper that everyone and their dog cites on an MD5 preimage attack[4], but it's not cheaper than the best generic attack[5].)

P.S.  The formula $\epsilon = 2^{-(s n - k)/2}$ appears to be a quotation from an ID Quantique marketing whitepaper with a garbled definition which Paul read out of context to draw a nonsense conclusion in the self-accepted answer of his own that he cited.


Order-preserving appending log Sorry for not having a better name, but I cannot seem to find a better name.

Each client will append an element $a_i$ to the server at some time, and the server keeps appending the element to the database $\{a_1,a_2, \dots, a_i\}$.

Is there a way for the server to "cryptographically" prove to the clients that it behaves honestly? one trivial example is to publish the whole database/hash of each element and handle one client at a time.

I am not sure if people have looked into this problem before

This is actually quite a common problem in cryptographic systems. This can be looked at as proving two different things:

Is the server currently storing all of the elements a specific client has given it before in order (is it honest with us)?
Is it giving us all of the other client's data (is it honest with others)?
Will it continue to act as an append-only log in the future (will it always be honest)?

Is it honest with us?
This is and easy to solve problem, solvable by a simple Merkle tree (also hyped as a "blockchain"). Publish a list of tuples <hash(previous_element), current_element> and the hash of the most recent one, known as the head. Now a verifier can update by looking at the head and downloading it, then looking at the previous hash and downloading that, and so on until it reaches the head it previously stored.
This only verifies that nothing before the previous head has been altered or removed: an omission or alteration before the previous head would change the head's hash, so the client would be able to detect it.
Of course, the client doesn't need to store the whole history; they just need to verify the hashes all the way down to their previous head, and then store the new head's hash, making this very space efficient.
If you want to restrict who can append, add a ring signature to the tuple, and give each validated client a key in the ring.
Is it honest with others?
The second one cannot be proven without some form of communication between the clients. This is a simple information-theoretical result: there is no evidence the server could provide that would convince you that a client had not added something to the database, as it could just present you with the state it had when you last appended to it. However, if two clients have diverging histories, you can prove that either the client is lying, or the server is. If there is a group of clients that all trust each other, then even an evil server would have to act honestly with all of them. Conversely, this could be turned into a peer-to-peer protocol, with clients acting as servers for others, making it harder for an adversary to compromise completely.
If you are going down the authenticated route, the server would be unable to successfully forge an entry in the log.
Will it always be honest?
The last one is impossible to prove. My evil server could be simulating an honest one, maybe even running the honest code, up until a point where I chose to change it for a different one. Someone could unplug the cable to my server and plug it into theirs. I could maintain two logs, an honest one I show to you, and a dishonest one I show to everyone else, or even just show each client only the results they themselves had appended. These are problems that would apply to any system, not just the one that I set out above.
In the real world
A real-life example of this is the "Certificate Transparency Logs". These are used to prove that a CA has issued a TLS certificate (used for securing websites). This means that an attacker cannot surreptitiously create a certificate and use it to impersonate a site: they must publish it's issuance for the world to see (allowing it to be revoked). This record is a kept as a Merkle tree (with each CA contributing a branch) and replicated by multiple different servers, who watch for alterations in the others history. If you want to read up on this similar system, their website is here.


What should be the size of a Diffie-Hellman private key? I'm implementing the SRP-6 protocol, which relies on discrete logarithms for it's security (essentially Diffie-Hellman).

The RFC documents state:

  The private values $a$ and $b$ SHOULD be at least 256-bit random numbers, to give
  approximately 128 bits of security against certain methods of calculating discrete
  logarithms.

I can't seem to find any info on this – is it still valid advice?

Is the reason for this simply that the best known method for calculating discrete logs of $n$-bit numbers requires $2^{n/2}$ steps?

Well, yes, that is generally good advice about DH.

Here is some background on this: support you were given a value $g^x \bmod p$, and you were also told that $1 \le x \le A$ for some value $A$.  If so, then there are several known attacks (such as Big Step/Little Step and Pollard's Rho) that can recover $x$ in about $\sqrt A$ steps.  If we have as our security goal that it should take at least $2^{128}$ steps, then means that $\sqrt A \ge 2^{128}$, or $A \ge 2^{256}$, that is, we take our private exponent $x$ to be a random 256 bit number (note: in this context, we count it as a 256 bit number even if the msbit happens to be zero).

Now, there are a few other notes I want to leave you with:

There isn't much point in making the private exponent much larger than that; there is another avenue (Number Field Sieve) which also can solve the Discrete Log problem in time which is independent of the size of the exponent, but only depends on the size of the modulus.  For realistic modulus sizes, this will also be around (or, at least, not significantly more than) $O(2^{128})$ steps, so making the private exponent significantly bigger will just make your computations more expensive, without making the system any more secure in any real sense.
One minor point about SRP (as opposed to straight DH); the protocol does leak the LSbit of the initiator's private exponent (by leak, I mean that someone listening to the messages being exchanged can deduce that bit value).  I don't believe that that's a big deal (as it's only 1 bit, and nothing else is leaked).  If you want to be pedantic, I suppose you could have the initiator pick a 257 big private exponent (so there will still be 256 unknown bits).


number theory question in a group with unknown order I was reading a paper and I am struggling understanding one part of it.
Lets say we have a group $G$ of an unknown order $n$. we know that $B<n<B+C$. both B and C are large values).

we choose a random element $z \in G$. and let's say we have some prime values $B+C<e_1,e_2,...,e_l$. We Calculate $h=z^ {\prod_i e_i}$.

The claim is as $\gcd(n,\prod e_i)=1$ (which is true as each prime is greater than $n$) we can say that $h$ is uniformly distributed in $G$. How can we prove this statement?

Define the function
$$\begin{align}
f: G&\to G\\
x&\mapsto x^{\prod_i e_i}
\end{align}$$
$f$ is injective. Proof: if $f(x)=f(y)$ then $x^{\prod_i e_i}=y^{\prod_i e_i}$, thus $(x\cdot y^{-1})^{\prod_i e_i}=1$, thus the order $k$ of $(x\cdot y^{-1})$ is a divisor of $\prod_i e_i$. Since the order of any group element divides the group order, $k$ is also a divisor of $n$. Since $\gcd(n,\prod e_i)=1$, $k$ must be $1$. Thus $(x\cdot y^{-1})=1$, thus $x=y$.

Any injection over a finite set is a bijection. It follows that $f$ is a bijection over $G$.

Thus $h$ is constructed as the image of a uniformly random element $z$ of $G$ by a bijection $f$ over $G$. Hence $h$ is a uniformly random element of $G$.


Are there cryptographical flaws in this e2ee website chat widget? For a product I'm developing I want to verify if the thinking behind it is cryptographically strong and secure. The product is a chat widget on websites of customers. Like an e2ee version of Intercom.

There are 3 parties that will connect to the service:

Customer of the service (i.e. user of the service I will offer)
Service that offers the chat widget + tools for its customers
Visitors are people that use the chat widget

A few features that are important for the product are:

The service should not see the content of messages send between customers and visitors
The traffic between service and customer and visitor are encrypted via SSL. In this product only important the service can't read the messages
The visitor does not have an account with the service
The customer has an account with the service
The customer can reply to chats from multiple devices
The encryption and decryption should be done in the browser of the customers and visitors only. It will rely on the SubtleCrypto API
The messages include a session ID so both users can verify if following messages are from the same sender

I created a diagram with all the steps I think I need to take:

Diagram explained

To be able to use the same public key on multiple devices of the customer it needs to be copied to other devices of that same customer.

The customer logs in the service with their password
We use the password to create a PBKDF2 key in the browser (key stretching)
We generate a RSA key pair
We encrypt the private key with wrapKey with the PBKDF2 key with AES-GCM 256 bits (the service will not have access to the decrypted private key)

Send the encrypted the private key and public key of the customer to our service
The visitor also creates a key pair with RSA-OAEP
The visitor sends the public key to our service
The visitor gets the public key of the customer from our service
The visitor includes a session ID in their message and encrypts it with the public key of customer
Visitor sends encrypted message back to service
Customer receives encrypted message and public key of visitor
Customer decrypts message with their own private key and encrypts message for the visitor with their public key
Encrypted message is send from customer to service
Encrypted message is send from service to visitor
Visitor decrypts messages from customer

Known flaws

The customer can't verify who the visitor is unless the visitor identifies themselves. This is totally fine for our service

What are there other cryptographic flaws in this e2ee service?

If the customer sends his public key to the business, then the business creates a new set of keys forwarding the new public key to the visitor then the business now has a way to decrypt messages from the visitor since the visitor is not aware that the public key is not the intended customers public key but the new one generated by the business.  The business now can decrypt all messages from the visitor to the business making any changes they wish and using the customers original public key to re-encrypt the changed message with the customers public key and passing that message along to the customer who is not aware that the message has been changed.  If the business does this with the public key of the visitor passed to the customer as well then messages can be read and changed in the opposite direction as well.  This is a classic man in the middle.  That is what TLS is designed for an encrypted communication channel directly between the visitor and the customer with no relay between the certificates for TLS can be verified through a certificate authority which both parties have to trust for the initial key exchange to take place.  In this scenario the business is trying to act as a trusted man in the middle however it maybe the intention to have the business act as a certificate authority  who signs both the businesses and visitors certificates or public keys to ensure that both parties are receiving the intended keys.  In order to do that both parties should have the businesses certificates installed as trusted certificates authorities on their systems which is not a great idea and can lead to major compromises in practice.


what actually the function for e(g,g)^xy I doing a project using ABE "Attribute-Based-Encryption" but i didn't understand what actually the function for $e(g,g)^xy$.
Just tell what's the calculation need to perform here. I gone through no of publications and thesis but i didn't understand this.

$PK = (T_1 = g ^{t_1} , ..., T_{|u|} = g^ {t|U|} , Y = e(g, g)^ y )$

Using the above values how can i calculate PK.

Thanks in advance

This is a bilinear pairing used in cryptography. More precisely it's an evaluation of an appropriate pairing friendly elliptic curve equation.(1,2,3,4,5)


Cracking plain RSA without private key I was wondering whether plain RSA encryption can be cracked given:

The public key
A plaintext of a known cipher text(s).
In other words the decrypted message from an encrypted one (but without knowing the private key)

I.E.: you have managed to find the plaintext of an already encrypted message using the public key, however, you DO NOT know the private key.

With maybe some form of adaptive-chosen-ciphertext attack?

edit: maybe also take advantage of plain-RSA malleability?

It depends on what you mean by "cracking", and also what you mean by "RSA".

"Plain RSA", also sometimes described as "textbook RSA", is the lone modular exponentiation. By itself, it is very weak. For instance, if $n$ is the modulus and $e$ the public exponent, suppose that you want to "decrypt" a cipher text $c_1$ (i.e. you want to find $m_1$ such that $m_1^e = c_1 \pmod n$). You can choose a random integer $c_2$ modulo $n$, and compute $c_3 = c_1/c_2 \pmod n$; then, obtain the decrypted messages $m_2$ and $m_3$, corresponding to $c_2$ and $c_3$, respectively. In that situation, you know that $m_1 = m_2m_3 \pmod n$. This is a chosen ciphertext attack, in which you ask for two decryptions and obtain three plaintext messages, including the target message $m_1$, and yet the decryption oracle did not see any request ending in revealing $m_1$. That's "cracked" by any decent definition of "cracking".

That's why "plain RSA" is not RSA. RSA, the asymmetric encryption algorithm, is described by PKCS#1 and includes a padding operation which is essential to security. With appropriate padding, there is no known attack on RSA which would help in decrypting a given message, even in an adaptative chosen ciphertext context.


Sextic twist of BN pairing parameters vs security I've previously asked questions on BN pairing parameters. Here's one more.

In the BN construction, one is working in a subgroup of a curve over an extension field $\mathbf{F}_{p^{12}}$ for some prime $p$. Now, in the scheme I'm looking at, they suggest selecting parameters so that $p$ will end up being a $256$-bit prime. Hence, the total field size will be around $2^{3072}$. The article claims this scheme has security equivalent to RSA 3072-bits.

Now, one can optimize the BN implementation by doing some of the calculations on the  "sextic twist" since it turns out that there exists another curve over $\mathbf{F}_{p^2}$ which has a subgroup isomorphic to the subgroup of the original curve over the full field. I'm wondering, couldn't an attacker also use this to his advantage and to optimize his attack?

After all, the field now only has $p^2$ elements – so I'm wondering of the security really is still $p^{12}$ compared to RSA… or stated differently, why bother with such a high embedding degree when there's an isomorphic group over a much smaller field extension? Or is the attack that implies the equivalence to RSA 3072 bit not possible on the sextic twist, and that's why the full security is retained?

A current conservative estimate of the security level of a BN curve with an extension field size of 3072 bits, taking into account the Kim-Barbulescu attacks, is 2110. See the paper http://eprint.iacr.org/2016/1102.pdf and the discussion of it at https://github.com/zcash/zcash/issues/714#issuecomment-263007229 . An earlier discussion of these attacks is https://ellipticnews.wordpress.com/2016/05/02/kim-barbulescu-variant-of-the-number-field-sieve-to-compute-discrete-logarithms-in-finite-fields/ .

On the specific question about the sextic twist, G_2 is still an elliptic curve group, not the multiplicative group of a finite field. So index calculus attacks, including variants of TNFS based on Kim and Barbulescu's work, do not apply to it.


Why does OpenSSL differentiate between PSS and non-PSS for private key generation? RSA-PSS private keys

The following command will generate an RSA-PSS private key:

openssl genpkey -algorithm rsa-pss -pkeyopt rsa_keygen_bits:2048 -pkeyopt rsa_keygen_pubexp:65537 -out CA.priKey

Here's a sample one I just generated:

https://pastebin.com/AQk0gkkT

Here's the asn1parse output:

    0:d=0  hl=4 l=1213 cons: SEQUENCE
    4:d=1  hl=2 l=   1 prim:  INTEGER           :00
    7:d=1  hl=2 l=  11 cons:  SEQUENCE
    9:d=2  hl=2 l=   9 prim:   OBJECT            :rsassaPss
   20:d=1  hl=4 l=1193 prim:  OCTET STRING

Regular RSA private keys

This command, in contrast, will generate a regular RSA private key:

Here's a sample one I just generated:

https://pastebin.com/s6gES7hr

Here's the asn1parse output:

    0:d=0  hl=4 l=1213 cons: SEQUENCE
    4:d=1  hl=2 l=   1 prim:  INTEGER           :00
    7:d=1  hl=2 l=  13 cons:  SEQUENCE
    9:d=2  hl=2 l=   9 prim:   OBJECT            :rsaEncryption
   20:d=2  hl=2 l=   0 prim:   NULL
   22:d=1  hl=4 l=1191 prim:  OCTET STRING

My question

Why do RSA-PSS private keys have their own format? The probabilistic signature scheme (PSS) affects how the signatures are made. At least according to PKCS#1 v2.2. The keys are the same. They both make use of the same CRT parameters and what not. So why two different OIDs in this context? Is there a difference or is this just OpenSSL being dumb? And are there any other OIDs OpenSSL might be using to represent RSA private keys?

If you reuse the same key material for different algorithms, you rely not on the security of any one algorithm individually, but on the security of the composition of the two algorithms simultaneously.

For a particularly egregious example, if you use the same RSA public key for RSASSA-PKCS1-v1_5 and for HMAC-SHA256, the results might be entertaining.

It may turn out that while we have high confidence in the security of RSASSA-PSS assuming the RSA problem is hard, and reasonable confidence in the security of RSASSA-PKCS1-v1_5 because after decades nobody's made progress on it, the combination of the two with the same key material could have catastrophic results.

The theory behind these tags is presumably that associating such metadata with the key may serve to reduce the danger of accidentally reusing the same key material for different cryptosystems.


Distribution of randomness in elliptic curve Diffie-Hellman shared secret The specification for a project I'm working on says to use elliptic curve Diffie-Hellman for key exchange, specifically using the secp224r1 curve.  In the notes it is stated:

  take the last 16 bytes of the shared secret byte array (do not use the first 16 bytes — those are not as uniformly distributed as the last 16 bytes!).

So my questions are:

Why are the last 16 bytes more random than the first 16?
Is this specific to the secp224r1 curve, or is it general to the elliptic curve version of the Diffie-Hellman algorithm?

Fix a short Weierstrass curve $y^2 = x^3 + a x + b$ over a finite field $\mathbb F_p$ of order $n$.  (secp224r1 is an example, with $p = 2^{224} - 2^{96} + 1$, $a = -3$, and $b$ selected from an allegedly randomly chosen but unexplained seed passed through SHA-1.)

There are at most $n$ distinct values of $(x, y) = [\alpha \beta]G$ where $\alpha$ and $\beta$ are secret scalars in $\mathbb Z/n\mathbb Z$ and $G$ is the standard base point, all satisfying this equation.

If you choose uniformly among them, e.g. by choosing $\alpha$ and $\beta$ independently uniformly at random, and encode the pair $(x, y)$ into a $2 \lceil\log_2 p\rceil$-bit string, there is a trivial algorithm to distinguish the resulting string from a uniform random $2 \lceil\log_2 p\rceil$-bit string: decode it as a pair of integers $x$ and $y$ and test whether $y^2 \equiv x^3 + a x + b \pmod p$.  So not only do the encoded values of $(x, y)$ cover a tiny fraction of the space of $2 \lceil\log_2 p\rceil$-bit strings—square root of the number of all such strings of that length—but they're trivial to distinguish from uniform random.

But that's partly because for each $x$, there's only at most two values of $\pm y$, so we can compress it into a much shorter $(1 + \lceil\log_2 p\rceil)$-bit string by storing only a bit to discriminate between the two possible values of $y$.  Is that uniform random?  No!  If you decode $x$, you can test whether $x^3 + a x + b$ is a quadratic residue modulo $p$, which only about half of the integers are.

Distinguishers for the encoding of uniform random elliptic curve points were some of the first problems documented publicly in Dual_EC_DRBG[1], before everyone realized it was an obvious vector for a back door.

In general, when a random string is readily distinguishable from uniform like this, it is unfit to be used as a secret key in a cryptosystem whose contract demands a uniform random key—if you violate the security contract, it is null and void.  But if the random string, while not uniform, nevertheless has high min-entropy, you can effectively get a uniform random string by hashing it, say with SHAKE256—what this means is that the best an adversary can do is test a guess about what the input might have been.

As for the low-order or high-order bits of $x$ and $y$?  Don't bother; just hash them all.  The cost of computing a hash like SHAKE256 is negligible compared to the cost of computing an elliptic curve scalar multiplication even on a small curve like secp224r1.


Why $e>n^{3/2}$ prevents Wiener's attack Here's the Wiener's attack as I understand it.

Suppose $n=pq$ with $q < p < 2q$, and $d < n^{1/4}/3$ where $ed=k\phi(n)+1$ and $e < \phi(n)$.

$$\begin{align*}
n-\phi(n) &=n-(p-1)(q-1)\\
&= n-(n-p-q+1) \\
&= p+q-1 \\
&< 2q+q-1\\
&=3q-1 \\
&< 3\sqrt{n}
\end{align*}$$

and $e<\phi(n)\implies ke < k\phi(n) =ed -1 < ed \implies k<d<n^{1/4}/3$.

Therefore,
$$\begin{align*}
\left|\frac{e}{n}-\frac{k}{d}\right| &= \left|\frac{ed-kn}{nd}\right|\\
&=\left|\frac{de-k\phi(n)-(kn+k\phi(n))}{nd}\right|\\
&= \left|\frac{1-k(n-\phi(n))}{nd}\right|\\
&\le \frac{3k\sqrt{n}}{nd} \\
&\le \frac{3(n^{1/4}/3)\sqrt{n}}{nd} = \frac{1}{dn^{1/4}}\\
&< \frac{1}{2d^2}.
\end{align*}$$

The last inequality (by some theorem about continued fraction) and $gcd(d,k)=1$ imply that $\frac{k}{d}$ is a convergent in simple continued fraction of $\frac{e}{n}$.

Why does $e>n^{3/2}$ imply that $k/d$ is not a convergent in simple continued fraction of $e/n$? Or why does such an $e$ prevent Wiener's attack?

It suffices to show that $|e/n-k/d| > 1/d^2$.

Thank you!

In Wiener's attack $k$ is a small number ($k<d$). If we set $e^{'}=e+t\phi(n)$ for some large $t$ then $e^{'}$ can be used in place of $e$ for message encryption.Also the k became a big number and we can't using of Wiener's attack.For more detail you can see "Twenty Years of Attacks on the RSA Cryptosystem".


Is symmetric encryption vulnerable to plain-text-attacks? Imagine that Bob sends a message to Alice for symmetric encryption to send to Charlie. (Only Alice and Charlie know the key.) Alice sends the encrypted message back to Bob to send to Charlie. Can Bob compare the plain text he sent to Alice with the encrypted version to guess, for example, what is Alice's AES key?

If the encryption is any good, no.  What you're describing is a known-plaintext (or possibly chosen-plaintext) key recovery attack, and any encryption system that was even suspected of being vulnerable to such attacks would be considered hopelessly broken by modern standards.

The "gold standard" that modern encryption methods aim for is generally taken to be "IND-CCA2" security, or ciphertext indistinguishability under an adaptive chosen-ciphertext attack.  Loosely speaking, this security property means that an attacker who gets to choose two plaintexts (of equal length) to be encrypted and sent back to them, and may also request the encryption or decryption of any number of other messages, will not be able to tell which ciphertext corresponds to which plaintext.


MitM with regard to unauthenticated clients I'm trying to understand how man-in-the-middle attacks are prevented during key exchanges, and am confused by this Wikipedia statement:

Use of mutual authentication, in which both the server and the client
validate the other's communication, covers both ends of a MITM attack,
though the default behavior of most connections is to only
authenticate the server.

Is that saying the client authenticates it is really receiving from the server, but the server doesn't care who is sending?  Doesn't that mean the server might be talking to an eavesdropper who inserted himself in the middle and the eavesdropper can't decrypt server responses (which are simply forwarded to the client) but can pretend to be the client and see what the client is sending?

but can pretend to be the client and see what the client is sending

No, the eavesdropper can't see what either side is sending except the ciphertext and size of the ciphertext.
To eavesdrop on any connection where the server is authenticated, the eavesdropper has to be able to convince the client that he is the server, which the eavesdropper cannot.

Doesn't that mean the server might be talking to an eavesdropper who inserted himself in the middle

Any internet middle box can do that.

and the eavesdropper can't decrypt server responses

True, and the eavesdropper can't decrypt client requests either since the eavesdropper doesn't have the session key.

but can pretend to be the client and see what the client is sending

Again, the eavesdropper doesn't have the session key, he can't do that.


Is it possible to spoof an identity cert modulus? I was looking at FOAF+SSL and wondering if its possible to spoof the modulus of the browser certificate so that the FOAF and browser certificate's modulus match?

I'm not sure exactly what you are asking. In the scenario, there are two certificates: Romeo's FOAF certificate and Juliet's SSL certificate. However Romeo's certificate is used in two different ways: once to authenticate (over mutually authenticated SSL) and once as posted on a domain he controls.

I believe your question may be, if an active adversary saw Juliet request the certificate information from Romeo's domain (as specified in the cert's alt name), could the adversary modify the response to match a bogus FOAF certificate it provided? The answer is yes, since this connection is not over SSL!

The real question is what happens in step 6? Does Juliet look in her friends databases for the URL or for the public key? If it is the former, there seems to be a security vulnerability. If it is the latter, it is ok, since an adversary has to substitute their own public key to form the HTTPS connection (which requires them to know the corresponding private key).

I once experimented with FOAF but don't know anything about FOAF+SSL beyond this article.


Is the mod_auth_tkt scheme secure? The third-party Apache plugin mod_auth_tkt uses a tragically-not-HMAC construction:

digest0 = hash(
    encode_ip_timestamp(ip, timestamp) + secret + userid + '\0'
    + tokens + '\0' + user_data).hexdigest()
digest = hash(digest0 + secret).hexdigest()

How bad is it? Clearly the performance is worse than HMAC.

At a glance, I see no obvious weaknesses.  Obviously, the security proof of HMAC won't apply to this construction, but that doesn't necessarily make it insecure — it just means that we can't prove its security (given appropriate assumptions on the underlying hash function), or at least that we'll need different methods to do so.  Certainly, none of the (practical) attacks in section 6 of the original HMAC paper seem to apply.

Ps. Why do you say that the performance is worse than HMAC?  Both involve two calls to the hash function, one for arbitrarily long (but in this case, poribably fairly short) input and one for only fixed-length input.  Indeed, in some cases (keys longer than one hash input block) this scheme could be faster than HMAC.


Does ECIES imply authenticity? Assume:

Alice and Bob both generate separate EC keypairs
Alice obtains Bob's public key, and together with her private key creates a shared secret key
Alice encrypts a message using the shared key and some mode of authenticated encryption (AES-GCM, for example)
Bob generates the same shared secret key using his private key and Alice's public key
Bob decrypts the message, paying attention to whether or not the auth-tag is valid

My question is; if Bob is confident that Alice's public key really belongs to Alice, then can he be confident that it was Alice who encrypted the message? Or to put it another way, in this scenario does the auth-tag effectively serve as a signature created with a public-key? Intuitively I want to say yes, but I just want to make sure I'm not overlooking anything.

I guess the answer is no, as long as you are using ECIES then this protocol does not work - you cannot trust the public key of Bob, which is required for ECIES.

You could however use ephemeral-static Diffie-Hellman, using ECDH as cryptographic algorithm. Alice would supply the static part as her public key is trusted, Bob may use any key pair. That means that Bob can trust Alice, but not the other way around. This may however be sufficient for some protocols (TLS normally does not perform client authentication either).

Of course, you may just as well use a static key pair for Alice instead of randomly generating it again and again, requiring to set up trust for each key pair creation.


Looking to verify my understanding of RSA math I want to explain RSA to a programming audience with no cryptography background and I want to be sure my explanation is correct. The goal is to help them understand how RSA works under the hood. You can assume the audience knows modular arithmetic at this point. Could you please let me know if this explanation is clear or if I've missed anything critical for a lay audience? Do you think I should cover more number theory? The actual delivery will be refined later and I'll cover OAEP further along. I just want to be sure I haven't made a mistake here.

---EXPLANATION BEGINS---

RSA's security is based on factoring primes. A problem which is considered hard though there's no formal proof of that.

We start by selecting two large primes, p and q. Each should be 2048 bits. We multiple p and q to yield n.

$n = p\times q$

n is referred to as the modulus and will be 4096 bits long, which is the recommended number of bits to achieve ~128-bit security.

Our plaintext, p, is then represented as a number less than n. We also have a public key (e) and a private key (d).

RSA works as follows. The ciphertext, c,  is generated by raising p to the power e modulo n:

$c = p^e mod\ n$

The plaintext is recovered by raising c to the power of d modulo n:

$p = c^d mod\ n$

So encryption then is a matter of multiplying p by itself a certain number of times modulo n. And d is a matter of multiplying the ciphertext by itself a certain number of times modulo n to arrive back at the plaintext. Another way of looking at it is that encryption involves mapping the plaintext to another number (the ciphertext) in the finite set n. And decryption is about mapping the ciphertext back to the plaintext. You can look at it mathematically like this:

$c^d mod\ n = (p^e)^d mod\ n = p^{ed} mod\ n = p$

RSA's security comes from it being easy to map the plaintext to ciphertext, but being computationally infeasible (when the keys are sufficiently large) to do the reverse unless you know the decryption key (d).

So we need to generate keys e and d such that this scheme is possible. Specifically, d needs to be the inverse of e. To do this, we can use something called the totient of n, represented by $\Phi(n)$. The totient of n is the number of elements from 1 to n - 1 that are coprime to n. Two numbers are coprime if their only common divisor is 1. Finding $\Phi(n)$ when p and q are both prime is easy. It's:
$\Phi(n) = (p-1)(q-1)$

So to take a toy example, let's say p = 3 and q = 11, in that case:

$n = 3 \times 11 = 33$

$\Phi(n) = (3-1)(11-1) = 20$

So there are twenty numbers from 1 to 33-1 inclusive which are coprime with 33.

To generate the public key (e), find a value of e such that the following is true:

$gcd(e, \Phi(n)) = 1$

In other words, e should be coprime to $\Phi(n)$. By doing this, we're guaranteed to be able to find an inverse (d) to serve as our private key.

From our toy example above, e could be 3. To find the corresponding private key, we need to find a value of d such that the following is true:

$d \times e \equiv 1 \ mod \ \Phi(n)$

$d \times 3 \equiv 1 \ mod \ 20$

We can find d using the Extended Euclidean Algorithm. In this case, that would be 7.

So now that we've generated our public (e) and private (d) pair, let's encrypt a piece of plaintext encoded as the value 29. Our ciphertext is then:

$c = p^e mod\ n = 29^3 mod\ 33 = 2$

Recovering the plaintext is then:

$p = c^d mod\ n = 2^7 mod\ 33 = 29$

Some additional notes:

Common keys for e are {3, 5, 17, 257 or 65537}.
Notice that when we generate the private and public keys we mod against $\Phi(n)$, and when encrypting and decrypting, we mod against n

---EXPLANATION ENDS---

Some random comments:

  RSA's security is based on factoring primes.

Actually, it's based on the hardness of the RSA problem. It is still an open question whether its difficulty is equivalent to that of factoring.

  RSA works as follows. The ciphertext, c, is generated by raising p to the power e modulo n

At this stage, you probably don't want to go into the full details, but you should mention (perhaps in passing) that we never use 'textbook RSA' as you described, but when doing public key encryption, we perform 'padding' before doing the raw RSA operation.

You mentioned that you'll be covering OAEP later; you should give a few words to the effect that 'I'll cover this more fully later; this is a simplified version for now...'

  So encryption then is a matter of multiplying p by itself a certain number of times modulo n.

Not an issue with what you said, but (depending on the time) might want to discuss how we raise p to such enormous powers without taking an enormous amount of time; I believe that your audience should be able to follow that.

  To do this, we can use something called the totient of n, represented by $\Phi(n)$.

Actually, it is more typically represented by a lower case phi, that is, either $\phi(n)$ or $\varphi(n)$.

  To generate the public key (e), find a value of e such that the following is true:

I don't know if you want to go into these sorts of details; however it is more common in practice to select e first, and then select p and q such that $p, q \not\equiv 1 \pmod e$ (which will ensure (for prime e) that $\gcd( \phi(n), e ) = 1$)

Everything else would appear to be reasonable (if simplified...)


Example of not computationally indistinguishable All the examples that I see for proving that two distributions are not computationally indistinguishable involve a pattern: choose a Distinguisher $D(\cdot)$ such that $D(x)$ is $1$ if $x$ satisfies some certain properties.
For example, consider the distribution $X$ such that it contains all the binary strings in $\{0,1\}^k$ such that they end with 1 and distribution $Y$ uniformly spread over all strings in $\{0,1\}^k$. Now I can choose my distinguisher to be $D(x) = 1$, if $x$ ends with $1$.
However, if there is no such pattern in our distributions, how can we prove that the given distributions are (not) computationally indistinguishable?

The usual way of proving that two distributions are distinguishable is by devising an attack such as the one you mentioned. Finding an attack may not be easy or even doable. In general, you should assume that two distributions are distinguishable unless you can prove otherwise. To prove indistinguishability, you can often use the technique of reduction to map the distributions in question to other ones that are known to be indistinguishable from random.


Help with breaking AES reduced to 2 rounds I was studying Rijndael AES proposal, and its cryptanalysis. I started with writing code to break AES reduced to 2 rounds. I am using 128 bit key size and 128 bit block size. 2 round AES means the following sequence of steps:

$AR \to BS \to SR \to MC \to AR \to BS \to SR \to AR$

where
AR = AddRoundKey
BS = ByteSub
SR = ShiftRows
MC = MixedColumn

One of the way of breaking the algorithm can be generating inputs following a particular pattern and analyzing the output. Following are patterns I consider:

$P:$ All values are distinct
$Z:$ Sum of all values in zero
$X:$ Any other pattern

I give 256 blocks of input to the algorithm at a time. The blocks follow the following pattern:

$$
\begin{matrix}
P & P & P & P \\
P & P & P & P \\
P & P & P & P \\
P & P & P & P \\
\end{matrix}
$$

i.e. all the elements at same position in 256 blocks are distinct. I will denote this matrix as $[P]$ for simplicity.

After applying the above AES steps following is the fate of these matrices:

$[P] -AR \to [P] -BS \to [P] -SR \to [P] -MC \to [Z] -AR \to [Z]  -BS,SR,AR \to [X]$

The last $BS$ operation destroys the structure of the matrix.

We can consider the last 4 steps $AR, BS, SR, AR$ to be a map (say $f$) from 256 inputs at each matrix position to outputs and try to obtain this map using the fact that the input has pattern $Z$. There will be 16 such maps. We can solve it in following way:

Lets consider we want to find the map $f_{00}$ i.e. for the first element in the matrix. We know what all outputs we are getting for the 256 inputs we have taken. Lets say they are:

$u_i, 0 \le i < 256 $

Lets denote:
$x_{u_i} = f_{00}^{-1}(u_i)$

Since the input has pattern $Z$, we can write the following equation:

$$\sum_{i=0}^{255} x_{u_i} = 0$$

This is a liner equation in 256 variables. We can take another set of 256 blocks of input of pattern $[P]$ and generate another equation. We can generate 256 of these equations and solve them to find $f_{00}$. Same we can do for other positions as well. Once we get all the maps. We can easily get the key of encryption.

However my problem is this: No matter how many equations I generate, I always get at max 247 equations that are linearly independent. This means they don't have a unique solution. But according to me they should get a unique solution. Where am I going wrong? Why only 247 equations?

You may be overthinking this a bit.  Just pick any byte in the ciphertext, and for each possible value of the last RoundKey in that byte, do the following: decrypt just that single byte of the 256 ciphertexts  (i.e. compute $AR-SR^{-1}-BS^{-1}$ for that single selected byte using the candidate RoundKey byte in the $AR$ step), and then check to see if the corresponding byte in the State at the beginning of Round 2 all sum to zero.  For the correct RoundKey value, the byte will  sum to zero.  Incorrect RoundKey values will likely not sum to zero.  In that manner, you can sieve out most of the incorrect values for each of the RoundKey bytes for the last RoundKey, and can then exhaustively check the remaining possible Keys (i.e. all combinations of RoundKey byte values that were not sieved out) by using the Key Schedule in reverse and checking to see if a candidate Key correctly decrypts all 256 ciphertexts.

Edit to add: By the way, there are more efficient attacks on 2 round AES than the one you outline (which needs 256 chosen plaintexts).  For example, here is one that only needs a handful of chosen plaintexts:

Request $N$ chosen plaintexts that differ from each other only in four bytes, such that if any pair of plaintexts is xored together you get a result like so:
$$
\begin{matrix}
W & 0 & 0 & 0 \\
X & 0 & 0 & 0 \\
Y & 0 & 0 & 0 \\
Z & 0 & 0 & 0 \\
\end{matrix}
$$
Where $0$ denotes a zero byte, and $W, X, Y$ and $Z$ denote the 'active' bytes with some non-zero difference.  With $N$ such chosen plaintexts, there will be ${N \choose 2}$ pairs of plaintexts that have differentially 'active' bytes in the above pattern.  This efficient 'packing' of pairs will enable us to attack 2 round AES with only a handful of plaintexts (a dozen is likely to be more than enough).

Now observe from the difference distribution table of the AES S-box that for any given input difference, about half of the possible output differences have a probability of zero (they wont occur given that input difference).  This will enable us to sieve out the incorrect keys very efficiently using an impossible differential attack.

Pick a pair of plaintexts and focus on each active byte, one at a time. From the pair of plaintexts we are given an input difference for the focus active byte, and we can use the S-box difference distribution table to figure out the impossible outputs that cannot be attained from that input difference.

For each 'impossible' output difference $I$ for the focus byte after the first SubBytes step, apply ShiftRows and MixColumns to $I$ (notice that for any of the active bytes, after ShiftRows the active byte is mixed with inactive 'zero' bytes).  This will give us a set of impossible differences for four different bytes going into the second round (so from all four focus bytes we can derive a set of impossible differences for all 16 bytes of the State for our pair of plaintexts).

Now select any of the corresponding bytes of the ciphertext pair, and decipher that byte under all possible 256 values for the last RoundKey byte (i.e. given some guess for the last RoundKey byte, compute $AR-SR^{-1}-BS^{-1}$ for both ciphertext bytes).  For each guess of the RoundKey byte, we can xor the 'deciphered' byte together to get a difference in that byte just before the 2nd round.  We can then compare the 'deciphered' difference under that RoundKey guess against the 'impossible' differences that we computed from the plaintext side.  If a RoundKey byte guess leads to one of the impossible differences, then we can rule that guess out as not being correct.

We should be able to rule out about a quarter of the possible RoundKey values for any given byte with each plaintext pair, and for each subsequent pair that we test we can be more efficient in the key-guessing phase by not bothering to test the RoundKey values that we have already ruled out.  In this way, we can sieve out the incorrect RoundKeys very efficiently.


Shamir's secret sharing scheme - type of channels For information theoretic security in Shamir's [m,m] secret sharing scheme, do i need both authentic and confidential channels?
Another related query is ;is it true that if the channels are only authentic; then the Shamir's [m,m] secret sharing scheme is only computationally secure?
If confidential channels are build on the basis of public key schemes; then doesn't that make the entire protocol computationally secure?

For information theoretic security in Shamir's [m,m] secret sharing scheme, do i need both authentic and confidential channels?

Regular shamir secret sharing provides no protection against modified shares. So we typically assume an honest dealer with authentic and confidential channels. That means the adversary cannot change the message in transit. If a party that receives a share is dishonest, however, they can change the share and go undetected.

  is it true that if the channels are only authentic; then the Shamir's [m,m] secret sharing scheme is only computationally secure?

updated this part of the answer
It appears that without some very non-standard assumptions, using only authentic channels completely breaks the security of the system. While all shares are needed to recover the secret, and one share is kept by each party (not transmitted directly), a function of that share is transmitted which would allow the adversary to recover that share and break privacy.

  If confidential channels are build on the basis of public key schemes; then doesn't that make the entire protocol computationally secure?

Assuming the adversary can see the cipertexts, then yes, using a public key scheme (or any computationally secure cipher) to protect confidentiality results in computational security since an adversary breaking the cipher would result in them finding all the shares, thus breaking the secret sharing.


Is there an information theoretic equivalent of a trap door collision free function? Warning: Possibly ill-posed question.

I'm using the following definition from a recent paper available here. I believe their terminology is slightly different but reproduce my understanding of it here.

  The concept of a 2 to 1 trapdoor collision free function
  satisfies the following properties. For every $y$ such that $f(x) = y$, there exists $f(x') = y$ and $x\neq x'$. If one has access to the
  trapdoor, it is easy to find $(x,x')$ for any $y$ and it is otherwise
  computationally hard.

In a recent talk posted online, the authors talk about information theoretic generalizations to this but give no further details. The obvious obstacle is that a computationally unbounded attacker can try all possible inputs to $f$ and eventually know the collisions. My guess is that somehow, $f$ is given in an obfuscated way so that the attacker cannot know of collisions. Is something like this possible at all and how might one achieve this?

Any fixed function $f\colon A \to B$ of a finite domain $A$ is guaranteed to have collisions if the range $B$ has fewer elements than $A$, so there always exists a random algorithm $C()$ which returns a collision: the algorithm that just returns one of the collisions.  We just don't know how to find $C$ for functions like SHA-256 (although we do for MD5 and SHA-1!).  This is why the notion of ‘collision resistance’ as applied to fixed hash functions like SHA-256 doesn't even have a formal definition, although there are attempts to formalize this elusive issue of human ignorance[1][2].

We might consider a probabilistic, or ‘information-theoretic’, model: a random function $f\colon A \to B$ drawn with uniform distribution from all functions from $A$ to $B$.  Any random algorithm $C(f)$ to find a collision is limited to birthday attacks that make $O(\sqrt{|B|})$ calls to $f$ to attain nonnegligible probability of success.*

Of course, choosing a function uniformly at random takes a lot of bits: in general, you need storage for a table of $|B|^{|A|}$ entries if you want to be able to specify all of them.  We might pick a smaller family of functions $f_k\colon A \to B$ with a short key $k$, and consider separately the adversary's knowledge about the key:

If the adversary never knows the key (and, of course, can't learn anything about it from side channels like time of hash table operations), there are many cheaply computed functions to choose from that have ‘information-theoretically’ guaranteed bounded collision probabilities called universal hash families—that is, for any $x$ and $y$, $\Pr[f_k(x) = f_k(y)] \leq \varepsilon$ for some small $\varepsilon$.  This is a theorem that is easily proven for many cases like GHASH or Poly1305.  See [3] for more related notions and references.
If the adversary doesn't know the key in advance, Rogaway and Shrimpton gave the standard formal definition[4] of the notion of collision resistance of the family $f_k$ in terms of the best cost of a random algorithm $C(k)$ to find a collision in $f_k$ (or, more specifically, the best success probability of a cost-limited algorithm in terms of the cost).  Families that we conjecture to be collision-resistant in this formal sense include HMAC-SHA256 and keyed BLAKE2b.

Obviously, for each $k$, there is a collision as long as $|B| < |A|$, but even if we had a precomputation oracle to find them all for us in advance, there is an extremely high cost to storing a table mapping every value of $k$ to a collision in $f_k$, and we assume the adversary probably can't afford $2^{128}$ bytes of RAM or even ROM to store it all.  Functions like HMAC-SHA256 and BLAKE2b seem to exhibit this notion of collision resistance, but proving any theorems about it seems difficult.  In contrast, functions like Poly1305 are easily proven to have low collision probabilities.

What about trapdoor functions like $m \mapsto x^m \bmod n$ where $n = pq$ for secret factors $n$?  Anyone who can find collisions in this function can factor $n$, so as long as factoring $n$ is hard—and until whoever knows $p$ and $q$ publishes a single collision!—it seems difficult to find collisions.  But as above, the domain and range are finite, and if $n$ is limited to a particular size then the space of these functions is finite too.  So there's no way you can guarantee a finite but cost-unlimited attacker has a limited probability of finding collisions.

I don't know what the authors might have meant by an information-theoretic generalization to this—you'll have to ask them.  Incidentally, the paper seems to be discussing claw-free function pairs $f_0$ and $f_1$ for which it is difficult to find $x_0$ and $x_1$ with $f_0(x_0) = f_1(x_1)$, not collision-resistant functions $f$ for which it is difficult to find $x_0 \ne x_1$ with $f(x_0) = f(x_1)$.

* You could naively make a table of results so far and check it for collisions each time you call $f$, but that costs $O(\sqrt{|B|})$ time and $O(\sqrt{|B|})$ space for a total area*time cost (which is a proxy for rubles or ergs) of $O(|B|)$.  In contrast, it takes about the same number of calls to $f$, and only constant memory, to use van Oorschot and Wiener's collision search algorithm[5], which can also be parallelized to speed it up with higher power consumption.  It doesn't even seem to help to have a quantum computer that can evaluate superpositions of $f$[6].


How to jusify {e,n} is a valid RSA public key? I have a  two set of key {36,77} and {50,117},

How can validate if it is a valid RSA public keys?
Is there any simple method?

That depends on exactly what you mean by a "valid RSA public key"; in general, it is difficult to validate a public key without the corresponding private key (unless the public key is obviously bad).

If you mean that there is a corresponding private key $d$ such that $(M^e)^d = M \mod N$ for all messages $M$, then there are two conditions; if both are met, then there will always be such a $d$:

$e$ is relatively prime to $\phi(N)$; if $N$ has k distinct prime factors $p_1$, $p_2$, ..., $p_k$ then $\phi(N) = (p_1-1)(p_2-1)...(p_k-1)$
$N$ is squarefree; that is, there is no integer $n > 1$ such that $n^2$ is a divisor of $N$.  Or, in other words, all the prime factors of $N$ must be distinct.

Note that there are varients of RSA for which a public key might not meet these assumptions; they deal with the fact that $M^e$ might not have a unique inverse in various ways.

As for how to determine whether a public key meets these criteria, well, neither critieria is feasible to verify for a large key.  On the other hand, it is easy to note by inspection that your examples do not; they both have an even value of $e$, and even numbers are never relatively prime to $\phi(N)$ (which is also even).  In addition, your second example has $N=117$, which is not square-free (as it has a divisor of $3^2$).

On the other hand, a "valid RSA public key" might mean a key that meets the above constraints, and is secure.  This implies that $e>1$ (easy to validate), and $N$ is hard to factor.  If $N$ is large enough to be not easily factored, this also is hard to validate.

Thirdly, by a "valid RSA public key", you might mean "all of the above, and in addition, someone knows the private key".  The only way you can accertain that is to work with the person who is supposed to know the private key (and, for example, have a Zero Knowledge Proof that they do indeed know the factorization of $N$).


Is the new preprint "An Algorithm For Factoring Integers" by Yingpu Deng and Yanbin Pan worth reading? I just discovered on the eprint server of the IACR the paper mentioned in the title. Scanning quickly over the paper I didn't find anything spectacular, so I doubt that their new(?) approach will be any good. But as I'm not an expert in the field of factorization, and as the proof for Primality $\in$ P is also deceptively "low-level", I wonder if someone here with more knowledge about factorization could quickly judge if the paper is worth reading.

EDIT: The paper I'm wondering about seems to be connected to the polynomial time primality test by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. So please be sure to know (or better: understand) the AKS-test before answering here.

If you have to ask, you are probably not the intended audience. Quoting the introduction of the paper:

  We implemented our method on a PC using Shoup’s NTL library version 5.4.1 [7].
  Unfortunately, we have to say that the practical effect of our method is not good on a
  single PC, it is worse than many known algorithms on this problem. However, we believe
  that our method yields interesting phenomena, and it is worth for further study.


Why is lcm(n) used now instead of $\varphi(n)$ in RSA? I know that lcm(n) or Carmichael's totient function $\lambda(n)$ is now used instead of $\varphi(n)$ or Euler's totient function to generate the public key in RSA encryption? Why is this so? Are there any mathematical, computer scientific reasons behind this related to key security or efficiency?

Defining the public and private exponents as inverses modulo φ(N), as originally done for RSA, provides a sufficient (but not necessary) condition for the decryption rule to recover the plaintext from any ciphertext. Since Carmichael’s lambda function is, by definition, the smallest number m such that $a^m \equiv 1 \pmod N$, for any integer a that is relatively prime to N. Thus, it is sufficient to define the public and private exponents as inverses modulo any multiple of λ(N).


Discrete logarithm with 2 solutions? A clarification request I need some clarification on the discrete logarithm problem...
When a friend and I were solving for the discrete logarithm problem of 9 = 2 ^ x mod 11, we got two different answers. My initial answer was 6 for x.
But his answer was 12 for x. So we decided to cross check our answers and indeed we were very correct.
So what does this mean? Does it mean that there can be more than one answer for a single discrete logarithm problem?
And does this also relate to the circumstance in a real discrete logarithm problem?

The powers of $2$ modulo 11;
\begin{array}{c|rrrrrrrrrrrrrrrr}
x&  1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ \hline
2 ^x \bmod 11&  2& 4& 8& 5& 10& 9& 7& 3& 6& 1
 \end{array}
We don't need the above 10 due to the Little Fermat Theorem; for a prime $p$ and $p\not| a$ then
$$a^{p-1} \equiv 1 \pmod p$$ We can use this theorem as
$$a^x \equiv  a^{x \bmod{p-1}} \pmod p$$
Therefore your friend's power $12$ is equal to $2$; $12 \equiv 2 \pmod{10}$. In power;
$$ 2^{12} = 2^{12 \bmod{10}} = 2^2 = 4 \bmod 11.$$

A little theory;
The non-zero elements of modulus $11$ form a cyclic multiplicative group. The order of the group is given by $\varphi(p) = p-1$ where $\varphi$ is the Euler's totient function, so it has order $10$.
By the Lagrange theorem, the order of the subgroups must divide the order of the group. The converse, in general, is not true, that is for a divisor of the order of the group, there may not be a subgroup.
$2$ is a multiplicative generator, $\langle 2 \rangle = \mathbb{Z}_{11}^*$ and we can see this in the above table. Besides, $3$ is not a generator, since $\langle 3 \rangle = \{1,3,4,5,9\}$, with $1=3^5,3=3^1,4 = 3^4,5 = 3^3,9 =3^3$. As we can see, the order of $3$ is $ord(3)=5 | 10$.
What about order 2? It is generated by $\langle 10 \rangle = \{1,10\}$. The reason is $10 = -1 \bmod 11$
Note that for a prime $p$ forms a field $\mathbb{F}_{p}$ (also written as $GF(P)$) with integer addition and multiplication.


How does re-hashing affects security strength? I am currently saving hashed passwords for my website. Passwords are salted and then hashed using SHA3-512. I understand the security level of SHA3-512, as it is for all Keccak algorithms, is half the capacity (as it is explained here) , so 512 bits in this case.

My question is, how does re-hashing the resulting hash n times affect the security? Is there a way to effectively compute that? In the scenario of someone stealing the database, what difference would it make having the password hashed, say, 500 times vs just once?

I have seen a similar discussion about entropy after re-hashing here, but they don't address security.

By using more iterations you increase the work factor that an attacker needs to deal with needed to conduct a brute force attack.  This is a good thing.  More is generally better as long as it doesn't affect user satisfaction with UI responsiveness.  I think 10,000 iterations would be considered a low number at this point.  50,000 or 100,000 would be preferred.

Indeed one needs to consider the usual advice for password hashing,

Salt stored on the DB to disable Rainbow Table attack
Pepper stored on the Application server so that DB only attack will fail.
Work factor to increase the attack time by brute-forcing the users's passwords
Huge memory requirements against massive parallel run like in ASIC.

The good candidates for password hashing algorithms are PBKDF2, Scrypt, and Argon2id, the last one was the winner of the password hashing competition and should be preferable whenever available.


block cipher algorithms with variable block lengths Rijndael supports block lengths of 128, 192 and 256. AES does not but Rijndael does.

What other algorithms support variable block lengths? Or is Rijndael unique in that regard?

Rijndael-128, Rijndael-192 and Rijndael-256 are actually 3 different variants of block cipher that are very similar.

Simon, Speck, Threefish and RC5 also define different block size variants in similar way. Rijndael is not unique in this regard.

Block cipher that really has variable block length is XXTEA as its block length is not limited.


Can we use numbers as a pad in the Vernam cipher - why or why not? I was playing with the Vernam cipher on some online converter.

But when I tried to encrypt my message string with numbers, it remained unchanged.

Moreover, it was ignoring numbers and was encrypting as some alphabet appears in the key.

So, can we use numbers as a pad in the Vernam cipher - why or why not?

Yes, you can use numbers as a one-time-pad key. In fact, the CIA used to do it all the time, as did many.

When you use numbers the plaintext becomes letters by referring to a conversion table such as the venerable "Tapir" used by the STASI.

Here the addition will be modulo 10.  Vernam Cipher, or the one-time pad (OTP), can also be done modulo 2:

SENDING
-------
message: 0 0 1 0 1 1 0 1 0 1 1 1 ...
pad:     1 0 0 1 1 1 0 0 1 0 1 1 ...
XOR      ---------------------------
cipher:  1 0 1 1 0 0 0 1 1 1 0 0 ...

RECEIVING
---------
cipher:  1 0 1 1 0 0 0 1 1 1 0 0 ...
pad:     1 0 0 1 1 1 0 0 1 0 1 1 ...
XOR      ---------------------------
message: 0 0 1 0 1 1 0 1 0 1 1 1 ...

Or, it can be done modulo 26 (with English letters). For example:

Plaintext:  DARLING THE NIST CURVES HAVE BEEN COMPROMISED AND MY RANDOM NUMBER GENERATOR HAS A KLEPTOGRAPHIC BACKDOOR I FEEL SAD
Key:        NLQVT ZBOFW MFAVS RJMDE PGNEX GGQMU VOFNE PBWXT ICDWK VEEYL EGVWS ZRDKD IDJGO HWKFF MBEGA KEUNQ BEYDO
---------------------------------------------------------------------------------------------------------------------------------
Ciphertext: QLHGB MHHMA ZNSOU LAHHW WGIIY KKDOI HDWBQ XTAAT VFPUB VRHMX RAHXW QXHXH ZDCUF OWCFP XFTZO QVUCX JGZDQ MUYBN VQUZE RBR

The reason you could not insert numbers into the online encrypt/decrypt tool you found is because that tool was only designed for the modulo 26 addition of letters.

Here is one example of what a CIA one-time-pad key looked like during the Cold War:


What prime lengths are used for RSA? Let's assume we have an RSA 2048 that was produced by two primes multiplication. What is the digit's difference in those 2 factors? For example one prime is 1024 digits and second one 1024 or, one is 900 and second one 1148? Are there any limits for primes that could be used in RSA or it could be "1" and a 2048 bit prime?

When you multiply an $n$-bit integer by an $m$-bit integer, the product is an $(m+n-\epsilon)$-bit integer, with $\epsilon \leq 1$.

For RSA the security recommendations specify that secret factors of the public modulus must be of approximately the same size. If the difference in the number of bits is modest (less than a machine granularity) it could be approved.

There is also another suggestion from Shamir about generation of RSA keys for paranoid, which recommends for example a prime $p$ of say $1000$ bits and the other prime $q$ of $5000$ bits.


SEAL-CKKS max multiplication depth I am trying to understand how SEAL-CKKS scheme works and I wonder what multiplication level can we achieve using this scheme?

Like 100 possible?

I think it will most likely scale out of bounds with 100 multiplications.
Even with quite large polynomial modulus degree with small scale goes out of bounds with tens of multiplications.


How Shannon’s concept of perfect secrecy is linked with mutual information? For a system to be unconditionally secure

  $H(K) \geq H(M)$, i.e entropy of the secret key must be at least as great as the entropy of the plaintext

The mutual information is:

  $I(X;Y)=H(X)-H(X\mathrel|Y)$

The mutual information will be equal to zero if $H(X\mathrel|Y)=H(X)$.  That means the ciphertext does not leak any information about the key.

is it correct?

Almost—you changed letters partway through your question, so it's hard to be sure which mutual information you're discussing.

The attacker may know something about the message already: most messages are not uniform random noise, but highly structured.  For example, the attacker may know the message is either ‘DO NOT attack at dawn!’ or ‘YES, DO attack at dawn’.  The entropy of the message, in the attacker's state of knowledge, is exactly one bit; the entropy of the key and the ciphertext, however, had better be at least 176 bits, if the message is encoded in US-ASCII.

What you want is for the attacker's state of knowledge about the message to be the same even if they learn the ciphertext.  So you the mutual information of the message and the ciphertext to be zero: $I(M; C) = H(M) - H(M \mathrel| C) = 0$.  The mutual information of the key and the ciphertext $I(K; C)$ may be nonzero, e.g. in the above case it is pretty much guaranteed to be 1 bit, because knowing the key there's only two possibilities for the ciphertext.


cipher text only attacks on deterministic homomorphic encryption schemes If we consider a set of numbers say a set $s=\{a,b,c,d\}$ , where $a,b,c,d>1$ and the numbers $a, b, c, d$ do not share any relation between them , i.e. for any two numbers,  $n_1,n_2\in s$ the following relations are guaranteed to hold: $n_1+n_2\neq 0$ and $n_1*n_2\neq 1$.

Is it possible to break the fully homomorphic encryption scheme on these set of numbers?

Note
This is a followup to this question which does not restrict the set $s$ is at all.

This is an interesting question. If the input set does not have any identity element (for both mul and add operations) then one cannot construct a field and subsequently there cannot be homomorphic operations.  More clearly, if the input plaintext elements do not form a field (and their respective ciphertext elements do not form a field either)  then there cannot be homomorphisms of operations. This is by definition of Field.

So if the input set contains identity elements (and other properties needed to become a field) then while the given set members may not have any obvious relation. There would be some constant $c$ for which  $enc(n_1) + c * enc(n_2) = enc(0) $ subsequently finding which attacks mentioned in previous question apply !

Also  an attacker could try to find random complex relations among them. For example is $ enc(a) + enc(a) = enc(b) $ or is $ enc(a) *enc( b) = enc(c) $ etc. revealing inferences.