ECIES/ ECDHE/ EC-ElGamal encryption comparison I need to choose an encryption system, so I am trying to understand the differences between the existing options. I always find that people compare ECIES (Elliptic Curve Integrated Encryption Scheme) with RSA or ElGamal. It is clear that elliptic-curve-based encryption schemes are much more robust than RSA and ElGamal. So, I have decided to use an EC-based solution.

The problem now is that there are different EC-based encryptions--ECIES, ECDHE (Elliptic Curve Diffie-Hellman Encryption), EC-ElGamal--but I have been unable to find a clear explanation of their common features and differences.

Could someone provide me with a reference/study/comparison of these EC-based encryption solutions? Or could someone explain to me their basic differences? In particular, which one is the best in terms of resources consumption?

Fix a group $G$ of order $q$ in which discrete logs are hard, and fix a standard base point $g \in G$.  Fix an authenticated cipher $E_k$ of bit strings.

In (EC)IES, roughly:  A public key is a point $h \in G$.

To encrypt a message $m$, the sender:

picks an exponent $y \in \mathbb Z/q\mathbb Z$ uniformly at random,
computes an ephemeral public key $t = g^y$,
computes an ephemeral shared secret $s = h^y$, and
sends $t$ alongside $c = E_k(m)$ where $k = H(s)$ is a hash of the shared secret.

Note: The total computational cost is two exponentiations; the total ciphertext overhead is one group element.  Effectively, we are generating an ephemeral Diffie–Hellman key pair $(y, t)$ and doing a Diffie–Hellman key agreement with it.
The receiver, who knows the secret exponent $x \in \mathbb Z/q\mathbb Z$ such that $h = g^x$, computes $k = H(t^x)$ and decrypts $c$ with $k$.

Note: The total computational cost is one exponentiation.

In (EC-)Elgamal:  A public key is a point $h \in G$.

To encrypt a message $m$, the sender:

picks an exponent $y \in \mathbb Z/q\mathbb Z$ uniformly at random,
computes an ephemeral public key $t = g^y$,
computes an ephemeral shared secret $s = h^y$,
picks $k$ uniformly at random from some subset of $G$,
computes the product $z = k \cdot s$, and
sends $t$, and $z$, alongside $c = E_k(m)$.

Note: The total cost is two exponentiations and one multiplication; the total ciphertext overhead is two group elements.
The receiver, who knows the secret exponent $x \in \mathbb Z/q\mathbb Z$ such that $h = g^x$, computes $k = z\cdot t^{-x}$ and decrypts $c$ with $k$.

Note: The total cost is one exponentiation and one multiplication.

As you read, you may see a resemblance here!  Elgamal does essentially everything IES does, plus some extra work that adds no security, which I have written in bold.

In the elliptic curve case, Elgamal is even trickier.  Why?

In the finite field case where $G = \mathbb Z/p\mathbb Z$, the integers modulo a prime $p$ (or where $G = \operatorname{GF}(2^n)$), $k$ can be (say) a 256-bit string that serves a dual purpose as an AES key and, interpreted as an integer in little-endian, as an element of $G$.
In the elliptic curve case, there's no natural map between bit strings and elements of $G$, so you need to choose some correspondence between random elements of $G$ and (say) AES keys—like a hash function $H(k)$.  But if you were going to hash an element of $G$ into a key anyway, you might as well have just used ECIES!

Even worse, Elgamal requires computing multiplication in $G$, not just exponentiation $G$, which means that you can't take advantage of DH functions like X25519 which support only the equivalent of exponentiation (‘$x$-restricted scalar multiplication on Curve25519’, using the fast constant-time Montgomery ladder) but not the equivalent of multiplication (‘point addition on Curve25519’).

The only reason to use Elgamal is exotic applications that require expert guidance like voting systems, where the message $m$ is concealed directly, rather than some key $k$ used for an authenticated cipher; this happens only if you are exploiting the homomorphic properties of Elgamal, and doesn't work with arbitrary bit string messages but rather requires you to be very judicious about what messages are and how they are chosen.

If you want public-key anonymous encryption, you should use libsodium crypto_box_seal, which is conceptually the same idea as ECIES (with all the details I go into done differently).  Note, of course, that public-key anonymous encryption is a kind of weird thing to do that most applications, outside journalists accepting leaks, don't need.  More likely, you want public-key authenticated encryption, for which you should use NaCl/libsodium crypto_box_curve25519xsalsa20poly1305, if you have a definite notion of a sender and receiver who know one another's public keys and want to exchange unforgeable secret messages.


Hypothetical unknown cipher - security in obscurity? I'm curious what would happen in the following scenario:

Suppose an attacker gets a hold of a cipher-text of sufficiently large length. And suppose he has the means to verify a successful decryption.
But the attacker has no clue what cipher is used and assumes it's unbreakable with anything but brute-force whatever it is.
He also assumes it's a block cipher. (Thus, whatever operations the cipher performs are repeated over each block.)

Suppose he knows the block is of length 128bit. How long (what is the complexity) will it take him to brute-force all possible operations that can be performed?
What if it's XTS and the attacker doesn't know anything about any standards?

I guess this is just to contrast the security in obscurity argument, but I'm also interested in the complexity numbers.

Also, what would happen if you modify AES in some way, like adding some extra rounds or an extra operation, something simple. And make it such that the change is NOT hard-coded into the algorithm but is instead loaded as a module/script as PART of the key to access the encrypted data? How much complexity would that add to someone trying to get your plain-text if he doesn't even know precisely what algorithm is used.

An unknown block-cipher with an $n$-bit block length can just be viewed as an arbitrary permutation of size $2^n$. Assuming you have the means to verify a correct decryption, you can just try each of every $2^n!$ possible permutations.

Naturally, if your ciphertext consists of fewer than $2^n$ distinct block values then you can omit permutations which result in previously-tried plaintexts.

An extreme example of this would be a ciphertext consisting of one block of $n$ bits which would need only a maximum of $2^n-1$ decryptions to be tested. This is of course significantly less than $2^n!$


Why would using a random seed with other variables be bad for ecrypting if you can't guess the key? I asked this on stack exchange with it being code based, but someone suggested to ask here.

Basically, I've done a script in python and wanted an option to encrypt the input, but I couldn't get any libraries working so I decided to try make my own, despite not knowing how actual encryption works. The result I think still needs a few tweaks, but I don't understand how it could be cracked.

I know the random feature of python is apparently very bad for encryption, but I'm using other things too, so you can't just fake an md5, you also need the exact same results from looping through each letter in the key.

