confusion about LUKS encryption from Can I clone a LUKS container?

  You can, but it breaks security, because the cloned container has the
  same header and hence the same master key.  You cannot change the
  master key on a LUKS container, even if you change the passphrase(s),
  the master key stays the same.  That means whoever has access to one
  of the clones can decrypt them all, completely bypassing the
  passphrases.

From What users should know about
Full Disk Encryption based on LUKS

  If  we  set  a  new  secret user key, the encrypted master key stored
  on disk changes but the master key does not. Hence, users can change
  password frequently without re-encrypting all the data.

My questions:

If we can have up to 8 slots for decryption does that mean we have 8
corresponding Master Keys split in anti-forensic stripes or is it
still ONE MK ?
If it is ONE MK how the passphrase from slot 2 decrypt it when it is already encrypted with the passphrase from slot 1 (yes I know it
is not the passphrase itself, but I keep it like that for
simplicity).
Regarding the second quotation. So per my understanding while changing the LUKS passphrase we first provide the current
passphrase, we then provide a new one and that changes the encrypted
representation of the MK but after decryption it is still the same
that was randomly generated during first initialization, correct?
Then regarding the first quotation. I simply don't get it, at least notthe last sentence

  That means whoever has access to one of the clones can decrypt them
  all, completely bypassing the passphrases

Does that mean that if a have server A with LUKS encryption protected by a high-entrophy passphrase and clone that drive I would be able to decrypt that drive without even knowing or having to provide that passphrase ? If yes how would I do that ? Dump the MK from memory on server A, or how ?

Data is encrypted with Data Encryption Key. Each slot encrypts the DEK using a Key Encryption Key derived from a passphrase. Access to the DEK gets you the data. Access to any of the KEKs will give you access to the DEK. Clearing a passphrase slot, changing the passphrase, etc. does not change the DEK.

Whoever had access to the volume and a working passphrase could have extracted and saved the DEK, and that means they can use the DEK to decrypt the data in the future, when the slot with the passphrase they knew has been deleted. It also means they can decrypt any of the clones of the volume, even those for which the passphrase they knew was never valid.

If you really need to give different people access to a copy of the volume and be able to revoke access from other copies or from data added to the volume after their access was revoked, you have to change the DEK - reencrypt the volume or create a new encrypted volume (with possibly same passphrases protecting the new DEK) and copy all the data.

See https://crypto.stackexchange.com/a/24024

See https://security.stackexchange.com/a/205190/70830


OpenSSL Signature different each time I have a file that I am generating a signature for using OpenSSL, and each time I generate the signature, it is different to the last time.

openssl dgst -sha1 -sign update_key.pem TERM010134.bin > Update.sig

Anyone able to tell me why that might be?

It depends on what algorithm (determined by key type) and padding you use.

If the key is a DSA key, or an ECC key used for ECDSA, those algorithms normally use randomized signatures to remain secure, and OpenSSL does so. (There is a variant scheme that makes k unique and unpredictable without making it truly random, but it is not widely used and not implemented in OpenSSL.)

If the key is an RSA key, OpenSSL supports 3 RSA paddings other than none: pkcs1 (more exactly the type-1 scheme of PKCS#1 through v1.5, now retronymed RSASSA-PKCS1-v1_5), pss, and x931. dgst -sign for RSA defaults to pkcs, which is deterministic and should not produce varying results; if it does please edit your question with details (preferably using a test key). Only if you specify -sigopt rsa_padding_mode:pss should you get a randomized result.

Note RSA encryption is different, and OpenSSL supports two paddings other than none: pkcs1 (this time meaning RSAES-PKCS1-v1_5) and oaep, both of which are randomized; the newer OAEP is randomized in a way that is provably secure which the older v1_5 scheme does not.


Sigma-protocol for 3SAT problem I have some questions from previous years exams, I hope you could help me with them. :)

Let $g,h$ denote generators of a group $G$ of large prime order $n$ such that $\log_g h$ is unknown to anyone. Consider an instance of the 3SAT problem for Boolean variables $v_1, \ldots , v_l$, given by a Boolean formula $\Phi$ consisting of $m$ clauses, which each consist of $3$ literals:

$ \Phi = (l_{1,1} \vee l_{1,2} \vee l_{1,3}) \wedge \ldots \wedge (l_{m,1} \vee l_{m,2} \vee l_{m,3})$.

Each literal is of the form $l_{i,j}=v_k$ or $l_{i,j}=\overline{v_k}=1-v_k$ (negation of $v_k$), $1 \le k \le l$. Construct a $\Sigma$-protocol for the following relation:

$R_{\Phi}=\{ (B_1, \ldots, B_l;x_1,y_1,\ldots,x_l,y_l)\colon \Phi(x_1,\ldots,x_l), \forall_{k=1}^l B_k=g^{x_k}h^{y_k}, x_k \in \{ 0,1 \} \}$.

Thanks, Peter.

This is doable by
(1) opening all commitments $B_k$ with standard responses $Q_{k}(z)$ that are linear in challenge,
(2) proving that all $x_k \in \{0,1\}$ (with at most second-degree polynomials in challenge), and
(3) proving $m$ polynomial identities for (at most) third-degree polynomials in challenge
$$U_i(z) = T_{i,1}(z) T_{i,2}(z) T_{i,3}(z) $$
where
$T_{i,j}(z) = Q_{i,j}(z) - z l_{i,j}$ and
$Q_k(z) = v_k z + \alpha_k$
considered over the ring modulo group order and
$\alpha_k$ are initial random coins.

With such a $\Sigma$-like protocol, prover will send commitments to 3 coefficients of polynomials $U_k(z)$.
It is actually proven that such a polynomial is of 2nd degree, not 3rd.
Informally, we need at least one TRUE out of each triple for satifstiability,
so at least one constant (degree 0) polynomial for each $(T_{i,1}(z), T_{i,2}(z), T_{i,3}(z))$.
The well-known $\Sigma$-protocol would evaluate a linear (degree 1) polynomial at a random point chosen as a challenge.

(Soundness) For any (that is, dishonest) prover, there are at most 3 chances (unlike just 1 for the well-known $\Sigma$-protocol) for such a polynomial to evaluate to zero by choosing some random value for the free variable $z$.
See Schwartz-Zippel lemma for details.

One would choose the challenge from a large set comparable to (large) group order.
Or maybe from polylog-cardinality set for zero knowledge.

For point (2), one would prove that $Q_k(z) (Q_k(z) - z)$ is linear (not quadratic) by sending commitments to two coefficients.


Decrypting two ciphertexts using the same key I'm currently trying to solve an online challenge, where I'm given two ciphertexts, encrypted using a one-time pad and the same key for both messages. The task is to decrypt those messages.

What I'm trying to do is to xor a common English word ("the" in this case) and for that word step by step XOR with the result of c1 XOR c1.

So basically: bits("the") XOR c1 XOR c2

My problem is that all the results I get are not usable.
I know that "the" should be the right word to find something, as the instructor dropped that hint.

My code looks like this:

