texts: SPHINCS and HORST: can we sign the same message twice?

texts:
I was reading about SPHINCS which uses layers of WOTS+ trees and a bottom layer of HORST trees. HORST is a few time signature scheme, using a selection function you can sign at least twice without compromising security.

I was then reading this blogpost where for the description of SPHINCS says:

  Signing the same message again should use the same HORST, signing two
  different messages should make use of two different HORST with good
  probabilities.

So as I understand, given the fact that the random bit masks are constant after instantiation of the scheme, SPHINCS is a deterministic scheme. Also it is susceptible to replay attacks since signing the same message twice produces the same signature. Am I correct?


texts: HKDF - Generating a new, random salt per user?

texts:
Regarding HKDF, the specification says a salt may be re-used.

However, I have set up my system to generate a new, long and cryptographically random salt that persists with the user.  This salt is not a secret. (See the RFC, section 3.1)

In addition, I am taking our unique user identifier and using it as context info for the third parameter in HKDF.

So our HKDF looks like this:

DK = HKDF(MasterKey, PublicUserSpecificSalt, UUID)

My questions are:

Are there any issues with creating a random, user-specific salt, and using this for the salt input in HKDF?  It seems the spec expects the salt to be re-used, which I am not doing.
If I do use a random, user-specific salt, what is the benefit of the UUID as context info? Should I just remove it, since it would add unnecessary complexity?


texts: Elliptic curve with prime subgroup equal to field size

texts:
I am aware that when the equation $\#E(\mathbb{Z}_p) = p$ holds for prime $p$, the elliptic curve is called "anomalous" and is insecure do to "Smart's attack".

Consider the similar case that $E(\mathbb{Z}_p)$ has a proper subgroup of (prime) order $p$, so $p \neq \#E$. In this case $p$ divides $\#E$ and $\#E > p$. This relationship of the (sub)group order matching the field size (thus forcing primality) is desirable for some applications.

Is such a curve secure for the discrete log performed in the $p$-order subgroup, or is this vulnerable to a similar attack? What would be the process to generate such a curve that is arguably safe for cryptographic use?

From what I read, curves over $GF(2^n)$ for some $n$ are less stable. But analogously, for $E(GF(2^n))$ there could be a subgroup of order $2^n$ and as long as $2^n$ has a large prime factor it should be safe for the discrete log. Is this also a possibility?


texts: Applying Trapdoor Function directly to plaintext

texts:
Suppose we have a secure trapdoor function defined on (G, F, F^-1) where G is a randomized algorithm outputs a key pair (pk, sk). Why would this trapdoor function become insecure if we apply F directly to plaintext message?
E(pk,m) = c = F(pk, m)


texts:
I've been trying to solve this question from Forouzan's book ("Cryptography And Network Security") and haven't been able to wrap my head around how to solve it.

The plaintext “letusmeetnow” and the corresponding ciphertext
“HBCDFNOPIKLB” are given. You know that the algorithm is a Hill
cipher, but you don’t know the size of the key.
Find the key matrix.

I inverse the 2x2 plaintext matrix and multiple with a 2x2 ciphertext matrix and take a mod 26. However, the key matrix is always in fractions, never an integer.
It would be great if someone could point me in the right direction / tell me what I'm doing wrong.
Thanks in advance!


texts: How to define a FHE scheme whose plaintext space is infinite using boolean circuits?

texts:
There are many kinds of fully homomorphic encryption scheme by using boolean circuits. And the plaintext space $\mathcal{P} = \{ 0,1 \}$.

If there is a -bit FHE scheme, we can construct a FHE scheme which can encrypt all the messages.
For a string $x \in \{ 0,1 \}^{*}$ and $x = x_{1} \Vert x_{2} \Vert \cdots \Vert x_{n}$, we can define
$$\mathrm{Enc}_{pk} (x) = y = \mathrm{Enc}_{pk} (x_{1}) \Vert \mathrm{Enc}_{pk} (x_{2}) \Vert \cdots \Vert \mathrm{Enc}_{pk} (x_{n})$$
where $x_{i} \in \{ 0,1 \}$

However, if I want to define a FHE with $\mathcal{P} = \{ 0,1 \}^*$, there is a problem.

Naturally,
$$\mathrm{Enc}_{pk}: \mathcal{P} \rightarrow \mathcal{C}$$
$$\mathrm{Dec}_{sk}: \mathcal{C} \rightarrow \mathcal{P} \text{ or } \{\, \bot \,\}$$
$$\mathrm{Eval}: \mathcal{B} \times \mathcal{C}^* \rightarrow \mathcal{C}$$
where $\mathcal{B}$ is the set of all the boolean circuits.

Given $C \in \mathcal{B}$ such that $C \colon \{ 0,1 \}^{n} \rightarrow \{ 0,1 \}^m$, if $c \leftarrow \mathrm{Eval} (C, c_{1}, c_{2}, \ldots, c_{l})$, we have
$$|\mathrm{Dec}_{sk}\left( c_{1} \right)| + |\mathrm{Dec}_{sk}\left( c_{2} \right)| + \cdots + |\mathrm{Dec}_{sk}\left( c_{l} \right)| = n$$
and
$$|\mathrm{Dec}_{sk}\left( c \right)| = m$$
But, how can we know the size of $|\mathrm{Dec}_{sk}\left( c_{i} \right)|$ when we ask the access to $\mathrm{Eval}(\cdot, \cdot)$?


texts: Telegram recently updated its symmetric-key encryption scheme MTProto, which seems to fix some known vulnerabilities. Nevertheless, I still do not understand why they roll their own crypto. What properties/advantages do they gain from their homemade MTProto encryption scheme beyond those already provided by the standard key derivation and authenticated encryption schemes?


texts: What does "a 15360-bit RSA key is the equivalent to a 256-bit symmetric key" mean?

texts:
NIST key management guidelines suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys. If a 15360-bit RSA key is the equivalent to a 256-bit symmetric key, does that mean a 15360-bit RSA key can prevent factoring  by the strongest quantum computers in the next 100 years or so? If not, how can the following statement be true?

  …a 15360-bit RSA key is the equivalent to a 256-bit symmetric key.