I'll break it down into stages as to what it does:

  Step 1:Get md5 of the key and set that as the seed (it could be
  more complicated than an md5 but I don't think it'd make much
  difference

  Step 2:Loop through the key one letter at a time, and for each
  letter, crc32 it, and select one random digit from the result. Repeat
  this until you have x numbers (currently set to 128), and then shuffle
  the list.

  Step 3: Based on the size of the key, calculate how many extra
  characters to add for each character in the input. For all
  characters, generate another number between 0 and 255 to add to it.

  Step 4 (reverse all this to decode): Loop through the input one letter at a time, convert the
  character to a number, and add on the results from step 2 and 3,
  before converting back to a new character (making sure it is in the range of 0 to 255). The result is then all of these
  characters together, and can be reversed if the right key is given.

So, here's what the output is like:

key = "super secret key"
input = "Test!"

(encode)
Result: hxrBVvYX27YlyKWKMxrA

key = "super secret key"
encodedstring = "hxrBVvYX27YlyKWKMxrA"

(decode)
Result: Test!

key = "Super secret key"
(decode)
Result: ýO¼É

As you can see, the result is dramatically different when a lowercase letter is swapped for a capital, but it still comes out with something. In what way is this really insecure? The only way I'd know how to break it is by just trying millions of combinations until it finds an output word that's in the dictionary.

Also, as an example of it in use, I got it running here: http://goo.gl/VBRYpfHit the execute button, click in the green box, and follow the instructions :)

Apologies if it's not a suitable question for the website anyways, I'm not sure if I worded it a bit too specifically for my case

Your option has the flaw of allowing either key recovery, or RNG state recovery, or both. Cryptographically strong constructions do not allow key recovery with less effort than brute force, even with millions or billions of known message pairs. In your case an attack will most likely succeed in a short period of time. It took me only a few hours to completely break something quite similar that at first glance appeared much stronger than this, but suffered from the same key recovery attack with modest computing power.

Since Python does not have native encryption, you kind of have to roll your own from the standard library, or use an addon library such as PyCrypto.

If you do not have the option of using an addon library, a stream cipher can be built from HMAC-SHA512, plus a nonce and a some counters. The high level overview is:

Generate salt and nonce (nonce can be 128-bit salt + 32-bit message counter).
The salt should be randomly generated, if a good RNG is not available in Python, use random.org
Salt needs to be stored, it is used to generate the encryption key for all messages.
Message counter is very important to keep current.

Generate key from password and salt using PBKFD2. If you are using a true random key and not a password you can skip this part.
key = hashlib.pbkdf2_hmac('sha512', 'Password', 'Salt', 32768)[:44]

I use truncated HMAC to generate 44-byte blocks, and a 32-bit message counter. The reason I truncate is to hide 160-bits of the hash state, which may provide additional security, but slows it down to around 2/3 of what is capable.
Find out how many blocks of keystream are required to encrypt the message. A 113-byte message would need 3 44-byte blocks

hm0 = hmac.new(key, 'Nonce', hashlib.sha512)
hm = hm0.copy()
hm.update('BlockCounter')
KSBlock = hm.digest()[:44]

Loop the last 3 lines for each block of keystream you need, XORing the plaintext with the keystream to generate the ciphertext with the same length as the plaintext. Once that is done, prepend (or include in some way) the message counter. Decryption and encryption are the same operation, with the difference being you are using a specific message counter instead of a new one. You can also decode blocks out of order, which can be useful for large messages. Text readable encoding such as Base64 can be applied after encryption.

This example ties the encryption key directly to the password, which I assume is what you are looking for. Other methods use the password to encrypt a random key, then the key encrypts the message. This would allow for the password to be changed without having to reencrypt the entire message. On the other hand it needs a good random number generator.

The 32-bit counters give you a max message size around 176GB, and over 4 billion messages before the nonce counter runs out. This should be more than enough for a single person using a web application. Note that I am not a Python programmer, and the code samples here may not be proper syntax, and are more of a pseudocode. I would still highly recommend a cryptographic library and use AES-CTR instead, but sometimes you have no option.


Is HMAC-DRBG or Hash-DRBG stronger? Out of the two deterministic random bit generators defined in section 10.1 of NIST SP 800-90A (i.e. based on hash functions), which one is cryptographically stronger?

Hash-DRBG (Section 10.1.1)
HMAC-DRBG (Section 10.1.2)

Is there any other criteria to select between these two?

To complement fgrieu's short answer, here is an overview of the two RNG algorithm sets.

Hash-DRBG

The state of Hash-DRBG is composed of a value $V$ (which is updated with each request of new bits), and a same-size constant $C$ (which is only updated on reseeding the generator), and a counter $c$ to track when the next reseeding is needed.

Only $V$ is directly used to generate new bits, by concatenating $H(V), H(V+1), H(V+2), \dots$ until enough bits are generated.

After each generation of new bits, both the constant, the counter and a hashed version of the value are added to the value to generate the new value:

$$V_{\text{new}} = V + H(\text{0x03}||V) + C + c $$

Then $c$ is increased by one.

You can also provide additional input to the generator, in which case another hash call with $V_{\text{new}} = H(\text{0x02}||V||A)$ is done before generating the output.

For initial seeding and reseeding, an adaptable-output-size version $\tilde H$ of $H$ is used (as defined in Section 10.4.1), to generate enough bits for $V$ and $C$.

Hash-DRBG relies on $V$ and $C$ staying secret. For $V$, this is the preimage-resistance of the hash function (as $V$ is hashed to generate the output), while $C$ can be easily derived from two (or three, if the counter value is not known) consecutive values of $V$ (as it is simply added).

From this, the following output can be predicted, until the application adds non-predictable additional data or the state is reseeded.

(Of course, we also need that the output of $H$ is pseudo-random, i.e. has no detectable patterns.)

Initialization: The value $V$ is created by hashing the "seed material", and the constant $C$ then by hashing $V$ (with a prefix byte of $0$) (both producing 440 bits).

HMAC-DRBG

In HMAC-DRBG, the state is composed of a key $K$, a value $V$ and a counter c (to keep track of when a reseed is needed - it is not used for generation itself).

The actual generation of random bits uses

$$ V := HMAC(K, V)$$

in a loop and concatenates these new values of $V$ until enough output is generated.

After this, an update function is called, which changes both key and value by two HMAC calculations:

$$\begin{align*}
   K_{\text{new}} &= HMAC(K_{\text{old}}, V_{\text{old}} || \text{0x00}) \\
   V_{\text{new}} &= HMAC(K_{\text{new}}, V_{\text{old}})
 \end{align*} $$

Update can alternatively also incorporate additional data $A$ provided by the application, using four such calls in total:

$$ \begin{align*}
  K_{\text{tmp}} &= HMAC(K_{\text{old}}, V_{\text{old}} || \text{0x00} || A) \\
  V_{\text{tmp}} &= HMAC(K_{\text{tmp}}, V_{\text{old}}) \\
  K_{\text{new}} &= HMAC(K_{\text{tmp}}, V_{\text{tmp}} || \text{0x01} || A) \\
  V_{\text{new}} &= HMAC(K_{\text{new}}, V_{\text{tmp}}) \end{align*} $$

(If additional input is given to the generate-function, update will be called before and after generating more output.) This will also be used for seeding and reseeding, where the additional data contains entropy input (and maybe any application-specific stuff).

HMAC-DRBG's security depends on the key $K$ staying secret (intermediate values of $V$ are output directly as pseudorandom bits), i.e. on the key-retrieval-resistance of the HMAC.

If value of $K$ is known, all the following ones can be derived, until the application adds non-predictable additional data or a reseeding occurs.

But other than this worst-case break, there might be other weaknesses in the hash function's output which make HMAC's output be non-random (i.e. show patterns). Optimally, we want the HMAC output be a pseudorandom function of the input.

Initialization: The HMAC_DRBG_Instantiate_algorithm function sets $K$ to 0 and $V$ to $0x01010101\dots01$, before calling first the Update function with the seed material as "additional data".

Summary

One can see that HMAC-DRBG shuffles stuff around a bit more than Hash-DRBG ... and HMAC itself even contains two hash invocations.  Thus HMAC-DRBG is certainly slower.

But as any possible weaknesses of HMAC will come from weaknesses of the underlying hash function, HMAC can't be
weaker than the hash ... but it could be stronger (i.e. some weaknesses of a hash function will not transfer to the corresponding HMAC). For now, there is no weakness known in either of both constructions, though.


Affine of Inverse Sboxes "All 8x8 s-boxes created using Galois Field inversion plus an Affine Transform have the same non-linearity, as the Affine Transform does not change the linear or differential properties" is what this answer claims.

Is there a proof of this statement?

I am unable to see how this is true. I tried to calculate the Walsh and autocorrelation spectrum but was unable to see how they are equal.

To be precise, different affine transformations following the Galois field inversion should give the same Walsh spectrum up to a $\pm$ sign, in terms of how many times each value occurs. Since an affine transformation is a linear transformation plus a constant vector addition, this is not surprising.

Don't forget linear cryptanalysis measures distance to the unbiased case (prob. 1/2) so signs of Hadamard coefficients switching between positive and negative is allowed. This is how come we can ignore the sum of the non targeted key bits modulo 2 during Linear cryptanalysis, since all they would do is switch the sign of the relevant coefficient.

Let
$$L_{a,b} := \sum_{x \in V_n} (-1)^{a \cdot x \oplus b \cdot S(x)}$$

where $V_n$ is the n dimensional binary vector space. Let $A x+c$ be an affine map where the linear part $x\mapsto Ax$ is full rank and thus invertible. It is then a simple matter of algebra to prove the result:
$$L_{a,b}' := \sum_{x \in V_n} (-1)^{a \cdot x
\oplus b \cdot (A \cdot S(x)\oplus c)}$$
by a change of basis.

Even better, in "The Design of Rijndael" by Daemen and Rijmen, (See  here, Appendix A.1 onwards, provided for personal research use only) there is a coordinate free approach using trace functions on the finite field to show this.

Similar comments apply for the correlation spectrum.


Is RSA signature as strong as the RSA encryption? Is it proven that breaking RSA signature is as hard as breaking the RSA encryption, considering the same key size?

I know that they both are based on the RSA function, but I believe that, as always with cryptography, the answer can't be that simple.

First, technically, RSA signing and RSA encryption use different exponents: the former uses a private exponent, and the latter uses a public exponent (which is typically smaller).

Second, padding schemes do matter - but I'm assuming in my question that a "good" padding scheme is used - for instance, for signatures it's RSA-PSS or RSASSA-PKCS1-v1_5 (the latter is non provably correct, but it's still widely deployed and not actually cracked yet).

Third, does the answer depend on the allowed usages of the RSA keys in question? I.e. comparing situations: a) having two keys, one restricted to only Digital signature, and another to only Key/Data encipherment, b) having a single key, with both usages allowed.

Any references to books/standards/conference presentations will be appreciated.
Thanks!

Breaking RSAES-OAEP encryption for generic hash functions can't be much easier than computing odd roots modulo a large composite of unknown large prime factorization.  (Likewise RSA-KEM, which is much simpler.)

Forging RSASSA-PSS signatures for generic hash functions can't be much easier than computing odd roots modulo a large composite of unknown large prime factorization.  (Likewise RSA-FDH, which is much simpler.)

(Forging Rabin-Williams signatures—which involves square roots, not odd roots—for generic hash functions is as difficult as factoring a large composite of unknown large prime factorization.)

This is the story for the individual cryptosystems RSAES-OAEP under a key independent of RSASSA-PSS under another key.  The security of a composite cryptosystem (RSAES-OAEP, RSASSA-PSS) under the same key, in which the adversary can witness decryptions and signatures of arbitrary messages, requires its own analysis: security of RSAES-OAEP and RSASSA-PSS individually does not imply security of the composite scheme.

The standard pathological example, in the scheme I like to call do you even RSA, bro‽, is that if I want to decrypt a ciphertext $c \equiv m^e \pmod n$, and if I can ask you to sign the message $c$, then your signature is $s \equiv c^d \equiv m^{ed} \equiv m \pmod n$, so you just unwittingly decrypted $c$ for me.

Are there attacks on (RSAES-OAEP, RSASSA-PSS) under a single key?  Unlikely, but I don't have a handy citation for a reduction of security to the RSA problem.