def text_to_bits(text, encoding='utf-8', errors='surrogatepass'):
    bits = bin(int.from_bytes(text.encode(encoding, errors), 'big'))[2:]
    return bits.zfill(8 * ((len(bits) + 7) // 8))

def text_from_bits(bits, encoding='utf-8', errors='surrogatepass'):
    n = int(bits, 2)
    try :
        return n.to_bytes((n.bit_length() + 7) // 8, 'big').decode(encoding, errors) or '\0'
    except:
        return "Not processable"

def xor(bit1, bit2):
    result = ''
    for idx, val in enumerate(bit1):
        result = result + ('0' if (bit1[idx] == bit2[idx]) else '1')
    return result

def crib_brute(bit_str, crib_word_bit):
    for i in range(50):
        xor_result = xor(crib_word_bit, bit_str[i: len(crib_word_bit) + i])
        print(str(i) + ": " + text_from_bits(xor_result))

c1 = "1010110010011110011111101110011001101100111010001111011101101011101000110010011000000101001110111010010111100100111101001010000011000001010001001001010000000010101001000011100100010011011011011011010111010011000101010111111110010011010111001001010101110001111101010000001011110100000000010010111001111010110000001101010010110101100010011111111011101101001011111001101111101111000100100001000111101111011011001011110011000100011111100001000101111000011101110101110010010100010111101111110011011011001101110111011101100110010100010001100011001010100110001000111100011011001000010101100001110011000000001110001011101111010100101110101000100100010111011000001111001110000011111111111110010111111000011011001010010011100011100001011001101110110001011101011101111110100001111011011000110001011111111101110110101101101001011110110010111101000111011001111"
c2 = "1011110110100110000001101000010111001000110010000110110001101001111101010000101000110100111010000010011001100100111001101010001001010001000011011001010100001100111011010011111100100101000001001001011001110010010100101011111010001110010010101111110001100010100001110000110001111111001000100001001010100011100100001101010101111000100001111101111110111001000101111111101011001010000100100000001011001001010000101001110101110100001111100001011101100100011000110111110001000100010111110110111010010010011101011111111001011011001010010110100100011001010110110001001000100011011001110111010010010010110100110100000111100001111101111010011000100100110011111011001010101000100000011111010010110111001100011100001111100100110010010001111010111011110110001000111101010110101001110111001110111010011111111010100111000100111001011000111101111101100111011001111"

crib_word = "the"
crib_word_bit = text_to_bits(crib_word)

crib_brute(xor(c1, c2), crib_word_bit)

Those are my first 15 results:

0: eP
1: Not processable
2: Not processable
3: Not processable
4: Not processable
5: Sgi
6: :v}
7: Not processable
8: L
9: Not processable
10: Not processable
11: Not processable
12: Not processable
13: {d
14: Not processable
15: Not processable

Nothing looks like part of the English language.
Can someone tell me what I'm doing wrong?


What are the curly brackets in this cryptographic hash function definition? Reading the Schnorr signature Wikipedia page, I stumbled upon the following statement:

  All users agree on a cryptographic hash function $H:\{0,1\}^*\to\mathbb{Z}_q$.

What do these curly brackets mean here and how exactly is the hash function's input domain defined? Normally, you can use whatever input you want for a CHF/ PRF.

This has little to do with cryptography or hash functions. It's slightly abused standard mathematical notation.

$\{0,1\}$ is the set consisting of $0$ and $1$, so the set of all single bits.
For any set $S$, $S^n$ for any natural number $n$ refers to the set of $n$-tuples of Elements from $S$, e.g., $S^2 = S \times S$.
So strictly speaking $\{0,1\}^n$ refers to the set of $n$-tuples of bits, however we generally call these "bitstrings of length $n$".

Finally, $\{0,1\}^*$ is defined as $$\{0,1\}^*=\bigcup_{n\in\mathbb{N}_0}\{0,1\}^n.$$ I.e. it refers to the (infinite) set of all finite length bitstrings.


Ensuring integrity and confidentiality together with symmetric encryption I've been required to answer a question:

As usually, we have Alice and Bob.
Suppose Alice wants to send a file F to Bob, ensuring integrity and confidentiality. They share a symmetryc key $K_{ab}$ and use AES. No hash algorithm is available.
Alice sends to Bob: $Enc(K_{ab}, F)$
In this simple scheme, are integrity and confidentiality guaranteed?

My answer:

Confidentiality is guaranteed if we use CBC (cipher block chaining) for example. But this is obvious. If we use a symmetric encryption algorithm as AES we have to use CBC, CFB, OFB or whatever.. right? So this answer seems too simple.

I would say that a computer is not able to tell if the message has been tampered with. So i would use CBC along with a "weak" cryptographic checksum inside CBC. A longer non-cryptographic checksum is suspect and subtle attacks are known if CRC is short.

Use OCB (Offset Codebook Mode). This mode of operation get both encryption and integrity protection while making only a single cryptographic pass over the data.

Are these answers correct? Could you give some background why the are correct or not?

P.S.: I could get privacy of a message with CBC encryption and integrity with CBC residue as long as the two are computed with different keys, but this requires twice the cryptographic power of encryption alone.

Do not invent your own authenticated encryption mode. Use a standardized one, and use a well-supported library to implement it in your code.

AES-GCM, AES-CCM, AES-OCB, and AES-CBC with HMAC-SHA256 over the ciphertext are all common options.

Some great direction from Matt Green here: How to choose an Authenticated Encryption mode


What's a good hash algorithm for hashing a short length (e.g. 256 bytes) buffer, which must be fast and very collision resistant? It doesn't need to be cryptographically secure.

Would CRC64 be a good choice?
What's the minimum hash length that can be considered cryptographically secure these days?

First you should check if a cryptographically secure hash such as SHA-2 is fast enough. It is likely it is fast enough, and then the fine details of your weakened collision resistance requirement become irrelevant.
If you really need something fast you may consider CRC-64, but it is obviously not cryptographically secure, It is rather trivial to construct collisions for CRC-64. However if you are trying to protect against random collisions, it may suffice, and with random input data, you may assume CRC-64 won't collide much more then a random function which mean you can use birthday paradox to calculate the chance of having a collision. Essentially you need number_of_messages << 2^(bit_length/2)


What's the difference between the long term key and the session keys? I'm currently studying secret key cryptography, and I've come across the terms "long-term key" and "session key".

What's the difference between these two kinds of keys?

First, understand that keys need to last only as long as you need to recover what they are protecting. If you are storing a secret in a box until next year, you have to keep the key until next year. But if we're talking on the phone, we only have to keep the key for the duration of the phone call.

If Alice and Bob are going to speak securely, they don't need to keep the shared secret key around for a long time.  They only need it for as long as they're speaking.  And they don't want someone who records their conversation to be able to learn what they said.  If they agree on a temporary key, one that lasts only as long as their conversation, that is a session key.

A session key is one that is not intentionally stored, and is not re-creatable.  Session keys are used only for communications protocols, never for storage purposes.  In computer protocols like SSL, the session key is generated randomly, exchanged securely with the other computer (using a key exchange protocol like DH), and remains in each computer's memory only for the duration it is needed (a session.)  When the session is ended, both sides wipe their copies of the key from memory.*

A long-term key is one that is deliberately stored somewhere, either on a computer disk, flash memory, or even printed on paper.  The key is intended to be used at multiple points in time, such as "I will use this key to encrypt this secret file today, and use it again to decrypt my secret next week."  A long term key can be used for any purpose, including stored information as well as transient communications.

* Note that an attacker can certainly record the session key exchange, and if they can break the key exchange cryptography they can decrypt the session key.


Cryptanalysis of AES on SSD with TRIM enabled Attack scenario:

SSD physically retrieved from a computer that is turned off. The entire disk is encrypted with AES 256-bit (GNU/Linux, LUKS). The SSD has had TRIM enabled for several years and the file system has seen a lot of use, i.e. a lot of files deleted over time (triggering TRIM). Assume that the key used is sufficiently strong to resist any brute force/dictionary attack.

Cryptanalysis:

As far as I understand it, TRIM aids in cryptanalysis in that it will be known which regions of the device are in use and which are not in use.

But exactly how does the cryptanalysis proceed from here? What kind of attack will be performed? Does the attack have a name? Does it have any realistic chance of success? It would be interesting to know if an attack like this ever succeeded, either in an academic setting or known to have succeeded in the field.

A conceivable attack is inspired by this extract of LUKS On-Disk Format Specification
Version 1.1.1, section 1:

  A partition can have as many user passwords as there are key slots. To
  access a partition, the user has to supply only one of these
  passwords. If a password is changed, the old copy of the master key
  encrypted by the old password must be destroyed. Peter Gutmann has
  shown in [Gut96], how data destruction shall be done to maximise the
  chance, that no traces are left on the disk. Usually the master key
  comprises only 16 or 32 bytes. This small amount of data can easily be
  remapped as a whole to a reserved area. This action is taken by modern
  hard disk firmware, when a sector is likely to become unreadable due
  to mechanical wear. The original sectors become unaccessible and any
  traces of key data can’t be purged if necessary.

Assume that a weak or compromised password has been used, then the password changed with hope of restoring security. Due to wear-leveling on the SSD, the master key enciphered using the weak or compromised password may remain physically on the drive, although it is no longer logically mapped. In theory, reading the bare flash in the drive (either physically, or using some undocumented commands that may or may not exist in the SSD firmware, perhaps after loading an instrumented version of that) may allow reading the block(s) still containing the master key enciphered using the weak or compromised password, which in turn trivially breaks the whole encryption. It is hard to tell if the " anti-forensic information splitter " of LUKS can prevent that.

This attack is in theory also relevant in the context of blocks that become bad on traditional hard drives (the original data then becomes logically unmapped while potentially physically there, unless the drive physically erases it after remapping, which is not an advertised feature); but the odds that precisely the block(s) enabling the attack becomes bad are minuscule. The odds are less low with a SSD, especially soon after the password is changed.

TRIM likely impact the odds of the attack to succeed, because it modifies the blocks erased by the wear-leveling algorithm, but I can't tell if that will increase or decrease the odds. I can vaguely imagine algorithms in which the periodical erasing of TRIM makes it unnecessary to use backup means to recover unused space, making it more likely that blocks logically rewritten in seldom rewritten areas still have their former values physically there.

I guess that reading logically-rewritten but still-physically-there blocks in SSD has become a forensic trick for high-value target and some SSD. But I have no indication that the LUKS attack I discuss was ever attempted, much less successful. I would fear, much more, a compromise of password or master key by more traditional means (key-logger, camera, paper backup of password, configuration goof, compromized software, DMA memory grabber..)


What is the meaning of $1$ in provable security? Sometimes, we use $1$ to represent "succeed". In CPA, if the adversary guesses $b'=b$ outputs $1$.
But I am confusing about the meanings of the following $1$.

Take the DDH for example,
$$|\Pr[\mathcal A(g,g^a,g^b,g^{ab})=1]-\Pr[\mathcal A(g,g^a,g^b,g^c)=1]\le\operatorname{negl}(n)|$$ where n is security parameter.

Does $1$ mean succeed  or output the same thing？

If we write
$$\Pr[\mathcal A(g,g^a,g^b,g^{ab})=1]-\Pr[\mathcal A(g,g^a,g^b,g^c)=1]\le\operatorname{negl}(n)$$
without an absolute value, meaning that the (distinguisher) algorithm $\mathcal A$ is not good enough to breach security, it is implicit that $\mathcal A$ outputs $1$ more likely when it has recognized something special. That something special is the condition that should be near impossible to recognize for security to hold. In the context, that special thing ideally is: for input $(g,g^a,g^b,g^c)$, the condition $g^c=g^{ab}$ holds. But an algorithm that does not exactly recognize that condition is still a valid distinguisher (breaking security) if it manages to make the overall condition false.

It is often written
$$\big|\,\Pr[\mathcal A(g,g^a,g^b,g^{ab})=1]-\Pr[\mathcal A(g,g^a,g^b,g^c)=1]\,\big|\le\operatorname{negl}(n)$$
and, thanks to the absolute value, it becomes immaterial if the special condition tends to make $\mathcal A$ output of $1$ or $0$, because
$$\big|\,(1-p)-(1-p')\,\big|\ =\ \big|\,p-p'\,\big|$$
Now, the only thing that matters is that the output of $\mathcal A$ has a significantly different mean over the inputs of the form $(g,g^a,g^b,g^{ab})$ than it has over the inputs of the form $(g,g^a,g^b,g^{ab})$.


Encryption and decryption example using the Pohlig-Hellman Exponentiation Cipher Let $n=11, d=3, e=7$ and $M=3$.

Encryption:

  M = BSK
  B -> 1 , S -> 18 -> k -> 10
  M1 => C1 = 1^7 mod 11 = 1
  M2 => C2 = 18^7 mod 11 = 6
  M3 => C3 = 10^7 mod 11 = 10

  C = 1 6 10
  <=>
  1=>B, 6=>G 10=>K

Decryption:

  C1 => M1 = 1^3 mod 11 = 1
  C2 => M2 = 6^3 mod 11 = 18
  C3 => M3 = 10^3 mod 11 = 10

  M = BSK

I would like to know that I am correctly doing encryption and decryption?

Using the Pohlig-Hellman cipher, you encrypt your message $M = 3$ using an encryption key $(e,n) = (7,11)$. The encryption is $C = M^e \mod n = 3^7 \mod 11=9$.

You decrypt with a decryption key $(d,n) = (3,11)$, such that $e\cdot d = 1 \mod (n-1)$. Since $3 \cdot 7 \mod (11-1) \equiv 21 \mod 10 \equiv 1$, this is satisfied.

So, to decrypt, compute $9^3 \mod 11 \equiv 3$, which was your $M$. You're done.

It looks like you are confusing the Pohlig-Hellman exponentiation cipher with the Pohlig-Hellman theorem used to solve a discrete logarithm problem. These are related problems.

You use the Pohlig-Hellman algorithm when you want to solve $g^x = h \mod p$, where $g,h$ are in a finite field $\mathbb{F}^*_p$, $g$ is a primitive root and $p$ is a prime. When $p-1$ factors into a bunch of small primes, you can solve several smaller discrete logarithm problems and reassemble $x$ from the solutions to those smaller problems via the Chinese remainder theorem.

Also, make sure you know why you're using this cipher in the first place.


Key-Agreement & Key-Transport for Symmetric Authentication System Question: I want to know what kind of Master Key sharing process is pursuit on Symmetric encryption environments (strictly symmetric, also in the key sharing scheme).

As I am aware there are several ways to establish the Master Key transportation and storage between two entities. The processes can pursuit a Key-Agreement or a Key-Transport scheme.

In key transportation a key wrapping function is used to protect the shared secret, then I assume that we do not need any public-key system such as DHKE or ECDH.

In key agreement asymmetric encryption processes are used to transport master keys between entities, then this is not a full symmetric master key exchange, correct?

Thanks in advance.

For a full symmetric key key transport, the symmetric key is created from a random number generator. This is then signed with the owners static private key and then encrypted with the recipients static public key (key wrapping), and then sent to the recipient. The recipient will receive, decrypt and verify the signature, and the symmetric key is decided on. Whilst a key agreement algorithm like ECDH(E) or DH(E) isn't needed, an asymmetric cipher such as RSA is needed. This is referred to as a KEM system (key management), and requires an asymmetric cipher algorithm for the key wrapping.

For a key agreement or KEX (key exchange), then ECDH(E) or DH(E) is used, where both parties exchange bits of info and then calculate a shared secret, which goes through a HKDF to convert in into the format of a symmetric key.

So even for key wrapping, an asymmetric cipher must be used at some point, so that the key can be securely transported to the recipient, and it's authenticity verifiable.


Deterministic Encryption - Generating IV from password key I need to encrypt file and directory names/paths but I need the encryption to be deterministic. I need to sync the local files with a cloud storage provider so I can't use probabilistic encryption.
Know that you should not use a static IV when encrypting text, would this be an acceptable work around:

Run passphrase through scrypt and store resulting output
Take the resulting output from scrypt and hash it (using MD5 for example)
Take the first 16 bytes of the hash and use it as the IV to encrypt the directory and file name

There is one thing to note that is really important here: The salt used for scrypt is hard coded most of the time. This is a local application that doesn't require a login and the users must be able decrypt the files on multiple computers so I'm unable to store the salts in a database like usual. The users can specify their own salt, but usually it will be hard coded for the application.
The only other thing I can think of:

Use probabilistic encryption
Read the directory/file structure from the cloud service provider and local directory
Map all the encrypted cloud provider names with their decrypted values
Map all the encrypted local names with their decrypted values
Sync based on the mappings found above

The only issue with that is that it is time consuming and really difficult to implement when using different cloud service providers.

From my understanding of your question, what you want is to hide the name of the file, while enable syncing. You don't actually need encryption per se, since the real name of the file could be encrypted together with the entire file (probabilistically). As such, a potential solution is to just HMAC the file name and use that as the value for syncing. No IV or encryption is needed.
If you want to be able to invert this (if that's important), then you should use something like AES-SIV or AES-GCM-SIV (with fixed IV=0; in general, this isn't recommended but if these are really your constraints then this works). This will ensure that two files with parts of the name the same won't be discovered. You can of course do this also by deriving an IV and encrypting as you say, but that's more complicated and not standard. As such, it's not recommended.
My recommendation would be HMAC on the name for syncing, and regular probabilistic encryption on the name and full file.


Is it possible to encrypt the key by sender's private key and again encrypt it with receiver's public key by using RSA algorithm at sender end Is it possible to encrypt the data by sender's private key and again encrypt it with receiver's public key by using RSA algorithm at sender end.How decryption is done at receiver's end?

It doesn't make much sense to "encrypt" with your private key, I suspect what you want to do is sign with a private key, which for RSA is essentially the same operation.
You definitely can sign a message with your private RSA key and then encrypt it with the recipients RSA public key. This is even common.
Obviously you want to use proper padding (e.g OAEP)

Note you can do this in either order, sign and encrypt or encrypt and sign.
Note public key operations are cheaper computationally compared to private key operations. If you encrypt and sign we can verify cheaply and not waste time decrypting unverified messages. If you sign and encrypt you can hide you identity If this is relevant.


Which cipher text is easiest to guess the plaintext? I know that there are approximately 2^88 different permutations of 26 characters. The stream cipher A5/1, which generates a binary keystream using three irregularly clocked LFSR, and has a 64-bit key.

  If we consider 1 000 characters of English text encrypted using either
  a substitution cipher or encoded in ASCII and encrypted using A5/1.
  From which ciphertext is it easiest to guess the plaintext?

In my opinion, the Substitution cipher is easy to guess. In the substitution cipher, it has repeated characters in the cipher-text make easier to figure out the text. Also, the substitution cipher has 26! possibilities. Can someone explain it to me in a more detail way?

You're right.

For a substitution cipher the huge size of the keyspace is quite irrelevant in terms of security: it does not change the frequencies of letters, just maps them to other letters. So you you can go from the most common letter and map that, then the 2. most common, etc. And after maybe the 10 most common letters you can use a dictionary with English words and the partially mapped words to exclude other possibilities to get the remaining mappings. "Security" is barely better than a Caesar cipher.

For A5/1 it took over 10 years to be broken, so in contrast it is is not trivially broken by modern computers, like basically any classical cipher.

I guess the point of the exercise is: A large keyspace does not mean, the cipher is secure.


AES-GCM not using two keys It is recommended to use different keys for different purposes, such as encryption and integrity protection. As I see it, AES-GCM only requires one key as input. Two different keys are then generated from the provided key, basically meaning that one key is used for two different purposes! Should one, not, consider using the traditional encrypt then HMAC instead? This would ensure that, under the assumption that the implementation does not simply use a single key, unrelated keys are used for different purposes.

My question is, therefore, why is AES-GCM so widely accepted? In what circumstances should one consider using EAS-GCM instead of the traditional encrypt then HMAC?

TL;DR: GCM has been shown to be secure, which is not the case for encrypt-then-HMAC.

There are a few things to distinguish here. First is the  difference between asymmetric and symmetric cryptography. If messages are encrypted with the public key of the recipient and signed with the private key of the sender then there is a clear difference in key usage. Obviously the private keys when sending messages are kept by different parties. Now these parties could use the same key for decrypting and signing, but these keys may well have different life times. For instance, it may be that you want to decrypt messages in the far future, meaning that you need to keep the private decryption key. However, generally you don't need to keep the signing key; you can still verify messages with just the public key and replace the signing key with the new key.

However, with an authenticated cipher such as GCM we're commonly dealing with session keys. The session keys for confidentiality and integrity protection / message authentication are commonly generated at the same time. So there is no need to have separate life times or access conditions for them.

Another reason to use separate keys are algorithmic vulnerabilities. Cryptographic algorithms will always be designed to keep the key secure. However, the algorithmic proofs (or at least indications of security) generally do not consider usage of the key in other algorithms. Imagine you have a set of equations trying to show security. Now mix those equations with a whole new set of equations from another algorithm that uses the same variables, and try to show that security holds. This is generally impossible, meaning that any security reduction is likely void.

In the worst case the encryption algorithm and MAC use similar constructions. In that case it might well be that the resulting set of equations is actually insecure. A good example of this is a block cipher mode in CBC mode that uses CBC-MAC. It is easy to prove that this scheme can be insecure when used with the same key.

HMAC is a completely different scheme than any block cipher mode of operation. That makes it very improbable that re-using the key for authentication will lead to vulnerabilities. However, it will also be next to impossible to prove that there aren't any, so it is therefore still not recommended to reuse the encryption key for authentication with HMAC.

A slightly less serious issue is that keys may not be usable for different algorithms. For instance, a HMAC-SHA512 (SHA-512 is often faster than SHA-256) key cannot directly be used for AES encryption, as the maximum key size of AES is 256 bits. For software this may not be a huge issue, but generally keys are generated for a specific algorithm. This is especially an issue on hardware modules, where the key data can often not be retrieved. It would be impossible to use a HMAC key as an AES key.

So it may be easier to have one input secret that can be fed into a key derivation mechanism such as HKDF. This mechanism can then be used to derive the encryption and authentication key. This is an easy way to split one secret key into two secret keys. Obviously this option is not available in the setting that requires asymmetric cryptography.

For AES-GCM the key is only used in AES-CTR mode. This mode is both used for protecting the GMAC value (with a specific counter value) as well as keeping the message confidential. This construction is shown to be secure in a paper that is unfortunately payware. This proof has been studied by other cryptographers and shown to be valid. There have certainly have been results that have shown weaknesses in the GCM construction with regard to construction of the authentication tag and derived authentication key, but the overall security claims have withstood the issues - after some tweaking.

So unless further holes in the security claims will be found, AES-GCM should be secure even though it just requires one key.

For the scholar, here is the security claim in the original paper:

  GCMis secure in the concrete security models introduced by Bellare, Killian, and Rogaway [20] for
  message authentication, and Bellare, Desai, Jokipii, and Rogaway for confidentiality [22], against
  adversaries that can adaptively choose the plaintext, the additional associated data, and the IV
  (as long as the requirements on these inputs are respected). Its security relies on the fact that
  the underlying block cipher cannot be distinguished from a random permutation, an assumption
  which is common in cryptographic designs and which appears to be valid for the AES.

And here is a link to a freely available draft that is likely the source for the linked-to payware paper in the previous section: Flexible and Efficient Message Authentication in Hardware and Software


Is it possible to create a "digital seal" to tell if a document has been opened? So, in real life we have a handful of ways to leave a physical mark on a packet to know if it has been opened without authorization (eg. you can use 'opened' security tapes, or you can put a signature or stamp right through the envelop opening). One thing i see these tells share, is that they are some sort of signature that self destructs on any attempt to open the package.

My question is if you can build a digital equivalent to these seals. I'm aware encrypting the packet is a way to ensure its confidentiality, but it requires the eventual recipient to know a secret to decrypt it. One scenario where I don't see this working is sealed wills/testaments (which should only be opened and read once the testator has actually died), in this case when the custodian of the will first receives it, the eventual recipients are still unknown (the testator could die many years in the future, by then many of the intended recipients could be gone too).
My first thoughts are, probably it's impossible, as it's always easy to make a bitwise copy of the "sealed" document, open it, and then deliver the unmodified one with its intact signature, but i wanted to know if someone with more experience in cryptography could come with a solution.

Encrypt your document, and embed a web address (and login details) in the packaging from which a reader can get the decryption key. The website must be trusted. The website logs will tell you when software has requested the key to decrypt it.
If you also want to protect confidentiality, encrypt with two keys. One is the usual private key used to protect confidentiality, that the recipient has been given securely, the other is the tamper seal that has to be obtained from the website.


Can I change an encryption key used without decrypting first I'm looking to solve for a little challenge I have in regards to changing the encryption on a message with asymmetric keys. I'd love to be able to swap the encryption to a different key in memory and without going via the plain text.

So clear text -> encrypted text with first key -> double encrypted text -> encrypted text with second key

I have a vague recollection that it can be done but the Googles are not being forthcoming. I'm far from an expert on this and my preferred implementation would be done in C#.

Thanks in advance.

It's important to define what you want and why. For example, if the server doing the transformation does not hold the secret key of the first kind, then this is "proxy re-encryption". However, if it does hold it, then the question is why not decrypt first. From a security perspective it doesn't matter, and sometimes not from an efficiency perspective as well.

If you are using ElGamal variant, then you can do this quite easily and it's actually more efficient than decrypting and encrypting. Given key pair $pk_2=h_1$; $sk=x_1$ and $pk_2=h_2$; $sk_2=x_2$ and given $c_1=(u,v)=(g^r \cdot m, h_1^r )$ you can compute $c_2=(u, v^{x_2/x_1})$. Check out why this works yourself...


Can you break an RSA modulus if you know $k \cdot \phi(n)$ where $k$ is a large prime? Given some RSA modulus $n$, can you factor $n$ if you are given $k \cdot \phi(n)$ where $k$ is also a large prime?
(Of course, you could factor $n$ if you were given $\phi(n)$ as discussed here, but that approach does not work when you cannot factor $k \cdot \phi(n)$, right? )

Yes we can factor an RSA modulus $n$ given $n$ and $k \cdot \phi(n)$, including where $k$ is a (reasonably) large prime. We just use $f\gets k \cdot \phi(n)$ instead of $f\gets e\,d-1$ in the algorithm of this answer.
The algorithm is heuristic, and I do not claim a rigorous proof of the distribution of the runtime. Also, a larger $k$ tends to make it more costly. But in practice it works fine for $k$ of size comparable to $n$.


Provable Lower Bounds for some Algorithmic Problems? Are there any problems for which we have known lower bounds?
For example, for comparison based sorting, we know you need $\Omega(n \log n)$ comparisons.
Edit: I'm aware that this requires restricting the algorithm to comparisons. I couldn't think of any lower bound in an unrestricted model, but I'm mostly interested in lower bounds for unrestricted computations.
My motivation for this is: while we don't know how to prove that one-way functions exist, maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it. Even a problem with $\Omega(n^7)$ could suffice to build somewhat practical cryptography: $c \cdot (2^{128})^{\frac{1}{7}} \approx c\cdot319557$ bits (for some constant $c$) would be required to obtain the same security level as a 128 bit key.
Does this question make sense? If not, where do I go amiss? Do my calculations make any sense?

maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it

Even that limited goal is beyond what we can prove.  People have done studies on tiny functions (functions small enough that exhaustive search is possible); the difference between evaluating the function forward and backwards was surprisingly small.  One would hope that the difference becomes wider once the size of the function increases; however we can't prove it.

Does this question make sense?

Yes, it does (although, depending on how you define things, the $c \cdot 319557$ may be the time required to evaluate in the forward direction, rather than the number of bits); we just don't know the answer.
Now, the obvious question may be, if we can prove that comparison based sorting takes $\Omega(n \log n)$ operations, why can't we do anything analogous with inverting functions?  Well, with the comparison based sorting proof, the only information we allow the sorting algorithm about the relative order of elements is to call the Oracle, which returns a single bit each time.  And, we can prove that any sorting algorithm with that restriction must call the Oracle $\Omega(n \log n)$ times (because it needs to distinguish between $n!$ different sort orders), and hence must take at least $\Omega(n \log n)$ time.  However, that proof is valid only if we restrict the program in that way; sorting algorithms that don't abide by that restriction (e.g. radix sorting or interpolation sorting) can go faster.  And (the point I'm really trying to make) when we ask for a function to be inverted by any means, we don't require the program to use any sort of Oracle to get the information we need, hence the type of proof we used for comparison based sorting doesn't work.


Pseudonymous publication of a series of texts online when a bad guy is expected to join in with fakes: will this approach to PGP verifiability work? Alice wishes to publish under a pseudonym a series of texts online. She expects the texts to circulate, and she will not include any way of contacting her. Bob will not know the identity of the pseudonymous author but he will seek to confuse the author's audience by publishing texts that he falsely attributes to the same pseudonymous person. For verification of the authenticity of her writings Alice wishes to use PGP but she does not wish to use a key server. She can only operate online.

Is the following approach sensible?

STAGE A

1) Publish several fairly anodyne initial texts in places that are sufficiently obscure for Bob not to notice for a while, and which are also places of record that date-stamp texts. I'm thinking Usenet here.

2) In each of those texts, include her PGP public key, its 40 hex-digit fingerprint, and a signature made using her PGP private key.

STAGE B

3) Start publishing the texts that Bob will find annoying on open-access websites. In each one, include the said fingerprint, the advice that readers may find her PGP public key in posts that were made to named Usenet groups between two stated dates, and a signature made using her PGP private key.

Bob will now start publishing fake texts. These may state that the author has changed their key and that the new public key is as follows. Or they may state that they have been signed using a key from a pair for which the public key can be found in Usenet articles posted between a different pair of dates.

Alice's idea is that although Bob's actions may be a minor annoyance, she can safely continue publishing texts in the knowledge that the more net-savvy of her readers will be able to verify their authenticity. And as readers start adding to their collection of texts published in Stage 2 who have already saved the public key from Usenet, all they need do to validate authentic texts and invalidate fake ones is to check the signature.

Is she thinking along the right lines? Or is there a gaping hole in the idea which her opponent will be able to drive a tractor through?

Yes, properly implemented including choice of keys and parameters, what's proposed makes Bob detectable when publishing texts under the pseudonymous identity used by Alice in stage A.

One detail is not made explicit: in step A2 the "signature made using her PGP private key" must be a (detached) signature of at least the text in A1. It is not useful to include in what's signed the PGP public key and fingerprint; but as long as it remains easy to verify the signature and extract the public key and fingerprint, such inclusion does not harm.

In stage B, Alice should I believe try to keep the same signing habits as in stage A, still including her PGP public key and fingerprint, and signing the same elements as she did in stage A. Things still work if the public key is removed (like due to limited publishing space), but including it eases the work of whoever actually try to sort out things, and makes it easier to detect forgeries when Bob chooses the first or second of these strategies:

not including a public key in his messages
including his public key in his messages
including Alice's public key in his messages

Per common practice, the date carried in Alice's signatures should be shortly before the date of the usenet posts or publication; anything else will raise suspicion.


Known-plaintext attack on two-dimensional affine cipher Problem:

We have a two-dimensional affine cipher with $n = 2,\,\,\,\mathcal{P} = \mathcal{C} = {\mathbb{F}_{16}^2}$, where $\mathcal{K} = \{ A,\,\,b\} $ and $b = (0,0)$. The encryption and decryption is in ${\mathbb{F}_{16}} = {\mathbb{F}_2}[x]/\left\langle {{x^4} + x + 1} \right\rangle $. The task is to recover first part of the key - $A$ given two plaintext-ciphertext pairs: ${e_K}((d,5)) = (7,4)$ and ${e_K}((3,1)) = (d,c)$. A known-plaintext attack should be applied to find $A$.

Some observations:

For a typical one-dimensional case in ${\mathbb{Z}_{26}}$ this task is easy. All we need to do is to solve for $A$ ${e_K}(x) - {e_K}(y) \equiv A(x - y)\,(\bmod \,26)$, considering $\exists \,{(x - y)^{ - 1}} \in {\mathbb{Z}_{26}} \wedge (x - y){(x - y)^{ - 1}} \equiv 1\,(\bmod \,26)$ is true. In this case we just multiply both sides by ${(x - y)^{ - 1}}$ and get the value for $A$.

Now in my case its more complicated. The difficulties come from the fact that we need to perform all calculations in ${\mathbb{F}_{16}} = {\mathbb{F}_2}[x]/\left\langle {{x^4} + x + 1} \right\rangle $ and the plain text - cipher text data is in hexadecimal format. Furthermore we are dealing with $2 \times 2$ matrix not just simple decimal value...

Solution attempt:

Based on the one dimensional case i tried to solve for $A$ using $${e_K}(x) - {e_K}(y) \equiv A(x - y)\,(\bmod{x^4} + x + 1)$$

$\begin{gathered}
  x = \left[ \begin{gathered}
  d \\
  5 \\
\end{gathered}  \right] = \left[ {\begin{array}{*{20}{c}}
  {{x^3} + {x^2} + 1} \\
  {{x^2} + 1}
\end{array}} \right],\,\,\,\,y = \left[ \begin{gathered}
  3 \\
  1 \\
\end{gathered}  \right] = \left[ {\begin{array}{*{20}{c}}
  {x + 1} \\
  1
\end{array}} \right] \\
  {e_K}(x) - {e_K}(y) = \left[ {\begin{array}{*{20}{c}}
  {{x^2} + x + 1} \\
  {{x^2}}
\end{array}} \right] - \left[ {\begin{array}{*{20}{c}}
  {{x^3} + {x^2} + 1} \\
  {{x^3} + {x^2}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
  {{x^3} + x} \\
  {{x^3}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
  a \\
  8
\end{array}} \right] \\
  x - y = \left[ {\begin{array}{*{20}{c}}
  {{x^3} + {x^2} + 1} \\
  {{x^2} + 1}
\end{array}} \right] - \left[ {\begin{array}{*{20}{c}}
  {x + 1} \\
  1
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
  {{x^3} + {x^2} + x} \\
  {{x^2}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
  e \\
  4
\end{array}} \right] \\
  {e_K}(x) - {e_K}(y) = \left[ {\begin{array}{*{20}{c}}
  {{x^3} + x} \\
  {{x^3}}
\end{array}} \right] \equiv A \cdot \left[ {\begin{array}{*{20}{c}}
  {{x^3} + {x^2} + x} \\
  {{x^2}}
\end{array}} \right]\,\,\,(\bmod \,{x^4} + x + 1) \\
\end{gathered} $

How can i proceed from the last step?

Your subtracting two known solutions would be one way to eliminate $b$ from the equations and allow you to work only with $A$.

However, you've already been told that $b = (0,0)$, and so we don't need to eliminate it.

Instead, we know that the cipher satisfies the relations (omitting $b$ because that's known to be 0):

$$\begin{gathered}
  A \times \left[ \begin{gathered}
  d \\
  5 \\
\end{gathered} \right] = \left[ \begin{gathered}
  7 \\
  4 \\
\end{gathered} \right]\end{gathered},
\begin{gathered}
  A \times \left[ \begin{gathered}
  3 \\
  1 \\
\end{gathered} \right] = \left[ \begin{gathered}
  d \\
  c \\
\end{gathered} \right]\end{gathered}
$$

Where $A$ is a 2x2 array, and all math is done in $GF(16)$.  So, if we replace $A$ with the array $A = \begin{gathered}
  \left( \begin{gathered} x \\ z \end{gathered} \begin{gathered} y \\ w \end{gathered} \right) \end{gathered}$ (where $x, y, z, w$ are unknown values in $GF(16)$, we have:

$$d \cdot x + 5 \cdot y = 7$$

$$d \cdot z + 5 \cdot w = 4$$

$$3 \cdot x + 1 \cdot y = d$$

$$3 \cdot z + 1 \cdot w = c$$

By doing Algebra in $GF(16)$, it's easy to solve these simultaneous equations (hints: remember, $GF(16)$ is a field, and so algebra works there just as you'd expect; you'll need to compute multiplications and inverses in $GF(16)$, if you don't have any tooling on hand to do that, you might find it helpful to whip together a quick program.


Are Lagrange Multipliers necessary for Shamir's secret sharing? What is the implication of not using the Lagrange multipliers in Shamir's secret sharing?

I mean each update will be $Poly(x_i) \bmod p$ where $p$ is a prime number instead of the original one that is $(Poly(x_i)* LPC_i) \bmod p$.
Assuming that the verifier has access to all secrets $x_i$s, it can re-do all the updates and check if the result is equal to the secret or not.

Is that less secure?

I will answer you by an example, assuming Shamir sharing algorithm with $d=2$ (minimum shares). So, by definition we need a $d-1$ degree polynomial as:

$Poly(x)$ = $ A_1 \cdot X^1 + S$ = $10x +20 $ where $S=20$ is the secret. The dealer will calculate the shares as (two shares for simplicity, where 2 is needed to reconstruct the polynomial):

$(1) [x_1, Poly(x_1) ]$ = $[ 5, Poly(5)]$ =$[5,70]$ , and

$(2) [x_2, Poly(x_2) ]$ = $[ 10, Poly(10)]$ =$[10,120]$.

Now, without using Lagrange interpolation: the verifier needs to reconstruct the polynomial equation (i.e., line equation) to find $S$ as:

$(1) Poly(5)=A_1 \cdot 5 +S =70$ and

$(2) Poly(10)= A_1 \cdot 10 + S =120$

So, you will need to solve the two equations. This is a simple one because it has only two equations. However, for larger  $d$ minimum shares it will be intricate process to solve lets say 10 equations.

Second, by using Lagrange interpolation it will be much easier because we are only interested by $Poly(0) \equiv S $.

In conclusion, both have the same security but Lagrange interpolation is much faster way.


Proving Non-Existence of ECC Backdoors In light of the NIST Dual EC DRBG scandal, I was intrigued by a NIST slide (slide 9) that said the two points P and Q can be chosen so that the chooser can  prove they don't have a backdoor. This seems rather magical to me, so I'm looking for some more information. I'm assuming they're referring to something more substantial than "nothing up my sleeve", which is hardly "proof". Do Safe curves or Koblitz curves have this property?

You need to clearly distinguish between the DualEC DRBG algorithm and the elliptic curves over which it is defined.

The backdoor in DualEC DRBG needs the attacker to choose P and Q such that they know the scalar $k$ for which $P=kQ$. Pretty much any algorithm which fixes both public keys at the same time without going through private keys is fine. For example you could choose the hex expansion of $\sqrt{2}$ and $\sqrt{3}$, or SHA2(x), SHA2(x+1). This is pretty similar to nothing-up-my-sleeves numbers, but the requirements are pretty weak, since the only thing you need to prevent is the attacker knowing $k$.

Backdooring curves is an entirely different matter. You start with the conjecture that NSA knows a certain fraction of weak curves and tries to choose one of them. To avoid this, the curve must be as rigid as possible, i.e. allow as little choice to the designer as possible. This is where "safecurves" fare better than the common NIST curves. So your question about "safecurves" having this property misses the point.

The only coupling between the DualEC DRBG backdoor and the choice of curve I can think of is is choosing the curve parameters so that particular points have a known relation. I don't know if that's possible at all, but I expect this to require a lot of freedom in choosing the curve, more freedom than even the NIST curves have. Preventing this attack is easy: just include the serialization of the curve parameters in the inputs of the hash used to derive the points.


Notion of Security in case of Covert Adversaries On the page 31 of the Book "Efficient Secure Two-Party Protocols by Y. Lindell and C. Hazay", while defining the notion of security in case of covert adversaries, it is mentioned:

  Define an adversary to be covert if the distribution over the messages that it sends during an execution is computationally indistinguishable from the distribution over the messages that an honest party would send. Then, quantify over all covert adversaries A for the real world (rather than all adversaries).

What do we mean exactly by quantifying covert adversaries?
Moreover, it says:

  Another problem is that adversaries may be willing to risk being caught with more than negligible probability, say $10^{-6}$. With such an adver- sary, the proposed definition would provide no security guarantee.

While quantifying the covert adversaries, how did we make it so that the probability of catching the "non-covert" adversaries is equal to statistical distance from the honest party's distribution?

Moreover, on page 32, why did we decide to quantify over all adversaries (including malicious), and how did that fix the problem we were dealing with?

What do we mean exactly by quantifying covert adversaries?

This means in the security definition (e.g., Definition 2.4.1 in that book), we say something like this "...for every non-uniform probabilistic polynomial-time (PPT) covert adversary, there exists...".

  While quantifying the covert adversaries, how did we make it so that the probability of catching the "non-covert" adversaries is equal to statistical distance from the honest party's distribution?

No, we didn't. The probability $10^{-6}$ is not a statistical distance, but just a non-negligible risk that a "non-covert" adversary has to take.

  Moreover, on page 32, why did we decide to quantify over all adversaries (including malicious), and how did that fix the problem we were dealing with?

If we quantify only covert adversaries, then the resulting security definition tells nothing about "non-covert" ones. That is, for a protocol that is secure in this sense, we are only guaranteed that no covert adversary can reveal additional information about the honest parties' inputs (except that implied by the function's output) by executing the protocol, but a "non-covert" adversary could still break this security. By quantifying all adversaries, the final definition (about secure computation in the presence of covert adversaries with $\epsilon$-deterrent) guarantees that every non-uniform PPT adversary $A$ can be caught with probability at least $\epsilon$ if $A$ chooses to cheat.


Example of a Hash function which is second pre-image resistant but not collision resistant We know that a collision resistant hash function is also second pre-image resistant. But the converse is not necessarily true.
I am looking for the example of a hash function which is second pre-image resistant but not collision resistant. Please help.

Let $H$ be a collision resistant hash function. This implies that it is also second preimage resistant.
Let $x_0,x_1$ be two arbitrary values from the domain of the hash function. We define the new hash function $$H'(x):=\begin{cases}H(x)& \text{if }x\neq x_0\\H(x_1)&\text{if }x=x_0\end{cases}.$$
This hash function is trivially not collision resistant, just output $x_0,x_1$. However, it remains second preimage resistant via a simple reduction.


Error-correcting Code VS Lattice-based Crypto I'm not an expert in PQ-crypto, but as I understand error-correcting code and lattice-based crypto, the cryptographic assumptions are very similar. The key difference for me is the nature of the noise. In one case, the noise is inspired by the "physical noise," in the other, it's more mathematical and considers a more complex distance (Euclidean distance instead of Hamming distance).
Intuitively, this reason makes sense because every application I know involving lattice-based crypto is more efficient than those based on
error-correcting crypto.

Does my intuition seem correct to you?

If yes, is there a theorem that certifies that every cryptographic protocol based on an error-correcting-code assumption could be transformed into a more efficient lattice-based protocol (i.e., with the same level of security and based on a weaker lattice assumption)?

If no, is there a more informal claim of available research which considers this question? Or it just doesn't make sense to compare these two families of assumptions?

Broadly speaking, it's true that the main difference between "code-based cryptography" assumptions and "lattice-based" assumptions is the noise distribution.
There are of course exceptions, e.g. code-based cryptosystems using the rank metric, or binary LPN, where the noise can be described as either small Hamming weight or small Euclidean distance.

In one case the noise is inspired of the "physical noise", and in the other one, it's more mathematical and consider a more complex distance (euclidean distance instead hamming distance).

I'm not sure about these analogies of "physical" and "mathematical" noise. Both types of noise may be useful mathematical models in different physical scenarios, e.g. low Hamming weight noise can model bits flipped during transmission, while Gaussian noise can model small perturbations in an image from a noisy sensor. In any case, these analogies aren't really relevant to cryptography.

is there a theorem which certify that every cryptographic protocol based on an error-correcting code assumption could be transformed in a more efficient protocol based on lattice (i.e with the same level of security and based on a weaker lattice assumption)?

I don't know of any general theorems like this. While lattice-based protocols are often more efficient, this is not always the case and it very much depends on the cryptographic application.
A natural example where lattices beat codes is key exchange. Here, lattice-based protocols such as Kyber are much simpler and faster than their code-based analogues like BIKE, largely due to an expensive error-correction step in the code-based setting, compared with cheap rounding techniques to correct errors in the lattice setting.
Another example is the challenge of constructing linearly homomorphic encryption schemes. This is quite straightforward using lattices, but still an unsolved problem from code-based assumptions. There is even evidence that this is impossible to achieve using natural "arithmetic" techniques - see the paper of Applebaum, Avron and Brzuska; this work only looks at specific applications, but may contain the types of theorems you are interested in.
On the other hand, there are cases where small-Hamming-weight noise can give efficiency benefits. A fairly recent example is when generating private, correlated randomness (e.g. multiplication triples or random oblivious transfers) for use in secure multi-party computation protocols. Using code-based assumptions, there are efficient techniques for compressing the correlated randomness down to much shorter seeds, which can be later expanded. This compression technique crucially relies on the sparse noise distribution, and analogous methods in the lattice setting are much more expensive. (See for instance, these works)


How rare are 1024-bit $B$-smooth numbers? What is the probability that if I choose a random $1 < r < n - 1$, $r^{65537} \pmod n$ will be $B$-smooth?  $n$ is a 1024-bit RSA modulus.

The Wikipedia pages on smooth numbers and the Dickman function are too obtuse for me to understand enough to calculate for my particular case.

I was contemplating an attack on something that uses a broken PKCS #1 v1.5 signature padding check.  I figured that if I found find many such $r$, I could forge signatures by manipulating the unchecked parts of the "message representative" to make it factor over the factor base $B$.  The signature then would be calculable as a linear matrix.

This all resembles parts of the quadratic sieve algorithm.  Quadratic sieve would be too difficult to do on a 1024-bit number, so it's quite possible that this attack idea is infeasible just from the rarity of smooth numbers.


Correlate HMAC key and MAC without message If I have a HMAC_SHA1 MAC and a potential key, can I check whether this key could have produced this signature without knowing any of the message body plaintext?

If I have a HMAC_SHA1 signature and a potential key, can I check whether this key could have produced this signature without knowing any of the message body plaintext?

No, there is no known efficient way.

Now, if you look at how HMAC works internally, then there will be (with high likelihood) will be values that cannot be produced by a specific key; that is, values which cannot be achieved by any message $M$.  This happens because the inner SHA-1 hash summarizes the message $M$ into a 160 bit value (in a key dependent operation); then it performs another key dependent operation t(the outer hash) to convert it into another 160 bit value.  This transform is unlikely to be invertible, and hence there are likely 160 bit outputs that cannot happen.

However, even though those impossible values almost certainly exist, we have no way of finding what these values might be, or whether if any specific output is one of those.

Also, a minor terminology note:

  If I have a HMAC_SHA1 signature…

In crypto, we tend to use the term 'signature' to refer to a public key signature operation (which HMAC is not).  Instead, we might call it an HMAC_SHA1 MAC (Message Authentication Code)


What is the difference between a forgery attack and an user impersonation attack? I'm new to cryptography, so I was searching for a forgery attack, but unable to find anything.

Can anybody tell me the difference between forgery attack and user impersonation attack?

Forgery and impersonation attacks are different. Forgerty attacks target on verifiability where impersonation attacks target on authentication. However, they are somewhat linked, as detailed below.

In cryptography, many schemes such as digital signature, message authentication code, verifiable secret sharing etc. require verifiability.

In such a scheme, a user has a key pair $(k,vk)$ ($k$ and $vk$ can be the same or different). There is an algorithm $f(m,k)$ that takes a piece of data $m$ and the secret key $k$ as input, and output some cryptographic data $c$, and there is another algorithm $v(m,c,vk)$ that takes data $m$ and $c$, and the verification key $vk$, and outputs 1 if $c$ is indeed generated using $f$ from $m$ and $k$, and outputs 0 otherwise.

Forgery attack in this context means an attacker who has no knowledge of the secret key $k$ can generate a pair $(\bar{c},\bar{m})$ such that he has never seen $f(\bar{m},k)$ before, and $\bar{c}$ can pass the verification, i.e. $v(\bar{m},\bar{c},vk)=1$.

A forgery attack can (but not necessarily) lead to an impersonation attack. An impersonation attack is when an adversary can successfully claim an identity that he doesn't possess, and pass authentication (i.e. he can pretend to be another person in the system). Many authentication protocols rely on verifying some cryptographic data, if the cryptographic data can be forged, then authentication will admit the wrong person.

One prominent example is many authentication protocols rely on PKI, and require the party to be authenticated to provide a valid certificate, and the validation of the certificate relies on much on the CA's signature on the certificate. If one can forge the CA's signature, he can forge a certificate, thus be authenticated as another person.


How to test massives amount of links? Ok, I have a wordlist of many many links (of the same site with a bit of difference in URL).

I'm certain that the majority of then will return the same result, a error page. But one will return the "correct" page.
The point is:
Is there a automatic way to test all of those links searching for the different one?

Sure, pick any coding language of you choice and iterate over the list of links connecting to the website. You will receive the website as some kind of object. If you know what the error page looks like, just check the object contains that error page (for example check for some string).

Also, just you could try one of the tools on this website:
http://www.softwaretestinghelp.com/tools/30-top-website-link-verification-testing-tools/


Is triple-CRC-32 a bad (or not) idea for generating a uniform distribution hash? I have an input of 288 bits (comprising 4 × 32-bit and 10 × 16-bit integers). I need to hash this to 96 bits with as few collisions as possible.

I'm aware that CRC is a bijective hash, thus ensuring 100% even distribution (as I understand it). In my view, I should be able to run 3 parallel CRC paths through the input, resulting in a 96-bit hash of optimum distribution.

However, I'm also aware that CRC is not used for such applications. An algorithm such as MetroHash would typically be used.

Could someone explain to me why CRC is a bad (or not) idea for this application?

Note: This is not intended for anything secure.

The identity function is also a bijection. That doesn't make it a good hash in any way.
If a function reduces input size, how can it be a bijection?
If you are not intending anything secure maybe this is the wrong place to ask. ;)
Maybe a more useful answer is this.


Consequences of Flipping a bit in an RSA public key I'm taking a cryptography class and one of the previous exam questions is "Alice requests Bob's public key which Bob sends her. She then encrypts the secret number $M$. Unfortunately, Malice flips the fourth least significant bit of Bob's key $e$ in transit which Alice then uses to form the ciphertext $C_1$. Bob can't decrypt so he sends his public key again. Malice leaves the key alone this time and Alice encrypts and sends $M$ in the form $C_2$.

Where $(e_\text{Bob}, n) = (17, 113291)$
 and
$C_1 = 68496, C_2 = 12465$.

I don't really know how to go about doing a problem like this in an exam situation (i.e. with just a calculator) so I'm wondering if there's some trick to doing it without just finding the factors of $n$.

First note that $e=17=10001_2$ and thus that $e'=11001_2=25$ with $e'$ being the one with the flipped bit. Now note that $M^{e'}\equiv C_1\pmod n$ and $M^{e}\equiv C_2\pmod n$.

Next note how $C_2/C_1\equiv M^{25}/M^{17}\equiv M^8 \pmod n$.
Now compute $M^{17}/M^8\equiv M^{9}\pmod n$ and continue this.
$M^{9}/M^{8}=M \pmod n$ and you are done.

Note that all divisions here are in $\mathbb Z^*_n$, that is, they are multiplications with the multiplicative inverses $\bmod n$.


How does a birthday attack on a hashing algorithm work? A "normal", brute-force attack on a cryptographic hashing algorithm $H$ should have a complexity of about $2^{n}$ for a hash algorithm with an output length of $n$ bits.

That means it takes about $2^{n-1}$ tries on average to find a colliding message $y$ for a given message $x$ so that $H(y) = H(x)$ while $y \ne x$.

However, a birthday attack (e.g. both $x$ and $y$ can be selected arbitrarily, but $H(x) = H(y)$ is of course still required) is supposed to be much faster, and take only $2^{n/2}$ tries to find a collision.

I see how that works out in terms of time complexity - since we are now looking at all tuples of all guesses so far, of which there are $n^2$, the probability of a collision now grows quadratically instead of linearly.

But shouldn't we also need space to store all of the already tried $x$ and $y$? If we don't, how can we even compare all the tuples of all the hashes enumerated so far? That seems to make such a birthday attack practically impossible, since $2^{n/2}$ bits of storage are a lot, not even thinking about the problem of accessing all that storage in constant time.

Update: I've found http://www.cs.umd.edu/~jkatz/imc/hash-erratum.pdf, which seems to say that the attack is possible with constant space. However, the proof and explanation given are way above my head.

The method described in the link you cited is based on Floyd's cycle finding algorithm, also known as "the tortoise and the hare" algorithm.  This is a general-purpose algorithm for detecting cycles in iterated maps, which I will first describe below.

Specifically, consider the sequence $(x_i)$ defined by $x_i = H(x_{i-1})$ for some map $H$ and some initial value $x_0$.  If this sequence is cyclic, then we have some integers $j > 0$ and $k > 0$ such that $x_j = x_{j+k}$, and thus also $x_i = x_{i+nk}$ for all integers $i \ge j$ and $n \ge 0$.

In particular, this holds for $i = nk$ and any integer $n$ satisfying $n \ge j/k$, yielding $x_i = x_{2i}$.
Thus, if the sequence $(x_i)$ is cyclic, there exists an integer $i > 0$ such that $x_i = x_{2i}$.  Conversely, the existence of such an integer also clearly implies that the sequence must be cyclic (with a period that evenly divides $i$).

It thus follows that, to detect cycles in the sequence $(x_i)$, it suffices to check whether $x_i = x_{2i}$ for any positive integer $i$.  We can do this iteratively using constant space by keeping track of two elements of the sequence, $y = x_i$ and $z = x_{2i}$ (both initialized to $x_0$ at iteration $i = 0$), and, on each successive iteration, updating them as $y \gets H(y)$ and $z \gets H(H(z))$.

If we find such an $i$, we'll know that the sequence $(x_i)$ is cyclic.  Now, we have two possibilities: either the initial value $x_0$ is part of the cycle, or it is not.  In the latter case, we have $x_0 \ne x_i$ but $$H^{(i)}(x_0) = x_i = x_{2i} = H^{(i)}(x_i),$$ and we've thus found a collision in the $i$-fold iterated map $H^{(i)}$, which in turn implies the existence of a collision in the underlying map $H$.

All that remains to be done is locating the underlying collision.  To accomplish that, we rewind the iteration back $i$ steps, so that $y = x_0$ and $z = x_i$, and advance them one step at a time, this time as $y \gets H(y)$ and $z \gets H(z)$ so that, at iteration $j$, we'll always have $y = x_j$ and $z = x_{i+j}$.  Since we know that $x_0 \ne x_i$ and $x_i = x_{2i}$, it follows that there must be some $j$ between $0$ and $i-1$ such that $x_j \ne x_{i+j}$ but $x_{j+1} = x_{i+j+1}$, and thus $H(x_j) = H(x_{i+j})$.  When we find that $j$ — i.e. when we find the first $y$ and $z$ such that $H(y) = H(z)$ — we stop; that's the collision we've been looking for.

This algorithm only requires space for storing a fixed number of values: $x_0$, $y$ and $z$.  How much time does it take?  Well, if $j$ and $k$ are the lowest positive integers satisfying $x_j = x_{j+k}$, then Floyd's cycle finding algorithm will take $i = k \lceil j/k \rceil < k(j/k + 1) = j + k $ steps (each involving three evaluations of $H$) to detect the cycle, and then $j$ further steps (involving two evaluations of $H$) to locate the collision, for a total of up to $5j + 3k \le 5(j+k)$ evaluations of $H$.

Now, if $H$ is a random function on an $m$-element set, then, by the birthday paradox, the expected number of steps $\mathbb E[j+k]$ before the first collision is $O(\sqrt{m})$.  Thus, the expected runtime of the collision-finding algorithm described above is also $O(\sqrt{m})$.


Does anyone have any hard ciphers to be cracked for fun? The title says it all. Do you have any ciphers or encoded messages that you could post as a brainteaser?
Thanks!

Not sure anyone here has a sense of humour.  But in case they do:-

Obviously Kryptos, CIA headquarters, Langley.

Less obviously, this sad one time pad message, Surrey, England (also proving that OTPs did exist and were useful).

Good luck, and please post your answers here :-(


How secure will this be against brute-force attacks? I'm looking into encrypting files like this: First, I SHA-1 hash the password. Let's say the password is something normal like "hello123", and then hashed. Then I encrypt a file using this:

openssl aes-256-cbc -a -salt -in file -out file.enc

(using the hash for the password).

So it's basically just an AES-256-CBC encryption with a salt.

How easy would it be to crack this by brute force? (Assuming the attacker knows that we have aes-256-cbc with salt and that the original password is hashed.) For instance, how long time would it take these days, on "normal" hardware?

I don't know how you're adapting the digest of SHA-1 to meet the key requirement of AES-256 (stretching the 160 bit digest into a 256 bit key), but if you somehow have a way of doing that without seriously compromising key entropy, then you have a theoretical key space of $2^{256}$. That window is limited by the limitations on your encryption passphrase however. In an ideal case for decryption where the person cracking your cipher has your program and knows the limits on your passphrases, they don't have to test all $2^{256}$, only your possibilities.

Say you limit passphrases to $10$ keys, alpha-numeric. That's $62$ characters to work with. The practical key space for you is $62^{10}$.

Arguably, it is currently impossible to decrypt even in the above worst-case scenario. This is largely due to another factor: verification of success. Say you only had $200$ possibilities. Someone trying to decrypt the file needs a way to check if each of the $200$ attempted keys yielded accurate results. Given that they may not know the nature of the file, that seriously complicates the process.

You're good for a while.


How to prove correct decryption in Goldwasser-Micali cryptosystem In How to prove correct decryption in Paillier cryptosystem, it was asked whether Alice (in sole possession of the secret key) can convince Bob that a given plaintext is the decryption of a ciphertext provided by Bob (who doesn't know its contents). In the case of Paillier encryption, the answer seems to be yes. Is anyone aware of a corresponding (preferably zero knowledge) solution to this problem in the case of Goldwasser-Micali encryption?
Thanks,
Neil.

Goldwasser Micali encrypts a 0 by sending a quadratic residue and a 1 by sending a non-quadratic residue. So, to prove that the encrypted bit is 0 what you need is a zero-knowledge proof of quadratic residuosity: for a given $b,N$, does there exist an $a$ such that $a^2 = y \bmod N$. There exist such proofs, and it should be easy to find online. However, for 1, that would be harder since in general it's harder to prove that something does not exist (naively, this would be a co-NP statement, which doesn't necessarily have an efficient proof). So, the idea is to try to change what you are looking to prove to something easier. The Goldwasser Micali public key includes a value $x$ that is not a quadratic residue. Then, an encryption of 1 is generated by choosing a random quadratic residue and multiplying it by $x$. Given this, you can prove that a value $b$ is an encryption of the bit 1 by first dividing by $x$ and then proving that the result is a quadratic residue (i.e., prove that $b \cdot [x^{-1} \bmod N] \bmod N$ is a quadratic residue). Note that the inverse can be computed using GCD, so that's easy.


Is it secure to use so many iterations of AES-CBC as a KDF so that it's slow even using AES-NI? Note: This is not the same as Multiple iterations of AES for key derivation?.

Almost everyone has AES-NI nowadays - when building a cryptographic application, is is possible to leverage this to create a kdf that is about as slow for the attacker to attempt a single key on a single CPU as it is for the user to derive one key?

Also, is it possible to feed the last block of AES-CBC as the key of the next round of encryption over the rest of the ciphertext to make it memory-hard, and avoid encrypt-one-block-at-a-time-many-times attacks, as the entire ciphertext needs to be in memory?

Essentially, key derivation would work something like this, just a lot more times:

Here's an answer that takes your question down a different path. RFC 2898, "PKCS #5: Password-Based Cryptography Specification: Version 2.0" is the document that defines the PBKDF2 function, in section 5.2.  Although PBDKF2 is normally instantiated with HMAC, the spec says that any pseudorandom function (PRF) may be used, with the implicit proviso that the PRF must accept variable-length keys (since the password is used as the key).

RFC 4615, "The Advanced Encryption Standard-Cipher-based Message Authentication Code-Pseudo-Random Function-128 (AES-CMAC-PRF-128) Algorithm for the Internet Key Exchange Protocol (IKE)" defines such a variable-length key PRF on top of AES-CMAC (RFC 4493):

  The AES-CMAC-PRF-128 algorithm is identical to AES-CMAC defined in [RFC4493] except that the 128-bit key length restriction is removed.

CMAC itself is a CBC-like mode that was designed to fix the shortcomings of the CBC MAC (which is only secure for fixed-length message spaces).

So by plugging in those reasonably standard components together you get an AES-based password-based KDF that is a bit different from your diagram but you might find close enough for your purposes.


how to get secret keys in xor? 1) a = b ⊕ s1

2) b = a ⊕ s1

3) b ⊕ s2 = c

Is there a way to find s1 and s2 if we know many different values of a and c?

4) a1 = b1 ⊕ s1

5) a1 ⊕ s1 ⊕ s2 = c1

I think it is possible if we analysis the result, but I am not sure how. Or is it impossible?

Edit: Sorry , a and c should be known but not b.

Alice sends 'a' to Bob. 2) Bob computes a xor s1 = b then 3) b xor s2 = c. Bob then sends c to Alice and verify if b =c .

