Is it possible to figure out the public key from encrypted text? Suppose Alice sends messages to Bob by encrypting the messages with Bob's public key.

Eve knows that the data is encrypted using RSA, but does not know the public key. Can Eve figure out the public key just by observing the encrypted messages?

And if so, approximately how much data would it take for Eve to discover the public key?

(assume that the public key used is the same throughout, and that Eve can potentially grab as many encrypted messages as she desires)

Actually, if Eve does have access to Alice's plaintext messages (and Alice doesn't do random padding as she should), then yes, Eve does have a chance, even with only two messages.

Suppose she guesses $e$ (the public exponent), and that it's not a not huge value (say, the common value 65537).

Then, for every plaintext/ciphertext pair $P_i$, $C_i$, she knows that (if $N$ is the unknown modulus):

$P_i ^ e = C_i \mod N$

or, in other words:

$P_i ^ e - C_i = k_iN$

for some integer $k_i$.

So, if she takes two plaintext/ciphertext pairs, and computes the value:

$gcd( P_1 ^ e - C_1, P_2 ^ e - C_2 )$

that is extremely likely to be the value $N$, possibly multiplied by a small integer.  Now, this gcd operation might be on operands of possibly a few hundreds of millions of bits long; not something you want to do every day, but it certainly in the realm of possibility if you're a bit patient.

Now, if Alice does do random padding before doing her RSA encryption, well, Eve doesn't have access to the values $P_i$, so this observation doesn't help her.


How can I generate a Koblitz curve? Is there the way to generate new Koblitz curves, over $\mathbb F_{2^n}$ and $\mathbb F_p$?

The Certicom SEC 2 standard says:

  The recommended parameters associated with a Koblitz curve were chosen by repeatedly selecting parameters admitting an efficiently computable endomorphism until a prime order curve was found.

What does "efficiently computable endomorphism" mean? Maybe it means that trace of the Frobenius map should be equal 1? I am confused about all the Frobenius maps, endomorphisms, traces, etc.

So, is there the way to generate Koblitz curves, or find efficiently computable endomorphisms?

The paper introducing the application of endomorphisms in arbitrary curves to cryptography was Robert P. Gallant, Robert J. Lambert, and Scott A. Vanstone, ‘Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms’, in Joe Kilian, ed., Proceedings of Advances in Cryptology—CRYPTO 2001, Springer LNCS 2139, pp. 190–200, after the initial idea of Neil Koblitz, ‘CM-Curves with Good Cryptographic Properties’, in Joan Feigenbaum, ed., Proceedings of Advances in Cryptology—CRYPTO 1991, Springer LNCS 576, 1991, pp. 279–287 (after whom the class of curves with efficient endomorphisms is named) to exploit the Frobenius endomorphism when it has trace 1 in binary curves.

The basic idea is that sometimes there is a scalar $\lambda$ such that computing $[\lambda]P$ given the $(x, y)$ coordinates of a point $P$ on the curve can be computed much more efficiently than by the standard double-and-add algorithm on the binary expansion of $\lambda$.

Here's a class of examples.  Let $p \equiv 1 \pmod 3$ be a prime, and let $$E/\mathbb F_p\colon y^2 = x^3 + b$$ be an elliptic curve over the finite field $\mathbb F_p$ of $p$ elements.  Suppose $\beta \in \mathbb F_p$ is an element of order 3, so that $\beta^3 \equiv 1 \pmod p$.  The map $f\colon (x, y) \mapsto (\beta x, y)$ (and $f\colon \mathcal O \mapsto \mathcal O)$ is an endomorphism—if $(x, y)$ is on the curve so that $y^2 = x^3 + b$, then $$y^2 = x^3 + b = 1\cdot x^3 + b = \beta^3 x^3 + b = (\beta x)^3 + b$$ so that $(\beta x, y)$ is also on the curve.  (Verifying $f(A + B) = f(A) + f(B)$ is left as an exercise for the reader.)  Of course, $\beta = 1$ satisfies $\beta^3 \equiv 1 \pmod p$, but the map is interesting only if $\beta$ is a nontrivial cube root of unity, a root of $\beta^2 + \beta + 1$, which exists iff $3 \mid \phi(p) = p - 1$ so that $p \equiv 1 \pmod 3$.  It turns out that if $B \in E(\mathbb F_p)$ is an element of prime order $n$, and $\lambda$ is a root of $\lambda^2 + \lambda + 1$ modulo $n$, then for any scalar $k$, $f([k]B) = [\lambda \cdot k]B$.  (Obviously, this requires that $n \equiv 1 \pmod 3$ too.)

In brief, in the subgroup generated by $B$, computing $(x, y) \mapsto (\beta x, y)$, which costs only a single multiplication in the coordinate field $\mathbb F_p$, is a much cheaper way to compute $P \mapsto [\lambda]P$ than the standard double-and-add algorithm on the binary expansion of $\lambda$, which costs $H(\lambda) - 1$ additions and $\lfloor\log_2 \lambda\rfloor$ doublings, where $H(\lambda)$ is the Hamming weight of $\lambda$.

To take advantage of this, for any scalar $k$, write $k \equiv k_1 + k_2 \lambda \pmod n$; then to compute $[k]P$, you can reduce it to

\begin{align*}
  [k]P &= [k_1 + k_2 \lambda]P \\
       &= [k_1]P + [k_2]([\lambda]P) \\
       &= [k_1]P + [k_2]f(P).
\end{align*}

The GLV paper goes into a little more detail about how to turn this into a complete scalar multiplication algorithm.  Unfortunately, the recursive decomposition of $k$ itself has costs, so the net improvement is only a modest 50% or so.

To generate a new prime Koblitz curve, or GLV curve, exploiting this particular endomorphism, lay out candidate primes $p_0, p_1, p_2 \ldots$ and curve parameters $b_0, b_1, b_2, \dots$ in some order of preference (say, primes nearest a power of two below it, and smaller parameters), and pick the first $p_i$ and $b_i$ such that

$p_i$ is prime,
$p_i \equiv 1 \pmod 3$,
the number $\ell_i$ of $\mathbb F_{p_i}$-rational points on the curve $E/\mathbb F_{p_i}\colon y^2 = x^3 + b_i$ is prime,
$\ell_i \equiv 1 \pmod 3$, and
all other security criteria of interest are satisfied.

Next, pick a generator $g$ of $\mathbb F_{p_i}$, and let $\beta = g^{(p_i - 1)/3} \bmod{p_i}$; and pick a generator $h$ of $\mathbb Z/\ell_i\mathbb Z$, and let $\lambda = h^{(\ell_i - 1)/3} \bmod{\ell_i}$.  These are by construction cube roots of unity, since, e.g., $\beta^3 \equiv (g^{(p_i - 1)/3})^3 \equiv g^{p_i - 1} \equiv 1 \pmod{p_i}$, and they are nontrivial because if $g$ generates $\mathbb F_{p_i}$ then it must have order $\phi(p_i) = p_i - 1$ and so $g^{(p_i - 1)/3} \not\equiv 1 \pmod{p_i}$.  Since there are two nontrivial cube roots of unity in each group, they may be mismatched like socks: you may have to use $\ell_i - \lambda - 1$ instead, or $p_i - \beta - 1$ instead, to make them match.

For binary Koblitz curves, see Koblitz's original paper.  The endomorphism in this case, on the $\mathbb F_{2^m}$-rational points, is the Frobenius map $f\colon (x, y) \mapsto (x^{2^m}, y^{2^m})$, with which $[2^m]P$ can be computed by $f(P) - f^2(P)$.  The trick is to find an appropriate extension field $\mathbb F_{2^m}$ over one of the four curve shapes $y^2 + x y = x^3 + a x^2 + b$ where $a, b \in \{0,1\}$.


How to handle points in extended finite field Following the response to my previous question, I would like to know if you could give me some information or give me a link on how to perform arithmetic operations once I changed a point from the field $\mathbb{F}_p$ to $\mathbb{F}_{p^2}$ ?
If I have an elliptic curve $Y^2 = X^3 + 1$ over $\mathbb{F}_p$ and I want to make a distortion map $\phi(x,y) \rightarrow (\beta x,y)$ to have a point of the form $\{a+bi : a,b \in \mathbb{F_p}\}$ in $\mathbb{F}_{p^2}$.
How can I compute the addition of two points in $\mathbb{F}_{p^2}$ for example since the field arithmetic is not the same ?
Thank you for your answers

As you note, the elements of $\mathbf F_{p^2}$ can be represented as $a+bi$  with $a,b \in \mathbf F_p$ and $i^2 = -1$; however note that this only works if $p\equiv 3 \pmod 4$.

Then you can add and multiply two elements of $\mathbf F_{p^2}$ in basically the same way you add and multiply complex numbers. Namely, $(a+bi)+(c+di) = (a+c)+(b+d)i$ and $(a+bi)(c+di) = (ac-bd)+(ad+bc)i$.

And the formula for point addition is the same, but you need to keep in mind that all your "numbers" are elements of $\mathbf F_{p^2}$ and must be handled as above.


Resources for mathematics of cryptology I am an undergraduate student looking for resources (books or lectures) explaining mathematics involved in cryptography, such as number theory, elliptic curves etc.
I found the book 'A Course in Number Theory and Cryptography by Neal Koblitz' hard to follow.

I think
Johannes Buchmann, Introduction To Cryptography, Springer, 2nd Ed, 2004
is very nice and pitched squarely at undergraduates. You can see a preview here
https://books.google.com.au/books/about/Introduction_to_Cryptography.html?id=BuQlBQAAQBAJ&printsec=frontcover&source=kp_read_button&redir_esc=y#v=onepage&q&f=false
Its contents are:
Integers
Congruences and Residue Class Rings
Encryption
Probability and Perfect Secrecy
DES
AES
Prime Number Generation
Public Key Encryption
Factoring
Discrete Logarithms
Cryptographic Hash Functions
Digital Signatures
Other Systems
Identification
Secret Sharing
Public Key Infrastructures
It is broad, as opposed to very deep, but really well written.


BouncyCastle style ThreadedSeedGenerator I've written a BouncyCastle style threaded seeder and was wondering about the predictability of the data the program generates.

The reason I'm not simply using BouncyCastle is because security isn't a concern, I don't want to use a whole library just for one function, and this code is MUCH faster.

The idea is to make several threads which operate on a circular buffer (a simple array), where each thread performs a different operation on the data in the buffer. The randomness comes from thread scheduling irregularities in the OS.

How much randomness can I expect from a mechanism like this?

C# code:

using System;
using System.Threading;

class ThreadedSeeder
{
    static public ulong[] buffer = new ulong[1024];
    static public bool doThread = true;

    public ThreadedSeeder()
    {
        MakeThread(Add);
        MakeThread(Multiply);
        MakeThread(Xorshift);

        Thread.Sleep(10);

        doThread = false;
    }

    static private void MakeThread(ThreadStart a)
    {
        Thread b = new Thread(a)
        {
            Priority = ThreadPriority.Lowest
        };

        b.Start();
    }