So, a 256-bit symmetric key could be reduced to 128-bit with Quantum computers (Grover's algorithm). Even if it takes 20 years or so from now to develop a strong enough quantum computer, once quantum computers become strong enough, a 256-bit symmetric key would still be strong enough to prevent brute forcing when the keys are random enough. So, do they think a strong quantum computer can factor 15360-bit RSA keys using Shor's algorithm (or any similar algorithm) in 100 years or so from now?


texts: FSB Hash Functions and Convetional hash Functions

texts: I'm reading FSB cryptographic hash function and the authors say that security of this function depends on NP-Complete Problem: "Decoding Linear Code Unlike most other cryptographic hash functions in use today" and I'm agree with the first part of claim. But I have a doubt respect to conventional hash functions for example the family SHA. The security of these functions depend of any NP-Complete Problem? According my understanding this hash function will be able to express than multivariate polynomials equations and solve multivariate polynomial equations is proved NP-Complete. Then a question is: Am I right?


texts:
Everyone says that you shouldn't use the same IV and Key.

Is it safe to use the same IV and Key on only one file. EDIT: I will be using CBC or CFB encryption modes so the IV will be updated based on previous block.
Is it safe to use the same IV (EDIT: Same first IV, which will then be updated with each block.) each time I access and add data to the file.  Each time this happens, there will only be one encrypted file so multiple files with same IV and Key will not happen.

Edit: The program using the file will just add data to the end of the file.  From what I could find, this will not change the encryption of the first sections of the file, as the IV is changed based on what was done in the previous block.  Is that correct?

Edit 2: For simplicity, let's say this is a log file that I want encrypted for some reason.  I want to be able to add on to the end of this log while not needing new key/IV.  Since it is the end of a file, I was thinking while decrypting, I will have the next IV for CBC or CFB and use it to begin encrypting the next entry.  As for mutability, I will never have a reason to change anything in the middle of the log/file, only to add on to the end.  I don't know how that lines up with cryptographic mutability/immutability, but that is what I want to do.

Final: I am using CBC.  At the beginning of every line I have a new IV (first 16 bytes are the IV) and the rest of the line is encrypted using that IV.  Thanks for all the pointers.  If anyone sees any major thing wrong with this, please let me know.


texts: Can rainbow tables find the preimage of a hash?

texts: Given a hash value, how are you supposed to find its preimage? What steps can I take to solve find the preimage of a hash such as this 2d202cb6a781edf6ac01d14e1dd6367497db90ba9e8ad721fd17239228a213f9 (SHA256)


texts: Encryption with both plaintext and ciphertext public

texts:
Does there exist a system wherein the encryption key/algorithm can be made indecipherable despite making arbitrarily many plaintext and ciphertext pairs available to the cracker? (Does this qualify as KPA attack security? ) If so, how strong is such a system, what kind of key and algorithms should be used?

What minimum size should the keyspace be to ensure recovering key from the known plaintext-ciphertext pairs is not efficient? Are there any known attacks which can recover key faster than a brute-force attack?


texts:
Suppose we define a PRG as the xor of two LCGs modulo a 64-bit prime: something like the following Python code.

p = 14692456042302986707
alpha, beta = 1416483285059710267, 1922202445720274864
gamma, delta = 8868330555542893802, 9736145736144160231

def prg(x, y):
    while True:
        x = (alpha * x + beta) % p
        y = (gamma * y + delta) % p
        yield (x ^ y)

To express it more mathematically, starting from a seed $(x_0,y_0)$ the outputs are $z_1, z_2, \ldots$, where

$x_{i+1}=\alpha x_i+\beta\ (\mathrm{mod}\ p)$,
$y_{i+1}=\gamma y_i+\delta\ (\mathrm{mod}\ p)$,
$z_i=x_i\oplus y_i$,

with constants $p=14692456042302986707$, $\alpha=1416483285059710267$, $\beta=1922202445720274864$, $\gamma=8868330555542893802$, and $\delta=9736145736144160231$.

How broken is this construction, in the sense of being predictable given some output? Of course it can be broken in at most p iterations given two consecutive outputs (guess x, derive y from the first output, and check against the second). But is it more broken than that? Can it be predicted in significantly fewer than p iterations given some amount of output? Is there anything in the literature about attacking this construction? It is surely simple enough that it has been considered.

Please forgive this beginner’s question. I have not been able to find an answer online or in the literature, searching under all the search terms I can think of. Nevertheless I suspect the answer is well-known, hence I am asking here.

I should emphasise that I am not proposing to use this construction for anything security-sensitive (nor indeed for anything at all). I am only curious about crypto fundamentals, and this is the simplest LCG-based construction that I cannot easily break, though I do of course suspect it to be breakable.

Update: In response to Thomas’s request for a smaller variant to analyse, here are some 24-bit constants:

$p = 14435129$, $\alpha = 881969$, $\beta=8713582$, $\gamma=12608927$, $\delta=9284034$.

Here $p$ was selected as a random 24-bit prime, then the others as random numbers less than $p$.

Of course this reduced version can be brute-forced very easily, but the question remains of whether there is an even faster attack.


texts: Why is an RSA public key BITWRAP-ed in ASN.1 DER encoding?

texts:
While playing around with creating an RSA public key, and decoding it using a home brew ASN.1 decoder, I ran into the fact that the public key is BITWRAP-ed. BITWRAP seems to be an OpenSSL modifier, and I wonder why it is needed, what the rationale is?
This page describes what BITWRAP is but not why it is needed.
Why can't $n$ and $e$ be encoded in a regular non-BITWRAP-ed ASN.1 sequence?
Below example shows the BITWRAP modifier in an ASN1 definition (copied from OpenSSL docs):
asn1=SEQUENCE:pubkeyinfo

# BITWRAP here
[pubkeyinfo]
algorithm=SEQUENCE:rsa_alg
pubkey=BITWRAP,SEQUENCE:rsapubkey

[rsa_alg]
algorithm=OID:rsaEncryption
parameter=NULL

[rsapubkey]
n=INTEGER:0xBB6FE79432CC6EA2D8F970675A5A87BFBE1AFF0BE63E879F2AFFB93644\
D4D2C6D000430DEC66ABF47829E74B8C5108623A1C0EE8BE217B3AD8D36D5EB4FCA1D9
e=INTEGER:0x010001


texts: How to test distribution of a hash function?

texts: From what I've found, it is generally accepted a cryptographic hash function like SHA-2 has an evenly, randomly distributed output.  Is there a way to test this without running through the entire 2^512 keyspace?  Generate a large number of high-quality 512 bit random numbers?  What about random 64 character "keyboard ascii" strings?


texts:
I've found a way to complete a task which I'd solve with passwords or by sending keys over the wire (otherwise) by using RSA's homomorphic property.

I'm restricted to RSA (any padding; for hardware reasons) to implement "blindable decryption", where one party holds some encrypted data, blinds it, sends it to the decryption oracle, receives it and recovers the embedded key by unblinding.

For this a "secure-as-possible" version of RSA is required which still has the multiplicative homomorphic property.

So what is the best padding for RSA that keeps this property?

Note: An IND-CCA1 version of RSA would be perfectly fine.
My definition of best (in order of preference): Highest security level, easiest implementability, fastest run-time.

Edit: I removed the ECDH unit as the question is way more interesting this way. The ECDH unit can solve the problem using ElGamal and an ECIES like approach.


texts:
I recently bought an SSL certificate from a website and was able to make it work on my Apache server.

As far as I know, it uses asymmetric keys and the private key is stored on the server while the public key is inside the browser.

My question is, how does the private key work on the browser side? Is it one for everyone, or each time I visit the website, my server sends the visitor a new public key? How is the public key generated every time?


texts: Encryption & decryption in AES CBC mode - Which is faster?

texts: I wrote a small code to compute the time consumption by the AES in CBC mode, I noticed that the encryption is faster than the decryption, my question: Is my result correct? If yes, why is the encryption faster?


texts: Is it okay to use a hash of a timestamp as the IV for AES?

texts:
The message format includes a datetime field in the clear. Is it okay to also use this field (or some hash thereof) as the initialization vector?

In this case, CBC is the mode being used.


texts: Can I use the ChaCha core as a 256-bit to 256-bit one-way function?

texts:
I'm looking to implement Lamport signatures as a little fun project, and I need a fast one way function that maps $\{0,1\}^{256} \rightarrow \{0,1\}^{256}$.

I was wondering whether I could safely use the ChaCha core for that, by setting the input as the key, the nonce and counter to 0 and truncating the output to 256 bits?

If there are other secure, fast one-way functions I'd love to hear about them.


texts: How secure is a password generator that runs SHA256 on a passphrase

texts:
I was looking into how password managers work and it seems to me that they all store the passwords (albeit encrypted).
How secure would a scheme be where the password manager always generates the password when you ask for it based on your master password and some salt that can be generated from the website name. For example something like
password=sha256("mymasterpassword"+md5("facebook"))
Trivially it seems no more vulnerable than the normal scheme, the attacker still needs to guess my master password, so what security flaw am I missing?


texts:
I read this question in my book (that doesn't have a response).

2DES is doubly more secure than DES?

I know that 2DES can be attacked from meet in the middle attack.

In fact, from Wikipedia Meet in the middle say :

  The MITM attack is one of the reasons why Data Encryption Standard
  (DES) was replaced with Triple DES and not Double DES. An attacker can
  use a MITM attack to bruteforce Double DES with 2^57 operations and
  2^56 space, making it only a small improvement over DES.[5] Triple DES
  uses a "triple length" (168-bit) key and is also vulnerable to a
  meet-in-the-middle attack in 2^56 space and 2^112 operations, but is
  considered secure due to the size of its keyspace.[1][2]

But DES use key from 2^56. 2DES with meet in the middle have 2^57 operation (that is exactly a double of 2^56)
I'm not sure if the question ask a "doubly secure " in order to key space , so want a key big as 2^112 (that is double of 56 in previous DES).

I think that DES is double secure from this other phrase on Wikipedia that says:

  Diffie and Hellman first proposed the meet-in-the-middle attack on a
  hypothetical expansion of a block cipher in 1977.[3] Their attack used
  a space-time tradeoff to break the double-encryption scheme in only
  twice the time needed to break the single-encryption scheme.

So if 2 times Diffie/Hellman uses twice time to break the algorithm, also for 2DES we can use a double time of DES to break this algorithm.

Anyone can confirm my hypothesis?


texts: Secret key generation in the BGV scheme in HElib

texts:
This question is about secret key generation, based on section 4.7 in the design document:
https://homenc.github.io/HElib/documentation/Design_Document/HElib-design.pdf
It seems that if $m$ is not a power of two, then we choose coefficients of the secret key such that the secret key is a polynomial of degree $m$. How is it reduced into a polynomial of degree $\phi(m)$? If we just reduce mod $\Phi_m(X)$ then the coefficients may be outside $\{-1,1\}$, so I assume based on the way it is written that there is some other method.


texts: What math should I learn to get in depth with Elliptic Curve Cryptography research?

texts:
My background is computer scientist. I have done applied cryptography research for a while. Currently, I'm working on Elliptic curve cryptography.

To understand the idea and how to use Elliptic curve cryptography (ECC) is not that complicated. I understand basic algebra, EC point addition, finite field, Discrete Logarithm problem, etc.

However, When it comes to improving ECC research, it requires a lot of mathematical knowledge. For instance, if I want to introduce a new curve (like when Bernstein, Birkner, Joye, Lange, and Peters introduced Twisted Edwards curve in 2008) and evaluate its security, or trying to solve Elliptic Curve Discrete Log Problem (ECDLP), what math field(s) should I study?


texts: Is there a name for this 'enhanced' caeser shift and if so, is it trivial to break?

texts:
This cipher shifts the letter that it will shift to, after each shift...

I used to play with this when I was a kid. I was thinking about it recently and realized that it wasn't as simple as I thought. Here's the description:

  The second number makes the code much harder to break. It changes the number of letters above the letter to be replaced by a different amount each time. For example "a" will be subsituted by "b" (one place higher), "b" by "d" (two places higher), "c" by "f" (three places higher) and so on. Try changing the second code number in the code maker and see how much more difficult trying to break the code will be.

Source: http://web.archive.org/web/20120818085711/http://www.puzzlepixies.com/activites/activites/make-secret-codes.html

Is there a name for this type of shift?


texts: RSA: Given two very large prime $p,q$ and $n=p\;q$, how to quickly find $e$ such that $\gcd(\varphi(n),e)=1$?

texts: I can imagine that finding $p,q,n$ are easy, but my text book also says the $e$ can be found rapidly, so how does modern RSA find this $e$?


texts: Authenticated AES 256 CBC HMAC SHA512 - What's the right way to implement in C#?

texts:
I have a "Encrypt-then-Mac" C# implementation of "AE_AES_256_CBC_HMAC_SHA_512" WITHOUT associated data, only authentication. In my code, I follow these steps to encrypt strings:

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

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


texts: Using scrypt to generate key + IV/nonce together

texts:
Is there any security issue in using scrypt for Key + IV/nonce generation? In other words, can I safely use only a salt for scrypt and derive the nonce along with the key?

For example:

I have data I want to encrypt using password and AES in EAX mode. I want to use scrypt key derivation function to make a key from entered password. So I will need a salt for scrypt and a nonce for EAX. Both values need to be stored somewhere and it seems to be quite redundant. So instead I generate 384 bits of output using scrypt and use the first 256 bits as key and last 128 bits as nonce for EAX.


texts: Can I use guids / uuids as counters for key derivation?

texts:
I have a 512 bit master key, and 128 bit unique identifiers.  I'm going to derive 256 bit keys to for use with deterministic and block ciphers.

For reference, The KDF I'm going to use is Hash( C | Z).

The implementation will be SHA256( uuid | master key).

I don't particularly care if SHA256 generates collisions as I never intend to store the derived key.

It think this will be fine, but would love a second opinion.


texts:
On page 7 of NIST's views on SHA-3's security requirements and Evaluation of attacks, I see that, at least at this point, NIST planned on offering SHA-3 having eTCR security (defined on page 3):

  eTCR: Find $M$ and then for a randomly chosen $r$, find $M’$
  and $r’$ s.t. $H_r(M) = H_{r’}(M’), (r,M) ≠ (r’,M’)$ where
  $H_r$ is the randomized hash.

However, I never saw any subsequent references to the eTCR property for the SHA-3 candidates.

Does SHA-3 have an eTCR mode?


texts: Improving differential cryptanalysis of a vulnerable cipher

texts:
How to avoid differential cryptanalysis attacks when you are inventing new cipher?
Let's say you have a $16$-round $128$-bit cipher vulnerable on differential cryptanalysis attacks. Now let's say you will add between every round:

bitwise NOT (optional you make it ot not - randomly),
xor with $128$-bit subkey,
moving bits by $0$ to $127$ places.

Now it looks like the attacker have to guess many variables first (we defined it by keys), to make differential cryptanalysis attack. Because he can do it easily only without this obstructing steps between rounds. Is it good idea to use it, if I would like to make cipher resistant on differential cryptanalysis?


texts: How to determine the shift key to decrypt a ciphertext which was encrypted using Caesar cipher?

texts:
So I found this question in a model paper,

  Break ciphertext ”BJJY GPXF DI TJPM ZSYH” which is encrypted by a
  Caesar Cipher.

This gives a meaningful plaintext if we use 21 as the shift key. So the answer is

  "GOOD LUCK IN YOUR EXAM"

Do we have to find the shift key by guessing all the possible keys until we find the correct one, or is there any other way to find it?


texts: Comparing n-multiple amount of merkle trees?

texts:
I would like to know what best steps are there in finding differences between a high order amount of merkle tree's or if a better associative structure should be used.

I ask this questions because while i have found on comparing two trees for differences i have not found any specifics on comparing n amount at the same time (100-200 for ex).

While i would imagine a sequential validation process from one tree to the next, my question would be if there are any general way to do so.


texts:
Does ISAAC use key scheduling? I do not know programming.

Is it safe if ISAAC derives subkeys using ISAAC itself?


texts: ECDSA Message Recovery from Two Encrypted Messages with Signatures and Public Key

texts: I am currently working on a problem where I have two encrypted messages, their corresponding signatures, and the public key. Furthermore, the value of $r$ is the same in the two signatures. I am trying to recover the plaintext messages and stumbled upon the Wikipedia : Elliptic Curve DSA page that explains that one can recover the private key given two cleartext messages, and their corresponding signatures where r is the same in both signatures. The problem is I don't have the cleartext messages, so I am wondering if it is possible to derive the private key and subsequently decrypt the messages from the givens that I currently have.


texts: Parallel Composition of ($\epsilon, \delta$) differential privacy

texts:
I know that if there are $n$ functions $M_1, M_2, \cdots, M_n$ computed on disjoint subsets of the private database whose privacy guarantees are $\epsilon_1, \cdots ,\epsilon_n$ differential privacy, respectively, then any function $g$ of them: $g(M_1, \dots,M_n)$ is $$(\max_i \epsilon_i)$$differentially private.

This is known as the Parallel Composition Theorem.

My question is: does this Parellel Composition Theorem extend to $(\epsilon, \delta)$ differential privacy? In other words, is the following statement true?:

If there are $n$ functions $M_1, M_2, \cdots, M_n$ computed on disjoint subsets of the private database whose privacy guarantees are $(\epsilon_1, \delta_1), \cdots ,(\epsilon_n, \delta_n)$ differential privacy, respectively, then any function $g$ of them: $g(M_1, \dots,M_n)$ is $$(\max_i \epsilon_i, \max_i \delta_i)$$differentially private.

If this statement is NOT true, then what bounds are there are on the privacy of the composition function $g$.


texts:
I'm trying to get my server to establish trust with a client.  Neither is on the Internet, so there are no certificate authorities.  The typical way to establish trust in my domain is for a client to "request a seed", the server provides a seed, and the client "provides a key", and the server "verifies the key".  (In case you are curious:  ISO 14229-1,  Unified Diagnostic Services)  There is no required way to generate either the seed or the key, or to verify it.

Assuming I can properly generate an RSA asymmetric key pair and distribute it, the server holds the public key (n, e) and the client holds the private key K.  Assume good cryptographic hashes, strong random number generators, appropriate retry timeouts to prevent replay attacks, etc.

Is the private key vulnerable in the following scheme?

Server provides the seed:  A random number M.
Client signs said seed (S = RSASSA-PKCS1-V1_5-SIGN(K,M))  and sends the signature to the server.
The server verifies that signature (RSASSA-PKCS1-V1_5-VERIFY ((n, e), M, S)).
If the signature could be verified with the public key, then the client can be trusted.

I'm worried about a known-plaintext attack:  I see the private key getting mixed into the signature, unlike with encryption where only the public key is mixed into the output.


texts: Computational Complexity of SHA-3 (SHAKE128)

texts:
Please, I got the question "what is the computational complexity of SHA-3 (SHAKE128)"?

What does that mean and how can I calculate that??

*I am using SHA-3 (SHAKE128) in my mechanism to hash fix input (100-bits).

Thanks in advance...


texts:
I've seen pseudocode of this form in the Montgomery multiplication related theses: $(C, S) := a[j]*b[0]+C$.

What's the meaning of "$(C, S):=$", or what is the real code that was converted from this pseudocode like?


texts: Secure Computation: Reactive Functionalities in the Hybrid Model for Standalone Security

texts:
A common approach to make (secure computation) protocol descriptions and proofs simpler is to describe them in a hybrid model, where the protocol in the real world has access to some auxiliary ideal functionality F (e.g. an ideal OT functionality). Lets say I only care about standalone security (vs. UC). Assuming all calls to F are sequential (i.e. not interleaved or in parallel) and the parties do not communicate with each other in between starting a call and finishing it, then (as far as I understand) I can use regular sequential composition of standalone secure protocols to instantiate the hybrids with standalone secure protocols to obtain an overall standalone secure protocol.

My problem is with reactive functionalities, i.e. functionalities that keep a state and, for the sake of concreteness, with commitments.
Say, for example, I want to prove Blum's coin tossing protocol secure in a commitment hybrid model (see here for the protocol and a proof, which is not in the hybrid model).

Protocol recap: Alice and Bob want to toss a fair coin:

Alice commits to a random bit $r_a$.
Bob publishes a random bit $r_b$.
Alice opens commitment and the output of the protocol is defined as $r_a \oplus r_b$

It seems I run into a problem, because I cannot instantiate my hybrid with a standalone secure commitment scheme, because in between Alice doing the commitment and Alice opening it, the parties communicate.

What is the most common way of circumventing the issue?
The only thing I could find right now was in Complexity of Multi-Party Computation Functionalities, where the authors state (in Footnote 8 on page 6):

  A reactive functionality can be reduced to a non-reactive
  functionality by secret-sharing the internal state of the functionality among all n parties

I don't understand what this means. What does it mean (concretely for the example of coin tossing) and is this the most common approach of handling my described issue in the coin tossing example?


texts:
Is there any problem with using social media (i.e. Facebook) as a directory of public keys?

For example, couldn't Alice put a note containing $(g^a \bmod p, g, p)$ on her Facebook page so she could receive email attachments which have been encrypted with the common secret value?

That is, Bob would encrypt his message with the value obtained from $(g^a)^b \bmod p$ and send it along with in-the-clear $g^b \bmod p$ to Alice.  She then can decrypt the message.

If everyone were to publish their public keys, wouldn't this defeat most "man-in-the-middle" attacks?


texts: What SALT value will be used in HKDF_EXTRACT in TLS1.3?

texts: What SALT value will be used in HKDF_EXTRACT while generating the Handshake Secret (when there will not be any PSK)?


texts:
I'd like to use the Itoh-Tsujii algorithm for a dynamic substitution table, but I do not get the following line:
$$r\ \gets\ (p^m - 1)\,/\,(p - 1)$$

And why can $r$ be used to calculate the multiplicative innverse of a number in a Galois field containing $p^m$ elements by calculating it in the field $GF(p)$ and use this result to calculate the inversion in the $GF(p^m)$ field?


texts: Why is pqRSA in the NIST PQC submissions?

texts: In the NIST post-quantum cryptography workshop, the round one submissions included pqRSA. If memory serves, this is an implementation of RSA using the product of a very large number of 4096-bit primes to protect against Shor's algorithm. It requires something like a terabyte of private key material. Why was this submitted to NIST given that its impracticality obviously disqualifies it?


texts: How do I construct and use the Okamoto protocol simulator?

texts:
Proof Okamoto protocol has zero knowledge if we constructing a suitable simulator

I found the following schema of Okamoto:

But I don't really understand —how can I construct such a simulator and create proofs?


texts:
In the book "Introduction to Cryptography with Coding Theory ", in the chapter about the Differential Cryptanalysis for Four Rounds for DES algorithm, the authors say:

  There is a weakness in the box $s_{1}$. If we look at the 16 input
  pairs with XOR equal to 0011, we discover that 12 of them have output
  XOR equal to
  011. Of course, we expect on the average that two pairs should yield a given output XOR, so the present case is rather extreme. A little
  variation is to be expected; we’ll see that this large variation makes
  it easy to find the key. There is a similar weakness in $s_{1}$,
  though not quite as extreme. Among the 16 input pairs with XOR equal
  to 1100, there are 8 with output XOR equal to 010.

I've understood the attack in case of a 3-round scenario.
However, it's not clear to me how this particular weakness of sboxes is used in order to attack the DES algorithm in a 4-rounds scenario.
Can you explain to me ?

ps: you find the book writing on google "Introduction to Cryptography with Coding Theory pdf" and taking the first link. The related chapter is 4.3


texts:
Following @poncho's nice clarification of the RSA speedup here, let's see if I'm able to do the same in the case of the DGK cryptosystem:

We have pk = (n, g, h, u), sk = (p, q, $v_p$, $v_q$) which are generated as following:

we have 3 numbers, $k > t > l$
we pick u as the next prime greater than $2^{l+2}$ (having more than $l + 2$ bits)
we pick 2 random t bit primes, $v_p$, $v_q$
we generate p and q primes of length $k/2$ bits such that u and $v_p$ divide $p-1$ and u and $v_q$ divide $q-1$
we generate h of order $v_p*v_q$ modulo p and q
we generate g of order $u*v_p*v_q$ modulo p and q

Encryption: $E(m,r) = g^mh^r\pmod n$
Decryption: $E(m,r)^{v_p} = (g^{v_p})^m\pmod p$, which determines m uniquely, so we precompute all possible values of the right side (since the message space, u, is really small) and during decryption we just search for $c^{v_p}$ among the precomputed values. Later edit: The correction to the original paper states that $c^{v_p}$ uniquely determines m, so it's not necessary to use $c^{v_pv_q}$. I am not able to figure out how they came to this conclusion, but it does seem to work.

I know that there are a lot of details missing, but for those that are curious, I suggest reading the entire paper and the subsequent security correction (which replaces v with $v_p$ and $v_q$).

Now, we want to speed up the encryption process, since those exponentiations modulo n are rather slow, so we express $E(m,r)$ in $\mathbb{Z}_n^*$ as $E_p(m,r)$ and $E_q(m,r)$ in $\mathbb{Z}_p^* \times \mathbb{Z}_q^*$:

$E_p(m,r) = g^mh^r \pmod p$
$E_q(m,r) = g^mh^r \pmod q$

Now we apply the Chinese Remainder Theorem in order to obtain $E(m,r) \pmod n$. The formula used to achieve this is: $$\sum_{i} a_i \frac{N}{n_i} \left[\left(\frac{N}{n_i}\right)^{-1}\right]_{n_i}$$

So we have: $$E(m,r) = E_p(m,r)*q*(q^{-1}\bmod p) + E_q(m,r)*p*(p^{-1}\bmod q) \pmod n \Rightarrow$$

$$E(m,r) = (g^mh^r \bmod p)*q*(q^{-1}\bmod p) + (g^mh^r \bmod q)*p*(p^{-1}\bmod q) \pmod n$$

The above formula seems to make sense, right? Right?

Because further optimization is required, I need to somehow compute the above formula in two steps. More precisely, the random numbers can sometimes be generated in a different process, so I need the ability to split $E(m,r) = g^mh^r\pmod n$ in half:

first compute $E_{nonrand}(m,r) = g^m \pmod n$
then randomize: $E(m,r) = E_{nonrand}(m,r) * h^r\pmod n$

My intuition tells me that in this case I can still perform the encryption speedup and the formula should look something like this:

$$E_{nonrand}(m,r) = (g^m \bmod p)*q*(q^{-1}\bmod p) + (g^m \bmod q)*p*(p^{-1}\bmod q) \pmod n$$

$$E(m,r) = E_{nonrand}(m,r) * [(h^r \bmod p)*q*(q^{-1}\bmod p) + (h^r \bmod q)*p*(p^{-1}\bmod q)] \pmod n$$

I tested this formula and it seems to work, but I am unsure that I'm doing it right... Also, is it OK to skip the $\pmod n$ operation when computing $E_{nonrand}(m,r)$? It seems to me that it is redundant.


texts: When using same nonce in OCB mode of authenticated encryption, how forgery attack can be done?


texts: Key Size for Symmetric Homomorphic Encryption Over the Integers

texts:
In the paper Fully Homomorphic Encryption over the Integers, it mentions a symmetric key scheme on page 1 and 2.

Key Generation: Pick a random odd number $p \epsilon [2^{N-1},2^N)$
Encrypt A Bit m: $c = pq + 2r + m$
Decrypt A Bit c: $m = (c \% p) \% 2$
Homomorphic XOR: $result = c + c'$
Homomorphic AND: $result = c * c'$

Note that when encrypting a bit, $q$ is a random number to help hide the key, and $r$ is a small noise value to turn breaking the encryption into a "learning with error" problem.  $N$ is effectively the number of bits in the key.

In the second to last paragraph on page 1, the paper suggests these values to make the above secure:
$r ≈ 2√N$
$q ≈ 2N^3$

However, the font used is rather unfortunate and I can't tell if the paper means the way i wrote it above, or the way I wrote it below:
$r ≈ 2^{√N}$
$q ≈ 2^{N^3}$

Is anyone able to understand which way it should be?  Also, I'm kind of curious where these specific values for security came from, if anyone is able to shed light on that.

Edit:

Later in the paper, on page 5, it talks about how to calculate some parameters for the public key implementation:

  γ is the bit-length of the integers in the public key
  η is the bit-length of the secret key (which is the hidden approximate-gcd of all the public-key integers),
  ρ is the bit-length of the noise (i.e., the distance between the public key elements and the nearest multiples of the secret key), and
  τ is the number of integers in the public key

  These parameters must be set under the following constraints:
  • ρ = ω(log λ), to protect against brute-force attacks on the noise;
  • η ≥ ρ · Θ(λ log^2 λ), in order to support homomorphism for deep enough circuits to evaluate the “squashed decryption circuit” (cf. Sections 3.2 and 6.2);
  • γ = ω(η^2 log λ), to thwart various lattice-based attacks on the underlying approximate-gcd problem (cf. Section 5);
  • τ ≥ γ + ω(log λ), in order to use the leftover hash lemma in the reduction to approximate gcd (cf. Lemma 4.3).
  We also use a secondary noise parameter ρ′ = ρ + ω(log λ). A convenient parameter set to keep in mind is ρ = λ, ρ′ = 2λ, η = O˜(λ^2), γ = O˜(λ^5) and τ = γ + λ. (This setting results in a scheme with complexity O˜(λ^10).)

It never explains what ω is.  Is that some commonly known notation?  How did the "convenient parameter set" come from those formulas?

Also, what exactly does it mean when they say that using that parameter set results in a scheme with complexity O˜(λ^10)?  Does that mean that the attack against the encryption has that for complexity?  I'm wondering about the case where maybe increased speed is desired, even at the cost of decreased security, to understand what to change to get those results.


texts: Modular exponentiation on calculator for textbook RSA

texts:
How do you encrypt $51$ with public key $(n,e) = (91,23)$

I understand that $c = 51^{23} \bmod 91$.  How can I calculate the result on a calculator?


texts:
(a) Briefly explain the following round transformations of AES Encryption. Please indicate
if it helps diffusion or confusion or both.

SubBytes
ShiftRows
MixColumns
AddRoundKey
(b) Suppose you are computing one round of AES. In MixColums step, one row of your input
is 21A07C3D. Compute the multiplication of 03010102 by 21A07C3D.
Note that: The irreducible polynomial is P (x) = x 8 + x 4 + x 3 + x + 1.


texts: Does length-prepending stop length-extension attacks?

texts: Does length-prepending stop length-extension attacks on Merkle-Damgård hash functions, assuming that the length is checked?


texts:
I have some basic understanding of ECC - but pretty far from advanced concepts. I've been reading about BLS12-381 curve here and here, but I can't seem to fully understand it.

The things that I think I understand:

The order of the curve is $≈2^{381}$
The security level of the curve is 126 bits

The things that I don't understand:

What is the size of the private key for this curve? Assuming I'm right about the order, is it 381 bits?
The materials mention two generator points which produce public keys of different size - why is that? Shouldn't all points on the curve be of the same size?
What exactly is the subgroup $r$ and what is its significance?


texts: Perfectly secret cipher can leak about the key?

texts:
As defined by Shannon, a cipher is perfectly secure if ciphertext leaks no information about the plain text.

Under this definition, can ciphertext leak something about the key? Are there any ciphers for which this is true?


texts: How to encrypt the number one using RSA?

texts:
for example: if we have public key : (5,221) and private key : (77,221) and we want to encrypt 1:

c(m) = (m)^p mod n
c(m)=(1)^77 mod 21 =1

so how to deal with that? is there some work around ?


texts: Is the security of MAC function is based on HASH function

texts: It is widely known, generally, that a MAC is a HASH with key. I just want to ensure that my understanding is correct to avoid base further assumptions on wrong conception. So, if I used MAC that uses strong key but weak HASH such as MD-5. Does this means my MAC does not provide security and can be forged?


texts:
how to break a transposition cipher, especially a turning-grille-cipher?

For example:

$\begin{array}{rrrrrr}
T & E &R& E & W& E \\
E & E&  & N & P & Q \\
T& U & I & A& G & H \\
Y & - & L & T &U & T \\
S& L & E & S & E &   \\
  & N& T & O& H&   \\
\end{array}$

How would you break this cipher? Could you maybe give me a short step-by-step-explanation?

Please note: The spaces are there purposely and the text is in English.


texts: State of the art in zero knowledge proof compilers?

texts:
What is the current state of the art zero knowledge  proof compiler ? I need one that can minimally handle double exponentiation  by a known value  E.g.

$$Pok\{(\alpha):h=g^{\alpha^b}\} $$
where b, g and h are public but $\alpha$ is secret.

Preferably it should be able to handle double discrete log proofs E.g.

$$Pok\{(\beta):h=g^{a^\beta}\} $$ where a, g and h are public and $\beta$ s secret.

ZKPDL does not handle at least the later case.


texts: What are Cryptographic Multi-linear Maps?

texts:
I've encountered this term many times in the fields of Fully-Homomorphic Encryption and Obfuscation.

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

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


texts: Reversing Diffie Hellman from the secret

texts:
This is a homework assignment that's been giving me some trouble:

By eavesdropping on a Diffie-Hellman key exchange, we observe

modulus $p$

the base $3$

$A\ =\ 3^a \bmod p\quad$ and

$B\ =\ 3^b \bmod p$

If we somehow had access to the
secret $=\ 3^{ab} \bmod p$,
how could you retrieve the secret exponents $a$ and $b$?

$p$ is 996-bit. $A$, $B$ also are very large numbers. I think I am missing something about exponential arithmetic. I've tried working on the actual numbers using PARI/GP, but the numbers are too big to use the built-in discrete logarithm functionality.


texts: Knowing that $G(s)$ is a PRG, is the following construction $G'(s) = G(s||0)$ a PRG?

texts: I know there already is a very similar question. However, I can't understand why $G'(s)$ is not a PRG. If $G(s)$ is a PRG, then why $G(s||0)$ can't also be a PRG? How can the distribution over $G(s||0)$ be distinguished from a truly uniform distribution of the same output range?


texts: AEAD: Is it secure to decrypt the content encryption key before verifying the MAC?

texts:
The JSON Web Encryption (JWE) standard defines a number of encryption modes with the same basic form:

First, the a unique content encryption key (CEK) is generated and used to encrypt the payload with associated data in an AEAD mode (e.g. AES-CBC with HMAC or AES-GCM). If a separate block cipher and MAC are used then the individual keys for each are concatenated to form the CEK.
Then, the CEK is encrypted with the public key of the recipient (e.g. using RSA with PKCS#1 v1.5 padding) and the result is prepended to the ciphertext.

My question is: while the underlying symmetric cipher provides authenticated encryption, the recipient must decrypt the CEK before they can verify the MAC on the underlying AEAD construction. Does RSA with appropriate padding when used just for key wrapping already provide authenticated encryption?


texts:
I created my PGP key in 2000. I’ve revoked the older, weaker sub-keys in favor of a 4096-bit RSA one, but the primary key is 1024-bit DSA. I read on Wikipedia that…

  NIST 800-57 recommends lengths of 2048 for keys with security lifetimes extending beyond 2010.

Should I consider my primary key insecure?
If so, is there any way to replace it without revoking my entire key and creating a new one?
If my primary key were compromised, the attacker would be able to create signatures as me, but they wouldn’t be able to decrypt information that was encrypted to my public key, right?


texts: How can I obtain the raw decimal value of an RSA key's modulus?

texts:
So maybe I'm thinking about this too hard, or maybe I'm missing a piece of information.

We'll use Google for this example. Say I wanted to obtain the modulus of Google's current public key.
Well I can do this relatively simply using OpenSSL:

  openssl s_client -connect www.google.com:443 | openssl x509 -text -pubkey

Great, so now I export that into a pem file. So now I have their certificate and their public key. Let's discard their certificate for this instance.
Also using OpenSSL, I can list the raw hexadecimal value of the modulus:

  openssl rsa -in pubKey.pem -pubin -text -noout

Now that lists this information:

Public-Key: (2048 bit)
Modulus:
    00:c3:d5:12:42:8a:36:02:f5:77:01:8b:f6:83:2f:
    ab:c5:c7:00:e4:c0:3e:94:33:3a:2e:7a:2d:37:30:
    c0:6c:75:67:d4:13:d0:30:b1:11:34:16:21:6f:95:
    99:b0:f6:31:3c:55:51:b9:3f:8c:c3:63:50:b9:d0:
    03:7f:bb:76:53:66:80:4e:3e:51:d6:77:e6:5c:f5:
    38:b1:19:88:7b:86:f8:2d:39:d0:12:4c:d0:6a:5e:
    37:f1:bb:22:47:ec:d8:08:ca:06:81:44:4b:11:ef:
    51:aa:e6:96:b8:ad:ed:6b:15:be:01:4b:bc:60:c9:
    df:42:0a:df:d3:8b:e5:b0:03:ac:18:ef:c3:f8:3a:
    96:5e:a6:77:61:fe:36:1e:f5:f2:aa:83:1f:69:d4:
    79:5d:69:a9:d9:a1:18:a2:98:cd:e6:3d:5b:1e:0f:
    a9:66:c8:42:f2:ba:b0:74:e8:5f:b3:b5:30:6d:79:
    a9:e8:9f:9c:23:5f:51:aa:36:2e:35:a7:9a:08:76:
    f9:46:f0:34:de:70:1a:3d:4e:f7:34:68:e4:43:75:
    bf:20:58:54:66:1c:9f:6d:9b:9d:28:21:15:ae:89:
    a7:e9:6f:75:7e:22:49:93:85:c6:a4:c5:2b:1a:23:
    92:f9:eb:8f:67:a8:26:56:e1:9f:66:e5:74:2a:01:
    0c:17
Exponent: 65537 (0x10001)

Great! I have the hexadecimally encoded modulus.
I've read many articles and have seen many websites that offer this, but, for future purposes, I'll just say that I don't necessarily prefer uploading keyfiles (public or private) to external services and "hoping" that they don't record it.

For experimental purposes, how might I obtain the plain decimal version of this modulus using a local client in Linux? I've seen a lot of posts showing that people have done it, but I'm having trouble figuring it out for whatever reason.

Also, I've heard a little bit about the prefixing "00" of this hexadecimal string (00:c3:d5:12:42...), about how it's just a bug. Can you give me more information on this, such as why it occurs and if it's relevant?


texts:
From wikipedia: "They differ in the word size; SHA-256 uses 32-bit words where SHA-512 uses 64-bit words."

In this context what do they mean with words? is it the same as a 32 bit (or 64 bit) block in a block cipher? just simply the size in which it divides up it's input?


texts: Block cipher's output in case of uniformly drawn input

texts:
Consider a block cipher $E_k$ where $k$ is an arbitrary key. $E_k$ takes input messages from $\{0,1\}^n$ and outputs a ciphertext $c\in\{0,1\}^n$. Let $m$ be an input message which is uniformly drawn from $\{0,1\}^n$ and let $c = E_k(m)$.

My question is simple - is $c$ also uniformly distributed in $\{0,1\}^n$?

Note: I know that $c$ has to be indistinguishable from a uniform distribution, but I ask if it is actually uniformly distributed. I'd appreciate a proof (or proof sketch) in case it is.

Thanks


texts: Testing Kasiski Test and Mutual Index of Coincidence on Vigenere Encryption on Vigenere Encryption?

texts: I was learning about Vigenere Ciphers and its various cryptanalytic attacks. One of them was, Kasiski test and Mutual Index of Coincidence. So, I was wondering can Kasiski test and Mutual Index of Coincidence crack the Vigenere encryption of Vigenere encryption itself (keys may be different or same) i.e. plaintext encrypted using Vigenere cipher and the output of this again encrypted using Vigenere cipher? Will using such scheme create appropriate confusion for the attacker or will it act as a vulnerability?


texts: Can N, q be shared for multiple users when using SRP-6A

texts:
Is it considered bad practice to use the same N and q parameters for all users in an SRP-6A based authentication system?

I know that q MUST be a Sophie Germain prime and N a safe prime, but can they be generated ahead of time and be somewhat fixed / hardcoded in the client and server? Or should I generate a fresh pair for each new user registration?

I imagine, it's better to have a different one for each account, but if it's not affecting the security of the system in any way...


texts: The definition and origin of Schnorr groups?

texts:
Wanting to write something on Schnorr groups in a publication I realised how hard it is to find anything citable about them on the internet. Who can help me with the following questions?

What (and where) is the actual definition of a Schnorr group? Are all of its criteria fulfilled if it is a multiplicative finite cyclic group with a prime order? In the answer to What is a cyclic group of prime order q such that the DLP is hard? it sounds like it is only a Schnorr Group if the $r$ in $p = qr + 1$ is $r>2$?
Where have Schnorr groups first been introduced and who called them Schnorr groups? I checked the references in Security of Schnorr signature versus DSA and DLP, but I could not find anything useful in Schnorr's patents and his papers start off directly with:

  The KAC chooses primes $p$ and $q$ such that $q \mid p - 1, q \le 2^{214}, p > 2^{512}$, $\alpha \in \mathbb{Z}_p$ with order $q$, i.e., $\alpha^q = 1 \pmod{p}$, $\alpha \neq 1$

So they already use Schnorr groups, but neither do they call them that nor do they give a procedure how to generate them. Which leads into my next question:
Where was a procedure to generate Schnorr groups first published? The Wikipedia article only gives a procedure without source, which is basically the same as in FIPS PUB 186-4, A.1 even though there it is not even called Schnorr group (proably due to patent reasons?).

UPDATE: Digging deeper I found this in PS96:

  results for other signature schemes like Schnorr's are considered as folklore results but have never appeared in the literature

"Folklore results"? Maybe that's why Schnorr groups are so difficult to grasp.


texts: Paillier Cryptosystem - Practical applications?

texts:
I wonder: are there any real-world practical applications using the Paillier cryptosystem , as introduced in [1], or some derivations of it?

I'm aware of quite a few schemes proposed in literature how to use it for voting, zero-knowledge proofs and such, and also of many prototypical implementations online, but I can't seem to find any application where a Paillier(-based) scheme was effectively used...(also, I don't think there is any standard defining it).

[1] Paillier, Pascal (1999). "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes". EUROCRYPT. Springer. pp. 223–238


texts: Can one calc the 16 subkeys in DES in one step ? I mean that we create for example a new “box“ where we directly permute the key k in 16 subkeys


texts: El Gamal Cryptosystem Proof, Step-by-Step Explanation Needed. I feel like I don't understand what I have on this proof

texts:
Can someone provide a good and thorough explanation of the El Gamal proof? Basically, I need a step-by-step breakdown of what is happening at each important part in the algorithm.

I haven't been able to find any good notes on El Gamala that explain the proof in an easy to understand format.

Here is the proof in this image:


texts: Determining which encryption algorithm to use

texts:
I'm a traditional software engineer.  Recently, due to the nature of a current project, I have been exposed to many cryptographic libraries--there are so many encryption algorithms!

How do you choose the right algorithm for your application? What advantages/disadvantages do different types of algorithms bring with them?. Is there one algorithm that could be seen as the "standard" that should always be used?


texts: Why round off vector sampling from continuous Gaussian distribution not directly sample from discrete Gaussian distribution

texts:
For any vector $\mathbf{c}$, real $s > 0$, and lattice $\Lambda$, define the probability distribution $D_{\Lambda, s,\mathbf{c}}$ over $\Lambda$ by
  $$D_{\Lambda, s,\mathbf{c}}(\mathbf{x})=\frac{D_{s,\mathbf{c}}(\mathbf{x})}{D_{s,\mathbf{c}}(\Lambda)}=\frac{\rho_{s, \mathbf{c}}(\mathbf{x})}{\rho_{s, \mathbf{c}}(\Lambda)}, \forall \mathbf{x} \in \Lambda$$
  where $\rho_{s, \mathbf{c}}(\Lambda)=\sum_{\mathbf{x} \in \Lambda}\rho_{s, \mathbf{c}}(\mathbf{x})$.

We refer to $D_{\Lambda, s,\mathbf{c}}$ as a discrete Gaussian distribution.

Many algorithms sample a vector from continuous Gaussian distribution $D_{s,\mathbf{c}}$ and round off(then the sampling vector is distributed by discrete Gaussian distribution), instead of sampling vector directly from $D_{\Lambda, s,\mathbf{c}}(\mathbf{x})$ by computing $\frac{\rho_{s, \mathbf{c}}(\mathbf{x})}{\rho_{s, \mathbf{c}}(\Lambda)}$.

I think that the reason why a vector is not sampled directly computing $\frac{\rho_{s, \mathbf{c}}(\mathbf{x})}{\rho_{s, \mathbf{c}}(\Lambda)}$ is that computing $\rho_{s, \mathbf{c}}(\Lambda)=\sum_{\mathbf{x} \in \Lambda}\rho_{s, \mathbf{c}}(\mathbf{x})$ costs expensive. Because a lattice $\Lambda$ has many vector.(for example, the lattice $\mathbb{Z}^n$ where error is sampled in LWE). Whereas $D_{s,\mathbf{c}}$ costs not expensive.(because $\rho_{s,\mathbf{c}}(\mathbb{R}^n)=s^n$, so $D_{s,\mathbf{c}}=\frac{\rho_{s,\mathbf{c}}(\mathbf{x})}{\rho_{s,\mathbf{c}}(\mathbb{R}^n)}=\frac{\rho_{s,\mathbf{c}}(\mathbf{x})}{s^n}$)

If it isn't, in order to get samples from discrete Gaussian distribution, why many algorithm sample from continuous Gaussian distribution then round off?


texts: HMAC for encrypted authentication token: recommended iteration number

texts: In the web application I use 10,000+ iterations for hashing passwords stored in database (random salt and all). Password-related operations are not frequent enough to create a noticeable performance hit. Signing authentication tokens is a different story. This happens on every token renewal which may happen on every request but in practice is configured to happen at least every X seconds. I cannot find any recommendation as to the number of iterations for generating HMAC for encrypted payload such as the token. What are the risks of using a very low number, let's say 10? I use 24 byte salts.


texts: Secure scheme to share symmetric key using asymmetric keys and certificates with N parties

texts:
I need to distribute symmetric AES key into number of end points which will use it to decrypt data. The AES key will be the same on all end points, it is not possible to generate unique on every end point.

I am thinking about using asymmetric keys and certificates stored on USB cryptographic token to provide access to encrypted AES key and decrypt it with private key.

Is there any cryptographic scheme that can ensure that N of private keys will be able to decrypt AES key (assuming that the cryptogram of AES is same on all endpoints)?

The AES should be encrypted by public key and distributed.


texts:
According to this:
http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/rsa.pdf

One can calculate the message m, if there was no padding scheme involved.

My question: is it possible to find m if the $n_a n_b n_c$ moduli are unknown?

Also: if one can see the encrypted version of a known plaintext, can one find the modulus?


texts:
Can we have single hash function both for data integrity and key derivation function? Why and Why not?
Any link describing difference analytically will be appreciated.
Thanks.


texts: Triple DES: Does knowing the plaintext limit my keyspace for brute force?

texts:
My goal is to try and decrypt a single 8 byte block of a Triple DES encrypted data block and in doing so discovering the 8 byte keys that were used.  This is mostly an academic exercise but could solve a real world problem.

I know the plaintext data is 7 numbers in ASCII encoding with what I believe is a 0x0 padding on the end, Eg. 0x30-0x39.  There is a roughly 20% chance that my block is in fact a plaintext data that I already know, it could be potentially one of three values.  Triple DES ECB mode, either two 8 byte keys or three 8 byte keys were used but I can't be completely sure.

Through core dumps a colleague collected 5 different 8 byte sequences that I have suspicion are either the keys, or at least could be part of the 2 to 3 sets of keys.  I wrote a program to attempt every possible combo for EDE2 and EDE3 and none of them turned up any sequences of 0x30-0x39.

I also know that the application in question utilizes a key schedule to generate encryption/decryption keys, but am unsure if this would be required or if it would help me to identify the keys used.

Knowing so much information about the encrypted 8 byte block, does this provide any possible exploits or clues to the possible keyspace if I were so inclined to search it brute force?  I am kind of a crypto noob so I am wondering if this does narrow the key space is it still feasible to brute force with commodity hardware?


texts: Public Key Encryption, how do you handle not trusting the middle man?

texts:
With public/private key encryption you must trust the central authority correct?

What can you do if you don't want to trust the centeral authority? Are there any ways around that?

for example in a chat app

I imagine, no matter what, you will have to make the client open source so as to keep it known you are not saving the users private keys.


texts: Encrypting the relationship between two database tables

texts:
I'm not a cryptography expert myself, and know enough to know that I shouldn't design my own crypto schemes, so I thought I'd seek advice here.

In an application, let's say we have two database tables: Lawyers and Clients. There exists a many-to-many relationship between these two models, so a Lawyer can have many Clients and a Client can have many Lawyers. As is typical in relational databases, there is a Join Table containing pointers to rows in each table in order to define the relationships between them.

The columns for the Join Table might look like this:

id | client_id | lawyer_id

Now let's say that in our security model, information about lawyers and information about clients are not considered privileged information on their own, so there's no need to encrypt them in any way. However, information about the relationship between Lawyers and Clients is privileged information that we would like to protect in the event an attacker gains access to the database.

Does there exist a common encryption scheme that securely encrypts client_id and lawyer_id without rendering the Join Table useless?


texts: Adding identical homomorphically encrypted inputs

texts: What would happen if you added two inputs, one known and one unknown, both encrypted with a fully homomorphic encryption scheme, and then checked the result by dividing it by two? Wouldn’t this tell you if the data is identical?


texts: How many codes can I safely generate using the same HMAC key?

texts: Can an attacker guess the key given enough codes for the same key? And if so, how many times is it safe to use the same key?


texts:
While researching the topic of random number generation, especially practical aspects of using TRNG devices on different platforms, I found this code in MacOS kernel sources.

int
write_random(void* buffer, u_int numbytes)
{
#if 0
    int     retval = 0;
    prngContextp    pp;

    lck_mtx_lock(gPRNGMutex);

    pp = current_prng_context();

    if (ccdrbg_reseed(prng_infop(pp), pp->statep,
              bytesToInput, rdBuffer, 0, NULL) != 0)
        retval = EIO;

    lck_mtx_unlock(gPRNGMutex);
    return retval;
#else
#pragma  unused(buffer, numbytes)
    return 0;
#endif

Unless I'm wrong, this code snippet means that MacOS's random number generator cannot ever be manually reseeded by writing random data to /dev/random.

Is there some good reason for not allowing user-level reseeding in an operating system's random number generator?

Or maybe there are some other ways to do it? (Using securityd somehow?)


texts: openssl sha1 message digest not matching with NIST vector input?

texts:
When I call openssl sha1 from the command line

 echo "00" | xxd -r -p | openssl dgst -sha1

the output I am receive is

(stdin)= 5ba93c9db0cff93f52b521d7420e43f6eda2784f

But the NIST Vector output is:

 MD = da39a3ee5e6b4b0d3255bfef95601890afd80709

Can anyone please explain this?


texts: Pseudo Random Generator (PRG) not deterministic

texts:
Usually a Pseudo Random Generator is supposed to be IND-CPA secure.

But apparently, it is not in some cases such as the following:

A PseudoRandom Generator $G$ has expansion factor $n + 2$.
Encrypt $m \space \in \{0,1\} ^ {n+2}$
Choose a random value $v \leftarrow \{0,1\}^n$
Then send $(v, G(v) \oplus m)$

The question is why is it not IND-CPA secure and also not IND-EAV secure?


texts: Possible to check if $a \in \mathrm{QR}_n$?

texts:
It is possible to check $a \in \mathrm{QR}_p \text{ iff } a^{(p-1)/2} \equiv 1\ (\bmod\ p)$ if $p$ is a prime.

$n$ is a large RSA modulus. Is it also possible to check if $a \in \mathrm{QR}_n$ if the factorization of $n$ is unknown?


texts: Change initial hash value of SHA-512/$t$

texts:
Fips 180-4 defines under 5.3.6 how to calculate initial hash values for SHA512/$t$ for a given value $t$.
Can someone explain me how the t actually affects the outcome of the procedure (which, as far as I understand, just calculates the eight 64-bit words XOR with a5a5a5a5a5a5a5a5)? Furthermore I don't understand how to pass the new calculated initial hash values to the hash function instead of the default values for SHA-512.
Can someone explain how to do it in Java using the java.security.MessageDigest class (or something else)?


texts: Can any part of AES encrypted blocks be used as PRFed value?

texts:
Suppose we need a PRF whose output space is 255bit.

Then, what I can do with AES with 128-bit security is producing 2 AES blocks that are of 256-bit.

Then, I will remove the most significant bit of one block so that I have 255-bit output.

Is it secure if I remove the top-bit of the one block to make it 127-bit?


texts: Creating hash data signatures using RSA-CRT

texts:
I have taken two prime numbers p=137 q=131 M=64 and i want to create a digital signature
n=pxq=17947
phi=(p-1)x(q-1)=17680
e=3                                     (I have taken public key e=3 as gcd(3,n)=1)
d=e^-1 mod phi
 =3^-1 mod 17680 = 11787
dP= d^-1 mod (p-1)
  = (11787)^-1 mod 136 = 3
dQ= d^-1 mod (q-1)
  = (11787)^-1 mod 130 = 3
qinv= q^-1 mod p
    = (131)^-1 mod 137 = 114
mp= M ^dP mod p
  = 64^3 mod 137 = 87
mq= M ^dQ mod q
  = 64^3 mod 131 = 121
h= 114*(87-121) mod 137
 =97                              (after converting to positive remainder)
Sig= mq+ h*q
   =121+ 97*131
   =12828

Verification
 M= (Sig)^e mod N
 = (12828)^3 mod 17947
 = 8301

Not matching with the message M=64 . Where did i make a mistake?


texts: How to identify the difference between two cryptographic schemes in terms of security?

texts: I am currently working on a project, that requires using encryption libraries namely (LibScarab and FHEW). I want to know how can I compare the two schemes in terms of security (I already compared between them in terms of execution time). All I know that LibScarab uses SV scheme, while FHEW uses LWE scheme. Can I get help in how to bring comparisons between two schemes to decide which one is more secure?


texts: Do RSA keys contain a checksum mechanism?

texts:
I'm new to cryptography, and I was making an experiment a few minutes ago, but I want to have some deeper knowledge about RSA public and private keys.

I have a set of keys

One begins with

-----BEGIN RSA PRIVATE KEY-----
MIIBOgIBAAJBAOlnH1jZ2YLfWuYMop1a4N9jsUPK......
-----END RSA PRIVATE KEY-----

and another with

-----BEGIN PUBLIC KEY-----
MFowDQYJKoZIhvcNAQEBBQADSQA....
-----END PUBLIC KEY-----

I've parsed them using Java and I can make use of them, as RSA private and public keys respectively.

But the question I have is....

Are there some checksum mechanisms built into RSA keys ?

I ask this because, I'd like to know what happens if, by error or intentional, one or more characters from the encoded PEM are modified.
Does this breaks the key ? Or changes the key internally, without breaking it ?


texts: Is double AES-CBC encryption with the same key and IV unsafe?

texts: If some plaintext encrypted twice with the same AES function (CBC-mode), same IV and same key, is it possible to retrieve either the key or the plaintext?


texts: What is the difference between PIR and OT?

texts:
A private information retrieval (PIR) protocol is a protocol that allows a user to retrieve an item from a server in possession of a database without revealing which item is retrieved.
An oblivious transfer (OT) protocol is a type of protocol in which a sender transfers one of the potentially many pieces of information to a receiver, but remains oblivious as to what piece (if any) has been transferred.

As the Wikipedia said, PIR is a weaker version of 1-out-of-n oblivious transfer, but I do not really know why is a weaker version.


texts: Reference AES-NI assembler code for AES-128-GCM?

texts:
I want to implement AES-128-GCM in assembler using Intel AES-NI instructions. I have found reference code in the Intel AES-NI Whitepaper but I don't see code for the GCM mode there (or indeed any use of the PCLMULQDQ instruction). Do I miss something in this document? Or could somebody point me to another similarly clean and simple implementation in assembler with AES-NI instructions that uses GCM mode?

I am hopeful that the implementation will be pretty straightforward given a good reference implementation and also good reference benchmarks for cycles per byte. The main reason I am reimplementing this is as an exercise in using an unusual assembler (DynASM).


texts: Multivariate Cryptography: Security of the affine transform T

texts:
In this question, I'd like to discuss the security of the last transformation $T$ employed in the construction of a MV-scheme. MVCrypto is based on solving a system of polynomial equations, but eventually, those polynomials are constructed by a linear combination of $T$ and a vector represententing an univariate polynomial in $F_{q^n}$ with coefficients in $F_q[x_1,\cdots, x_n]$. The following construction illustrates a typical description, where $\alpha : F_{q^n} \mapsto F_{q^n}$ is the transformation function (i:e Matsumoto-Imai) that changes the coefficients of $x'$ that are multivariate linear polynomials to multivariate non-linear polynomials. Note that here $v_s,v_t=[0]_n\in F_q^n$.
\begin{equation}
S,T \in F_q^{n \times n}, \quad x=(x_1,\dots,x_n)\in F_q^n \\ x'=S\cdot x \\y'=\alpha(x')\\y=T\cdot y'
\end{equation}

Matrices are very useful since we can represent $F_{q^n}$ as $F_q^n$: the n-dimensional vector space over $F_q$. So $x'$ can be viewed as a polynomial with coefficients that are linear combinations on $x$.

$$x'= \sum_{i=1}^{n}(\sum_{j=1}^{n} S_{i,j}\cdot x_j)y^{i-1}$$

The attacker has $n$ multivariate polynomials and their evaluation on $x=(x_1,\cdots,x_n)$. If he finds out the transformation $T$, he could attempt to invert $\alpha$ to obtain $x'$ and finally, $x$. My intuition tells me that an attacker can find a pair $z\in F_q^n, T'\in F_q^{n\times n}$ s.t satisfies $T'\cdot z = y$. As an example, consider the following case where $V=F_5^2$:

$T=\left(
\begin{array}{cc}
 1 & 2 \\
 3 & 1 \\
\end{array}
\right)$
$y'=(x_1x_2-1,x_1^2x_2+3)$

$T\cdot y' = y = (x_1x_2+2x_1^2x_2, 3x_1x_2+x_1^2x_2)$

It's pretty straightforward to recover $T'=T$ and $z=(x_1x_2,x_1^2x_2)$ since $y$ contains coefficients that are $n$ sums of the same $n$ factors, here $n=2$. Note that $z\neq y'$ but in this case is not hard to "bruteforce" until reaching the correct one.

EDIT: It's important that you note that $S$ and $T$ are interchanged in my example, $S$ is the first affine transformation and $T$ is the last one, however, in literature you found this to be the opposite. So the remark is that this question is about the last transform applied in the construction.

Question: Is there any information that describe an inversion of this construction, not by solving the polynomial eqs. but inverting the maps?


texts: Certificate Path Verification of X509 Certificate

texts:
I have the trusted root certificate which I am validating using the self signed key. I also have the intermediate certificate, which i am validating using the root certificate.
Now when i am validating the certificate do i need to trace back the whole chain to validate the certificate?
Or can i say i have done TPC, if i just validate it using the intermediate only(since i have already validated my intermediate with its root before)?


texts: Using only pseudorandom function to drive many deterministic keys

texts:
My question is related to:

Can Pseudorandom values be used as secure keys?

But here I'm only using pseudorandom function.

Assume we have a pseudorandom function, $PRF$. We have a truly random  master key: $mk$ for the PRF function.

I want to deterministically generate $n$ keys, so I do:

$\forall i, 1\leq i\leq n: k_i=PRF(mk,i)$.

Question: Is it secure to use each key $k_i$ to generate $m$ pseudorandom values? E.g. $\forall j, 1\leq j\leq m : k_{i,j}=PRF(k_i,j)$.

Is there any protocol using such scheme (if the scheme is secure) ?


texts:
According to wikipedia: BDZGO is the expected outcome when doing the enigma chipher on the letters AAAAA with rotors I,II,III and reflector B.

ABCDEFGHIJKLMNOPQRSTUVWXYZ | Alphabet

EKMFLGDQVZNTOWYHXUSPAIBRCJ | Rotor I wiring
AJDKSIRUXBLHWTMCQGZNPYFVOE | Rotor II wiring
BDFHJLCPRTXVZNYEIWGAKMUSQO | Rotor III wiring

YRUHQSLDPXNGOKMIEBFZCWVJAT | Reflector B wiring
ABCDEFGHIJKLMNOPQRSTUVWXYZ | Reflector B wiring

If we now track the first A:

A-E | etw to rotor I
E-A | rotor I to rotor II
A-B | rotor II to rotor III
B-R | Reflector B
R-X | rotor III to rotor II
X-V | rotor II to rotor I
V-I | rotor I to etw

So the output is I instead of B, where is my mistake?


texts:
I want to find a secure and efficient way to tally votes.

Say we have N ~ 10000 voters. Each one can vote for candidate 1, candidate 0, or both. But no one can vote more than once. The groups who voted for 1 or 0 want to tally their votes.

Is there a way to tally votes that is fast and cryptographically secure? Perhaps a zero knowledge proof or a ring signature? Thanks!


texts:
I am writing a small personal project where I would like to use AES to encrypt some documents. It seems to work pretty well, but I was wondering about one point of my code. The current structure is user inputs password -> key = sha256(password) -> compress(key) -> AES(document, key). Where compress XORs the key with itself. So for 128 bit AES the first half is XORed with the second to get a 128bit key. I do a similar operation for 192 bit AES. I have a few questions about this:

Is it safe? If not, could I just drop the extra bits?
Is there a better way to go from a password to a key? I think for the average password entropy is pretty low.
Could I use this method to generate an IV for some other block cipher mode?


texts:
I am new in cryptography. I want to determine the complexity of revealing a random bit permutation which is used as block cipher for plaintexts (bitstrings of length n). An adversary catches different ciphertexts (the permuted bitstrings of length n) and he also knows the set of possible plaintexts. If he tries all possible inverse permutations at the end there are more permutations that result in legal plaintexts. The difference is that all of the remained permutations result in different sending order of the plaintexts. Is it possible to reveal the used permutation?

Any insight will be helpful.
Thank you in advance


texts:
I was given an argument in a conversation today and I don't know how to respond to it:

H( k || m || k ) should be a better choice of MAC than the traditional HMAC. The person's rationale was that: "You don't know where to pick up extending from, and you don't know what to finish extending into. Sure using k twice looks ugly, but HMAC also uses the key twice, except it also hashes twice. This only hashes once and therefor is faster."

I couldn't refute this on the spot and now the more I think about it the more it bothers me. Are they right? I'd imagine that the cryptographers who decided on HMAC had way more experience when they made their decision. But then why?


texts: Curve25519/Montgomery curves points with order 8

texts: I found this post about Curve25519. It states, that there are only 5 points with a very low order. With this paper I was able to understand, how the points with order 2 and 4 were computed. My question is: How to compute the points with order 8?


texts:
I don't quite get frequency analysis..

I see percentages and else, when I tried to do a frequency analysis on a pictogram cipher, the only letter I was able to analyze was the letter A.

Any step-by-step tutorial on this?

I did count, but why are there decimal numbers for certain frequencies?

Like this picture, downloaded from the Wikipedia page.

Do mathematics have anything to do in this, such as dividing?


texts: Can keys from Bitcoin's Hierarchical Deterministic Wallets be correlated (reducing privacy)?

texts:
I'm trying to understand if the feature "Hierarchical Deterministic Wallets" in Bitcoin allows for complete privacy of all derived keys, and if any of those keys can be associated with each other after they are generated.

Knowing the answer to this will greatly impact the scenarios these keys are usable in.


texts: Time complexity of DLP over Elliptic curve group

texts:
Consider NIST 192 elliptic curve group https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf. What is the time complexity
of discrete log problem of it? Is it Pollard $\rho$ i.e $\sqrt{N}$, where $N$ is the size of the group?


texts: Decrypt all RSA ciphertexts if you can break 1% of them

texts:
I was given a cryptography question during an interview the other day.

Imagine you are given an efficient algorithm which for a given RSA public key (n,e) is able to decrypt 1% of the messages encrypted with that key.

1% means that the algorithm will deterministically decrypt 1% of all possible ciphertexts on the first call, and will never decrypt the other 99% of all possible ciphertexts with any number of invocations.

Figure out an algorithm that uses this one and can decrypt any message. Any ideas?


texts:
From BSI-TR-03111 (PDF), on page 15:

  The class number of the principal order belonging to the endomorphism ring of E SHOULD be at least 200.

This value commonly is referred to as $h$ in that publication.

I‘ve got two questions related to this:

What does $h$ mean/denote?
Why should it be 200 or larger?


texts: Can a secure MAC break if the adversary is given oracle access to Verify?

texts:
In the Mac-forge experiment, the adversary is given access to a tag-generation oracle, which generates a tag for each message given by the adversary. The adversary's task is to generate a valid tag on a message that hasn't been queried to the tag-generation oracle before, in polynomial time. If the adversary can do so with a non-negligible probability, then the MAC scheme is insecure or broken.

My question is whether giving the adversary access to a verification oracle, i.e. an oracle the adversary queries with message-tag pairs and finds out whether it's a valid tag for the corresponding message, reduces the security of the MAC scheme or not. Clearly, if the tag generation algorithm is deterministic, then the verification oracle gives nothing new, but if the tag-generation is randomized, is it still the same?


texts: Attack for RSA 1024 bit with Low Public Exponent

texts:
I am facing a challenge at university.
Our teacher give us the challenge to try to break an RSA 1024 bit.

We have public modulus N and public exponent e (0x03), we don't know the padding.

We have a signed message with RSA key (128 bytes) and we know that the unsigned message is an MD5 hash, we have also the MD5 hash (jus to verify).

The first goal is to find if possible the private exponent d.
The second goal is to forge a new signed message (hash) valid.

Can someone point me out which type of attack i can use and what programming language give more performance to do that?

Thanks a lot, any information will be helpful.


texts:
Consider the primitive polynomial P(x) = x^4 + x^3 + 1, initialized with the bit string (shifting occurs from left to right, were the right-most bit represents the LFSR output): 1101.
List the first 8-bits generated by the LFSR, starting with the bit 1 that is the right-most bit of the initialization sequence above.
This was my work to solve this:
          s1 s2 s3 s4  output (s4 xor s3)

         [[ 1  0  1   1    0
          0  1  0]]   1    1
          1  0  1     0    1
          1  1  0     1    1
          1  1  1     0    1
          1  1  1     1    0
          0  1  1     1    0
          0  0  1     1    0

The answer is : 10110010. Is this because it is in result of what I have put in brackets?


texts:
In AES-GCM, from what i understand, the plaintext(as well as AAD and IV) bit length taken in must be a multiple of 8 (as specified by NIST Spes. Pub 800-38D). The AES-CTR however, doesn't "care" about the bit length.

The majority of my confusion comes from looking at how the AES-GCM works as a whole. It seems to me that to appropriately generate an authentication tag it needs two strings of plaintext. Additionally , the GHASH function seems to take in n 128-bit ciphertext strings.

Which leaves me with the question: What is the minimum amount of plaintext data required(after any padding) to appropriately encrypt and authenticate using AES-GCM?


texts: Is encrypted e-mail sent over TLS 1.3 a form of "forward secrecy" (similar to something like Signal)?

texts:
One common complaint about GPG-encrypted e-mail is that it doesn't provide forward secrecy; however with opportunistic TLS becoming increasingly common in both IMAP and SMTP, it's not unreasonable to expect that e-mail sent from one message transfer agent (MTA) to another is done over a TLS protocol that utilizes (EC)DHE—by far the biggest e-mail provider, Gmail, is configured to send and receive e-mail this way by default. Thus if communication between mail user agents (MUAs) and message submission agents, MUAs and message delivery agents, and MTAs and MTAs is done using such a protocol (e.g., TLS 1.3); then even if the GPG key that was used to encrypt the e-mail is fairly static, shouldn't this constitute as "forward secrecy"?

It seems to me that the only way to decrypt someone else's e-mail is if the end-point device has been compromised. This is also true for Signal though. Am I mistaken?


texts: How does the offline authentication work?

texts:
In these slides, offline and online PUF-based authentication protocols are explained in minute 16:30 and 17:30, respectively. I understand the way the online protocol works. Basically, the server keeps a table of CRPs, sends a challenge, then verifies the generated response (by PUF) from the table.

However, I do not understand the offline protocol. Who has the CRP table to verify the response? Batteries and printer cartridges are two of the examples mentioned in these slide that use offline protocol. In my opinion, they should be online, so the server can check the response.

My reasoning: suppose that a new battery is issued (a new CRP table is generated). The server can store the CRP table before sending out the battery (so that it can check the response). However, the smartphone cannot get the new CRP table because user is the owner (not the server). I was wondering which part of the protocol I am missing and why and how the offline protocol works.


texts:
On wikipedia there is an example of a picture encrypted with ECB:

http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Electronic_codebook_.28ECB.29

I just wanted to know how an encrypted file could be displayed as a picture ?


texts:
Recently I've been reading papers about MPC protocol, but when I read the paper by Zahur, S., M. Rosulek, and D. Evans. 2015 Two Halves Make a Whole- Reducing Data Transfer in Garbled Circuits Using Half Gates.
The researchers proposed the state-of-art technology of optimizing garbled circuit.

Their main idea is to divide the AND gate into two half-gates.
\begin{align*}
  c &= a \land b \\
    &= a \land (r+r+b) \\
    &= (a \land r)+(a \land (r+b))
\end{align*}

As far as I can see, it seems that the generator half-gate is enough for an AND gate. based on the input value that the garbler has, it produce the garbled table:
$H(B)+C,H(B+R)+C+aR$. the evaluator can calculate the output label based on the label of its own input $B$ or $B+R$, and that's it, that's all for an AND gate.

I don't see why the authors construct the gate by combining two half gates.

I don't really see the intuition behind this construction, after reading the book A Pragmatic Introduction to Secure Multi-Party Computation written by David Evans, he wrote:

  It remains to show how the two half gates can be used to evaluate a gate vc = va ^ vb, in a garbled circuit, where neither party can know the semantic value of either input`.

As classical Yao circuit, two-party have their own input independently, why he assumes that they both know neither input?


texts: Is there a cryptographic algorithm which is immune to side channel attacks?

texts: Is there any cryptographic algorithm immune to side channel attacks based on scan chain? In VLSI point of view.


texts: Does Shamir's Sharing Scheme make sense if k=2 and n=2?

texts:
Given that I have a secret which I want to split into 2 parts (n=2) and require 2 parts to restore it (k=2), does it still make sense to use Shamir's Scheme or would a trivial scheme with XOR (generate a random string, same long as the secret, XOR those, random string and the XOR result become shares) be just as secure? Are there any benefits in using Shamir's Scheme in such case?

In general, what would be the recommended sharing scheme for this use case?


texts: Upper bound Linear Feedback Shift Register

texts:
It is clear that when we have any output stream $x_0,x_1,...$ produced by linear-feedback shift register, then this output has to be periodic.

Now I was wondering if we can find an upper bound for the period of the output sequence from a linear-feedback shift register with $R$ registers over $\mathbb F_q$?


texts:
Java's SecureRandom is meant to be cryptographically secure, and I know part of that means that the output should not be usable to predict further output.
Though, admittedly, my knowledge in the area is limited, and I'd like to test the limits to get an idea of how secure Java's SecureRandom really is.

So let's say I do this: I seed a SecureRandom with a secret long value (8 bytes) and then use it to encrypt 100 bytes of data by generating 100 bytes with the SecureRandom (right after seeding) and adding them to the original 100 bytes. Very silly of me, however, the original 100 bytes are all zeros, and you know this. Could you use some variant of a known-plaintext attack (or anything similar) to break my encryption? That is, could you determine the initial seed or predict the next values?

Okay, I need to specify it a bit more. I'm going to assume - as a worst case scenario - the SecureRandom implementation uses SHA1PRNG (that is SHA-1) as a mixing function. I know that this algorithm is considered to have some flaws, so then my question is whether - in the given circumstance - these flaws would allow for an easy break on the encryption; meaning one could determine the initial seed without great difficulty from the output. Meanwhile -in a better scenario - the mixing function would be SHA-256, and I still wonder if this situation would allow for vulnerabilities with that algorithm as well, other than brute force.


texts: Is it reasonable to consider that an encryption scheme must be invertible?

texts:
I am in a dispute regarding a test question in an exam.
The question is something like that:

What would happen if one were to use RSA with $n=100$ and $e=13$ to
encrypt a message $m$?
a) You would be able to encrypt the message but not decrypt it.
b) You would not be able to encrypt the message.
...

Both parties agree that the operation $c = m^e \bmod n$ (a transformation known as encryption when using proper RSA) is no longer bijective, as $n$ is not the product of two primes. For example, $m=10$ and $m=20$ would both result in "cryptogram" $c=0$.
I consider that an encryption function must be invertible, as the purpose of encryption is to hide information from non-authorized eyes while allowing authorized parties to retrieve it. The fact that this transformation (which I'd argue could not even be called RSA, as $n$ does not fulfill RSA's rules) is not bijective means that it is not invertible, so it cannot be considered encryption. I would say that, under this assumption, any discussion of encryption/decryption is pointless, and if one answer had to be marked, it should be B: we cannot call $c = m^e \bmod n$ "encryption".
On the other hand, the other party sustains that the only correct answer is A, and that "it is fallacious to believe that encryption must be invertible, as there are many non-invertible encryption schemes". They are not available for questioning, so I cannot seek further clarification about what they meant. I assume they meant cryptographic hashes, but I would not consider them encryption schemes, but cryptographic primitives.
My question is therefore two-fold:

Am I correct in assuming that it is not wrong to impose the condition that a transformation must at least be invertible in order to be considered encryption?
If I am correct: Could I be pointed out to some reputable bibliographic source to use to strengthen my case?
If I am incorrect: Is it because cryptographic hashes are considered encryption schemes or because there truly are non-invertible cryptographic schemes? If so, how do they meaningfully differ from hashes?


texts: Diffie-Hellman based password challenge response scheme

texts:
A very commonly used (examples: HTTP digest auth/CHAP/Kerberos) authentication scheme is something that looks like:

Setup.

Client and server both know a password $p$.

Authentication.

Server sends a random challenge $\alpha$.
Client computes $r = \text{KDF}(p || \alpha)$ and sends $r$ to the server.
Server computes $r' = \text{KDF}(p || \alpha)$ and checks $r' \overset{?}{=} r$.

This scheme is also described in other questions (example).
Now this scheme has the disadvantage that the server needs to know the plaintext password. Could we make a public-key-based scheme for challenge response authentication?

For example, we could use elliptic curve arithmetic:

Setup.

Client has a secret password $p$ (with reasonable entropy) and from this derives a key  $k$ using a hash function.
The client computes $[k]P = Q_k$ and the server will store this value as the user's public key.

Authentication.

Server sends a random challenge $Q_\alpha = [\alpha]P$.
Client computes $Q_s = [k]Q_\alpha$ and sends $Q_s$ to the server.
The server computes $Q_s' = [\alpha]Q_k$ and checks $Q_s' \overset{?}{=} Q_s$.

Does this scheme work? Why would most systems use HMAC-based scheme instead?


texts:
Suppose $n=pq$, where $p,q$ are prime numbers.
Let $p ( \le q)$ be the smallest prime, then we know that $p \le \sqrt{n}$.
In trail division, we check  $n \mod i$  for the values of $i$ from 2 to $\sqrt{n}$, to find the value of $p$ and then we calculate $\dfrac{n}{p}$ to get $q$.
In general, the time complexity is (assuming finding remainder and division takes place in constant time) $\sqrt{n}$.
How to calculate cryptographic time complexity?
Suppose $b$ is the number of bits to represent $n$ in binary format, then can I directly substitute in $\sqrt{n}$, so that I can get $2^{\frac{b}{2}}$.
Or should it be calculated as $(\sqrt{n}-1)*$ time taken for modulo operation $+$ time taken for division?
How to arrive at time complexity in terms of $b$?
How much time does it take for calculating modulo and division in terms of bits? If we substitute those values, finally should we get $2^{\frac{b}{2}}$?


texts:
I come across this:

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

and

  every number has a multiplicative inverse under integer mod prime

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

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


texts: How to create an EC point from a plaintext message for encryption

texts: It seems that ElGamal encryption is also possible for Elliptic Curve cryptography. However, that requires the user to convert the message to a point on the curve. What strategies are there to derive a point from a plaintext message? Is it simply generating an X value that just the message converting to a number and finding the Y coordinate for that X value?


texts: What is hardened SHA-1, how does it work and how much protection does it offer?

texts:
From the shattered website:

  You can use the online tool above to submit files and have them checked for a cryptanalytic collision attack on SHA-1. The code behind this was developed by Marc Stevens (CWI) and Dan Shumow (Microsoft) and is publicly available on GitHub.

  It is based on the concept of counter-cryptanalysis and it is able to detect known and unknown SHA-1 cryptanalytic collision attacks given just a single file from a colliding file pair.

And later:

  Is Hardened SHA-1 vulnerable?

  No, SHA-1 hardened with counter-cryptanalysis (see ‘how do I detect the attack’) will detect cryptanalytic collision attacks. In that case it adjusts the SHA-1 computation to result in a safe hash. This means that it will compute the regular SHA-1 hash for files without a collision attack, but produce a special hash for files with a collision attack, where both files will have a different unpredictable hash.

finally from the GitHub pages - which I assume is called "hardened" SHA-1 above:

  ... More specifically they will detect any cryptanalytic collision attack against SHA-1 using any of the top 32 SHA-1 disturbance vectors with probability 1:

I(43,0), I(44,0), I(45,0), I(46,0), I(47,0), I(48,0), I(49,0), I(50,0), I(51,0), I(52,0),
I(46,2), I(47,2), I(48,2), I(49,2), I(50,2), I(51,2),
II(45,0), II(46,0), II(47,0), II(48,0), II(49,0), II(50,0), II(51,0), II(52,0), II(53,0), II(54,0), II(55,0), II(56,0),
II(46,2), II(49,2), II(50,2), II(51,2)

What precisely are these vectors? Could there be other vectors that are vulnerable? How much protection does "hardened" SHA-1 offer?


texts: Proper Way to Encrypt Data with Two Keys?

texts:
I'm going to develop a system that will have two keys. One supplied and generated by the system that's specific to an individual user and one from the user.

I plan on using AES.

Does it make sense to:

Concatenate the two keys to make a "master" key and then encrypt the data?
Encrypt with one key and the encrypt again with the other key?

Does it really matter? I can't see that it'd really matter, but maybe I'm missing something.


texts: Using bcrypt derived keys for encryption?

texts:
Sorry for this ignorant question but I am currently weighing up the advantages and disadvantages of BCrypt over PBKDF2 and from what I have read BCrypt is considered more secure but from what I have discovered BCrypt only derives as 248-bit key (Example: E2cP18g8DyWwg3emgpHOaPBZzrcRVrO) and the rest of it is the salt, however I require a 512-bit key so I can split it into two sub-keys on for a AES encryption key and the other for HMAC generation.

Would it be secure to take the sha-512 hash of the key produced by BCrypt and split that or should I just keep using PBKDF2?


texts: Adaptation of Stern Zero-Knowledge protocol from coding to lattices

texts:
I'm currently working on Zero-Knowledge-proofs in lattice context, for which there exist two major frameworks. One of those two is the adaptation of Stern protocol from code-based-crypto.

There is in particular $2$ articles :

[KTX08]  https://www.iacr.org/archive/asiacrypt2008/53500376/53500376.pdf
[LNSW13] https://eprint.iacr.org/2012/569.pdf

which build the lattice version of Stern protocol.

In coding theory: Stern allows to prove knowledge of a vector $x \in \mathbb{F}_2^{n}$ such that $Hx = y\bmod\ 2$. With $H \in \mathbb{F}_2^{m \times n},\ y \in \mathbb{F}_2^{m}$ public.

In [KTX08] : They managed to prove knowledge of a binary vector $x$ such that $Ax = y\bmod\ q$, but there is no mention on any trial to just apply in a straight manner the protocol with an average ISIS instance : That is to say :
proving knowledge of $x \in \mathbb{Z}_q^m$ such that $Ax=y\bmod\ q$ and $||x|| \le \beta$, $A \in \mathbb{Z}_q^{n \times m}$, $y \in \mathbb{Z}_q^n$ public.
As a permutation doesn't affect the norm, I'm not sure why this should doesn't work.

Does anyone know why?

My guess is that it's related to the lattice-based commitment scheme security: If you find a collision with two binary vectors on those commitments, you break a SIS instance with an optimally small bound, which is not necessarily the case for a collision with higher coefficients vectors.
Anyway, I wonder if I'm right and/or if there is another reason because I'm not fully convinced.


texts: RSA:Plaintext block has a common factor with modulus

texts:
I've seen a couple of posts stating the following fact: If $(n = pq,e)$ is the public key of an RSA instance and some plaintext block $m$ has a common factor with $n$, then also the corresponding ciphertext block $c$ has the same common factor with $n$.

Yet, I could not find any formal proof of this statement. I tried to come up with one by myself, but I could not quite make it. What I have so far:

As $m<n$, $m = p * z$ or $m = q*z$ for some $z \in \mathbb{Z}$. Assume w.l.o.g $m = p * z$. Then $c = m^e \mod n = (p * z)^e \mod n$. I don't really know how to continue. One could rewrite this further as $c = ((p^e \mod n)  * (z^e \mod n)) \mod n$ but that didn't help me either. Does someone have a hint for me?

Any help is appreciated! Thank you.


texts: How many pairs of ${b_i}^k \equiv g_i\pmod p$ are enough to solve discrete logarithm problem?

texts:
On the group of multiplication modulo large prime $p$ of $m$ bits

Given
$$ b_1^k=g_1 \;\text {mod}\;p$$
$$ b_2^k=g_2 \;\text{mod}\;p$$
$$ b_3^k=g_3 \;\text{mod}\;p$$
$$ \vdots $$
$$ b_n^k=g_n \;\text{mod}\;p$$

How many pairs are enough to computationally solve $k$ of this discrete logarithm problem? I have this question because if we erroneously use the random number generator in Elgamal encryption The masking key may have relation, e.g. the masking key is the square of previous one modulo $p$. We can decrypt the ciphertext easily, but we may still not know the private key of Bob (the receiver.), but we can know many pairs of relation like equations above. Are the pairs let we solve the private key of Bob(receiver)?


texts: How can I make a message into a blocks for NTRU?

texts:
I have more bits than the degree of the NTRU polynomial.

For example: $x^{11}-1$
message: Hello (I am using ascii, 8 bits for 1 symbol)
got: 0100100001100101011011000110110001101111.

How should I split up message into blocks? Please answer with example.