The way your question is written, it's hard to tell what you're asking.

The trivial answer to your original question is that, if you only know $a$ and $c$, then you can calculate $s_1 \oplus s_2 = a \oplus b$, but not the individual values $s_1$ and $s_2$; for every $s_1$, there's a corresponding $s_2$ that satisfies the equations, and vice versa.  The same holds true even if you know multiple $(a,c)$ pairs calculated using the same $s_1$ and $s_2$, since each such pair will just yield the same value of $s_1 \oplus s_2$, and no other relevant information.

As for the protocol description you edited in, I have no idea what your protocol is supposed to accomplish, and I suspect you've garbled the description somehow.  In particular, if Bob indeed computes both $b = a \oplus s_1$ and $c = b \oplus s_2$, and only sends $c$ back to Alice, then the value $b$ plays absolutely no role in the protocol: Bob could equivalently just compute $c = a \oplus s_1 \oplus s_2$ directly.  Also, without knowing $b$, Alice cannot possibly verify that $b = c$.  Bob could do that, but that's equivalent to just verifying that $s_2 = 0$, which he could just as well check without running the protocol at all.  So your protocol, as written, makes no sense.

Anyway, even if the protocol was fixed to actually work, I don't see any way to build a secure authentication protocol out of just linear operations like XOR.  You'd need something else, like a block cipher, to do that.