    static private void Add()
    {
        int i = 0;

        while (doThread)
        {
            buffer[i & 1023] += (ulong)DateTime.UtcNow.Ticks;
            i++;
        }
    }

    static private void Multiply()
    {
        int i = 0;

        while (doThread)
        {
            buffer[i & 1023] *= 6364136223846793005;
            i++;
        }
    }

    static private void Xorshift()
    {
        int i = 0;

        while (doThread)
        {
            ulong y = buffer[i & 1023];

            y ^= (y << 13);
            y ^= (y >> 17);
            y ^= (y << 5);
            buffer[i & 1023] = y;

            i++;
        }
    }
}

The approach is deeply flawed in many ways.

It is very plausible that the whole buffer is returned at zero under heavy load, which is something that an attacker can often intentionally cause (e.g. with a flood of network traffic requiring high CPU load; starting a number of https connections comes to mind). That's likely to be a practical disaster.
Mechanism: the three threads launched by ThreadedSeeder are set to Lowest-priority, thus it is reasonable that they won't do anything before the Thread.Sleep(10). If the machine has higher-priority-than-Lowest things do during that pause, execution can proceed to doThread = false before the Add thread has ever tested doThread, thus with Add performing nothing related to buffer. The same could hold for Multiply and Shift too, but that's immaterial, as these threads can not un-zero buffer even if they run.
More generally there is little insurance about the number of times DateTime.UtcNow.Ticks is called; that could be very few, including less than once per buffer entry, thus always leaving all the other entries at zero. The busiest the machine, the more likely it is that a buffer entry has no, one, or very few readings of DateTime.UtcNow.Ticks to influence it.
I see no mechanism preventing Multiply or Xorshift from competing with Add about what element of buffer it operates on, and thus void a change Add makes meanwhile. This is an uncontrolled race condition, and it can loose some of the entropy gathered.
DateTime.UtcNow.Ticks can be closely approximated by adversaries. That's supposed to be the UTC time, which is not a secret. Further, common mechanisms such as RFC 7323 high-resolution TCP time stamps allow to find what a particular machine believes the UTC time is, even when it is poorly synchronized. And when the machine is under light load, with one CPU running each thread including Add at full blast, the difference between readings will be reasonably repeatable.
The transformation made from DateTime.UtcNow.Ticks to what is in each element of the buffer is one among relatively few public transformations. And each of these possible transformations is trivially reversible (modular multiplication by an odd constant modulo a power of two is reversible in Multiply, as well as each of the three bitwise operations in Xorshift). Combined with 4, it trivially allows a very selective distinguisher on each buffer element output whenever there is only a single DateTime.UtcNow.Ticks that influenced it, also revealing which transformation occurred. It looks like this could be extended to a few such influences.
Neither the code nor the text of the question shows any effort to create explicit diffusion of the entropy gathered: elements of buffer are never mixed. Absent such mixing or/and post-conditioning before use of buffer, some degree of 2/4/5 can be a practical disaster.
Timing execution won't gather any entropy in some precisely controlled execution environments, including VMs/simulators used by hardware engineers or reverse-engineering of malware. Ultimately, the state of buffer on output, and whatever is deterministically derived from that, will dependent only on when the task is launched.


Why must IV be sent with each packet? I was reading about Encrypt-then-MAC and everywhere I go it seems people include the IV with the ciphertext generated for each message then MAC that and send all the information concatenated.

Why do I need to send the IV more than once?

I assume your protocol is message oriented. You needn't repeat the IV, but need to supply a new one for every message.

This can be either:

a random string from a CSPRNG,
a concatenation of a random string (sent once per session, if you're traffic-savvy) and a message counter (can be omitted from the packet, too), or
a member of any other unique sequence of 'reasonably random' block-sized blobs.

For CBC mode, the IVs should be sufficiently random, e.g. output from (2) may be hashed.


BEAST Attack: from guessing to decoding I understood the XOR trick that allows an attacker to guess a block of a previously sent message from the client to the server: the attacker forces the client to send the message $\tilde{m} = c_n \oplus m_g \oplus c$ where

$c_n$ is the last block of the last ciphertext;
$m_g$ is the attacker guess of the decryption of an arbitrary block of a previously sent message;
$c$ is the encrypted block that was chained with the real plaintext block $m$ (i.e., the one that attacker is trying to guess).

When the client sends $\tilde{m}$ to the server the result is

$$E_K(c_n \oplus \tilde{m}) = E_K(c \oplus m_g)$$

that is equal to $E_K(c \oplus m)$ iff the block $m = m_g$. Iterating this attack on all the blocks of a message $M$, the attacker can say if the message $M = M_g$.

So far, so good. What I can't figure out from now on, is how can he change his attack to decrypt a message, without doing a guessing attack. In particular, the problem is that if he tries to guess the block, he only has $2^{-64}$ (supposing to use a 8 byte block cipher) chance of success.

The articles that explain this second part of the attack say: "suppose you already know 7 byte out of 8, you only got a few more guessing to try ($2^8$)", but I don't understand how an attacker can know the first 7 byte of the block he want to decrypt.

As an example, this is an article that goes into the details of the attack. In the last part, he gives the following example

GET /index.html HTTP/1.1
Host: mysite.com
Cookie: Session=123456
Accept-Encoding: text/html
Accept-Charset: utf-8

How could an attacker find out the session number? This message would be encrypted as

GET /ind         ex.html         HTTP/1.1         \r\nHost         : mysite         .com\r\n         Cookie:          Session=         12345678
a7d25abbd67b2dbf e2ade7246ea5ed5 e99063ebe430b75b 746ae5eca36e2bc3 f6f62f99a076056f 6b14704973a779ae 7fa9300d4e490cba b6040b9542a59ad5 f9bb888ac3763722b

It's not clear (to me) how they achieved this result in the article.

Other resources that I've checked out are

BEAST attack confusion
https://www.slideshare.net/danrlde/20120418-luedtke-ssltlscbcbeast

(added) Disclaimer: in the years since 2011 browsers have closed the holes that allowed sending a fully-chosen first block plus practically all TLS stacks now do 1/n splitting for TLS1.0 CBC providing defense in depth. And many servers no longer allow TLS1.0 at all (particularly those subject to PCI-DSS). So this A and Q are mainly of historical interest.

Actually that example is wrong, because it counts \r and \n each as two bytes instead of the single byte each actually represents. Also it uses DES as the block cipher, which has been broken and obsolete since the late 1990s.

However, if we ignore those minor errors, in the very next paragraphs that article does correctly explain the principle (graphics simplified to what I can do in SX):

  .... On the other hand, if he can inject packets, he can make modifications to the request as well. Lets say he did this:
  GET /ind | ex.jsp H | ... | ession=1 | 2345678
  Here, I've removed one character from the page being requested to the completely innocent-looking index.jsp, but I've also split the victim block across an 8-byte boundary. Now, if I want to find the first digit of the session ID, I only need a maximum of 10 guesses:
  ession=0
  ession=1

Notice the latter is a result of the former; making the URL one character shorter caused a subsequent block to contain known text ession= (we know the server uses cookie name Session and the secret is the value) plus only one unknown character from the beginning of the value, so we only need to try a small number of possible guess blocks.

  ... Now, armed with the first digit, I can alter the request again:
  GET /ind | ex.js HT | ... | ssion=12 | 345678
  And make up to 10 guesses:
  ssion=10
  ssion=11
  ssion=12

Again by changing the URL we caused a block to contain known text ession=1 and a single unknown character (the second), making it easy to guess. Repeat as needed.

If index.js or even index.j causes a server error and attracts attention, as it might, it is easy to choose other URLs that are the correct length (modulo 8 for DES/3DES/IDEA or 16 for AES/Camellia) like query.cgi?search=able query.cgi?search=baker query.cgi?search=chubby

poncho's answer in the question you link says the same thing, except he calls it 'maneuver[ing] the cookie' into the desired position just before a block boundary and then 'remaneuver[ing]'.


What's a proper window size in RSA exponentiation? I want to use the window method for RSA modular exponentiation.
Because of Side Channel Attacks (SCA).
But I don`t know what a proper window size is.

Window Size (W) for many practical implementation of RSA Algorithm (like OpenSSL) is related to key length.for example in openSSL library for insecure 80 bits key, W is 4 or for insecure 320 bits key , W is 5 and for 1024 or 2048 bits key (length), W is 6.

note:Maximum of Window size in openSSL Library is "6"


Designing a key expander out of ciphers Is it possible to compose or combine $n$ ciphers ($cipher_0, cipher_1, ... cipher_n$) in such a way that they generate $n$ ciphertexts from the same key, $k$, and that recovering the key, $k$, from the $n$ ciphertexts is equivalent to breaking all $n$ ciphers.

Note that the size of the key, $k$, is the same as the size of the $n$ ciphertexts.

$$ ||k|| = ||cipher_i(k, k)||$$
$$ n \times |k| = ||cipher_0(k, k)||+||cipher_1(k, k)||+...+||cipher_n(k, k)||$$

I'm not asking about finding the pre-image of the $n$ ciphertexts, but rather the original key that was used.

This is related to this answer ( Changing algorithms during encryption ).

I think you can just generate all the plaintexts but one randomly, and make the last one the XOR of the key and the other plaintexts. To recover the key, one must recover all the plaintexts and XOR them. Even every plaintext but one gives you no information about the key.


Are HTTPS web sessions non-repudiable? (This is probably a basic question, and may be a duplicate; if so, just let me know.)

Suppose there are two clients A and B, and some server C. Suppose B and C establish an HTTPS tunnel, and C sends a response to B. And suppose B records the response, and sends it to A.

Can A verify that the alleged response from C was actually sent by C?

This is essentially equivalent to "Are HTTPS responses non-repudiable?". As far as I am aware, HTTPS only provides a secure channel, but does not provide digitally signed traffic.

Motivation

I'm tentatively planning to create a social network add-on which would allow users to flag other users who have sent them offensive material via private messages. I would hypothetically run a web service which would receive flag requests, and in order to avoid spam flags, I would need some way for the flagger to voluntarily send me a minimum but sufficient amount of information to verify that the private message actually exists.

In this scheme, I am A, the flagger is B, and the social network is C.

Is there any sane way to do this, without compromising the flagger's security?

No you can't prove that C sent something.
The only thing you can reliably prove to somebody is that somebody at some point had a HTTPS connection to C, by presenting the key exchange.

You can't prove that C send something because the record layer is symmetrical, meaning everything C sent, could be forged by B as he has to have the neccessary keys.

To understand, let's quickly recap how TLS (the security layer behind HTTPS) works:
The server and the client negotiate a shared secret using the key-exchange which also proves to the client that he is communicating with the correct server. Both parties derive four keys (2x authentication and 2x encryption). The data you consider is symmetrically encrypted and then symmetrically authenticated meaning the receiving party can as well construct this exact message using the symmetric methods (by encrypting and authenticating the message with the appropriate keys). If the user presents you with a full transcript of his side of the key-exchange and communication you can't be sure if he forged the claimed message or if the server sent it legitimately as he must have the keys for that or he couldn't have received the message in the first place.


Authenticated AES 256 CBC HMAC SHA512 - What's the right way to implement in C#? I have a "Encrypt-then-Mac" C# implementation of "AE_AES_256_CBC_HMAC_SHA_512" WITHOUT associated data, only authentication. In my code, I follow these steps to encrypt strings:

Generate a crypt random salt of 32 bytes using RNGCryptoServiceProvider;
Generate an auth random salt of 32 bytes using RNGCryptoServiceProvider;
Derive a crypt key of 32 bytes using Rfc2898DeriveBytes (PBKDF2) passing as parameters password bytes, previously generated random crypt salt bytes, and the number of 100,000 iterations.
Derive an auth key of 32 bytes using Rfc2898DeriveBytes (PBKDF2) passing as parameters password bytes, previously generated random auth salt bytes, and the number of 100,000 iterations.
Encrypt plain string bytes using AES with the 256 bits/32 bytes derived crypt key, in CBC mode, with a random IV and PaddingMode.PKCS7.
Write encrypted data bytes, IV, crypt salt and auth salt to a memory stream, respectivelly.
Compute the HMACSHA512 hash from the memory stream data, using the previously derived auth key.
Truncate the output of HMACSHA512 to initial 32 bytes and append this tag bytes to the end of memory stream.
Return the output bytes as Base64 string.

To decrypt I do the reverse way, comparing the sent tag with the calc tag before decrypt data.
I've been wondering if this implementation is correct, could you please give me a direction? Am I on the right way?

I'm going to use the answer field as I think the question is about doing a full review, which is typically off topic. However, since the comments are too short, I'll give a few hints and then allow the question to be closed.

You're on the right track if you have to use a password, however:

32 bytes of salt is excessive, you only need 16 bytes / 128 bits at max.

The idea to use dual PKBDF2 is not a good one as an attacker only needs one of the keys to verify a correct guess of the password. That means that per password you'd doing twice the work as an attacker needs to do. It is better to use the output of the first PBKDF2 and either split that up (e.g. using SHA-512 for two 256 bit keys) or derive keys using a KBKDF such as HKDF from it.

CBC mode is still vulnerable to attack if you don't verify the authentication tag first. You should make sure that the correct order is preserved, or use an AEAD scheme.

The IV might as well be set as all zero or be calculated from the password & salt, as the salt already provides the required randomization. You could even use the salt itself as IV.

Generally we write the IV / salt and other static information at the beginning - not the end - of the file. First of all, it's easier to find / parse that way and furthermore, you need the keys before you can start verification and / or decryption.

Base 64 encoding the entire output is fine if text is what is required. Otherwise you should just store the ciphertext and header as binary file.


Safety of AES ECB when used with openssl_seal function I'm trying to use PHP to encrypt files with a public key. I'm using the function openssl_seal that "encrypts data by using RC4 with a randomly generated secret key."

RC4 is considered unsafe so the alternative is to use AES ECB, but it too is generally considered unsafe (AES CBC is sadly not an option).

My question is:
Is AES ECB still unsafe, even when used with a randomly generated key, which is different for each file?

ECB is not secure even with per file keys, because if two blocks of the file are identical, this is visible in the ciphertext. The only * cases where ECB is secure is encrypting completely random data or encrypting a single block per key.

You should pick something more secure if your can help it.

If there is literally no other option than RC4 and AES ECB, you could use first RC4 and then AES ECB. RC4 would make it almost random and AES ECB would hide the biases. However, general concerns with cascaded ciphers would apply.

* Ok, fine, or if plaintext blocks are known to be unique, but that's rare and not the case here.


Implementation of Leighton-Micali Hash-Based Signatures I am trying to follow the RFC instructions but am not sure if I understand it. In the RFC there are also some test cases given, although my implementation yields different results.
Test Cases: https://tools.ietf.org/html/rfc8554#appendix-E
How is the SEED for private key generation used? It is stated, that LMOTS private key generation creates a 32B SEED at the start of the process, although does it create a new SEED for every new key from 0 to q=2^h-1?
The I value seems to be a constant 16B value generated only once for a given keypair.
In the test case 2, for
I=d08fabd4a2091ff0a8cb4ed834e74534
SEED=558b8966c48ae9cb898b423c83443aae 014a72f1b1ab5cc85cf1d892903b5439
the resulting public key is
K= 32a58885cd9ba0431235466bff9651c6 c92124404d45fa53cf161c28f1ad5a8e
although it is not stated for what q the LMOTS public key is generated, or does it mean, that this public key is the LMS public key, which is the root of the tree created by leaves of LMOTS public keys K? In this case this "K" is the "T[1]" value?
I have a slight problem using the reference implementation, as it is created for HSS. Do you know how can I force it to use only LMS?

It is stated, that LMOTS private key generation creates a 32B SEED at the start of the process, although does it create a new SEED for every new key from 0 to q=2^h-1?

If you use the suggested key generation method found in Appendix A, you use the same seed value for each Merkle tree.  If you use multiple Merkle trees (in HSS with L>1), then each tree gets its own SEED value

although it is not stated for what q the LMOTS public key is generated, or does it mean, that this public key is the LMS public key, which is the root of the tree created by leaves of LMOTS public keys K?

It is the HSS public key, which is the LMS public key of the top level Merkle tree.

I have a slight problem using the reference implementation, as it is created for HSS. Do you know how can I force it to use only LMS?

Tell it to use L=1; that is, when you call hss_generate_private_key, pass it a 1 as the levels parameter (the second one).


Why is release of unverified plaintext so Bad? Lately I came across of release of unverified plaintext. I was told that this is a bad thing, but I don't really get why. Isn't unverified plaintext released just nonsense? How can this be attacked in the context of authenticated encryption?

If you don't care about the authenticity of the plaintext, why are you listening for it in the first place?  You could make up plaintext on the spot with your ears plugged up and it would be just as good!

Here's the traditional example:  You are a general.  You receive a message that says, Attack at dawn!.  Since it is late at night already, your cryptographer on staff decided to rush it to you before verifying the authenticator on it.  Alas, it was a forgery.  The secret message actually sent by your fellow general was Attack at dusk!.  That message, encrypted by a one-time pad, was intercepted in transit, and its ciphertext xored with the Attack at dawn! xor Attack at dusk!.

That is:

the original plaintext $P$ was Attack at dusk!;
the modified plaintext $P'$ is Attack at dawn!;
the original ciphertext was $C = P \oplus K$ where $K$ is the one-time pad;
the modified ciphertext is
\begin{align*}
    C' &= P' \oplus K \\
       &= 0 \oplus P' \oplus K \\
       &= P \oplus P \oplus P' \oplus K \\
       &= P \oplus P' \oplus P \oplus K \\
       &= P \oplus P' \oplus C.
  \end{align*}

This may sound contrived and goofy, but mistakes like this still happen today—and much faster, because your cryptographer on staff is actually a computer making millions of decisions every second and leaking the content of your encrypted email to an attacker.

‘But, but,’ you say, ‘you contrived that example to make it really easy for the attacker to modify the message, by using xor.  Surely the well-known mode of operation like CBC thwart this?’  It does not.  In fact the additional unnecessary complexity of CBC enables other attacks.  A one-time pad with a one-time authenticator guarantees secrecy and negligible forgery probabilities; CBC guarantees nothing whatsoever about forgery—every string of blocks is a valid ciphertext in CBC, so the cryptography can do nothing to distinguish valid messages from invalid messages.

To make the one-time pad and authenticator practical, generating the one-time pad and the one-time authenticator key from a short secret by a pseudorandom function like ChaCha or AES-CTR is widely accepted to be a good method that nobody is likely to break.  Better yet, just use NaCl crypto_secretbox_xsalsa20poly1305 when you and your peer share a secret key and you want to exchange secret messages on a potentially compromised channel.  (In a sequential conversation, use message sequence numbers as the nonce; in a nonsequential conversation, pick the nonce uniformly at random and affix it to the message.)

Unauthenticated data is pure evil—don't touch it!


TLS handshake with client later on acting as a server Is it possible that a client which gets the Digital certificate of the Server during the TLS handshake then acts as a server? Because a server only needs to have a valid digital certificate which it already possesses.

Is it possible that a client which gets the Digital certificate of the Server during the TLS handshake then acts as a server? Because a server only needs to have a valid digital certificate which it already possesses.

Are you asking whether a client can take the certificate it receives from the server, and later pose as that server?  No, it cannot - in addition to the certificate, it would also need the private key that corresponds to the public key that's in the certificate.  That is, later on in the TLS protocol, the server is required to perform some operation that depends on the private key (which might be decrypting a value encrypted with the public key, or it might be signing some data - which it is depends on the ciphersuite and TLS version).

That private key is not sent through the TLS handshake, and so the client would not be able to perform either of these actions.  Hence, just the information that the client learns via the TLS connection is insufficient.


Why is counter mode encryption with a 16-byte cipher block not broken? We determine a system IND-CPA secure when an adversary has a negligible advantage after any feasible amount of queries.

AES256-GCM uses a 128bit block cipher.

We know that the distinguishability from random of counter mode encryption follows the birthday bound.

If we encrypt a stream of static data, with counter mode encryption we will never see a repeated cipher text block.

A purely random oracle will have repeats. The probability of this happening follows the birthday bound, eg after $2^{64}$ blocks we expect a repeat with probability of about a half. This would give an attacker an advantage of one half with $2^{64}$ queries, which is completely insecure.

If we assume a negligible advantage of $10^{-9}$, we reach that after about $2^{54}$ blocks. This means we should limit the maximum amount of blocks encrypted under a single key to $2^{54}$ blocks right?

This is way less than the advertised $2^{32}$ invocations of $2^{32}$ block chunks in NIST SP 800-38D.

Why don’t we see any recommendations of limiting the use of AES256-GCM dependent on its security parameter due to this attack on the counter mode encryption?

You are right that it is generally foolish to try to use AES-GCM for zetabytes of data under a single key.  The standard ought to have clearer data volume limits.

For a long time, the folklore understanding was that a non-collision in a CTR stream doesn't really leak all that much…until sweet32 demonstrated that it actually can be a real problem.  Still, what is feasible for a 64-bit cipher with online cost ${\sim}2^{32}$ may be considerably harder for a 128-bit cipher with online cost ${\sim}2^{64}$.

An alternative is to use crypto_secretbox_xsalsa20poly1305, which is a pseudorandom function family rather than a pseudorandom permutation family like AES, so the generic birthday distinguisher for permutation-based CTR doesn't apply.  One could also imagine using a wider-block cipher like Threefish-256, in which case the birthday bound is unimaginably larger; it is a pity that AES was standardized with a meager 128-bit block.


Curve25519 Base Points calculation I ran the following Sage script from  A.3. Base Points Section of rfc7748 for Curve25519

def findBasepoint(prime, A):
       F = GF(prime)
       E = EllipticCurve(F, [0, A, 0, 1, 0])

       for uInt in range(1, 1e3):
         u = F(uInt)
         v2 = u^3 + A*u^2 + u
         if not v2.is_square():
           continue
         v = v2.sqrt()
         point = E(u, v)
         pointOrder = point.order()
         if pointOrder > 8 and pointOrder.is_prime():
            Q=u^3 + A*u^2 + u
            return u, Q, sqrt(Q), point

res=findBasepoint(2^255 - 19, 486662)
res

(9, 39420360, 14781619447589544791020593568409986887264606134616475288964881837755586237401, (9 : 14781619447589544791020593568409986887264606134616475288964881837755586237401 : 1))

and got the expected result (from 4.1. Curve25519):

The base point is u = 9, v = 1478161944758954479102059356840998688726
   4606134616475288964881837755586237401.

But now I can't understand how sqrt(39420360) can be such an enormous value. Seems sqrt() is not math.sqrt() here. How did Sage calculate it?

It computed the squareroot modulo $2^{255} - 19$

A normal (that is, computed in the field of the reals) squareroot of 39420360 would be that value $Q$ such that $Q^2 = 39420360$, where the squaring operation is done as multiplication within $\mathbb{R}$

What Sage did is the equivalent operation within the field $GF(2^{255}-19)$.
That is, it found a value $Q$ such that $Q^2 = 39420360$ when computed in that field, or equivalently, $Q^2 \equiv 39420360 \pmod{2^{255}-19}$.

Because such a $Q$ is an integer between 0 and $2^{255}-19$ (all elements of $GF(2^{255}-19)$ are), it's not surprising it's a large value.


Bitwise homomorphic encryption I am fairly new to HE and would like a short clarification on how exactly integers are securely encrypted using bits. The main idea is that one encrypts each bit value and represents the n bit number as n ciphertexts like this: $$E(x)=(E(x1),E(x2),...,E(xn))$$ where xi is the bit on position i. Why is that secure, when I have just ciphertexts that correspond to '0' and '1' in a particular order? Example:
$$101 -> (E(1), E(0), E(1))$$  Can't I just guess 101 only from the E() values.
Why is this not possible?
Pointing me out to a good paper or read on that would be greatly appreciated!

Yes the adversary can guess the plaintext, and there is some probability $p$ his guess is correct. There is no way we can prevent that, and this is not a security flaw of the encryption scheme.

If the homomorphic encryption scheme you use is IND-CPA secure (or equivalently, semantically secure), the ciphertext should be indistinguishable. It entails that any (PPT) adversary cannot gain useful information from the ciphertext about the plaintext, hence the ciphertexts do not give the adversary any advantage in guessing the correct plaintext. So without the ciphertext, the probability of guessing correctly is $p$, and with the ciphertext, the probability of guessing correctly is $p+\epsilon$ where $\epsilon$ is negligible. Thus the ciphertexts, although are produced from the plaintexts, are useless from the adversary's point of view.

So the takeaway message is that security of an encryption scheme is not defined in term of "plaintext cannot be recovered" (which is impossible to achieve), but in terms of "the scheme does not make it easier for the adversary to recover the plaintext".


Why does Schnorr's Digital Signature scheme necessitate two prime numbers? One of the necessary components to the Schnorr Digital Signature scheme is a pair of prime numbers $p$ and $q$ such that $q$ divides $p-1.$ However, there is never a modular inverse taken of q so why is there an extra constraint on $q$? Couldn't $q$ be a number that divides $p-1$ but not prime?

First of all, while Schnorr Signatures are usually described that way, the two primes are not necessary for it to work. In principle, Schnorr works in any cyclic group.

However, to achieve security we need that the discrete logarithm problem in that group is hard.
So the reason for the choice of $q$ (which is the group order) is that DL is believed to be hard in subgroups of prime order $q$ of $\mathbb{Z}_p^*$, where p is a safe prime, i.e. $p=2q+1$. (And also for other values than $2$, but I'm currently not sure what the conditions are.)


How many AES-operations have to be watched for key-exploit by side-channel attacks? If I would like to exploit a used key by side-channel attack, one that measures electromagnetic fields, how many runs of the AES-128 do I need to spy on for a successful exploit?

I can't use any programs or software on that device. AES is software implemented. And I try (theoretically!) to spy in a distance of X meters. I am able to reduce the noise by surrounding emissions. But I can't have any type of access. So the attack model specifies using a sniffer.

I do not need an exact number of traces. There are only certain values for trace/distance that I could think of. I just found the TEMPEST attack, which needs 400k traces in a distance of 0.3 meters and 2.3m in 1 meter.

As pointed out by poncho, it is not possible to precisely answer your question since too many parameters are involved:

About the AES implementation: is it an unsecured implementation? Does it use masking? If yes, at which order? And so on...
The physical properties of the device also matter, does it leak a lot? Are there some hardware countermeasures such as a shield, a jitter, etc...
What equipment is used to measure leakages? Depending on the probe, the oscilloscope and its setup, the number of AES executions to achieve a 100% success rate may vary greatly.

To put it in a nutshell, you have to make practical experiments to answer your question.


PBKDF2 for key diversification I am looking for a secure key diversification function to create individual AES keys for a local smart card deployment. The keys need to be derived from a secret master key and the smart card serial number. Key calculation can happen on the host system.

Is it secure and practical to use PBKDF2(password=master_key, salt=serial_number, rounds=1000, dkLen=16) to get individual keys, or would an easier scheme like AES(key=master_key, data=serial_number) suffice?

Edit: the master_key will be created only for this purpose, with at least 128 bits of random data from a proper RNG. An issue that I wondered about is: typically, the salt is also a high-entropy value. Will this scheme become vulnerable if the serial numbers are not high-entropy (but still unique)?

For the purpose of key diversification (that is, assigning a unique key per device), a true master_key is customary; that is, one with plenty of entropy (like, 128 bits or more random bits). Edit: that's now stated in the question.

With that caveat, yes, PBKDF2(password=master_key, salt=serial_number, rounds=1000, dkLen=16)is appropriate to generate one 128-bit key; it's even overkill, especially as parameterized: rounds could be 1, since the only purpose of rounds is to stretch the password input, which is not needed if that input is a true key. Reducing rounds will speed up production, and use by a master server, with no cryptographic drawback.

And yes, AES(key=master_key, data=serial_number) is appropriate, and usual. As a benefit, that allows to just state: each card has a different key, something that has a (minuscule, and non-exploitable) chance not to hold with PBKDF2.

Edit: For the purpose of having strong diversified keys, the salt (typically, the serial number) needs not be high entropy. It is enough that it is different from one device to the other [one drawback occurs in case of temporary compromise of a resource capable of doing the diversification, without compromise of the list of salts/serial numbers of existing devices: it becomes possible to compute the diversified keys of all the devices if the serial numbers are sequential; PBKDF2 with rounds=1000, or whatever slow KDF, is not an adequate way to mitigate that risk; a delay is much better].

Also, ask yourself one question: is there potential for a side channel attack on the device(s) doing diversification? If yes, is PBKDF2, which is hash-based, really appropriate from that implementation standpoint? I have yet to see a hash implementation evaluated against DPA, contrary to AES implementations, where this risk of DPA attacks is at least assessed.

Side note: if key stretching was needed (it is not), rounds=1000 in PBKDF2 is clearly obsolete; that was a suggested minimum over 12 years ago, and IMHO was not enough even at that time. Moore's law and friends (in the form of the democratization of GPU and FPGA accelerators) have made it necessary to use at least rounds=100000 for equivalent security. Further, PBKDF2 is obsolete as a key stretcher, except perhaps if you have a hardware-accelerated hash and positively no memory; scrypt is the new state of the art.


Is there a standard, or widely accepted convention, for magic constants in crypto software? Inspired by Magic "Nothing Up My Sleeve" Numbers - Computerphile - YouTube [5:31]. If you just need a constant to begin your algorithm, and the value of that constant isn't important, why not have a widely known convention to always use the digits of Pi or Phi or other well known constant? It would seem that choosing arbitrary numbers is bad because it causes doubt as to the origin of the numbers which may lead some to suspect they were cherry picked for undisclosed weaknesses.

If you just need a constant to begin your algorithm, and the value of that constant isn't important, why not have a widely known convention to always use the digits of Pi or Phi or other well known constant?

Why not use all zeros or all ones then? Why not use what user provided us with?

There is a joke: Good thing about standards is that we have so many to choose from.

Often there are some values that are supposed to have specific properties, like being prime numbers. Then you have to use CSPRNG with that constant. Why not use this CSPRNG, why not that one. This one is simple, this one is more secure, this is newer, this is more well-established etc.

In short: because they are used in widely different settings, and we usually have some vague requirements:

Sometimes it has to be of any length and secure (DH safe prime generation)
Sometimes it has to be of any length and just simple constant (HMAC)
Sometimes it has to be specific length and have high entropy (AES)
Sometimes it has to be fairly independent from another constant we used somewhere else

Last requirement is probably worst. There might be interference from two different algorithms that happen to use same constant, and since you have one standard you increase such possibility.

Even if you managed to fulfill that somehow, some values are supposed to have high entropy, and some can be plain anything. Making them meaningful decreases speed your algorithm will work on.

All that and you gain that 1% extra security that nobody did plant bug in algorithm. Sadly IMO this doesn't give us much and prevents smart designs that are faster while retaining security.


Is it possible to recover AES-GCM plaintext when having everything but the additional data? I'm using the window.crypto library in browsers.

I use iv from window.crypto.getRandomValues, key from window.crypto.subtle.generateKey, and additionalData from a user-input password.

After the encryption, I store iv, key, and encrypted_content in the local storage.

If someone gets these three things, is it possible for them to crack it without additionalData?

GCM is an authenticated wrapper around CTR mode. The authenticated data is only considered when verifing the authentication tag - after decrypting the data.

If your adversary has the $(\text{iv}, \text{key}, \text{ciphertext})$ they can recover the $\text{message}$ but they cannot detect tampering.

I recommend that you use Argon2i with a user's passphrase, running inside a WebWorker instead of the main thread such that you do not freeze the browser while computing the key. Do not store the key in localstorage. Similarly, do not store the key in any globally accessible variables I.e. not in window.mysecretkey!

Libsodium has an argon2i implementation and has been compiled to JavaScript/asm.js and WebAssembly.


What is the best practices for storing ed25519 private keys which is used by nodes of my application to communicate with each other? I am developing some kind of a P2P network where the nodes communicate with each other via TCP and each message is signed by Ed25519 private key. I use libsodium for signing and signature verification.
I am currently developing a configuration of nodes and I had this question:
How to store public/private keys on a disk? Are there any common file formats and best practices for this?

If you are storing the file on disk then PKCS#12 Personal Information Exchange Syntax format is best practice. It is commonly referred to as a key store. But note that PKCS#12 relies on secret key encryption to encrypt the key store entries. That generally means that entries in such a store are encrypted with password based encryption. Which of course means that the library that performs the encryption has to be passed a password.

The entries themselves are generally wrapped using PKCS#8: Private-Key Information Syntax Specification which can also be used on it's own. PKCS#8 is a format to store a single encrypted key. It consists of an outer layer which defines the methods of encryption and an inner format that is used to describe what kind of key is encrypted. Sometimes the inner format itself is used to describe keys stored in plaintext (or wrapped by some other means).

Finally there are formats to describe the key themselves. These are again used within the PKCS#8 entries (much like Matryoshka dolls). Generally these use the X9.63 format for EC keys to describe the keys using ASN.1 (which is also the method of encoding PKCS#12 and PKCS#8). The ed25519 curve is however rather new so it seems to be lacking an official ASN.1 specification. There is however an internet draft that describes (a possible) standard format.


How to perform authentication without central server in P2P? How can one be sure that the man who you're talking with is the one who you think he is? i.e. How can one perform authentication in P2P network without a central trust server or Certificate Authority?

I'm just wondering how someone can make distributed (peer-to-peer) overlay network or chat using DHT for finding peers (like BitTorrent Chat has done).

BitTorrent chat uses DHT to find some information about peers and then to connect to them directly. I think it uses assymetric cryptography, as well. But this doesn't solve the problem of somebody trying to perform a MiTM attack by putting a lot of incorrect data about peers into the DHT (i.e. incorrect peer IP addresses or public keys).

For P2P authentication, you can go for web of trust concept. Simply this means, if someone is trusted by people you can trust, you can also trust that unknown person. In OpenPGP, a certificate can be signed by other users who trust the association of that public key with the person or entity listed in the certificate. So trust relationships can be propagated.
In addition This presentation discusses about P2P authentication, including authentication methods without central server. It proposes web of trust and few other concepts. Also I found a survey about this topic. You can choose a method according to your requirements. Hope this helps.


Quantum Cryptography Algorithms Implementations The Post Quantum Cryptography is a type of cryptography that lies on physics properties instead of mathematics , it has many algorithms and implementations like NTRU , McEliece , SIDH ... etc

But there is a difference between Post Quantum Cryptography and Quantum Cryptography , i'd like to know some algorithms of that and also if they have implementations for example on Github or any thing like that

Thank you

The Post Quantum Cryptography is a type of cryptography that lies on physics properties instead of mathematics , it has many algorithms and implementations like NTRU , McEliece , SIDH ... etc. But there is a difference between Post Quantum Cryptography and Quantum Cryptography

Let's try to classify this:

Quantum Privacy Amplification, which is the honest name of the better known Quantum Key Distribution. It was formerly the meat of Quantum Cryptography, and has become a sub-field of that. It matches “(re)lies on physics properties instead of mathematics” well. More precisely, the aim is establishing a trusted shared secret key between parties, with security relying on:

a Quantum physics model of the devices used;
mathematical facts (contrast with other cryptography, which additionally relies on a few mathematical conjectures);
a shorter trusted shared secret¹ key (hence Privacy Amplification).

Quantum Computing, which aims at performing useful² computing tasks that today's ordinary computers can't do. It uses physical devices directly relying on Quantum physics effects, without the abstraction/limitation of Boolean logic as today's computers do. There are many burgeoning and hopefully cross-fertilizing sub-fields, in which I vaguely distinguish three levels:

Experimental+theoretical³ physics to get these things going at the atomic scale and avoid the accumulation of errors; this subdivides according to technology and level of abstraction.
Study and even development of quantum algorithms to run on hypothesized quantum computers, with a subfield Quantum Cryptanalysis aiming at attack of cryptographic algorithms (not to be confused with attack of cryptographic hardware using quantum sensors)
Development of classical software tools running on classical computers to support development and simulation of quantum algorithms.

Post-Quantum cryptography, which develops cryptographic algorithms that run on ordinary computers and hopefully would resist Quantum Cryptanalysis. This field has “many algorithms and implementations like NTRU, McEliece, SIDH…”.

Sticking to the three disjoint things on-topic for crypto.SE, there is a lot of software involved in Quantum Privacy Amplification, Quantum Cryptanalysis, and Post-Quantum Cryptography. Some is on Github or similar. But as a matter of policy we generally do not recommend software.

¹ In some KPA/KQD setups, that initial key would only need to be kept secret until first used by the first party doing so, and could be public in the part of the plot where some old-fashioned courier then carries it to the second party by a process insuring its integrity. However, because couriers are slow, practice is to send the initial key in advance. In that case it must be secret while the courier moves it, else we loose security reducible to having a valid quantum model of the devices used.

² There are recent well-substantiated claims that we can do things with today's bleeding edge quantum computers that today's classical computers struggle at. However these things are not, yet, the kind of things ordinary heavy users of computing want to do. In particular, these things are as far as can be from cryptanalysis and “big data”. To caricature, today's bleeding edge quantum computers excel in the study of quantum phenomenons, by implementing them.

³ The two are hard to distinguish these days. Before 2020, “wear protective gear” did quite well, for guys in experimental mode need to protect themselves from liquefied gaz, laser, acid and other toxics… and protect their work and tools from the contamination their body generates.


Digital Certificate Chain Verification Does a certificate contain the complete chain of all certificates up to the trusted root certificate, or does the program that verifies certificates have to fetch each parent certificate individually in the chain to reach a trusted root certificate?

In Theory
In theory, either method works and has its advantages and disadvantages. Sending the entire chain up to the root means the other party (e.g., web browser) has everything they need to do the validation. A disadvantage is that more bandwidth is used.

Sending only the one certificate could yield better bandwidth usage (the verifying party still has to request other certs in the chain, but these could be cached). But, the certificates then must embed information on how to retrieve the next link in the chain. This creates problems because if that information ever changes. In the case of SSL, then, the server would have to constantly be checking if the location was still valid and accessible. This could lead to DOS attacks on any server in the certification chain causing the server to be inaccessible.

In Practice
I'm not exactly sure how existing protocols do this. It seems that SSL requires you to install the entire chain on the server (e.g., instructions for apache).


Is it possible to securely combine multiple hashes without hashing them? Let's say we have 1000 files and 1000 already computed cryptographic hashes for those files. Now we want to derive a single hash that authenticates all of them. Is there a more efficient way to do this than just hashing the concatenation of all those hashes (and thereby presumably calling the hash round function about 1000 times), without sacrificing security? What about also verifying the sequence?

What you're looking for is called a Merkle tree. BLAKE2b, a modern hash and an evolution of one of the SHA-3 finalists (BLAKE), supports tree hashing natively.

Edit: This may or may not actually be what you're looking for. Initially hashing the tree will take more work ($\mathcal{O}(n\log(n))$ operations) than just hashing the set of hashes, but subsequent partial updates will take less work ($\mathcal{O}(\log(n))$ operations). If you're ever updating the list, a Merkle tree is probably more efficient.


Why does PSS produce an EM message that's almost as long as the modulus? I try to understand the reasons behind the design of PSS scheme for RSA. Why is the length of the EM message (that is, the result of PSS transformation just before signing) equals approximately to the size of the modulus? Why PSS does not use a last call to a hash function (for instance SHA-256) so as to reduce the size of the resulting element before performing the exponentiation?

To prove that, for a generic hash function, forging PSS signatures is not much easier than computing arbitrary $e^\mathit{th}$ roots modulo a large composite of unknown factorization, we need to grant the attacker, who is trying to compute $e^\mathit{th}$ roots, oracle access to a forger for a signature scheme that uses the entire set of residue classes $\mathbb Z/n\mathbb Z$.  That way, any attack enabling forgery also implies way to solve the RSA problem at only slightly more computational cost than forgery.

If we granted the attacker access to a much more limited signature scheme that only revealed $e^\mathit{th}$ roots of a very small subset of possible residue classes, then an attack on that would not necessarily imply an easy way to solve the RSA problem.

And there are pitfalls with signature schemes involving subsets of the residue classes: e.g., if a signature on a message $m$ is defined to be an integer $s$ with $s^3 \equiv H(m) \pmod n,$ you may be tempted to test the similar-looking criterion $(s^3 \bmod n) \equiv H(m) \pmod{2^{256}}.$  Although $e = 3$ is a good sensible choice for near-fastest verification in a well-designed signature scheme (only $e = 2$ with Rabin–Williams will beat it), this modified criterion gives the adversary leeway to find a cube root by varying the higher-order bits of $s$ until they get an integer perfect cube whose low 256 bits happen to coincide with $H(m)$ for some chosen $m$.  Our friend poncho here sketched a similar attack on a variation on this theme several years ago.

This doesn't mean that a variant of RSA-PSS using a short hash would be insecure: only that we don't have confidence it can't be much easier than solving the RSA problem in general.  Compare, for example, Rabin–Williams, which can't be much easier than factoring the modulus—but we don't discard RSA-PSS simply because we haven't shown a reduction of the RSA problem to factorization.  For a similar example, see my proposed not-quite reduction of RSAP-KEM to factorization.

That said, having the security reduction helps cryptanalysts to focus their attention on a small number of problems—the RSA problem, factorization—for a large number of cryptosystems, instead of having to divide it among potentially much easier problems for each cryptosystem like RSASSA-PKCS1-v1_5, of which naive implementations may be vulnerable to the low-exponent attack I described above.  The security reduction guarantees that there isn't any much easier attack on the specific cryptosystem, so the cryptanalyst's attention might as well be focused on the general problem.


Cyclic group Generator I am reading a paper which defines an algorithm as following: Suppose for the BLS algorithm I have parameters (p,g , G, GT ,e) where , G and GT are multiplicative cyclic groups of prime order p , g is a generator of G and e: G X G --> GT.

Now the client choses a random x from Zp as secret key and from here the public key is derived as g^x.

Now this paper states that Let a <--R--G (which means that a is randomly chosen from the cyclic group G) be another generator of G.

But how is this possible? How can a cyclic group have two genertors. Is it possible ?

How can a cyclic group have two generators?

I believe part of the difficulty you are running into is because, in cryptography, we use the word 'generator' in multiple distinct (albeit related) ways.

One meaning (which is what is intended here) is this: we say that an element $g$ is a generator for a group $G$ if the group of elements $\{ g^0, g^1, g^2, ... \}$ is precisely the group $G$; that is, every element $h \in G$ can be expressed as $h = g^i$ for some $i$, and conversely, for every $i$, $g^i \in G$ [1].

Now, the obvious question is: for a given cyclic [2] group $G$, is the choice of $g$ unique?  It turns out that (as long as the order of the group is > 2) it is not.  In fact (as mentioned in the comments), if the size of the group is prime, then every group element (other than the identity) happens to generate the entire group, and so (in this sense) there are also generators.

Now, to give you some perspective, I will give you another meaning we give 'generator' that isn't meant by this question.  Sometimes, in a cryptographic protocol, we need to specify a public generator $g$ that will be used by both sides.  A simple example of this is Diffie-Hellman, where one side computes and publishes $g^a$, and the other side computes and publishes $g^b$; both sides must use the same $g$ value for this to work.  We call this common value the generator; yes, there are other values that are (in the first meaning) also generators for the group we're working in, however, they are not the generator as far as protocol is concerned.

[1]: for infinite groups, we also need to consider negative exponents; we don't worry about infinite groups that much in cryptography.

[2]: actually, the definition of a cyclic group essentially is "there exists a generator"


Is IPsec IND-CCA secure provided the used block cipher is a pseudorandom function? I am trying to solve the question whether
"IPsec is IND-CCA secure provided the used block cipher is a pseudorandom function" (with IPsec using a variant of Encrypt-then-MAC)

As a resource I am given the paper
Mihir Bellare & Chanathip Namprempre (2000). Authenticate
andd Encryption: Relations among notions and analysis of the generic composition paradigm

where I should focus on Theorem 3.2, which is the following implication:
INT-CTXT $\wedge$ IND-CPA $\rightarrow$ IND-CCA

Accordingly, I am trying to verify that the antecedent of the implication holds when using a pseudorandom function as a block cipher. I am currently stuck with the part whether the property of IND-CPA security holds. If I understood it correctly, the IND-CPA security depends on the mode of operation in which the pseudorandom function is used.
In our lecture it was mentioned that an encryption scheme using a pseudorandom function as block cipher is indeed CPA-secure if the CTR mode (with a randomly chosen initial ctr) or the CBC mode is used. However, as far as I know it does not hold for other modes.

Therefore, I would like to know which mode of operation is used by IPsec and whether my approach makes sense.

I would like to know which mode of operation is used by IPsec

That depends on what is negotiated; if we assume we're using AES as the block cipher, then the standard modes (that is, ones which have transform numbers assigned by IANA) are CBC, CTR and GCM.

  and whether my approach makes sense.

Sounds good to me.


Is it necessary to prove EUF-CMA security of blind signature based on one-more type assumption？ One more type means one-more DL, one-more DHP, etc. I find many papers do the EUF-CMA security proof in this way. Is it necessary? What is the difference between proof based on one-more type assumption and one based on non-one-more type assumption? Is the one based on one-more type assumption stronger?

One more type assumptions are a better fit for blind signature schemes since they fit their security model (e.g. receive valid but anonymous coins from a bank where you should not be able to spend more than you received).
Indeed they are stronger when compared to other types of assumptions (eg. DLOG).
However there have been proofs of security based on the dlog such as the proof of Pointcheval Stern on the Okamoto Schnorr blind signature unforgeability in https://www.di.ens.fr/david.pointcheval/Documents/Papers/2000_joc.pdf where the situation is better explained.


What are Cryptographic Multi-linear Maps? I've encountered this term many times in the fields of Fully-Homomorphic Encryption and Obfuscation.

I want to learn those subjects and Cryptographic Linear Maps seems to be an obstacle in the way.

Can you help me with that and explain it in simple words (as much as you can)?

Ok, I will start with a cryptographic bilinear map.

Cryptographic Bilinear Map

A cryptographic bilinear map $e: G_1\times G_2 \rightarrow G_T$ as the name says is a map that is linear in both components, i.e., it holds that for all $g\in G_1$ and $h\in G_2$ and all $a,b\in Z_p$ (where $p$ is the order of all groups) we have that $e(g^a,h^b)=e(g,h)^{ab}$.

For cryptographic use we want a setting
where the discrete logarithm problem is hard in $G_1,G_2$ and $G_T$ (typically one requires also that variants of the computational Diffie Hellman problem are hard and the decisional Diffie Hellman problem may be easy in $G_1$ - that depends on the type of pairng, e.g., symmetric or asymmetric and w/o efficient computable isomorphisms from $G_2$ to $G_1$). Furthermore, we want $e$ to be efficiently computable and non-degenerate, i.e., if $g$ and $h$ generate $G_1$ and $G_2$ respectively, then $e(g,h)$ generates $G_T$ ($e$ which maps to $1$ in $G_T$ is useless).

For pairings there are various Diffie-Hellman like assumptions (bilinear Diffie Hellman assumptions), e.g., in the setting of $G_1=G_2$ and $g=h$ the bilinear CDHP states that it should be hard to compute $e(g,g)^{abc}$ given $g^a$, $g^b$ and $g^c$.

Groups $G_1$ and $G_2$ that we know today where we find such a pairing $e$ are (subgroups of) rational points on elliptic curves (or abelian varieties) over finite fields and the group $G_T$ is a subgroup of a multiplicative group of a finite field. The map $e$ thereby is a variant of the Weil or Tate pairing.

Cryptographic Multilinear Map

Now, a cryptographic multilinear map for $n>2$ is a $n$-linear map $e:G_1\times \ldots \times G_n \rightarrow G_T$, i.e., a map that is linear in all $n$ components. Essentially one requires the same as above but you want to have that it be $n$-linear, which basically means that $e(g_1^{a_1},\ldots,g_n^{a_n})=e(g_1,\ldots,g_n)^{\prod_{i=1}^n a_i}$ and that it is non-degenerate. As in the bilinear case we can also define multilinear CDHP etc (see for instance here).

Such cryptographic multilinear maps would be a very nice tool if they would work as in the pairing setting (as envisioned in the paper linked above). However, the recent constructions for cryptographic multilinear maps are based on tools from constructions of fully homomorphic encryption schemes (AFAIK there is a construction using ideal lattices and one over the integers) and there the encodings of the elements are noisy and thus are approximations of the ideal case and not that nice as within the pairing setting working with cyclic groups. Note that some papers simply assume the existence of a multilinear map that behaves like an extension from the known bilinear map setting with the associated Diffie Hellman assumptions  (although it is not yet known if such multilinear maps exist). Worth mentioning is the first candidate construction for indistinguishabiliy obfuscation that relies on a concept related to multilinear maps (which also yields functional encryption for circuits).


Private Information Retrieval and Writing at the same time possible? Are there any (possibly multiserver) private information retrieval (PIR) schemes that support private reads and writes (so called PIR Writing) at the same time, while having sublinear (in the database size) communication overhead?
The most recent, very efficient, PIR scheme I could find is the one based on distributed point functions, but it seems to only support one operation at a time. That is, I can either outsource a database, where I have private reads or I can outsource a database, where I have private writes, but not both on one database. Preferably I am looking for something that is not based on heavy tools like FHE.

Here's a single-server one: https://link.springer.com/content/pdf/10.1007%2F978-3-642-13708-2_26.pdf

Obviously the data would need to be encrypted, otherwise it will be obvious what was changed, and the PIR-write protocol needs to somehow re-randomize the ciphertexts that were not modified.


Minimalist memory-hard function? What would be a minimalist memory-hard function, reasonably conjecturable to

require $\approx2^k$ bits of memory per running evaluation, $k\approx32$;
require $\approx2^n$ R/W accesses to $2^w$-bit words per evaluation, $w\approx6$ (likely $n\ge k-w+3$ or something on that tune);
be practically impossible to significantly optimize using a much smaller cache memory or a different word width so as to lower the above number of accesses?

My purpose is convincing a hardware designer that speeding-up a full-blown memory-hard function, much beyond the cost of main memory accesses, is doomed; see comments there. I thus don't care about proof of the conjectures, that auxiliary functions (as used for computing addresses and data) offer more than basic cryptographic strength, resistance to hypothetical optimizations requiring at least twice as much more main memory, side-channel resistance..

Tentative answer to my own question. Please criticize!

All variables in capital are one 128-bit word, with $w=7$. Parameters are as in the question, and $k-4\le n\le128$.
I use an auxiliary arbitrary public permutation $\large\mathscr P$ of one word; a simplistic one is constructed using Addition-Rotation-Xor. A function evaluation goes:

set $D$ to the function's input
memory setup: repeat for $C$ from $2^{k-w}-1$ down to $0$

write $D$ to memory at address $C$

set $A$ to zero.
main loop: repeat for $C$ from $2^n-1$ down to $0$

set $A$ to $A\oplus{\large\mathscr P}(D\oplus C)$
read $R$ from memory at address $A\bmod2^{k-w}$
write $D$ to memory at same address
set $D$ to $D\oplus{\large\mathscr P}(R\oplus C)$

output $D$.

Some rationale of the design:

Address of the next memory location used depends, thru two nested invocations $\large\mathscr P$ and depending on chronology thanks to $C$, on the value previously read $R$, and will-be result $D$.
The main loop has reversible effect on the combination of memory, $A$ and $D$; hence the input-to-output entropy loss can be estimated as at most 0.8272… bits.
Mixing of counter $C$ makes getting into a short cycle unconceivable.
The average number of accesses to each memory cell is at least 8.

Permutation $\large\mathscr P$ is:

set $X$ to the function's input
repeat for $t$ each of the six constants 3, 5, 7, 13, 23, 43

set $X$ to $3\big(X\oplus(X\operatorname{\lll}t)\big)\bmod2^{128}$ where $\lll$ is left rotation on 128 bits

output $X$.

Note following comment: this is a toy/simplistic permutation, not to be reused outside the present context of deep iteration, and was not the focus of the answer. There are far less rounds than necessary for complete propagation of a bit difference; but in the context, two invocations (thus twice more rounds) are nested from $R$ to $A$. Zero is a stationary point, since the only constants are rotation counts (hastily obtained by starting from 3, doubling, and rounding down to the next prime).
Tentative test vector: for ${\large\mathscr P}\big({\large\mathscr P}(1)\big)$ I get 0x5be8f27af383369a91de3e614e6650dd.


Common Modulus Attack in RSA Consider the following scenario:

The Information Security Department (ISD) of an organization issues each of the organization's employees, domestic and abroad, with an individual RSA key. To simplify the PKI maintenance for the organization, it was decided that a single modulus n will be generated by the ISD and each employee will be issued a personalized public encryption exponent e, and corresponding private decryption exponent d. All key-generating computations will be done by the ISD. This way the organization will also have a copy of each employee's RSA key-set. The reasons for this were given as:

When an employee loses a key, the ISD can always reissue a key.
When an internal security leak is suspected, the ISD will have all keys available to investigate the incident.
When law enforcement obtains a "supina" for a perticular employee's RSA keys, a central office - the ISD - can see to it that the "supina" is honored.

Suppose further that the ISD decides that the encryption exponents will be chosen so that the gcd of any pair is 1; for example, to speed up selecting values of encryption exponent e, the ISD selects from a database of prime numbers.

An eavesdropper can under certain circumstances decrypt messages sent in this system without needing access to any private keys.

Suppose that the CEO dispatches the same message M to two different offcie managers whose encryption exponents respectively are $e_1$ and $e_2$. The encrypted messages are:

$E = M^{e_1} \bmod{n}$ and $F = M^{e_2} \bmod{n}$

An eavesdropper has access to the public keys n, e1 and e2, and the encrypted messages E and F. Since gcd($e_1$, $e_2$)=$1$, the eavesdropper applies the extended Euclidean algorithm to compute integers x and y such that $x \cdot e_1 + y \cdot e_2 = 1$. Then with x and y in hand, the eavesdropper computes

$E^x \cdot F^y \bmod{n} = M$ (original message)

But unfortunately I don't understand why it makes sense that $E^x \cdot F^y \bmod{n} = M$ (original message). Is anyone here able to drop some ideas to me?

You just have to do some simple algebra.

$$E^x \cdot F^y$$
$$(M^{e_1})^x \cdot (M^{e_2})^y$$
$$M^{xe_1} \cdot M^{ye_2}$$
$$M^{xe_1 + ye_2}$$

Well, what is $xe_1+ye_2$?


Exact communication of the IPS compiler? I'm reading papers related to the IPS compiler.

I'm confused about one point: The paper IPS08 (PDF) proposed a protocol with $O(s)$ communication for a circuit of size $s$ in the OT-Hybrid model.

Are they actually assuming a bit-OT Hybrid model, where parties can perform OT on single bits? For example, the communication of GMW is counted as $O(m^2 s)$ for m parties with circuit size s.

They do not specifically assume a bit-OT… but at least in the semi-honest case, it seems that having an ideal bit-OT is indeed sufficient.

If you are wondering about the fact that they do not specify which kind of OT they use: their purpose was to focus on a black box use of the primitive; bit OT and string OT can be easily reduced in black box to each other.

And if you are wondering about the fact that the communication is only $O(s)$: the costs of the OTs are not counted, as they are replaced by an ideal primitive to which all the players have access.


Why Distance-128 relation in Plain texts is reflected in Cipher texts The two text having relation as "\x10\x11" → "\x90\x91" (80+10) will have relation after encryption/decryption also in RC4. Following code clearly describes the problem I am mentioning.

 from Crypto.Cipher import ARC4
 key = '12345678'
 obj1 = ARC4.new(key)
 obj2 = ARC4.new(key)
 d1= obj1.decrypt('\x01\x02\x03\x04\x05\x06')
 d2= obj2.decrypt('\x81\x82\x83\x84\x85\x86')

 p1='';p2=''
 for i in d1:
     if ord(i)>=128: p1+=chr(ord(i)-128)
     else: p1+=chr(ord(i))

 for i in d2:
     if ord(i)>=128: p2+= chr(ord(i)-128)
     else: p2+=chr(ord(i))
 print p1==p2

output: True

I mean if i have two ciphers that are related with (0x80) 128-distance, I get some relation in decrypted outputs. I tried it many times and got the same replation with respect to the ciphers’ characters related as +-7F. What is the reason behind it?

The short answer to your question is because RC4 is a stream cipher.

Try comparing the xors of the two plaintexts and the two ciphertexts... Better still, replace the second ciphertext with \x00...\x00 and then look what happens.

A stream cipher works by taking a secret input (the key) and turning it into a long stream of pseudo-random data (the stream). This output stream is the xor'd with the plaintext to produce the ciphertext. To decrypt, we again generate the stream, but this time by xoring it with the ciphertext we retrieve the plaintext.

One of the biggest issues with using xor is that bit's flipped in the plaintext translate into bit's flipped in it's ciphertext.


2048 bit hashing and 1024 bit symmetric encryption The most strongest public encryption key today, is $256$ bit symmetric (e.g. AES-256) and $512$ bit hash (e.g. SHA-512).

So, if there are 2048-bit hashing and 1024-bit symmetric encryption, it is theoretically unbreakable by the universe by current science.

Today, the theoretically smallest length is planck length (~$10^{-35}$ meter), and the theoretically smallest time is planck time (~$10^{-44}$ seconds). The observable universe is $93$ billion light years ($10^{27}$ meter), and the age of universe is $13.8$ billion years ($10^{18}$ seconds).

Just a simple calculation, we can found that the universe is actually around $10^{186}$ cubic planck length (or planck volume).  ($(10^{27}/10^{-35}) ^3$), and the age of universe is $10^{62}$ planck time ($10^{18}/10^{-44}$).

If the smallest particle (planck length) in universe trying to crack the 1024-bit password, and it can crack 1 time in the smallest time unit (planck time). Using all universe particle to crack the password in fastest way, it still not possible to crack a 1024-bit password ($10^{186}$ planck length $10^{62}$ times = $10^{248}$, which is much smaller than $2^{1024}$ bit = $10^{308}$ combination).

Due to birthday problem, 2048-bit hash strength is approximately equivalent to 1024 bit encryption.

So, is that we can conclude that, 2048-bit hash and 1024-bit symmetric encryption is never obsolete. No matter the strongest quantum computer is, it still impossible to crack. But Why there are no 2048-bit hash and 1024-bit encryption available in the public market ?

Because the numbers required to achieve that level of security are much lower, even versus an adversary with a quantum computer. See this question/answer on security.stackexchange for the specifics.

Assuming that 256 bits/512 bits are secure for encryption/hashing, anything greater cannot serve a functional purpose in terms of security (it cannot be "more secure").

The biggest major factor besides security is performance. If the algorithms are not more efficient then their traditionally sized counterparts, then there is no motivation for their creation. Your proposed extremely large algorithms could potentially have performance issues. Using copious amounts of data is not necessarily register or cache friendly. Such large algorithms could also be difficult/expensive to implement on constrained/dedicated hardware.


Is it safe to split the output of PBKDF2? I would like to know if splitting a key generated by PBKDF2 to derive two keys is a safe practice.

Concretely, in my system, I need to derive two keys. One for symmetric cipher used in the client side, and one for authenticating the user by sending to the server. The first key is never sent to the server so that only the client knows how to decrypt ciphertexts.

User enters email and password;
Derive k <- pbkdf2(password: password, salt: email, alg: 'sha256', iteration: 10000, dkLen: 512);
Split k into (k0, k1) = (k[0:255], k[256:512]). Use k0 as client side key and send k1 to the server.

My idea is that there is no risk in splitting the key in such manner because the key is a pseudo-random string. Any ideas?

It's secure as the bits are unrelated. It is not secure because it removes a bit of security by giving advantage to an attacker.

PBKDF2 has indeed been defined to generate a dynamic amount of key material. The bits of the output are independent of each other, and having any part of the output doesn't give you any information about the rest of the output values. So $k_0$ and $k_1$ are unrelated because PBKDF2 is indeed a pseudo random generator. Great.

However, PBKDF2 has also a design problem: if you require more than the output of the hash function (in this case SHA-256) then it requires you to perform all the iterations again to calculate the next block of output. This is problematic as an adversary may not need to perform those calculations themselves.

For instance, if the attacker just needs to compare against a value encrypted with $k_0$ then the adversary doesn't need to calculate $k_1$: just calculating and validating $k_0$ is enough to guess the password. You, on the other hand, need $k_1$ so you will have to perform all that work without gaining any advantage from it. As the adversary only needs half the work, obviously you lose one bit of secure. And, as your keys are both the exact output size of the hash function, you've inadvertently made it easy for the adversary.

There are a few ways around this. First of all, you can use a more modern function such as Argon2 (check for secure Argon2 configurations first). Secondly, it is possible to use the output of PBKDF2 and derive two keys from it using a key based key derivation function or KBKDF such as HKDF, e.g. k0 = HKDF(k, "Enc") and k1 = HKDF(k, "Auth").

Finally, you can "hack" PBKDF2 by using SHA-512 and have it deliver 512 bits, which you can split. That's solution obviously doesn't scale well, but it is useful if the other options are not available to you, and it is very simple to achieve; you just have to change the hash function after all.


In RSA, how to make sure that $p-1$ and $q-1$ are still hard to factorize? See this question. The comment by Brett Hale stated:

  On the other hand, ensuring $(p - 1)$ has a large prime factor requires very little extra effort.

What's actually the 'little extra effort'?

The procedure to do this is:

Find a large prime factor $r$
When searching for the prime $p$, look among numbers of the form $rk+1$

When we find our prime $p$, we know that $p-1$ will have $r$ as a factor.

Step 1 is comparatively cheap compared to original search from the prime $p$; we select an $r$ which is large (as far as factors of $p-1$ go), but is small compared to $p$.

Step 2 is the original prime search, with an additional condition.  That additional condition doesn't actually slow it down; it doesn't make checking a candidate any more expensive, nor does it make it less likely that a candidate is actually prime.

Hence, the has little extra effort; step 1 is fairly cheap, and step 2 has no additional cost.


Proving a function is one way hash function I am working on a project which computes the hash of the given input, I have to prove that the function is pre-image resistant that is given an output we cannot get back to the input.

While proving the function to be pre-image resistant. The function that I am using has a property that for every output there are more than one possible input. In other words, I have proved my function is many to one function. Is it sufficient to show that we cannot calculate the inverse of the function because it is a many to one function and not a one-one function.

The inverse cannot be calculated, you're right. However, in can be guessed.

In many scenarios, for example cracking hashed password, it's enough for the attacker to know a set of possible inputs which result in certain output (of course if their number is reliable) instead of  one certain value.

So if the one-to-many function is weak, given the output $y$ the attacker can calculate $x_1,x_2,...,x_n$ such that for each $x_i$ $H(x_i)=y$ and try them one by one.

Concluding - it's not enough to show that it's one-to-many function. You must also show that finding the set mentioned above is computationaly hard for your function.

PS. You might wonder why $n$ can't be so big that trying all possible inputs resulting in a certain output will be impossible. This would cause another weakness - low collision resistance.


Total password count, given length and pool size First, if my password is exactly 8 characters long, derived from a pool of 95 characters, then is the total amount of passwords I can create simply $95^8$                                                                                (6,634,204,312,890,625)?

Secondly, if my password can be upto 8 characters long, derived from a pool of 95 characters, then is the total amount of passwords I can create computed the same way, or would it be something like $95^0$ + $95^1$ + $95^2$ + $95^3$ + $95^4$ + $95^5$ + $95^6$ + $95^7$ + $95^8$ (6,704,780,954,517,120)?

Is the correct term for these called permutations, or search space or key space, or...?

Thanks for the assist!

Possible combinations (permutations) = sequenceOptions to the power of sequenceLength

Assuming a pool of 95 sequence options

sequenceLength 0 = 0 permutations (950)
sequenceLength 1 = 95 permutations (951)
sequenceLength 2 = 9025 permutations (952)
sequenceLength 3 = 857375 permutations (953)
etc

This is not limited to passwords/characters. For example, when a password is put through a key derivation algorithm, it ends up as a string of bits for which there are two options; 0 and 1.  Hence, a 256 bit length key contains 2256 permutations.

More simply, a 4-digit numeric pincode has 10000 (104) possible permutations.

As for the second part of your question, yes; if the sequenceLength were <= 8 then the total number of permutations would be 950 + 951 + 952 + 953 + 954 + 955 + 956 + 957 + 958

Of course, the above assumes that each option in the sequence can appear more than once. If that's not the case then factorials come into play.


When only using one-way hashing, is it possible to tell the number of characters changed between the old and new password? The other day when changing my password on a Solaris 10 system I was surprised that Solaris was able to detect that I hadn't changed enough characters between the new and current passwords.

MINDIFF is the password security configuration parameter that specifies the minimum number of characters that need to be different between the current and new password when the password is being changed.

I'm pretty sure that Solaris is using one-way hashes to protect the secrecy of the plain-text password.

That got me thinking, how can Solaris (or any system) detect which characters have changed between passwords if it is using a one-way hash to validate passwords?

When only using one-way hashing, is it possible to tell the number of characters changed between the old and new password?

No. If the hash function is strong, even a single bit change will give a completely different hash.

The only way to tell how many characters differ between a particular unknown hash value and a known password would be an exhaustive search, which might be possible for determining e.g. that more than one character must differ, but not in general.

  That got me thinking, how can Solaris (or any system) detect which characters have changed between passwords if it is using a one-way hash to validate passwords?

Most likely answer: it asks for both your old password and the new when changing passwords, and can compare them at will.

Alternatively: it stores something other than just a hash (e.g. an encrypted password) that does allow comparisons. You should suspect this if a system has rules that concern more than one previous password. That is not a secure way to store passwords.


How to find the value of a vector modulo a basis in lattice-based cryptography In Gentry's paper on fully homomorphic encryption using ideal lattices, he finds the values of vectors modulo a certain basis. For instance:

$\psi \leftarrow \psi' \mod B$

Taken from page 69 of Gentry's thesis.

What does it mean to evaluate a vector modulo a basis?

Examining the definition provided by A. Sakzad, I now have the intuition for what this means which I'll explain through an example.

In the diagram below, the red dots are a lattice, and the two red arrows represent a basis, $B$, for this lattice. We have a green vector, $ψ'$ = [2, 2]. We might ask which point on the lattice $ψ'$ is closest to. If we are just looking at this in the grid reference frame, $ψ'$ is equidistant from [3, 1] and [3, 3]. But within the reference frame of basis $B$, which is shown by the red parallelograms, $ψ'$ is closest to (3, 3). The value of $B⋅⌈B^{−1}ψ′⌋$ is the point in the lattice to which $ψ'$ is closest in the reference frame of $B$. $ψ=ψ′(\mod B)=ψ′−B⋅⌈B^{−1}ψ′⌋$ is the vector from $B⋅⌈B^{−1}ψ′⌋$ to the original vector. It could be viewed as the error or remainder when $ψ′$ is approximated by a point on the lattice. In the diagram below, $ψ$ is the blue arrow.

Since the basis vectors are [3, 1] and [0, 2] the basis matrix is:
$$
B = \left( \begin{array}{ccc}
3 & 0\\
1 & 2 \end{array} \right) $$
Doing the math we find that (3, 3) is indeed the value of $B⋅⌈B^{−1}ψ′⌋$:
$$
B⋅⌈B^{−1}ψ′⌋
=B⋅⌈1/6 \left( \begin{array}{ccc}
2 & 0\\
-1 & 3 \end{array} \right)
\left( \begin{array}{ccc}
2\\
2 \end{array} \right)⌋ $$
$$
= B⋅⌈\left( \begin{array}{ccc}
2/3\\
2/3 \end{array} \right)⌋
= \left( \begin{array}{ccc}
3 & 0\\
1 & 2 \end{array} \right)
\left( \begin{array}{ccc}
1\\
1\end{array} \right)
= \left( \begin{array} {ccc}
3\\
3\end{array} \right)
$$
Therefore the remainder of $ψ′$ modulo the basis is:
$$ ψ=ψ′(modB)=ψ′−B⋅⌈B^{−1}ψ′⌋ = \left( \begin{array} {ccc}
-1 \\
-1 \end{array} \right)
$$


Algorithm to factorize $N$ given $N$, $e$, $d$ I have an RSA public key (public modulus $N$ and public exponent $e$), and the private exponent $d$ of matching private key.

How can I compute $p$ and $q$, the primes factor of $N$ ?

Algorithm

An RSA modulus $N$ product of large distinct primes can be factored given $(N,e,d)$ per:

Compute $f\gets e\,d-1$, and express $f$ as $2^s\,t$ with $t$ odd
Set $i\gets s$ and $a\gets2$
Compute $b\gets a^t\bmod N$ , and if $b=1$ then

set $a$ to the next prime, and proceed at 3

If $i\ne1$ then

compute $c\gets b^2\bmod N$ , and if $c\ne1$ then

set $b\gets c$, decrease $i$, and proceed at 4

If $b=N-1$ then

set $a$ to the next prime, and proceed at 3

Compute and output $p\gets\gcd(b-1,N)$ , and $q\gets N/p$.

For standard RSA where $N$ has 2 distinct factors, we have fully factored $N$. Otherwise, $p$ or/and $q$ won't be prime, just re-run the algorithm from step 2 replacing $N$ by any still unfactored component, until all the prime factors of $N$ have been pulled out.

Justification

In an RSA context, $N$ has no small prime factor, thus the algorithm's $a$ at step 3 will remain small enough that $\gcd(a,N)=1$ will hold (if it did not, $a$ would be a factor of $N$ found by trial division; a trivial modification of the algorithm additionally handles $N$ with such small factors).

For any valid RSA triple $(N,e,d)$, it holds that $\left(a^e\right)^d\bmod N=a$ for any integer $a$ in $[0,n)$ (because textbook RSA decryption works).

Thus for any $a$ used in the algorithm, $a^{e\,d-1}\bmod N=1$ holds, that is $a^f\bmod N=1$ for the $f$ of step 1.

The $t$ and $s$ of step 1 are uniquely defined, with $s>0$, and $\left(a^t\right)^{\left(2^s\right)}\bmod N=1$.

For most $N$, step 3 will quickly find an $a$ with $a^t\bmod N\ne1$. Argument: Since $N$ is squarefree, by the Chineese Remainder Theorem, an $a$ coprime with $N$ is rejected at step 3 iff $a^t\bmod p=1$ for all primes $p$ dividing $N$. Since $t$ is odd, if $a^t\bmod p=1$ holds for $a$, then $\tilde a^t\bmod p=p-1\ne1$ for $\tilde a=-a\bmod p$. Thus for $a$ coprime with $N$ chosen randomly in some large interval, the probability of $a^t\bmod p=1$ is $\le\frac12$. That is independently for each $p$, thus $a^t\bmod N\ne1$ has probability $\ge1-2^{-m}$ where $m\ge2$ is the number of factors of $N$. Using the consecutive primes $a$ (rather than random $a$) works well in practice for random instances of the problem (I have no proof, and one may require the Extended Riemann Hypothesis).

Before each iteration of step 4, it holds $1<b<N$, with $i\ge1$, and $b^{\left(2^i\right)}\bmod N=1$ ; thus after at most $s-1$ computations in step 4 we reach step 5 with $b\bmod N\ne1$ and $b^2\bmod N=1$.

Step 5 excludes the case $b=N-1$, which is rare in practice (I'm looking for an argument).

Thus at step 6, $\gcd(b-1,N)$ is a non-trivial factor of $N$.

References

A similar algorithm was hinted at in the original RSA paper: Ronald L. Rivest, Adi Shamir, and Leonard Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, in CACM 1978; see last two paragraphs of section IX-C. That uses and references the proof of a primality test in Gary L. Miller's Riemann's Hypothesis and tests for primality, in proceedings of STOC 1975.

A more detailed exposition is in Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, CRC Press 1997; see last paragraph of section 8.2.2 (i).

That answer's algorithm differs by using incremental primes $a$ rather than random $a$. That makes the algorithm deterministic (not its runtime), and works well in practice. As a minor aside, the number of modular squares computed in step 4 is minimized by using a test of $i$ rather than an additional last square.

Note: Simpler variations restrict to $b=a^t\bmod N$ or $b=a^{f/2}\bmod N$, but require testing sizably more $a$ when $s$ is large, which occasionally happens. Some justifications assume $d=e^{-1}\bmod\varphi(N)$ or $e\,d\equiv1\pmod{\varphi(N)}$, which does not consistently hold in modern RSA: for FIPS 186-4 that has probability less than $\frac1 3$, because $d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$ is required.

For a (different) deterministic polynomial-time algorithm, see Jean-Sebastien Coron and Alexander May's Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring, in JoC 2007.


Cryptosystems defined over the real numbers In a computational setting it is clear that we cannot do computation over the real numbers, as we couldn't generate, much less store them, so we have to instead deal with numbers that approximate them.  If a cryptosystem has some component defined over the real numbers, or uses "real valued" functions such as $\sin$, then does using such systems over the discretized space compromise the theoretical security of the system?

I am particularly thinking of chaos based cryptosystems for example, where encryption consists of iterating a map over an interval of the real line.  Are such systems inherently less secure because they cannot be actually implemented over the reals, and instead are approximations?  Can such approximations be used to cryptanalyze the systems?

The complex roots of unity form a finite group under multiplication

$$z^k = \exp\bigg(\frac{2k{\pi}i}{n}\bigg) = \cos\frac{2k{\pi}}{n} + i\sin\frac{2k{\pi}}{n},$$

where $z$ is a complex generator of the order-$n$ multiplicative group. This is a cyclic group and is isomorphic to any other cyclic group of the same order, for example the integers modulo 2 under addition, which is equivalent to Boolean XOR

$$a \oplus b \iff z^a z^b = z^{a+b}$$

This equivalence gives rise to the group Fourier transform, in which vector convolution in the complex domain correspond to point-wise multiplication in the additive group. This fact is used by Joan Daemen in his thesis to derive the DC/LC properties for the AES S-BOX.

The obvious practical problem with computing in this group is the error associated with floating-point arithmetic. As the number of arithmetic operations increases, so does the error. This kind of round-off error may be more appropriately called quantization noise in the signal processing context.


Known text attack on Hash function (SHA 256 or SHA512) I was thinking the below attack scenario on hash function. Let's assume that three binary numbers A(1000 bits), B(16 bits) and C(283 bits) are concatenated together and H(A||B||C) is generated using SHA256 or SHA512. Here, the attacker knows C. Knowing C, is it possible for an attacker to find A or B or (A||B) from the output H(A||B||C)? If yes, what are the attacks and how to prevent them?
Thank You.

Let consider $h = H(A\mathbin\|B\mathbin\|C)$ for SHA-256 or SHA-512 where both are MD-based cryptographic hash functions of NIST with

$A$ is 1000 bits
$B$ 16 bits, and
$C$ 283 bits

and we further assume that the attacker knows $h$ and $C$
Brute-force search
Definitely, the attacker cannot test the 1016-bit of unknown data to match the $h$. Bitcoin miners, the biggest known collective entity, can reach around $\approx 2^{93}$ This road is closed.
Prime-image attack
To find a pre-image normally we look for the first $a2^n$ input to find an input $x$ such that $h=H(x)$. For your case a little different.

Try random $a2^n$ values in the range $[2^{1299},2^{1300}]$. This has two problems;

It is infeasible
Even if the attackers have found one, the probability of result is equal to your data is $$\frac{2^{1299}}{2^{256}} = \frac{1}{2^{1043}}$$ for SHA-256, and $$\frac{2^{1299}}{2^{512}} = \frac{1}{2^{787}}$$ for SHA=512. Impractical, this road is closed, too.

And, we know that SHA-256 and SHA-512 are pre-image resistant, this road is also closed, too.
A simple counter-argument

If there is an attack on your case, that is one can extract $A$ and $B$ from $H(A\mathbin\|B\mathbin\|C)$ with the knowledge of $C$, Then we can use the length extension attacks on SHA-256 and SHA-512 to execute a pre-image. Simple, for a given $h'$ with $h' = SHA-256(x)$, execute a length extension $h'' = \operatorname{SHA-256}(x\mathbin\|C')$, then extract $X$ form $h''$ with the knowledge of $C'$. We don't have such any method.
In other words, extend the hash then find a pre-image. End of the path.

If you are looking for a secure way to hash with a key, the obvious method is the HMAC or you can use KMAC of SHA3.