How is the MD2 hash function S-table constructed from Pi? For fun, I'm learning more about cryptography and hashing. I'm implementing the MD2 hash function following RFC 1319 (http://tools.ietf.org/html/rfc1319). I'll preface by saying I know there are libraries, I know this is an old hash, and I do not intend to use this in anything real-world, so don't anyone freak out.

In learning about S-tables I notice MD2 uses an S-table based on Pi. What I don't understand, is how these numbers relate to Pi. And oddly, I can't find anywhere that describes it. The RFC just says:

  This step uses a 256-byte "random" permutation constructed from the digits of pi.

In the reference code, there is the following comment:

  Permutation of 0..255 constructed from the digits of pi. It gives a "random" nonlinear byte substitution operation.

Looking at the first few bytes:

  41, 46, 67

I cannot see how you get these numbers from Pi. I've tried looking at the binary representation of Pi, and these numbers do not seem to match up with the first bytes of pi.

My usual Googling just leads me back to the RFC or other implementations which seem to copy the above comment exactly. No where can I find where the construction of this table from Pi is explained.

I sent an email to Ron Rivest and got an answer back.

The digits of $\pi$ are used as a sort of random number generator that is used in the Durstenfeld shuffle (see also Knuth vol 3, sec 3.4.2).

Below is some pseudocode adapted from the description and code he sent me.

S = [0, 1, ..., 255]
digits_Pi = [3, 1, 4, 1, 5, 9, ...] # the digits of pi

def rand(n):
  x = next(digits_Pi)
  y = 10

  if n > 10:
    x = x*10 + next(digits_Pi)
    y = 100
  if n > 100:
    x  = x*10 + next(digits_Pi)
    y = 1000

  if x < (n*(y/n)): # division here is integer division
    return x % n
  else:
    # x value is too large, don't use it
    return rand(n)

for i in 2...256: #inclusive
  j = rand(i)
  tmp = S[j]
  S[j] = S[i-1]
  S[i-1] = tmp

The next function just steps through the digits of pi. You'll notice that rand does not use some of it's possible outputs. Dr. Rivest says that using these values would not give a uniform distribution as they are too large.


How to generate a 16 X 8 perfectly nonlinear S-box I want to generate a 16,8 perfectly nonlinear S-box for an encryption algorithm I am working on. I don't have a background in math, and I'm an undergrad, so a lot of the math involved is very confusing.

I want the perfectly nonlinear S-box to have 16 bits of input and 8 bits of output.

I have been reading Kaisa Nyberg's 1991 paper Perfect nonlinear S-boxes, and I am having trouble understanding the method described.

In Section 4, A Construction based on Maiorana-McFarland method, the implementation is described as:

Take n bits of input (where n >= 2m)
Split the n bits into two parts (x1 and x2)
Obtain the first digit of the output (of length m) by doing x1 • x2
And the second digit of the output by shifting a n/2 size LFSR (with
a primitive feedback polynomial) once, and the calculating • between
LFSR's content and x2.

I am having trouble understanding how the two digits are to be used since both would be of length m..

concatenating them would make the output size 2m

Which is not right. The problems I face are:

Should there be a • operation between the two digits to produce an m-bit output? In a construction based on Maiorana-McFarland method?
Which (per my understanding modular) operation would be the optimal?
Is there anything else I should be considering in addition to
perfect nonlinearity?

$A:\mathbb{F}_2^m\rightarrow \mathbb{F}_2^m$ is the state space map induced by the primitive length $m$ LFSR.

Thus it maps the zero vector of length $m$ to itself and in general the LFSR state $(a_0,a_1, \ldots,a_{m-1})$ to $(a_1,\ldots,a_m)$.
$A^i$ is just $A$ iterated $i$ times (shift LFSR $i$ times).

Then, the APN map $z=(z_1,\ldots,z_n)=F(x_1,x_2)$ where $x_1,x_2,z,\in \mathbb{F}_2^m$ is given by
$$
z_i=A^{i-1}(x_1)\cdot x_2,\quad i=1,\ldots,m
$$
where $z_i$ are individual bits.


Why computation of $u*v^3*(u*v^7)^{(p-5)/8}$ is suggested instead of $(u/v)^{(p+3)/8}$ Working with Curve25519 I've faced with suggested form of computation square root candidate as: $uv^3(uv^7)^{\frac{p-5}{8}}$ instead of $\left(\frac{u}{v}\right)^{\frac{p+3}{8}}$. Why it is so? Or why is it less expensive?

Edwards-Curve Digital Signature Algorithm (EdDSA) https://tools.ietf.org/html/rfc8032#section-5.1.3
High-speed high-security signatures https://eprint.iacr.org/2011/368.pdf

Note that
$$\frac{7(p-5)}8+3=\frac{7p-11}8\equiv \frac{7p-11}8-p-1\equiv -\frac{(p+3)}8\pmod{p-1}.$$
Similarly
$$\frac{p-5}8+1=\frac{p+3}8$$
And so $v^3(v^7)^{\frac{p-5}8}\equiv v^{-\frac{(p+3)}8}\pmod p$.
Likewise $u(u)^{\frac{p-5}8}\equiv u^{\frac{p+3}8}$ as required.
The reason is to save a modular division which is quite a pricey operation.


Kryptos : K1. What is the origin of the "palimpsest" keyword? I'm studying the Kryptos sculpture with its cryptographic puzzles K1 to K4.

I understand that the keyword "palimpsest" was reverse-engineered using the tableau (and brute-force computer processing), but Sanborn always said that all sections could be solved using pencil and paper.

There are theories about the Morse, but I haven't come across a good explanation of how to tease "palimpsest" out of it.

I've been frustrated trying to find this in the Kryptos Yahoo group.

I'm not concerned that it has any "meaning" just whether or not there is any other way to derive the keyword other than brute-force, from e.g. the Morse code.

It was never determined how to derive the keyword PALIMPSEST from the sculpture or its text. It was, as you stated, found by brute-force hill-climbing algorithms.

One theory is that crib-dragging the morse phrase SHADOW FORCES reveals IMPS at SHAD, and working form there retrieving the entire keyword, but I find this far-fetched and implausible.

The keyword for K2 can be found by crib dragging morse phrases, but for K1 it´s still a mystery.


Is prime regeneration necessary for every new session using a Diffie-Hellman key exchange? As I understand it, bruteforcing a Diffie-Hellman generated secret key takes $P-1$ attempts to crack the shared secret, where $P$ is a very large prime used for modulus. If your $P$ is quite large, which according to the wikipedia page ought to be about 300 digits, then theoretically your encrypted data is secure.

Now, let's assume user A and user B generate a new personal secret for every session they hold. If a log of all of those sessions was stored, with a total of $N$ sessions, then in theory, given that you do not change $P$ or $G$ (where $G$ is defined as the primitive root mod $P$), the number of attempts it takes to crack any arbitrary session's generated secret should be $\frac{P-1}{N}$.

My question is, is that a giant security risk if $P$ is very large and kept static across many sessions? How often should it be updated, if ever? I am aware it increases the probability of a bruteforce attack succeeding, but is the increase something I should consider trivial?

Theoretically if someone is performing a bruteforce on this scheme, if the attack is random then am I correct in assuming that updating my prime would do me no good?

How long are parameters used for?

Usually $g$ and $p$ are kept static for a very long time indeed. In fact, the values to use are actually written in to standards. See here for an example. Those were values standardised ten years ago.

So the answer is basically decades.

The impossibility of brute force

Let's suppose that I as an attacker decide I'm going to compute $g^{x} \mod p$. I start at 1 and work up to $p-1$ and start logging them in a table.

There are two problems here. One is there is not enough matter in the universe to store the number of items in that table. The second is that there is not enough time between now and the heat death of the universe to generate it either.

This is a simple consequence of the size of the primes involved.

What about collisions?

Suppose you have access to PRISM and you can see every Diffe-Helman key exchange in the world. Suppose I log every exchanged value in the hope that one specific exchange is repeated.

You're going to need approximately the square root of $p$ invocations to get a probability of approximately 50% that the item already exits in the list. The square root of $p$ is still so big that there simply isn't enough time, energy or matter in the universe to make that attack work.

Even with that table, you still need both exchanged DH parameters to be in there, along with any ciphertext from both sessions, if you wish to have a shot at recovering the plain-text.

Worse, this doesn't even mention that a collision might not even help you. If the cipher used after the exchange uses an additional initialization vector or nonce input (and this one is not simply derived from the exchanged secret, i.e. likely different), then the fact that two sessions shared the same key doesn't help you.

It's important to note here that unlike the attack above where you knew each $x$ for every $g^{x}$, in this attack you still don't know the $x$. All you have is $g^x$. I sensed a bit of confusion on this point in your question.

How are these values actually attacked?

There are more efficient ways to solve the discrete logarithm problem. Wikipedia gives a nice overview of the problem and some algorithms that solve it.

The parameters we choose in cryptography are large enough so that solving the problem is infeasible in any reasonable amount of time.


Requirement for the exponent generation during DH protocol The setting is classic DH protocol. Alice computes $A = g^a \bmod p$. Alice then sends $A$ to Bob. Then Bob will send $B = g^b \bmod p$ to Alice.

Are there any requirements for the values $a$ and $b$ besides they should be greater than $1$?

Since $g$, $A=g^a$ and $B=g^b$ are made public, everyone could repeat the same operation and brute force DH with small exponents.

There are already many responses:
link to security.stackexchange.com
link to crypto.stackexchange.com

Summary: considering a security level of $n$, it is advised to use exponents of at least $2n$ bits.


About replay attack definition I have read .
Replay attack is a kind of attack in that the attacker eavesdrops valid message and sends that message repeatedly to make requestor in busy mode. It can be prevented by adding timestamp to the broadcasted message.

Does that definition true? Some says that the definition seems to be incorrect.

Replay attack is a form of network attack in which the attacker records messages and replays them later. Generally attacker uses them to get authenticated during one way or two way authentication.
Random nonces are used to prevent them instead of timestamp as the latter requires clock synchronization which is tough in practice.


Can one claim that AES has perfect secrecy for a key size and message size of 128 bits? While looking at this question I discovered the following here (question 5), and wanted to ask it as a separate question.

  Alice knows that she will want to send a single 128-bit message to Bob
   at some point in the future. To prepare, Alice and Bob first select a
   128-bit key k ∈ {0, 1}128 uniformly at random.
      When the time comes to
   send a message x ∈ {0, 1}128 to Bob, Alice considers two ways of
   doing so. She can use the key as a one time pad, sending Bob k ⊕ x.
   Alternatively, she can use AES to encrypt x. Recall that AES is a
   128-bit block cipher which can use a 128-bit key, so in this case she
   would encrypt x as a single block and send Bob AESk(x).
      Assume Eve
   will see either k ⊕ x or AESk(x), that Eve knows an initial portion of
   x (a standard header), and that she wishes to recover the remaining
   portion of x. If Eve is an all powerful adversary and has time to try
   out every possible key k ∈ {0, 1}128, which scheme would be more
   secure?

And the answer in the document is:

  They would be equally secure. Either way, Eve would not be able to
  learn the unknown portion of x.
  Even after trying every possible key
  (including the actual one), Eve will have no way of recognizing the correct
  plaintext or even narrowing down the possibilities in any way.
      Why is this? Well, since AES is a distinct permutation on {0, 1}128 under each possible key, and the key was selected uniformly at random, given any plaintext, each possible ciphertext is equally likely. So when AES is used for a single block with a random key of the same length, the effect is exactly the same as using a one time pad: the ciphertext reveals no information about the plaintext.

The question mentions a standard header, so I think its fair to assume we know all the plaintext except the very last bit. So my question, is this answer correct?

The answer is incorrect, but it's a bit more subtle than it seems. To make this clear, note that encrypting $x$ by computing $c=\operatorname{AES}_{0}(k) \oplus x$ would be perfectly secure (here the key is fixed to 0, but any fixed key value would give the same effect). This is due to the fact that AES is a permutation and so when $k$ is uniformly distributed, then $\operatorname{AES}_0(k)$ is a uniformly distributed value. More formally, for every $c$ and every $x$ there exists a $k$ such that $c=\operatorname{AES}_0(k)\oplus x$. In order to find this, compute $k = \operatorname{AES}_0^{-1}(c \oplus x)$.

Now, when encrypting $\operatorname{AES}_k(x)$ the same argument fails. This is because for $c=\operatorname{AES}_k(x)$ there is no guarantee that decrypting $c$ under all possible keys gives all possible plaintexts. Thus, it is possible that there is only one $k$ (or a few $k$'s) that give you the known initial portion.


Diffie Hellman groups I saw that non-negative integers with the addition operation cannot be the Diffie Hellman group. I'm having trouble understanding why it cannot be the DHKE group.
To be DHKE group, there are five properties to be held,

The operator is closed
associativity
identity element exists
inverse element exists
commutativity

I tried with the group of {0,1,2,3,4,5,6} and p=7, and all the above properties were held. I couldn't find any appropriate example to show the above properties are not held. What other examples can show that the non-negative integers with addition operator is not one of Diffie Hellman key groups?

To be DHKE group, there are five properties to be held,

This is true; however, to be a secure DHKE group, there has to be an additional property:

The "discrete log problem" needs to be hard; that is, given a public value $xG$ (where $G$ is the public group identifier, $x$ is your private value, and $xG$ is the generator acted upon itself $x$ times), it is hard to recover $x$.

In the addition case, we have $xG = \underbrace{G + G + … + G}_{x \text{ times}} = x \times G$., where $\times$ is integer multiplication.
If we know $x \times G$ and we know $G$, then it is easy to recover $x$ by doing a simple division (modular division if we're doing the addition modulo $p$, which isn't much harder), and hence the Diffie-Hellman would be trivially insecure.
Actually, just having a secure discrete log problem is not sufficient; the "Diffie-Hellman" problem also needs to be hard, that is, given $G$, $xG$ and $yG$, it should be hard to recover $xyG$ (this is known as the computational Diffie Hellman problem), or given $G$, $xG$, $yG$, $zG$, it should be hard to determine whether $xy = z$ (this is known as the decisional Diffie Hellman problem).  Either of these problems may be easier than the "discrete log problem" for any group; however, for addition, none of these problems are hard.


Comparison: complexity measures vs. security Assume that you want to compare several cryptographic primitives (say, encryption schemes), and choose one. You need to consider several complexity measures, such as the key length, encryption time, decryption time, etc. In order for the comparison to be fair, all primitives in question must provide the same level of security.

As an example, let us consider RSA, ECC, and NTRU. Assume that we want the cryptosystem to be secure against a passive adversary, whose computational power is limited to at most $2^{100}$ operations. By "passive adversary", we mean that the adversary is limited to chosen-plaintext attacks (since we are comparing public-key encryption schemes). Now, we want to know the key length to be chosen for each scheme.

To answer this question, we consider the complexity of the most efficient attacks against RSA, ECC, and NTRU, which in turn requires a great knowledge of the literature.

  Is there any resource/survey (website, paper, tool, etc.) which helps in such comparisons?

Note: The website keylength.com, while being a helpful tool in its own right, is not an answer to this question. The reason is that keylength.com merely recommends a minimum key length to be used in different scenarios (say symmetric or asymmetric encryption), but leaves out most of the concrete schemes (say, NTRU, twofish, serpent, etc.)

Not sure what you are trying to do but are you not approaching it the wrong way?

NIST already recommends algoorithms/ciphers for use in their environments. This means they have vetted these and are deemed secure. Now you want performance as well. So use openssl and see which of the algorithms are of acceptable performance to you. Like you said choose key lengths that provide the same level security when comparing different algorithms. That way your performance numbers will be comparable.

Also I wouldn't try to go beyond any algorithms NIST recommends. For example AES is good for any application. There is no reason to use or try twofish. There are enough ways to shoot yourself in the foot just by using AES itself. Stick to one and that way even if you are creating some recommendations for your users/employees its less complicated.

Hope that helps.


Is it possible to attack a one-time pad encrypting only slightly more than its length? This question might be uncannily similiar to this one posted over 6 years ago, but the structure is completely different.
It's written nearly everywhere that OTPs are incapable of sustaining more than their length of data - but I have yet to find an answer besides "reusing them makes cryptanalysis possible" in several different ways.
Suppose Alice and Bob wanted to maintain a OTP-based connection, but are unable to physically exchange entropy besides an initial file. Luckily, Alice has her own entropy source. What Alice and Bob could do is use the initial OTP to send two bits of data at the cost of one bit of entropy. The order of entropy and starting offset could be negotiated beforehand using typical OTP, but let's assume for simplicity's sake that you're sending 2 payload bits in series - and XORing them with an entropy "key" bit, and that the offset Alice picks is also taken from her entropy source.
A meddling Eve, if she knows how this protocol works, could only tell one of two metadata possibilities as a fact:

that any two linked data bits are the same (ambiguous between 00 and 11)
that any two linked data bits are different (01 and 10)

However, Eve should be unable to determine which of the 2 ambiguous combinations is the correct combination... right? After all, Eve could pick up on patterns of the metadata, but not before Alice and Bob notice.
The data transferred this way (which could be even more entropy - Eve doesn't know which part of the data is which!) would be protected by the initial challenge, and by the entropy of the initial OTP. Knowing all this, we can finally rephrase the question:
Is it possible to perform a cryptanalysis on a hybrid OTP described above, and if it is, what would be an efficient attack vector?
Would it be instead preferable to perform an RSA/Diffie-Hellman key exchange over the initial OTP?

This does not look like OTP, but like PSK with conflicting extra steps.

Alice has her own entropy source.

And by definition, Bob does not have this same entropy source, so what Alice have is a random number generator. And since she cannot tell Bob if the bit is 0 or 1, Bob have no way to decrypt anything. And if she can tell, Eve can know too. And if Eve cannot know the content of the message, why don't use this secure channel to send the message instead of entropy?

A meddling Eve, if she knows how this protocol works

Eve always knows the protocol, the algorithm, all obfuscations, she only needs the key. That's the Kerckhoffs's principle.

The data transferred this way (which could be even more entropy - Eve doesn't know which part of the data is which!) would be protected by the initial challenge, and by the entropy of the initial OTP.

Likewise Bob cannot decrypt anything because he does not have access to Alice's entropy source.

Would it be instead preferable to perform an RSA/Diffie-Hellman key exchange over the initial OTP?

Absolutely! Diffie-Hellman is used by every single bank out there for a reason. OTP can be unbreakable if done right, but is so cumbersome that isn't practical and that's why is rarely used in the real world. IfDiffie-Hellman is good enough to banks protect themselves, is good enough for you, Bob, Alice, and for me.


Zero-knowledge proof or zero-knowledge proof of knowledge? It has always been a question surrounding in my mind whether a zero-knowledge proof ($\mathrm{ZKP}$) is the same as zero-knowledge proof of knowledge ($\mathrm{ZKPoK}$), but it was not since today that these concepts are creating problems in my understanding of cryptography.
So, what is the real difference (if there is one) between $\mathrm{ZKP}$ and a $\mathrm{ZKPoK}$? Is people using both concepts indistinguishable?
Here is an answer difference that answers my question partially, but I am lookin forward a direct answer to mine.

Since you reference my answer to a very similar question, I'm assuming you already read it, so you know what the difference between ZK and ZKPoK is at a technical level. To recall briefly, though: a standard ZK proves the existence of a witness, while ZKPoK proves that the prover actually knows the witness, which is formalized by saying that there exists an efficient extractor which can recover the witness from the code of the prover. Actually, a better full name for "zero-knowledge proof" would be "zero-knowledge proof of membership" (it proves that a word $x$ belongs to a language $L$, which is equivalent to saying that there exists a witness for the statement "$x$ belongs to $L$").
To answer your main question:

So, what is the real difference (if there is one) between ZKP and a ZKPoK? Is people using both concepts indistinguishable?

There is a clear difference at the technical level, and this translates into a clear difference in the applications. First, zero-knowledge proofs are used as components in larger constructions of cryptographic objects (there are hundreds of example, but just to name a few: verifiable encryption, maliciously secure computation, anonymous credentials, etc). In many of those applications of ZK proofs, the proof of knowledge property is actually crucial. This is for example the case in verifiable encryption and anonymous credentials - but not in maliciously secure computation, where standard zero-knowledge suffice.
To give you an intuition of when the difference matters, here is a rule of thumb:

If you just want to prove that "some property is verified" (for example: "the ciphertext you sent me contains a bit"), zero-knowledge proofs (of membership) suffice.
If you need to authenticate the prover in any way, then you need a zero-knowledge proof of knowledge.

To put it even more directly: a ZK proofs only says something about the statement ("the statement is true"). A ZK proof of knowledge is much stronger since it also says something about the prover himself: "the statement is true, and the prover knows a witness for it". This is absolutely crucial in any "authenticated" cryptographic protocol: you can say that an authorized user (for whatever definition of "authorized" in your application) is a user that knows a witness; then, sending a ZKPoK can be seen as authenticating the user, without revealing is authentication credential (which prevents stealing his identity).


Cryptographic equivalent of family coat of arms As a layman when it comes to cryptography, I have recently been asking myself if there was a cryptographic equivalent of a family code of arms. I'm thinking of something asymmetric, that is future proof enough to hand down to another generation and that can be used to maybe access resources. If possible it should also have a graphical representation, similar to a QR code.

Maybe I am totally tapping in the dark, though. If that's the case, please elaborate on why this is a stupid idea.

EDIT: From suggestions, I have come to realize, that I indeed do not know what I am asking about. So here is a clarification:
I want the abstract "coat of arms" to be known "publicly". The authority on that would come from documents and physical proof (signatures, pictures of it being shown by members etc.). The goal would be to make it public enough, to give people a hard time convincing someone that theirs is the real deal, when it isn't. As per suggestion from @MaartenBodewes, using a certificate seems like a great idea to reinforce that by adding a central authority.
Now here is the difficult part: The abstract "coat of arms" could in my eyes be seen as an abstract lock. One that has one or a finite (reasonable) number of keys. Would it be possible to have something like that, so that one could prove beyond doubt that one had a key to that abstract lock, without exposing the key?
So what I'm getting at is: There are two authenticity questions here. One is of the authenticity of the abstract lock and one is of the authenticity of the party trying to prove their membership conncted to that lock. The former can come from CA but the latter can't.

I apologize for the uneducated terminology. Also, I hope this is actually comprehensible. :)

You can put almost any information in an X.509 certificate, and then pass the private key for the matching certificate along. People can of course claim that the certificate is theirs, but when holding the private key, you can prove it belongs to you.

Of course, you might need a central authority for the certificate to be trusted, but you can send a certificate request to many CA's. Of course, if there is sufficiently weird info in there to be notified you may need to explain the applicability (and most likely, pay up, but I guess that comes with the domain). If you start to dislike the CA you can always switch to another one.

Probably easiest is to include an URL to a website with e.g. an actual coat of arms.

Digital information is usually not used to show off. If you require something more physical then you could get e.g. a gold leafed ePassport. For that you would probably need a high up person in the government (and be a complete and utter - well you can fill that one in yourself).


Is there any quantum resistant pen-and-paper or mind cipher? I know about VIC and Solitare but as I understand they are not quantum resistant ciphers. Is there any quantum resistant pen-and-paper or mind cipher?

You are not likely to find such a construction. One problem you will run in to is that of size: In order to be secure against brute force search with Grover's algorithm, you will need to use at least 200 bits of secret material. And that assumes you are content with a security level of $2^{100}$.

This is equal to 25 random bytes or a 60 digit long decimal number that you will have to remember and do mental math with. In addition, you will also need to keep your message and any intermediate state in mind as well.

Assuming that your ciphertexts will be on paper or some other physical medium (because you wouldn't go through the trouble to compute AES by hand to send the result via e-mail), a quantum computer cracking your ciphertext is probably the least realistic of your concerns - if your adversary already has your ciphertext, they probably already have the messages sender and/or recipient as well, which means they have far less expensive ways of obtaining the message.


Algorithm for factoring knowing RSA private key According to this and this paper from Alexander May is possible to factor given the knowledge of the RSA private key.
This is possible via Coppersmith and LLL reduction.
Now I am trying to implement the code using the reduction in 2 (I prefer this to 1 given the fact []1] uses bivariate
integer polynomials).

Now I struggle to understand the parameter of the reduction in section 4.6 of 2. In particular it refers to and M to be applied to Theorem 1.
Giving a look to Theorem 1 though it doesn't mention M.
The problem is that M is the only place where d (the secret exponent d is mentioned) hence why I am lost....

May and Coron's result is a deterministic reduction from knowing a multiple of $\varphi(n)$, in this case $de-1$, to the factorization of $n$. This method involves lattice reduction and Coppersmith's algorithm.

But there is a much simpler probabilistic method to factor $n$ discovered by Miller, of the famed Miller-Rabin primality test. Suppose you are able to find a nontrivial square root of $1$, i.e.,
$$
x^2 \equiv 1 \pmod{n}, \quad x \neq \pm 1\,.
$$
Then $x^2 - 1 \equiv (x+1)(x-1) \pmod{n}$, and we find a factor by computing $\gcd(x \pm 1, n).$ But how do we find such a root? By exploiting the relation
$$
a^{\varphi(n)} \equiv 1 \pmod{n}\,.
$$
Let $t = \varphi(n) / \gcd\left(\varphi(n), 2^{\log_2(n)}\right)$ be $\varphi(n)$ with every power of 2 removed from it.
If we knew $\varphi(n)$ exactly, all we had to do was compute $a^{t} \bmod n$ for a random base $a$, and repeatedly square until we obtained a $1$—that value would be our $x$ as above. This will yield a factor depending on the order of $a$ modulo $p-1$ and $q-1$. This process naturally extends to any multiple of $\varphi(n)$, and in practice only a couple of bases are necessary to factor $n$.

Here's some Sage code that implements this:

def factor_from_d(n, d, e):
  kphi = d*e - 1
  # remove powers of 2 from phi multiple
  kphi = kphi // gcd(kphi, 2^int(log(n, 2)))
  while True:
    # random base
    b = randint(0, n)
    x = power_mod(b, kphi, n)
    # try to find a nontrivial square root of 1
    while x != 1 and x != n - 1:
      # found one!
      # x^2 = 1 (mod n)
      # x^2 - 1 = (x + 1)*(x - 1) (mod n)
      if x^2 % n == 1:
        return gcd(n, x + 1), gcd(n, x - 1)
      x = x^2 % n

p = random_prime(2^512)
q = random_prime(2^512)
n = p*q
e = 2^16 + 1
d = inverse_mod(e, (p-1)*(q-1))
factor_from_d(n, d, e)

Coming back to May and Coron, their algorithm is conceptually simple, but more complex to implement from scratch. Here we want to find a small root of
$$
f(x) = n - x \pmod{de - 1}\,,
$$
which is guaranteed to exist because $n$ and $\varphi(n)$ are relatively close together. This root is precisely $p+q-1 = pq - (p-1)(q-1)$. Having $p+q$, we can solve the polynomial $x^2 - (p+q)x + n$, which has $p$ and $q$ as its roots.

Using Sage's small_roots function, we can do this easily:

p = random_prime(2^512)
q = random_prime(2^512)
n = p*q
e = 2^16 + 1
d = inverse_mod(e, (p-1)*(q-1))

P.<X> = Zmod(d*e-1)[]
f = X - n
pq = ZZ(f.small_roots(X=2^513, beta=0.9, epsilon=0.1)[0] + 1)
disc = pq^2 - 4*n
(pq + isqrt(disc))/2, (pq - isqrt(disc))/2


Why is it inadvisable to increase the number of rounds or using a larger block size to a published(standardized) block cipher such as AES? I wanted to know how does the increase the block size or rounds in AES is not a good idea

Just in general messing with well studied cryptographic standards is inadvisable. Especially if there is no clear benefit.

Adding rounds to AES is fairly safe, before it became AES the number of rounds in Rijndael was discussed. You need to make sure you continue to use a reasonable key schedule.
This may have even some value, as we have seen attacks on reduced round AES making the safety margin smaller than originally believed.

Changing block size is far from trivial. It is not all obvious how to change AES block size while preserving it's desired properties. This is far more likely to end up in a weak slow cipher.


Is there any benefit to verifying PKCS#7 padding when using AES CBC and HMAC? As I'm using HMAC to ensure integrity and authenticity of the ciphertext, is there any additional security benefit to verifying PKCS#7 padding when decrypting using AES CBC?

A previous question asked Why verify Padding at all? Part of the accepted answer was:

  In general, use a cryptographic MAC to protect your ciphertext, and verify it first. Emit those errors. Then padding errors should not occur at all.

But I note the qualifier "in general" and I also know a number of cryptography libraries do validate the padding.

In general, use a cryptographic MAC to protect your ciphertext, and verify it first. Emit those errors. Then padding errors should not occur at all.

The "in general" seems to have been used to show that commonly is performed or should be performed. I don't think it had anything to do with the security of the scheme itself.

PKCS#7 compatible padding can range from 1 to 16 bytes for block ciphers such as AES. If your plaintext always happens to be $n * 16 + 15$ bytes in size then your padding would consist of a single byte. A single byte is never enough to guarantee integrity of the plaintext.

Padding isn't a checksum. It doesn't say anything about the value of the plaintext. It tells you only something about the size of the plaintext.

Even if you would be able to use padding as an integrity check then you shouldn't use it for transport protocol security. Padding checks allow padding oracle attacks to be performed. For instance OpenSSL uses sign-then-encrypt and requires special care to avoid padding oracle attacks.

Note that modern protocols often allow modes such as CTR or authenticated ciphers. Almost all authenticated ciphers based on block ciphers are based on CTR (i.e. CCM, GCM and EAX mode are all based on CTR mode to provide confidentiality). CTR doesn't use padding at all. So you can often avoid the use of padding pretty entirely.

This also shows that padding mode is not a requirement to validate the correctness of the plaintext. If it was, all current authenticated ciphers would fail.

Padding should not be used for verifying correctness period. It should just be used for determining the length of the plaintext.

[CHANGED] After verifying the integrity you should check all the padding bytes, if just to verify the correctness of the implementation. Another reason to check the other bytes is to avoid worrying about subliminal (covert) channels. A slight disadvantage would be that you couldn't use the same unpadding code to handle PKCS#7 and the withdrawn ISO 10126 padding (and you should make sure you don't break anything if you change existing code with that in mind).

It does make sense to check if the value isn't out of range, i.e. between 1 and the block size. You don't want to handle issues with index-out-of-range or partial information in the code surrounding the cryptographic routine.

An even better solution would be to use a mode that doesn't require padding at all. A good candidate would be the aforementioned CTR mode of operation which turns AES into a stream cipher or one of the authenticated (AEAD) ciphers.


How to generate a unique numerical value for an alpha-numeric string? I need to create a unique numerical value for every alpha-numeric string input. Size of output numerical value can be of any size like 32, 64 128 bits. The input string will always be a mongoID type if that helps.
Is there any hashing algorithm available for such purpose.

If you don't limit the length, there are infinitely many alphanumeric strings. The number of even 128-bit numbers is finite, so there's no way to assign a unique 128-bit number to every possible string.

That said, if you don't mind a very small risk of collisions, a cryptographic hash function like SHA-2 or SHA-3 truncated to your desired output length should be fine, as long as that output length is sufficiently large.  With e.g. a 128-bit output size, the average number of strings you'd need to hash before observing even a single collision is around $2^{64}$, probably far more than your software will ever see.  If you're really feeling paranoid, bump the length up to 256 bits.

(A point I should probably clarify is that hash functions like SHA-2 and SHA-3 output a fixed-length block of bits.  While this output is often represented in hexadecimal for convenience, it's really just a large binary number and could just as well be displayed in any other base, e.g. in the plain old decimal system we humans like to use.)


What's the least computationally expensive way to verify a message is from who they say they are? We're building an ingame GPS system where only 5 lines of code are executed a second. We're starting to face problems with people spoofing the satellites we use to triangulate. Is it feasible to filter out these messages with such low computing power, and if so, how?

The first step in verifying a signature is to hash the message, which takes a few thousand x86 instructions. Your language doesn't seem to support the logical operations that are common in modern hash functions - implementing those with arithmetic operations will cost you some overhead. So you're talking about hours before you even get to the public key portion of the signature. And you can't use a weak hash function, because your attackers aren't limited to such an under-powered platform to produce their forgeries.
I question if in-game cryptography is the best solution here. Since this is all in a managed environment, it seems like you could simply disallow spoofing of the sender property of these messages.


What are the security effects of reusing a public RSA key to encrypt large data by blocks? I'm trying to figure out a way to do public key encryption on a very large piece of data.

For this, I of course want one side to do the encrypting but is unable to decrypt the data, and the other side to be able to decrypt data.

But for RSA encryption, there's a limit to the reasonable size-performance on how big it can encrypt.

I haven't really figured out a good solution to this problem, but the simplest one that comes to mind is to just reuse the public key to encrypt the data in blocks. Of course, this would create some sort of security problems, but as of right now I still don't exactly know what kind of security problems it would cause.

Could someone explain to me what problems this simple method would cause and perhaps also tell me of a way to achieve my goal of being able to do public key encryption on a large piece of data?

I assume that by

  I want one side to do the encrypting but is unable to decrypt the data

you meant a general "encrypting only" party, since if you are talking about a specific piece of data, it does not make sense to disallow the encrypting party from decrypting that data since that party had the data already in the clear.

If that is the case, then your goal might be achieved by first encrypting the data with a symmetric algorithm like AES, which can do big data rather efficiently, and then encrypt the symmetric key/PW with the RSA algorithm. That way, only the other party, who has the private key for the RSA algorithm, can decrypt the RSA-protected symmetric key and then proceed to decrypt the big data.


Encrypt large data with RSA through blocks in java I'm working on a communication protocol where a client sends encrypted data to a server. What happens is that in some point, the client creates a symmetric key used to create data digests through the HMACSHA256 algorithm. Then, the idea is that data is sent to the server along with its digest, so the server can calculate the digest on its own and compare it to the digest sent to check data integrity.

For this, the symmetric key created by the client has to be sent to the server in a secure way, for which the key is RSA encrypted with the public key of the server but additionally, this encrypted message has to be encrypted with the private key of the client. I know that this second encryption has no sense since encrypting data with the private key doesn't assure data confidentiality, but the protocol states that I perform this action just for academic purposes.

The RSA keys are 1024 bits long so I can't encrypt data larger than 117 bytes and the RSA encryption produces 128 bytes long messages, so the question is, if after the first encryption (encrypting the symmetric key with the server's public key with RSA) I get a 128 bytes long message, how can I use RSA to encrypt this output with the client's private key?

The system is probably meant to effectively use an "RSA signature" on top of RSA encryption. If you used raw RSA it could "work", but only if the client's modulus is larger than the server's – or you get lucky and the encrypted key is small enough. Since you are using a library that handles padding for you, it expects a small enough input that it can pad it to size for encryption.

If you can, you could instead use an actual RSA signature algorithm in the second step. This would let the server to verify who the encrypted key is from.

However, if the protocol is something you must use, you should double check that you have understood it correctly. As you have stated it, it seems broken.


Multiple encryption using the same key I am a newbie to this area. I have a program that uses a custom algorithm to encrypt a message. I can encrypt it as many times as I want, but using the same key. I have couple of questions so that I can improve my algorithm.

My program support multiple passes. How many iterations of these passes my program should do? Is there any ideal number in the crypto world? I have read a little about three pass protocol. Does that apply in this case?
Any issues or trade-offs can you think of with this type of approach?

-Alex

I have a program that uses a custom algorithm to encrypt a message

This algorithm is called a cipher. There are plenty well known ciphers that are considered secure. If you have a "custom cipher" then you're either using something of your own design. Using proprietary schemes is not recommended except for learning purposes.

  My program support multiple passes. How many iterations of these passes my program should do? Is there any ideal number in the crypto world? I have read a little about three pass protocol. Does that apply in this case?

Any modern cipher should be secure with one pass.

Most block ciphers already contain a high amount of rounds internally. If you use the same key you're basically just multiplying that amount. If a break is found for all rounds of the cipher then it probably breaks multiple passes as well.

If you want to consider choosing a number of rounds for your cipher then you need a key schedule and a way to connect the inner functions that use the sub-keys. Cipher design is a large topic of which entire books are written (such as "The Design of Rijndael", the cipher that became AES).

If the key needs to be used multiple times - in different ways - then the key can be split into sub-keys using a *key-schedule. The key schedule is internal to a cipher.

The three pass protocol doesn't seem to have anything to do with message encryption directly.

  Any issues or trade-offs can you think of with this type of approach?

Once you have a secure cipher then you can focus on the protocol and system rather than the cipher. There are plenty secure ciphers - such as AES / GCM for symmetric encryption or RSA in OAEP mode for public key encryption. The trick is to apply them well.

Note that stream ciphers or block ciphers in streaming mode may produce a key stream and XOR that with the plaintext. If you would apply those ciphers multiple times using the same key and IV then you would either completely negate encryption an even number of encryption attempts or only apply it once for an odd number of encryption attempts.

Check out how a one-time-pad works and try to apply the encryption twice to understand what I mean.

This also shows that we cannot advise how to construct multiple rounds within your cipher without understanding the design. For all we know, we could be destroying security rather than improving it.


Is there a signature scheme for the Cramer-Shoup cryptosystem? I have a project that I have to use cryptosystem and signature scheme for it.

I've read about Cramer-Shoup cryptosystem and I want to use it since it is more secure the ElGamal cryptosystem, but, I need a signature scheme based on it which I did not find.  Is there such a signature scheme?

If it does not exist I thought of two solutions:

I can use DSA for it but since there is one generator $g$ in DSA and two generators $g_1$,$g_2$ in Cramer-Shoup cryptosystem. So I think I may not be able to use it.
I can generate a separate DH key and use it as a signature public key for the user. Then I could use this key for DSA. But I am not sure if this is considered secure.

Are these options valid?

It is very bad practice to use the same private key for two different schemes. In some cases this is secure but you need to explicitly prove it. One example of this can be seen here: http://www.pinkas.net/PAPERS/combined.ps.

My suggestion is to take the Cramer-Shoup group and to define a separate key pair for DSA or Schnorr signatures. You can use the generator g_1 and this will be fine (the group can be the same; it's just the key that has to be different).


Complete Attack on RLWE Key Exchange with reused keys, without signal leakage I am studying a research paper "Complete Attack on RLWE Key Exchange with reused keys, without signal leakage" . On page number 21 to 28, there is toy example explaining the scheme.

I am unable to get the desired value of $ \mathcal B$ as described in column 3 of table 1 on page number 22. My calculation is as follows:

$s_B=(2,3,0,0,-5,2,3,1), \qquad e_B=(0,0,0,0,0,0,0,1)$

$e_B \cdot s_B=(x^7)\cdot(2+3x-5x^4+2x^5+3x^6+x^7)$

$e_B \cdot s_B=-3+5x^3-2x^4-3x^5-x^6+2x^7$

So, coefficient of $k_B[n-1]=k_B[7]=2 \cdot e_B \cdot s_B=2 \cdot 2=4$.

Now, calculating $sk_B[n-1]=sk_B[7]=\mathsf{Mod}_2(k_B[n-1],w_B[n-1])$

$=\mathsf{Mod}_2(4,1)= \left( 4+1 \cdot \dfrac{257-1}{2}  \mod  257 \right) \mod  2=\left(4+128 \mod \ 257 \right) \mod  2=0$

Thus, $sk_A=sk_B$ and value of oracle $\mathcal B$ must be $1$ (as keys get matched) but it is given $0$ (in column 3 of table 1 on page number 22).

There is a condition that is not considered, that is, the value after modulo 257 should be in $\mathbb Z_q$.
When $q = 257,    \mathbb Z_q = \{ -128, ... , 128 \}$, so,  $(4+128)\mod 257$ should be $-125$ rather than $132$ .
And $-125 \mod 2 = 1$.
Thus, $sk_a \neq sk_b$  and the output of  oracle $\mathcal B$ is $0$.


How to determine the layers of a circuit? In many cryptographic applications like Multiparty Computation (MPC) or Fully Homomorphic Encryption (FHE), you consider a function $f$ described by a circuit over some algebraic structure, typically a field.

Now, it's very typical that the complexity of the algorithm heavily depends on the depth of the circuit, and not necessarily on its size.
For instance, this is the case in Lattice-based FHE, in which low-depth is required in order to perform the bootstrapping, or in some non-constant round MPC protocols where the number of rounds depends on the depth of the circuit.

Given the above, I have two questions.

Given a circuit for $f$, how can we optimize to get a "shallower" circuit for the same $f$? Are there any tools/algorithms available for this purpose?
Suppose the circuit for $f$ if given as a list of gates, where each gate points to the gate or gates corresponding to its input. How can we determine the layers of the circuit from such representation? Are there any tools/algorithms for this as well?

The second point is particularly relevant for MPC, in which the communication for the gates in the same layer can be parallelized, providing a big improvement.

Thanks!

Given a circuit for f, how can we optimize to get a "shallower" circuit for the same f? Are there any tools/algorithms available for this purpose?

Researchers have already identified this is a relevant problem for MPC and FHE, where low-depth circuits make a big performance difference.
Some works in this direction include [BDKK+18] and [BHWK16], and digging through their reference will reveal more work in that direction.

Some of the techniques in this area include adapting some optimization tools from circuit synthesis in the electrical engineering domain, and there are some other hand-crafted optimizations as well.

  Suppose the circuit for f if given as a list of gates, where each gate points to the gate or gates corresponding to its input. How can we determine the layers of the circuit from such representation? Are there any tools/algorithms for this as well?

I know of two ways of achieving this.

Greedy algorithm

One that is very intuitive works as follows, at a high level.
Take the input nodes and compute all the addition gates you can compute from these nodes without stumbling upon a multiplication gate.
Then compute the multiplication gates that only depend on any of the gates found above (including the input gates).
These gates have depth 1.

Then compute all the addition gates that depend on any of all the previous gates, and then compute the multiplication gates that depend only on the gates found up to this point.
These have depth 2.
This iteration is continued until all gates have been processed.

Using dynamic programming

This approach is considered in [KSS13].
To each edge $v_{ij}$ going from gate $g_i$ to gate $g_j$, assign a weight of $0$ if $g_j$ is an addition gate, and assign a weight of $-1$ if $g_j$ is a multiplication gate.
Then, it is easy to see that the depth of a gate becomes the (negative of the) shortest distance from the gate to any of the input nodes.
This can be computed via dynamic programming algorithms like Dijkstra algorithm.

[BDKK+18] HyCC: Compilation of Hybrid Protocols for Practical Secure Computation (link)
[BHWK16] Compiling Low Depth Circuits for Practical Secure Computation (link)
[KSS13] An architecture for practical actively secure MPC with dishonest majority (link)


Getting the encryption/has algorithm used for modem configuration file Hello guys I have backed up my modem configuration file and found the username and password is in clear text; the files shows the username and the password is :

password=_DEV_4FC6EA6A****************************

how do I get which encryption or hash algorithm is used to generate the given string and how strong it is?

You cannot; most (symmetric) encryption routines create output that is indistinguishable from random. This is however more likely to be the output of a password hash. The only thing you can say is that the result is 24 bytes. That 24 bytes hopefully contains a fully random salt (mostly 8 bytes) and a hash or password hash. In that case it's probably MD5 as there are only 16 bytes left. It could also be the output of SHA-224 directly over the password, or a HMAC using SHA-224 or similar with a device specific key.

If it is salt | MD5 or just SHA-224 is of course something you could test yourself. You could do this using your own password or - possibly - a dictionary attack. Note however that the password should now be changed ASAP as anybody can perform a dictionary attack.


How do I know if a given curve requires a FpCurve F2mCurve or ECCCurve? I'm trying to read a public key into Bouncy Castle (secp256k1) and need to choose from the following objects

        FpPoint;
        FpCurve;

or

        F2mPoint;
        F2mCurve;

or

        ECPoint;
        ECCurve;

Although it would be helpful if someone simply told me which object to use, what would be more useful is if someone can guide me through the general thought process in selecting any of the above objects for a given named curve.

The EC objects implement general elliptic curve properties, whereas the other 2 operate on specific fields. Since secp256k1 is a prime field curve, you want the Fp objects. For binary field curves, you would use the F2m objects.

Note that NIST "K" curves are binary field curves, wheras secp256k1 is a "K" curve but over a prime field. Koblitz curves allow efficient mathematical operations.


Understanding the groups used in bilinear Ate-pairing The bilinear ate pairing $e:G_1\times G_2 \rightarrow G_T$ is defined over the following groups:

\begin{equation}
\begin{aligned}
& G_1 = E(\mathbb{F}_p)[r] \cap Ker(\pi_p-[1]),  \\
& G_2 = E(\mathbb{F}_{p^k})[r] \cap Ker(\pi_p-[p]),  \\
& G_T = \mathbb{F}_{p^k}^*/(\mathbb{F}_{p^k}^*)^r,
\end{aligned}
\end{equation}

where $E(\mathbb{F}_{p^k})[r]$ is  $r$-torsion points of elliptic curve $E(\mathbb{F}_{p^k})$, $\pi_p$ is the Frobenius endomorphism and $[n]$ is the scalar multiplication of a rational point $n$.

I'm having trouble understanding the structures of the groups. Especially I'm confused with this mapping $\pi_p-[n]$ and the notation $\mathbb{F}_{p^k}^*/(\mathbb{F}_{p^k}^*)^r$ as whole. Further explanation, why the groups are like this and other discussion is also welcome. Thanks in advance.

Source: Implementing Cryptographic Pairings over
Barreto-Naehrig Curves.

$E(\mathbb{F}_{p^k})[r]$: all elements $P$ of $E(\mathbb{F}_{p^k})$ such that $rP = 0$. In other words, all points whose order divide $r$. In protocols $r$ is usually prime, so that means all points with order $r$ and the point at infinity.

$\pi_p$: the Frobenius endomorphism. This is a function that takes an elliptic curve point such that $\pi_p((x, y)) = (x^p, y^p)$.

$[1]$: the identity function, i.e. $[1](P) = P$

$\pi_p - [1]$: the function $(\pi_p - [1])(P) = \pi_p(P) - [1]P$

$Ker(\pi_p - [1])$: the kernel of the given function. The kernel of a function is composed of all elements that map to the identity element. In our cases, all points $P$ such that $\pi_p(P) - [1]P = 0$, i.e., $\pi_p(P) = P$. In non-extension finite fields (i.e. $k = 1$) it is true that $x^p = x$ and therefore $\pi_p(P) = P$ for every point with coordinates in a non-extension field. Therefore $Ker(\pi_p - [1]) = E(\mathbb{F}_{p})$ and that was a huge roundabout way to write that $G_1$ is the same as $E(\mathbb{F}_{p})[r]$.

$Ker(\pi_p - [p])$: following the same reasoning, in this case, these are all the points $P$ such that $\pi_p(P) = pP$, i.e. the Frobenius mapping is a much faster way to compute $pP$, which is a much more interesting mapping. Therefore $G_2$ are all the $r$-torsion points in $E(\mathbb{F}_{p^k})$ where that equality is true.

$\mathbb{F}_{p^k}^*$: the multiplicative subgroup of the finite field $\mathbb{F}_{p^k}$ (i.e. all non-zero elements under the multiplication operation).

$(\mathbb{F}_{p^k}^*)^r$: the multiplicative subgroup where all elements are raised to the $r$-th power.

$\mathbb{F}_{p^k}^*/(\mathbb{F}_{p^k}^*)^r$: this is the confusing part. This is a quotient group, and its elements are cosets (sets of field elements). Elements $x,y$ are in the same coset if $x/y = h^r$ for some element $h$. There will be $r$ such cosets, each with $(q^k-1)/r$ elements. However, since it is difficult to work with cosets in cryptographic protocols, in the end they select a "canonical" element by raising the element of the coset (which is the intermediate result of the pairing computation) by $(q^k-1)/r$, the so-called "final exponentiation". This implies that the set of canonical coset elements are the $r$-th roots of unity, i.e. all elements $x$ such that $x^r = 1$ (because $x$ was already the result of exponentiation by $(q^k-1)/r$, if we raise that by $r$, we are computing the full exponentiation by $q^k-1$ which is the order of the multiplicative subgroup and we get back to $1$).


Multiple private keys for single public key I am currently working in security in mobile ad-hoc networks.

I have several clusters, and I want to send some data encrypted with its public key, from the cluster head to the cluster members. I assume that each member has its own private key so it can decrypt the data.

I ask about how to get a single public key and multiple private keys for this public key?

What is the solution for this case?

Public-key algorithms such as RSA or ECDSA have exactly one private key for each public key and vice versa.

Attribute-based Encryption

Attribute-based encryption works (a little bit) like that. You have only one public key which is used to create all ciphertexts and you select the users that should be able to decrypt the data based on a policy of attributes. The policy can be a boolean formula and the users have secret attribute keys that should satisfy the policy if they must be able to decrypt the ciphertext.

If you use only one attribute for all users and a trivial policy containing that attribute, you've got that system that you wanted, but now the problem becomes that the user attribute secret keys have to be generated by a central server and you will need multi-party computation to get rid of the key escrow.

Conventional

This is almost certainly too complicated for your case. You should use a symmetric algorithm like AES and a public key encryption algorithm like RSA in conjunction. You can simulate your intended system by encrypting the data with AES using a randomly generated key, then encrypt the AES key with all the RSA public keys of the intended recipients. Concatenate everything into one package and send it on its way.

Thoughts

Let's say multiple recipients have (a different) private key and all of them can decrypt data encrypted with the same public key. You should ask yourself, how can the different private keys be generated to arrive at the same public key, but where all the recipients wouldn't know the private key of each other.


A perfect $(2; 2)$-threshold scheme Given a symmetric encryption scheme with $|K| = |C| = |M|$ that provides perfect
secrecy, it is possible to share a secret $s ∈ M$ between two players by giving one
player a key $k ∈ K$ and the other player the ciphertext $c =$ Enc$(k$, $m)$. Show that
this construction results in a perfect $(2; 2)$-threshold scheme.

I don't know how to do this. Would I go down the route of Shamir's threshold scheme?I know since $|K| = |C| = |M|$ provides perfect secrecy then for every choice of $m$ and $c$, there exists a unique key $k$ but can't see if that helps in any way..

You don't need to adress Shamir's, that is just needed for $k<n$. What you do here is along the lines of the proof that OTP is perfectly secure - actually OTP is one example for this (it is not the general case you are given).

Also see Wikipedia the section "trivial secret sharing", which does list elementwise-XOR with a truly random value for the $2,2$ case (also works for $n,n$. There you just choose $n-1$ shares randomly, and calculate the last one).


Forge CBC-MAC by creating a new message, given the MAC of two messages The question is quite similar to this one : Forge CBC-MAC given the MAC of two messages and of their concatenation
But I still cannot fully understand it, and here's my question:
given two messages with known MAC:
CBC-MAC(a||b)= x
CBC-MAC(d||e)= y
So from the given messages, I am able to forge a new message like this:
CBC-MAC(a || b || (d XOR x) || e ) = y
(which is just like the post I read).
But how about if I want to forge the message like this:
CBC-MAC(a || b || c || d || e ) = z
The "c" maybe is something calculated from those two messages and its MAC, but I am not sure about it.
Is it possible to achieve this?

That doesn't look likely.

Given $\text{CBC-MAC}(d||e) = y$, we know that, saying at the initial IV state of $0$, then processing the blocks $d$ and $e$ gives us $y$; that doesn't say where we end up at any other starting state.

If $c$ was a single block, what we'd need to happen is to have it reset the state to 0 (and then the $d$ and $e$ would be processed as expected).  That is, we would need to set $c$ so that $\text{Encrypt}_k( c \oplus x ) = 0$, or in other words, $c = x \oplus \text{Decrypt}_k(0)$.

That's where we get stuck; we can use $\text{CBC-MAC}$ as an encryption oracle (given a block $t$, what's $\text{Encrypt}_k(t)$?), but not as a decryption oracle; there's no query we can make that we tell us, given $t$, what's the value of $\text{Decrypt}_k(t)$.


Properties of Ideal Straight P-Boxes What properties should an ideal straight P-Box exhibit?

This is not an answerable question.  The requirements for a P-box (whatever that is) depend upon the cipher it is embedded in; that cipher imposes some requirements on the P-box.  Therefore, you cannot do P-box design in the abstract, without knowing what the requirements are.  There is no one, single answer that is valid for all ciphers.

P.S. Where did you hear the term "P-box"?  As far as I know, this is not an accepted or widely used term, let alone "straight P-box".


How can we determine if two discrete logarithms are equal? Let $p$ be a prime number, and let $g_{1},g_{2},...,g_{n}$ be $n$ generator of $Z^{*}_{p}$. We have a list $y_{1},y_{2},\dotsc,y_{n}$ of elements in $Z^{*}_{p}$  such that for every $i\in \lbrace1,2,\dotsc,n \rbrace$ we have $y_{i}=g_{i}^{x_{i}} \bmod p$ for some number $x_{i}$ (but we don't know $x_{i}$). I am trying to find an algorithm to determine all pairs $(y_{i},y_{j})$, $i\neq j$ such that $x_{i}=x_{j}$.

This problem is equivalent to the decisional Diffie-Hellman problem, and hence your problem is intractable (assuming, of course, that the group is well chosen).

Here's how we can use an Oracle that can solve the above problem to solve the DDH problem:

In the DDH problem, we're given values $g, g^x, g^y, g^z$, and we're asked whether $xy = z$.
We call the Oracle with the following instance: $n=2$, $g_1 = g$, $g_2 = g^x$, $y_1 = g^y$, $y_2 = g^z$.
The Oracle will return that $x_1 = x_2$ is a matching pair iff, for that same $w$, $g_1^w = y_1$ and $g_2^w = y_2$, that is, if $g^w = g^y$ and $g^{wx} = g^z$, which is to say, if $g^{xy} = g^z$

It's also obvious how to solve your problem with an Oracle that solves the DDH problem (using $n (n-1)/2$ calls to the Oracle).


How can I determine the GPG/PGP key ID from the RSA modulus? According to http://www.pgp.net/pgpnet/pgp-faq/pgp-faq-keys.html#key-public-key-forgery, key ID is some lower bits sequence from the modulus (i.e. the $n$ variable):

  A PGP key ID is just the bottom 64 bits of the public modulus (but only the bottom 32 bits are displayed with pgp -kv).

I have a key pair. According to pgpdump, my key ID (i.e. 64b) is the following one 0x6BA09C369E31148C. According to GPG, my key ID (i.e. 32b) is the following one: 0x9E31148C. Well, this is just the last 32 bits from the 64b key ID.

I'd like to see a relation to my public modulus. I haven't found any, even if I play with endianess.

The key id is also weird… if it was last 32b (or 64b) from the modulus, it should be an odd number (except if $p$ == $2$ || $q == 2$$, which is very unlikely).

However, when I search lower 32 bits in my modulus (dumped by pgpdump), I see 0x84cfe5c1, which is far different from 0x9E31148C:

RSA n(4096 bits) - c8 1a 2e 7d e5 22 84 5c 10 b9 02 3b 42 ff 09 4c 60 f9 8a ce 80 64 8a 95 6a 0e 53 23 a3 dc fb fb f5 96 c7 a2 de be a9 f0 c8 f8 d8 51
6d e8 bc 64 13 16 5e 25 f9 4d 44 bc 51 ef 7f 97 b4 05 a3 d9 9e e3 58 ef 88 c1 bb e5 23 65 45 1b 99 7b 68 c1 e4 1a 7d bc fb 51 c1 41 d6 10 33 34 90 c3 91 5c 5b
ae 48 63 4e 65 46 4e 35 8e 48 e6 85 e3 9b ff b2 4b e9 c6 aa f1 45 3f b8 b6 b5 be 56 f8 04 4e 1d 1a d4 78 4d 75 fa 5e aa 2d 6d dc 31 2b c8 28 db cb 10 34 1a 16
2c fd e2 67 e7 1d 0b e6 cc 53 92 5d 85 40 57 5c 9f 23 bb af 75 d9 11 2b 4a a0 6c ef c4 50 85 eb 79 46 b2 f7 03 54 8a c9 15 c0 ac d8 d4 5a 7c 5e 37 5e cc f2 13
8a 67 3c 1f 26 c5 f4 11 d0 38 19 9c 34 0f c0 3d e7 63 67 8e 3f 7d 82 2e b6 59 d3 da 74 61 68 1c 78 7b 4c ce c3 5a f0 18 8c 3b ab 3c 88 03 28 6b 93 f5 b9 eb eb
44 51 a7 b8 34 08 e9 a7 fa 81 d3 af 3d a0 f7 fa 6b f9 fb 98 97 38 32 d1 1f e4 e7 1a 4d af e3 e9 87 f8 ca b1 10 91 e5 9c fc db 4b 2d 23 3a 3f c3 fc 1b fe 15 c1
df ff a2 0e fb 51 fe c3 1c 67 26 f3 f3 9d 50 ff 8b a7 48 f4 57 1c e8 63 e9 1e 1b 4a 27 96 02 9c 06 5a 62 ed 99 80 02 13 b2 31 66 a8 ee 79 15 85 05 61 81 67 0f
b7 c6 4e d9 5f 31 81 64 d7 16 13 a8 70 a5 26 6f dc c3 cd f7 d3 8a 3d ab 79 60 34 6d 4e 9b f7 ef 32 eb 65 75 63 f4 79 1c 43 a8 ae 64 53 fd 56 77 d4 df 68 1e b6
05 b0 d1 1d 7c fc 10 5a a3 aa eb 90 90 a8 6d 15 a6 8c 03 85 97 7b 0f 15 fe 19 07 ff 12 ff 10 87 fe bb 85 7b d3 98 34 24 8e c0 cb 5f 9a 42 81 71 76 3c fc 2d fb
55 40 98 56 b0 b6 bd 26 8d bd 66 86 9a b2 49 cf a8 0f 4d 3c ed 62 34 79 4f 98 bd 5c 73 dc e5 45 cf 3f e0 a6 4a 59 e2 09 84 cf e5 c1

Where is the mistake in understanding the Key ID?

It depends on the version of the GPG format. In V3 the Key ID it is indeed the bottom 64 bits of the modulus, but in V4 it's the bottom 64 bits of the key fingerprint, which in turn is the  "SHA-1 hash of the octet 0x99, followed by the two-octet packet length, followed by the entire Public-Key packet starting with the version field" according to the RFC.


(EC)DSA signature without hashing, or with offloaded hash? In (EC)DSA as per FIPS 186-4, the message to sign is first hashed. Imagine that we skip this hashing stage, instead put the message where the hash was, and constrain the size of message $h$ to the original hash's output width $N$ bits. The resulting scheme is vulnerable to (at least) these existential forgeries ($q$ is the multiplicative group order):

any signature for message $0\le h<2^N-q$ is also valid for message $h+q$;
a valid signature for messages $h=0$ and $h=q$ is easy to obtain: in DSA, $(r,s)$ with $r=s=y\bmod q$ does the trick, where $y$ is the public key; there's an analog with ECDSA, which $r=s=x_A\bmod q$, where $x_A$ is the $x$ coordinate of the public key, and $q=n$.

Are other attacks possible? In particular, does temporary access to a signing oracle allow a total break (key extraction or other mean to sign any message)?

The question is of direct interest when one wants to lower the communication overhead between a signing device and a host using it to (EC)DSA-sign large messages: can we fully offload the hash computation to the host? I believe that holds (and as noted in comments, that seems to be practice), but can we demonstrate that? If not, how can we safely offload most of that computation, without breaking standard conformance?

Let's focus on DSA. The signing on a message $m\in \mathbb{Z}_q$ for the suggested "no-hash" protocol is done as follows:

Pick $k\in_R \mathbb{Z}_q$, compute $r=f(g^k)$, where $f(\cdot):=(\cdot \bmod p) \bmod q$.
Compute $s=k^{-1}(m+xr)\bmod q$
Return $(r,s)$ if the signature is not degenerate.

The verification algorithm, on input $(m,s,r)$, checks if $f((g^m\cdot y^r)^{(1/s)})=r$.

The following consists of a forgery on a random message under the key-only attack.

Let $K=g^a\cdot y^b$, where $a,b\in_R\mathbb{Z}_q$
Compute $r=f(K)$, and set $s=r/b$
Return $(r,s)$ as a forgery on $m=(a\cdot r)/b$

(I'll add the references in due course.)


Is there a cryptographic method to add noise to a plaintext instead of actually encrypting it? I'm looking for a cryptographic technique that instead of permuting a cleartext, would add noise to the cleartext to obfuscate the true text among a bunch of garbage.  For example,  a list of 10 numbers would be combined with a list of 90 random ones with the goal of making the true set of numbers difficult to recover.

I need an attacker to believe that the message is not encrypted. I'm trying to obfuscate a set of GPS coordinates that need to be submitted to a third party but the original route needs to be recoverable with only a key.

Is there a principled way to do this?  One idea is to use a secure PRNG to generate the 'noise' and, assuming there is no collisions, regenerate the noise on the receiver side and filter to decrypt.  Any pointers to other techniques would be appreciated.

You first need to consider your adversary and what are your goals for this mechanism.

This kind of mechanism appears less effective than proper cryptographic means:

having secure PRNG means that both ends of the message exchange have access to some proper cryptographic means
Adding noise means that the information exchange is less efficient: there is much more information to exchange
Even when garbage is added, some cryptanalysis techniques could be effective in retrieving the true text from the garbage.

The principled way (in my humble opinion) would be to use proper cryptographic primitives. Otherwise, you risk getting your system efficiently attacked by attacker who know the system (Kerckhoffs' principle).

Steganography

Steganography is about encoding and hiding message so that only sender and recipient should detect existence of the message. Steganographic techniques often involve adding various materials to make it easier to detect the message. I recommend studying steganographic techniques (in case you do not follow advice on just using cryptography) because there you may find partial aid for your problem.

Format preserving encryption

If the target is to make it look like it has not been encrypted, one possibility is to use format preserving encryption for encryption instead of adding garbage.


Generating child keys for a hill climb algorithm As a little pet project I'm writing some code to do a little cryptanalysis. Starting with something simple I have created a hill climbing algorithm for solving a simple substitution cipher.

So I start by generating a parent key by shuffling letters A-Z randomly. For the first iteration I am generating a child key by randomly swapping 2 characters from the parent key, and in each subsequent iteration I am shuffling two characters from the previous iteration's key.

While this approach works, it seems very inefficient, as the randomness seems to generate the same key over and over again on each attempt at a solution.

So my question is, is there a better solution for generating child keys than random? A few things I have considered but not tried:

memorizing previous keys and checking a new random key has not already been tried
Some other means of shuffling characters, such as swap 1-2, 1-3, 1-4 .... 2-3,2-4... etc (This feels much too much like brute force)

But both of these strike me as making the algorithm less efficient not more (ie, the overhead in doing each outweighs the gain made by using random chance).

Any particular thoughts?

Edit: As the comments have quite rightfully pointed out perhaps the problem I'm facing is not actually how to generate better child keys, but how to avoid a local maximum. Other relevant details of my algorithm are as follows:

I am scoring based on the Sum of the Log10 probability of Quadgrams
I am running my algorithm until 1000 iterations have not provided a better score
I am running the entire thing until 20 tries have not produced a better score

My experience is that hill climbing is very efficient for solving substitution ciphers. As I understand there are two topics now.

How to generate the child keysSwapping characters of the key randomly (stochastic hill climbing) as well as trying all possible swap combinations is reasonable.  But for solving a substitution cipher I believe trying all possible character swaps per parent is more efficient. First, trying the same key more than once is avoided (at least for one parent), secondly it provides a clear condition when to stop the hill climbing: If none of the childs provide a better result than the parent.  Using the stochastic hill climbing and keeping track of the tried keys would be overkill, and I think effectively it turns this into trying all possible key swaps.
How to avoid a local maximumOne option is to use the Random-restart hill climbing (or Shotgun hill climbing, see http://en.wikipedia.org/wiki/Hill_climbing#Variants). It simply repeats the hill climbing using different random initial conditions and it works very well for breaking substitution ciphers.

Resources:

http://www.guballa.de/crypto/substitution.html
A substitution cipher solver, using the Random-restart hill climbing algorithm choosing always the first better key (called "simple hill climbing"). It uses Javascript Webworkers, so it will not run on some older browsers.
http://www.guballa.de/crypto/substitution_breaker.js
The related Javascript implementation


Is there a checksum that gives the same checksum when in a text file? Let's say I have a text file (crypto.txt). Let's assume the checksum function can be any type of function (MD5, SHA-1, anything else). Is there a way that the checksum value IN the file (crypto.txt contains a string that could be a possible checksum), when put through a checksum program, outputs the exact same value as the content inside the text file?

In case I lost you, here's a quick breakdown:

crypto.txt contains a viable checksum value (said value = x)
checksum of crypto.txt = x

Is this even possible? Is there math that proves it wrong/right?

For a checksum such as CRC16 or CRC32 it is very much possible to have a value over a text that contains the same CRC value (in whatever format, be it binary, hexadecimals or base 64). The proof of this is simple: you can simply put e.g. 32-48 bits counter at the end of the text and wait until you find a CRC. But in practice you can just calculate the value you need to prefix, append or anything in between and get the right CRC - if it is included or not. Checksums such as CRC are not secure.

For secure hash functions this is not possible. It is even computationally not possible to find any message $m$ where the hash value is $h$, for any chosen $h$ (that is not a known hash value). This is a much stronger presumption than the one you are proposing. It is not possible to find $x = \operatorname{H}(a | \operatorname{encode}(x) | b)$ even if you can chose any special value of $a$ and $b$, and any $\operatorname{encode}$ operation.

It is not possible to prove above completely for the simple fact that the security of hash functions cannot be proven. SHA-1 was thought to be secure for a long time, but by now it might be possible to create a text where the hash value is included.


How to decrypt a PGP message with only the two primes and the public exponent? I'm trying to decrypt a PGP Message that is encrypted with an RSA key, but I only have this information:

Public exponent:
65537

Prime 1: c447376fcf2a4d4f03840c83f68b23202f081f8561a1f0295703df258a96b8fd6cc8cb307558d60cbd692a45ed2414370349e28badf0f180419fc1df2cd87e99

Prime 2:
d876bd7c4963b8c06f148da504d1f7c7b9b20a719a0d3788eacc7effa7acb9cc200ef3a18a29fb5c733d45e04104ef3e7fc77f3ec847526b0c5d50506a2f471b

It seems when generating a key, the primes are automatically generated so I can't find any tools online that will help me any.

Here's where I'm currently at:

  ~$ gpg -d green.gpg.asc
  gpg: encrypted with RSA key, ID 00000000
  gpg: decryption failed: secret key not available

The end goal is I'd like to create a key that can be imported which would then allow the above command to decrypt the message.

Here's the file I'm trying to decrypt for context:

green.gpg.asc (492k)

Look up the OpenPGP secret key format (some kind of ASN.1 I think?).
Use your favourite bignum implementation to multiply p by q and store this as the modulus n (in the correct format).
To calculate the decryption exponent, you need $d$ such that $ed=1 \pmod{(p-1)(q-1)}$. This can be found with the extended Euclidean algorithm (the wikipedia pages for RSA and the Euclidean algorithm explain the details) - you're probably going to end up implementing this in your favourite bignum library too.
Store $d$ in the secret key file you're building, import it into gnupg and decrypt normally.

Depending on what programming languages you know, there may be shortcuts - instead of building a key file you might be able to build a key data structure directly and use your language's gnupg/libgcrypt wrapper to work with that.