Are the following asymmetric encryption schemes equivalent? Consider the scenario where you want a machine to be able to send daily encrypted backups to a storage server.

You'd prefer to not use simply a symmetric key for encryption, because if the machine was compromised then the symmetric key would enable the entire history of backups on the storage server to be decrypted.

Are the following two schemes equivalent?

In all schemes, the storage server only allows uploads, and not downloads or deletions. In all schemes, generate a permanent EC keypair (a,A) (where a is the private key and A is the corresponding public key). Store only A on the machine.

Scheme 1: Generate an ephemeral EC keypair (e, E) for each backup. Encrypt the data using an authenticated cypher (such as AES256-GCM or ChaCha-Poly1305) using the symmetric key H(eA), where H() produces uniformly distributed hashes (such as SHA2-256). The backup is decrypted using the symmetric key H(aE), and E is stored along with the backup. Successful decryption proves that only a machine that knew A could have created the backup. Backups would include timestamps, so it would be detected if the same observed backup was retransmitted by an attacker at a later date.

Scheme 2: In addition to the permanent encryption keypair (a,A), keep a permanent authentication keypair (b,B) on the machine. Then, Scheme 2 is the same as Scheme 1 except that prior to transmission, the encrypted backup is signed with b. On decryption, verify the signature first.

At first glance, it might seem that Scheme 2 is superior, because it prevents backups from being uploaded by an attacker that learns of the public key A. However, the authentication private key b is stored on the same machine, so both b and A are likely to be leaked together. There is no way I can see that anyone compromising the storage server could deduce the public key A that was used on each occasion when sending each backup.

Therefore, scheme 2 does not look superior to me, other than if it is suspected that the machine is compromised, the signing keypair (b,B) can be replaced without also having to replace the keypair (a,A).

Is this correct? Does use of the authentication keypair in scheme 2 have any other advantage? Does knowledge of A effectively authenticate the backup just as well as if the backup was signed with b?

Generally, you should try to keep to standard practices unless the situation prevents you to do otherwise. That would mean that sign-then-encrypt should probably be used using two different key pairs.

Public keys are designed to be public and you should keep that in mind. Even if your scheme is secure, the system may not be. Public key operations could for instance leak the public key through side channel attacks. There is no need to protect the key after all. Key stores may not be available to store the key securely or at the right access level. Maybe you want to replace the software implementation with a hardware module that securely stores the private key - public keys won't be protected by such hardware.

An advantage of sign-then-encrypt is that you could decrypt the backup, then check the correctness of the signature afterwards. This allows you to store the backup decrypted somewhere without losing integrity. It also allows you to re-encrypt the package using a different key / scheme if that's required. Or to sign using a more fine-grained structure where parts of the backup are protected separately. In other words, using a separate signing key will give you a lot more flexibility.


Using a PRNG for a stream cipher instead of a dedicated algorithm I am aware, that it is possible to build a stream cipher using some deterministic PRNG (like HASH_DRBG or CTR_DRBG) with good key material as the seed.

What are the advantages of using a purpose built stream cipher algorithm (like Salsa20 or RC4 before it became obsolete) over a generic PRNG?

Rather than giving the advantages of purpose build stream cipher I'll give the disadvantages of using a PRNG / DRBG (you are using a PRNG for the use case of a stream cipher after all):

Implementation details (including reseeding) may differ between systems (this is less likely if the DRBG is well defined and tested, but as they have been designed to retrieve random numbers given some entropy, you never know);
Often deterministic stream ciphers are retrieved from the system. That means that they may be reseeded. You could argue that this is mainly what makes them different from a stream cipher in the first place.
PRNG's often contain additional counter measures to decouple the state from the input (seeding material) & output, making them slower;
PRNG's are often more complex than just a stream cipher (code size, number of instructions). They are indeed often created from stream cipher-like constructions (such as CTR_DRBG you mentioned);
PRNG's are simply not defined for this kind of functionality in mind, making implementation and code maintenance more complex (considering, for instance, the principle of least surprise, which using a PRNG as stream cipher definitely violates);
PRNG's often do not contain implementation details like buffering, the final XOR operation etc. build into them; you may have to wrap a DRBG to create the same experience of a stream cipher operation encrypt / decrypt (and in e.g. Java you cannot simply add a Cipher without implementing and signing a provider).


How many bits of an exponent are leaked when doing a powmod? How many bits of the exponent $x$ are leaked when you calculate and reveal $g^x \pmod p$ for some generator $g$ of $\mathbb Z^∗_p$?

The low bit of $x$ is obviously leaked: the low bit equals $1-\frac{\left(\frac{g^x}{p}\right)+1}{2}$, with parentheses representing the Legendre symbol.

The answer depends on the factorization of $p-1$; for any factor $q$ of $p-1$, the attacker can derive $x \bmod q$ in $\sqrt{q}$ steps (by first computing $(g^x)^q = g^{xq}$, and then searching for the value $y$ with $(g^{xq})^y = 1$ using, say, Pollard Rho.

Hence, if the attacker has a computation budget of $n$, and $p-1 = q \cdot r$, where $q$ is $n^2$ smooth, and $r$ has no prime factors $< n^2$, then the attacker can derive $x \bmod q$, which can be analogized to $\log_2 q$ bits.  However, if you're interested in the precise bits (and not just bit equivalents), then (unless $p-1$ is $n^2$ smooth, in which case you can derive the entire value of $x$), you're stuck with $m$ bits, where $2^m$ is the largest power of 2 which is a factor for $p-1$.

(Note: I'm ignoring the factor that if $p-1$ might have multiple prime factors near $n^2$, we might take more than $n$ work; not ignoring that makes the analysis more complex, without changing the result substantially)

By this logic, your observation that we can always derive the lower bit of $x$, that is $x \bmod 2$, is equivalent to the observation that $p-1$ is always even.


What is the point of separate links to the download and its digital signature I see a statement like this on a product's download page:
"The signature for setup-x86.exe can be used to verify the validity of this binary using this public key."

where each this above is a hyperlink.

I thought the purpose of a sig is so that you could verify the validity of a document.

So what's the purpose of such a statement?

Surely it can't be  a protective measure just in case the site has been hacked to point the download link of the exe to a malicious file? In that case, won't the links to the signature/public-key themselves be altered by the attacker?

They don't expect that everybody uses their infrastructure. So, someone, a Man-in-the-Middle can change the executable or you are downloading it from alternative download sites that can contain malicious code.

One way to make sure that the file is not tempered is publishing the hashes on their website. Hash is very common for ISOs of the Linux distributions. This protects as long as you can access the hash values correctly. Another method is signing that also gives us information about the signer.

In the case of their website is hacked, you may be very unlucky to be in the middle of the attack that we expect it is a short time. If, however, they use a chained certificate and you know it before you can still check the signature. The attacker to be successful must somehow access the signature key. In general, to be on the safe side, the companies sign the files with an off-line computer so that the signature key cannot be accessed from an online attacker. As usual, the corresponding public key can be published.

So, in short, if the signature key does not belong to a trusted key chain that is verifiable, don't accept the file. Everybody can create a file with a signature and publish it with a verification key.


Why is RSA private exponent much larger than RSA public exponent? RSA private exponent is much larger than RSA public exponent. For example, for a 2048 bit RSA private key, the private exponent can have more than 2000 bits. But the public exponent is usually 65537 (0x10001) which has a much shorter bit length.

Here is my guess of the reason. Let's use define the following symbols to describe RSA algorithm:

$n$: modulus
$e$: public exponent
$d$: private exponent
$P$: public key $(e,n)$
$S$: private key $(d,n)$

Encrypt a plain message $M$ with $M^e \text{ mod }n$. Decrypt a encrypted message $C$ with $C^d \text{ mod }n$. Since $d$ is much larger than $e$, decryption incurs much more mulipliation compuatuation. So the use of a large priavate exponent is to make the decryption harder.

Is my guess correct?

Is my guess correct?

Not really; we don't go out of our way to deliberately slow down the decryption operation.  Instead, things are set up that way because that's what's needed for security.

It turns out that if $d$ is small (e.g. less than a fourth of the size of $n$), and we tell people what the corresponding $e$ is, it turns out they can factor $n$ efficiently.  Hence, $d$ needs to be large to ensure security.
There's no similar issue for $e$; telling a people a small $e$ doesn't help them factor $n$ (or otherwise break RSA).  Hence, there's no reason not to select a small value (and make the encryption operation faster).


Asymmetry between public key and private key: digital signatures use the private key for “encryption”? I have a misunderstanding concerning public key cryptography...would be very helpful if you answer the questions...

Digital signatures: You use your private key for "encryption" and they use your public for "decryption". I thought that you can only decrypt with a private key and encrypt with a public key.. and that's why it is called asymmetric cryptography and this is where all the maths comes in with trapdoor functions and so on....
That's obviously wrong so please explain what I got wrong.
So obviously what I thought in 1) is wrong... so I have read a bit further.
Now I have the impression that private and public key are symmetric in a sense that you can choose one for encryption and then the other one is for decryption but you could also do it the other way round. Then the term "private" and "public" would only refer to which key you publish and which key you keep in secret. What I dont understand here is: Where is the math with trapdoor function used here if it is in a sense completely symmetric?
Is it possible to easily derive the public key from a private key? I have heard that in theory NO but in practice YES...

So I'm a bit confused at the moment, maybe you can help me out here.

You use your private key for "encryption".

That's a common misconception, which has roots in history. The point is that for RSA calculations the signature generation operation uses the same mathematical operation - modular exponentiation - with the private key as the encryption operation with the public key. So in older versions of PKCS#1 - itself called "RSA encryption - this is called "encryption with the private key":

  The data D shall be encrypted with the signer's RSA private key as
     described in Section 7 to give an octet string ED, the encrypted
     data. The block type shall be 01. (See Section 8.1.)

This is also reflected in RSA encryption originally being used as object identifier within X509 certificates, such as those within your browser.

This over-simplification was fixed in PKCS#1 v2 and higher, where the modular exponentiation got a different name: RSASP1 (RSA signature primitive 1) instead of RSAEP (RSA encryption primitive). A primitive here is simply an underlying function within the algorithm, by the way.

Other signature standards such as the Digital Signature Algorithm (DSA) use a specific operation to perform signature generation. This specific operation cannot directly be used for encryption. So there isn't a direct encryption counterpart for DSA. The Integrated Encryption Scheme (IES) can be used but it depends on Diffie-Hellman (DH) rather than DSA. The same goes for the more modern Elliptic Curve implementations (ECDSA, ECIES and ECDH respectively).

  Now I have the impression that private and public key are symmetric in a sense that you can choose one for encryption and then the other one is for decryption but you could also do it the other way round.

Yes, and that's precisely what you should not be thinking, Poncho has given a good answer here.

But note that if an implementation expects a public key that the operation with a private key may fail. Furthermore, as explained in the last part of the answer, the operation may not be secured for keeping the private key, well, private. And finally it may not use CRT speedup / security either as a public key generally doesn't contain CRT parameters - there is no need and they are not present during key pair generation for the public key.

  What I dont understand here is: Where is the math with trapdoor function used here if it is in a sense completely symmetric?

This is an RSA specific question. It's during the modular exponentiation. The trick is to keep the right exponent (and possibly the parts used during key generation for calculations that use the efficient Chinese Remainder Theorem (CRT) secret.

But please remind that padding is required for a computation using RSA. Just the trapdoor isn't enough; there are certain requirements to make the trapdoor secure.

  Is it possible to easily derive the public key from a private key? I have heard that in theory NO but in practice YES...

I'm not sure about the theory, but if the public key has a large public exponent (e.g. almost the same size as the modulus) then the public key may have as much security as the private key when it comes to the algorithm itself. But there are many reasons why RSA decryption with the public key would still not be secure; e.g. side channel analysis may be performed that the implementation is not protected against (no reason to secure the public key after all). Large public exponents are not common at all and many implementations would even fail if they were to be used.

So you could just test all public exponents, combine them with the modulus and test if an RSA operation is successful. However, in practice the public exponent is simply set at the value 65537 (the fourth prime of Fermat). Besides that, the public exponent is often included in the private key structure as well. So you should not expect to keep the public key secret, period.