texts:
I want to implement an identity based encryption scheme using Koblitz curves as scalar multiplication is faster due to Frobrenius endomorphism.

How can I tell if a curve over $\operatorname{GF}(2^m)$ is pairing friendly or not?

I have found this paper called "Elliptic Curves Suitable for Pairing Based Cryptography" but I think it talks about curves over $\operatorname{GF}(p)$.


texts:
I'm trying to generate AES256 key from user input password.
The size of the password can be anything from 4 bytes long to 32 bytes long but let's assume
it is the smaller one.
My API support either : SP800-108 HMAC in counter mode, SP800-56A, PBKDF2 or CAPI_KDF
According to several articles I read, the common PBKDF2 suffers from multiple weaknesses and so it's not an option.
I would like to know which one from the above is the most secure KDF for my purpose.
In addition I would like to know what the relations between the algorithms above to Argon2 and Scrypt.
Thank you in advance :)


texts: How many points in RSA, such that $m^e = m \bmod n$

texts:
For every RSA-cryptosystem, there exist some messages $m$, for which it holds that $m^e \equiv m \pmod n$
As to the question, how many such messages exist, this question has already been asked and answered here: https://math.stackexchange.com/questions/1298664/rsa-fixed-point
However, I do only understand the answer up to a certain point
Suppose that $n$ is only 1 prime. Then it holds that the number of unconcealable messages is $\gcd(e-1, p-1)+1$
This is because in $m^e \equiv m \pmod  p$ , either $m = 0$ or $m \not= 0$. In the latter case $m$ can be expressed as $g^t$, where $g$ is a Generator in $\mathbb{Z_p}$
$g^{t*e} \equiv g^t \pmod p$
$g^{t(e-1) \bmod p -1 } \equiv g^{0 \bmod p -1} \pmod p$
$t(e-1) \equiv 0 \pmod {p-1} $ has exactly $\gcd(e-1, p-1)$  solutions, so the total number of unconcealable messages is, together with $m=0$ , $\gcd(e-1, p-1)+1$
When we now look at real RSA, which has two prime factors in its modulus, it holds that the number of unconcealable messages is $(\gcd(e-1, p-1)+1)\cdot(\gcd(e-1, q-1)+1)$
Why is that so? I suppose it has to do with CRT, but I just cant understand why.


texts: Practical use of semi direct product of group in Cryptography

texts: Is there any example of semi-direct product used in any of cryptographic application? Does it help in choosing integers p, q in RSA?


texts: When it comes to linear cryptanalysis, is there always a key that could work for every possible input/output?

texts:
Until now every tutorial I've seen about linear cryptanalysis, is written on the basis that we have all possible inputs/outputs. Is that a condition? And if not, how many should we have as a minimum?

I also noticed that the idea is to find a key that would work for every possible combination. So, when it comes to block ciphers that could be cracked using linear cryptanalysis, is there always a key that could work for every possible input/output?


texts: How to design a secure challange-response authentication protocol?

texts:
I am implementing a custom challenge-response protocol to authenticate a client to a server. Mutual authentication is not required, i.e. the server doesn't need to be authenticated to the client.

The protocol works over TCP. Client and server are in a LAN (not over the internet). There is only one server and only one client. The authentication is designed as follows:

$S \rightarrow C : N$

$C \rightarrow S : \{N\}_K$

Where the server $S$ creates a 128-bit random number and sends it as nonce $N$ to the client $C$. The client encrypts the nonce with AES-192 with the pre-shared key $K$ and sends it as response to the server. Then the server decrypts the message and checks the nonce.

Questions:

Is this protocol design secure?
What would be the advantage to use HMAC (or any other MAC) instead of AES encryption?
Did I miss something?


texts: Use of Same Key for CTR and CBC-MAC in CCM Mode of Operation?

texts:
The NIST Specification Document for CCM Mode of operation 800-38C states on Page 13

  The same key, K, is used for both the CTR and CBC-MAC mechanisms
  within CCM.

is it secure to use same key? or one should prefer two distinct keys. One for CTR Mode and other for CBC-MAC?


texts: Dynamically building a Merkle tree for unkown size

texts:
Assuming a $k$-ary Merkle tree:

If the length of a file is known, based on a fixed chunk size, one could calculate the number of chunks and thus the depth of the tree. Then, based on $k$, the chunk index and the depth, one can parallelize the construction of the Merkle tree.

But if the file size is not known, i.e., the input is a stream, and we are reading the input until EOF, what could be an efficient procedure to build up the $k$-ary Merkle tree, assuming as usual that leaf nodes contain the chunk hash, while branch nodes contain the hashes of their children?


texts: Is HMAC-MD5 considered secure for authenticating encrypted data?

texts:
I've read something to the effect that the HMAC construct is able to lessen the problem of collisions in the underlying hash.

Does that mean that something like HMAC-MD5 still might be considered safe for authenticating encrypted data?


texts:
Reading through Katz & Lindell's Intro to Modern Crypto, I came across these notions which were introduced in quick succession without much differentiation between them.

How do Indistinguishability(IND) and Non-Malleability(NM) differ? Which is the stronger notion of the two, in which (if any) scenario are they equivalent?


texts: Asymmetric encryption that is secure for (almost) any foreseeable future

texts:
Recently, I've been reading a couple of papers about building cryptosystems that are secure for up to 30 years. But for some applications, this seems a bit low to me. So I am wondering if considering the current state of the art in cryptography and computing power evolution forecasts, one could instead build a public-key encryption system, running on today's consumer hardware, which is secure for any foreseeable future.

Of course, written like this, the problem is too broad, so my specific criteria are as follows:

Keys are permanent, ciphertext which has been encrypted today must remain secure
Security is broken if an attacker can reliably decipher text which has been encrypted with the public key, without possessing the private key
Scenarios in which the attacker gets a hold of the private key by stealing, torture, and other means of extracting it from the rightful owner, are not considered a breach of security
My (very generous) upper bound for performance forecast realism is 1000 years in the future
I personally do not consider general-purpose quantum computers, based on logic gates operating on a large number of entangled qubits, to be viable in any foreseeable future, so security against them is just a nice extra
More specialized quantum computing systems like D-wave's quantum annealing, however, which do not rely on many-particle entanglement, are within the realm of possibilities
Attacker may be considered to have access to exabytes of ciphertext and terabytes of plain text - ciphertext pairs
Attacker may have access to state-of-the-art computing power, like the supercomputers of his generation
It must be possible to transfer public keys over the Internet within a reasonable time (absolute maximum is 1 day on a low-end 30 kB/s Internet connection -> 2GB), but they do not need to be transmitted frequently so it is acceptable if the keys are unusually big
Encryption must be fast on today's hardware, let's say 30 MB/s on a high-end laptop as a lower performance bound

Is this totally crazy, or can it be done using today's knowledge in cryptographic algorithms + implementations which are either available today or can be made available in the near future?


texts: Why use base64 or hexadecimals for ciphertext?

texts:
They are asking me to deliver encrypted text in ISO/IEC 8859-1. I have always encoded it to hexadecimal or base64. This text will be sent in a file with plaintext and encrypted text. In my opinion it won't work because of the non-visible characters.
I also wonder if there are characters that exist in hexadecimal and not in ISO/IEC 8815-1 (Western-Latin encoding). Am I right in assuming so?


texts:
I checked the most common AES modes and I think I got the goal of them: avoid same cyper text for same plain text.
However all modes except ECB have the weakness that lost part of the message stream will result in a broken decryption because the key can not be generated.
CFB is one attempt to resynchronise, it needs the previous cypher block and CTR is another way, if you know how many blocks are missing.

I am not a specialist in cryptography but I would like to suggest a extended use for ECB:
Would it be appropriate to split each block into a part with plain text and another part with true random data in order to assure that each cypher text will be different from the other while keeping the same key (ECB mode)?
Of course I loose plain text capacity and safety depends on the ammount of random data. Lets say the first 10 bytes of each block are plain and the last 6 bytes are random content. That means that I reduce the randomness from 2^128 to 2^48 which is still high (and it applies only if I allways have the same plain text).

Is this an acceptable safety? OK, reply attacks are possible and need to be handled separately.


texts:
I have been asked to create an LFSR with a polynomial of x^15 + x + 1 and i am confused where the tap sequence would go.

The examples I was given show a 4 bit tap sequence with two polynomials: x^3 + 1 and x^2 + 1. These were shown having tap at positions 0101 and 0101 respectively, where the bold represents the tap sequence.

I am confused about where the tap sequence would go for x^15 + x + 1, since in the first above example, there is 4 bits but taps are at either ends with the polynomial x^3+1. So how would x^15 be placed on a 15 bit LFSR? surly it would not fit? (x^14 + 1 being taps at either end of the 15 bit LFSR following the examples?)

I have written code for this also and have placed taps 000001111100000, which i think is the correct tap sequence, however this outputs only 14 bits, being way under what i estimated. 0s and 1s being different then mentioned above. This also doesnt match the 4 bit examples i was given which is confusing me very much.

Where am i going wrong, any advice on this would be appreciated, thanks.


texts: What is the time requirement for pairing computation and modular exponentiation?

texts: I want to design a cryptographic protocol for encrypted search without pairing. I have seen some papers for protocols without pairing. How would I compare pairing computation and modular operations?


texts: Is it possible to sample HE ciphertexts using pseudo-random generator?

texts:
I'm trying to sample HE ciphertexts which serve as ciphertexts encrypting some random values. I have realized a example program using Microsoft SEAL, which implements a variant of BFV scheme. Unfortunately, the ''noise budget'' of these uniformly-distributed ciphertexts is zero and thus they cannot support any further homomorphic evaluation. However, when I draw these ciphertexts from discrete Guassian distribution (with mean = 0), they have non-zero ''noise budget'' and work fine.

I'm quite confused about this result. Since BFV scheme is IND-CPA secure, its valid fresh ciphertexts should be indistinguishable from malformed ones (i.e., drawn from uniform distribution). However, the experiment result shows that a uniformly-distributed ciphertext does not form a valid ciphertext of BFV scheme with overwhelming probability.

Is there something wrong? Many thanks.


texts: Generic hardcore predicate for one way functions

texts:
I'm going over hardcore predicates now and trying to understand the concept.
Some lecture slides I've seen online imply that there cannot be a generic hardcore predicate for all one way functions because for a OWF f(x) and predicate b(x) you can always define g(x) = (f(x), b(x)).

Which supposedly gives up the information of what b(x) is while g remains one way (because f is).

My question is, what about the predicate b(x) = x?

Since the functions are one way, there is no way we can guess x given f(x) in an easy manner.

And if we were to define a g as before it would no longer be one way seeing as it gives up what it's initial input was.

Am I missing something? Maybe I misunderstood the lecture and there does exist a generic hardcore predicate for one way functions? Any helps would be appreciated.


texts: Can I use the same key pair for authentication and Diffie-Hellman?

texts:
Assume Alice has a key pair $(A, a)$ and Bob has a key pair $(B, b)$, where $A = Ga$ and $B = Gb$. In general, the basic rule of crypto says that we should not use the same key for different operations, like in signing and encryption, but I wonder whether in my use case it would be actually possible to use it. Below, I describe the simplified version of my use case.
So Alice and Bob are communicating over an anonymous network, like for example Tor. Also, Alice and Bob from time to time publish (independently of course) some data signed with their private keys.
Alice doesn't know Bob, and Bob doesn't know Alice. They only are aware of their advertised identity keys A and B. Alice when sending the message $m$ to Bob uses Diffie Hellman to derive a shared key. First, for each new message, she generates a new ephemeral key $x$ and computes the key shared with Bob as $k = KDF(B^x)$ (alternatively, maybe she could first apply some Hash function on B, i.e., h = H(B) and compute $k = KDF(h^x)$, not sure? ). Next, Alice encrypts $m$ as $c = AES_k(m)$. She concatenates $g^x$ and $c$ as $v = g^x || c$ and sends it to Bob.
So, in my use case, Alice doesn't reveal any information about herself due to the freshly generated ephemeral key and the anonymous channel (which I assume is secure). She doesn't learn anything about Bob others done his identity public key $B$. Also, as long as Bob's secret key is kept safely no one should be able to decrypt the content of $c$ except for Alice and Bob, which is crucial.
So, is there anything that can go wrong here? If for example Bob published let's say a document signed with his private key $b$, does this allow anyone to infer any information about $m$? In general, my question is whether I'm missing any attack which might compromise the confidentiality of the communication between Alice and Bob? Many thanks in advance!


texts: How to avoid a chicken and egg scenario with encrypting passwords?

texts:
I am working on application that allows users to upload files containing company data and then share those files with a list of other users that have specific roles within the system.

I want to encrypt the uploaded files to protect the data at rest while allowing the files to be shared by people who do not know the encryption password. The uploaded files are owned by the company that they belong too not by the user who uploads them.

When a user creates an account on the system a private-public key pair is generated for the user, the private key is stored in the database and is encrypted with the users clear text password, which is accessible during the login process. User passwords are salted, , stretched hashes so other than during login the app does not know the clear text of the users password.
When a user log's into the system successfully the encrypted user's private key is pulled from the database, decrypted and the private decrypted key is stored in the http session. I am assuming that while the decrypted private key is in RAM it going to be very hard but not impossible for a hacker to get a private key out of the RAM of a running process.
When a user uploads a file the following happens:

A secure random UUID is generated and used as the password to encrypt the uploaded file using AES 256
The generated UUID is then encrypted with the user's public key and stored in the database.
The system determines a list of every user that can access that file

For every user that can access the uploaded file the generated UUID is encrypted with that user's public key and the encrypted UUID is stored in the database.

When a file is being downloaded here is what the system does.

It locates the encrypted password for the file being downloaded
Decrypt the encrypted password using the user's private key
decrypt the file using the file password
return the clear text of the file to the user

To me this seems to be more secure than just storing the files on the server unecrypted a hacker who steals a copy of the data would not be able to read the files, since they would have to figure out the clear text passwords of the users before they could get at the user's private key.

The problem is dealing with password rests, since the users private key is encrypted with the users password if the user forgets their password and does a password reset they would loose their private key and thus access to the files they uploaded. Since I need to have a password rest feature in the application I am into a chicken and egg scenarios because how do I safely store the private keys of the users without end result being less secure than doing nothing?

Is there any way to store private keys that are encrypted with a users clear text password and still have a way when resetting a password to preserve access to the users data?

I am not a security expert and would prefer to use a known solution / library for this problem but I can't seem to find any so I have to make my own solution.


texts: In reality, it is not practical for ciphers such as stream ciphers and AES to generate keys using a TRNG, so instead they have to use a CSPRNG. As an LFSR can generate pseudo random numbers,so can a LFSR be adapted so it can be used as CSPRNG, and what are the other ways to construct a CSPRNG.


texts: What kind of ECDSA signature encoding is this?

texts:
I am trying to generate an ECDSA signature using ARM's CryptoCell 310 (hardware cryptography module) and verify the signature using mbedTLS software library.

The harware module documentation says that the ECDSA is performed according to
ANS X9.62 standard.

The cryptocell generated signature for SECP256R1 is 64 bytes long and looks like this:

95D9AFCC53A8618FF99AA7AB86013F59148B112BDFB15A7775BDE04B1001A84AB77A0F1C82327BA3B420AA172DB288CA030028CAF7C43637EF3B9990B21D082C

I need to convert it into DER encoded signature so that mbedTLS can verify it, but I don't know how the R and S parameters are encoded in it.
I have tried to take first half of that string as the R parameter, second half as S and encode it to DER like this:

304602210095D9AFCC53A8618FF99AA7AB86013F59148B112BDFB15A7775BDE04B1001A84A022100B77A0F1C82327BA3B420AA172DB288CA030028CAF7C43637EF3B9990B21D082C

Unfortunately it didn't work. I have also tried to do big/little endian swaps, trying the second half as R and first as S, but it still didn't work.

I have tried to obtain the X9.62 standard, but couldn't find anything about the encoding.

Does anyone know what encoding is that?

Thanks in advance.


texts:
Consider a bilinear pairing $e: G_1 \times G_2 \rightarrow G_T$. Let's assume, $G_1 = G_2 = G_T = (\mathbb{Z}_n,+)$, i.e. additive group of integer modulo $n$ and $e(x,y) = xy$ mod $n$. Isn't it an example of bilinear map?

$G_1 = G_2 = G_T = (\mathbb{Z}_n,\ast)$, i.e. multiplicative group of integer modulo $n$ and $e(x,y) = y^x$ mod $n$, is it still a bilinear map?

Can there be other bilinear map defined over $\mathbb{Z}_n$?

EDIT:

Actually all my question were to understand Groth-Sahai proof system. Here, they have recast the general equation to fit the form of a quadratic equation. (See teh highlighted part below). But, how can they remark that all maps with $f(x,y) = xy$ mod $n$ will satisfy properties of bilinear pairing?


texts: Is there a reference where all common formal security-definitions are summarized (such as OW-CPA, IND-CPA, IND-CCA1, IND-CCA2, EUF-CMA and so on)? I need a PUBLISHED reference (paper, book) which would be possible to handily quote.


texts: What does "constant rate" mean in universal composable commitment scheme?

texts: I'm wondering what does the "constant rate" mean in universal composable commitment scheme? I have known the rate of a commitment scheme is message length divided by the communication complexity of the scheme. What's the "constant" mean here? Must the constant be a number less than 1?


texts:
Question:
  A stream of cipher operates on a data stream of 6-bit characters using a simple mono-alphabetic substitution technique. Estimate and explain the number of different substitution alphabets possible. The key is effectively the substitution alphabet, which can be expressed as a $384$-bit number (i.e. $64×6$ bits).

  Discuss the security of this system compared with DES/3DES and a one-time pad, providing a full justification for your conclusions.

This is a past exam question which I am struggling to solve. I am not a security expert, nor intending to move in that direction as a career path. The module is part of my MSc course and has nothing to do with my career.

Answer (what I have so far):

The number of different substitution alphabets is $26!$ (factorial), assuming use of the English alphabet. It is also assumed that letters can be in any position and cannot repeat themselves.

Why is the key suddenly expressed as a $384$-bit number? I don't understand. Why $64·6$?
We don't have $64$ characters in our alphabet...if each character within the English alphabet is represented with $6$ bit, then it should be $6·26=156$ bits. Correct?
Now I am thinking if the question says $64$, maybe the alphabet is custom (like including uppercase letters and some numbers + characters), so the number of permutations is $64!$ (factorial). Is this correct?
What does this key look like (or an example of such a key)?
I understand key substitution with a single key word. For example:

abcdefghijklmnopqrstuvwxyz
hatredbcfgijklmnopqsuvwxyz
Can you help me determine what the substitution alphabet key should look like?
I went to Wikipedia's page Six-bit character code and became even more confused. Is this link even relevant?

I would appreciate examples more than answers. Thank you. If you find my question too long, please ignore the part about comparison with other encryption systems.


texts: Can AES decryption be used as encryption?

texts:
Definition

E: AES encryption
D: AES decryption
x: plain text
y: encrypted text
k: key

In original AES cipher,

encryption: y = E(x, k)
decryption: x = D(y, k)

Then I define the "reverse AES cipher" as below.

encryption: y = D(x, k)
decryption: x = E(y, k)

Is "reverse AES cipher" safe as original AES?
or, is safe but the strength is not simply comparable with AES?
or, is not safe?

Or, do anyone know any ciphers that can be used as above and are safe and practical as AES?


texts: How can we authenticate a public key with limited secure side channel?

texts:
I'm looking for a method for 2 peers verifying the authenticity of each other's public key that was transfered over an insecure channel and where the needed secure side channel can only transfer short values (significanlty shorter than the length of a cryptographic hash) but in both directions. Are there standard methods for this?

Otherwise, the most naive approach would probably be only comparing a small part of each others public key, e.g. the first few bytes, or alternatively the first few bytes of a cryptographic hash of the keys. In this question it is already mentioned that this is not a good method when the prefix gets too small, but couldn't this be somewhat compensated by also exchanging randomized starting positions (instead of starting the comparison at the beginning or any other fixed position) over the secure channel to minimize the probability that a man-in-the-middle attack works?


texts: Found a mistake in a proof about when GGH will decrypt incorrectly

texts:
The proof is here on page 66, lemma 20. I found the same mistake in other sources also.

It claims that GGH decryption will fail only if $\lceil R^{-1}e\rfloor \not =0$. Here $R$ is the "good" private basis for the lattice and $e$ is the small random vector. Rounding symbol means just that every coordinate of the vector will be rounded to the nearest integer.

In the proof they use the "fact" that $B^{-1}R$ is an unimodular matrix. They come to this conclusion from the fact that the two bases are connected by a unimodular matrix $U$ like this

$$B=UR.$$

This is correct. However from this they deduce that $$U^{-1}=B^{-1}R.$$ This is clearly false. Actually $$U^{-1}=RB^{-1}.$$ There is no guarantee that $B^{-1}R$ is unimodular.

Have any of you come across another way to prove this result?


texts:
What's the difference between substitution and permutation in DES?
From my understanding substitution is replacing the data with new data and permutation is just rearranging the data?


texts:
Bear with me, I'm a utter newbie in this field.

I'm looking for a way to tackle this:

  Alice and Bob have a secret document. Alice gives Bob a key to secure
  the document. Bob uses this key to encrypt the secret document. Nobody
  that finds this key should be able to decrypt the data. Alice holds a
  special key that can decrypt the document.

  Some time passes and Bob needs to read the document again. Alice gives Bob
  the special key to decrypt the data.

So in this scenario, once the document is encrypted only Alice has control over when Bob can read the document with her special key. We assume that the key Bob used to encrypt the document can stolen or found. So the key to encrypt the document can not be used to decrypt it. Only Alice her special key can. So this means: use a public key to encrypt and a private key to decrypt the document. So my research points me to for example: RSA.

Now let's make it a bit more complex and closer to our real scenario:

  Alice and Bob have a secret document. Alice gives Bob a key to secure
  the document. Bob uses this key to encrypt the secret document.

  Alice and Cesar have a secret document. Alice gives Cesar the same key as
  Bob to secure the document. Cesar uses this key to encrypt the secret
  document.
  Nobody that finds this key should be able to decrypt the data. Alice holds a
  special key that can decrypt the document.

  Some time passes and Bob and Cesar need to read the document again. Alice gives Bob and Cesar each a different special key decrypt the data.

So this is sorta the same as before. Only this time we use multiple private keys and one public key. My first option was RSA but since RSA can only have 1 private key, what are my options?


texts: GGM PRG construction: Why do we need to change keys all the time with underlying PRG

texts:
When constructing a PRF that has n bit input using the GGM PRG, why do we always have to recursively run the PRG using its previous output as a seed key n times. Instead, why don't we run the PRG n times, and use that as the output.

Any answers would be great. My assumptions is that it has something do with producing independent random blocks, but surely a secure PRG would satisfy this?


texts: Is it safe to XOR-combine hashes by rotating them first?

texts:
I have a small number of hashes.
I would like to combine them into a single hash.
XORing the hashes ignores their order, which is important.  Also, it could lead to a result of zero if there were an even number of identical items hashed.
Would rotating each hash (by a distance equal to the item's position) before XORing be secure?


texts: Why does the ElGamal signature have the specific form that it does?

texts:
In the original paper, ElGamal(1985) starts his discussion of signatures by saying:

"The signature ..... is chosen such that the equation:

$\alpha^m = y^r r^s \text{mod p}$ (equation 3 from the paper)

is satisfied."

(In this paper:
$m$ is the message, $s$ is the signature, $y=\alpha^x$ mod $p$ is the public key, $x$ is the private key, $k$ is the ephermal (secret) key and $r=\alpha^k$ mod $p$)

Everything else follows from this. Why this particular form? What the rational if any? This just seems to come out of no where. Why not, for example:

$\alpha^s = y^r r^m \text{mod p}  $

with $s = rx+km$?
(There is probably an obvious reason that I am missing, please do point it out!)


texts: Secure Multiparty Computation with Secret Output

texts:
Is there any MPC scheme that allows a function with several secret inputs to be computed, while the output can only become known to one specific party?
If not, is this even possible?


texts: Have time-release servers been implemented?

texts:
Conceivably, Alice could release a public encryption key and promise to release the private decryption key on a certain date. That way anyone could use that encryption key, combined with others from similar services, and throw away the key so the message will only be readable after a certain proportion of the keys have been released.
This procedure is explained here and here.
Does such a service actually exist to date?


texts: Why is keysize almost always expressed in bits?

texts:
I've never actually seen a time when somebody has expressed RSA keysize in bytes, and I haven't seen keysize expressed in bytes in other encryption algorithms either (can't be certain that that's always the case). Is there a reason why keysize is almost always expressed in bits instead of bytes (in encryption algorithms in general, not just RSA)?
P.S. if possible possible, please link any documentation to support your answer.


texts: What's a quadratic map and how do I invert it?

texts:
I'd like to get just the mechanics of multivariate-quadratic cryptography, so I'm trying to understand the definitions involved.  From Wolfram's website, I get that a quadratic map is for example a recurrence of the form $x_{n+1} = 2 + (x_n)^2$.  I will need an initial value too, right?  I choose $x_0 = 3$.  What's the inverse of this map and how do I get it?

I'm guessing an inverse of a quadratic map would be the transformation that takes $x_n$ back to $x_{n-1}$ so the using the example given in the first paragraph, $x_0 = 3, x_1 = 11, x_2 = 123$.  So given $x_2 = 123$, I can return to 11 by subtracting 2 and taking square root: that is, $x_{n-1} = \sqrt{x_n - 2}$ is the inverse map of my example.

It's just a guess.  I've never seen these things before.  Can't find any reference that explains this in baby-steps.

Also, I'm wondering what would be an example of a quadratic map whose input is say a vector.  My example is a 1x1 vector.  What would it look if my input would be a 2x1 vector?


texts: How does the user get the private/public key with HMAC based request signing?

texts:
I need to implement a HMAC signing of requests and I have read this article which explains the basics of what it is and how to achieve on theory.
https://blog.andrewhoang.me/how-api-request-signing-works-and-how-to-implement-it-in-nodejs-2/
But I have no idea how the user initially gets their public/private key pair. Is it during login or during registration? Do they change? If yes how do you send them the new private key?


texts: Is adaptive security the same as full security?

texts:
This question contains a great answer about adaptive security, but I haven't yet found a proper definition what full security is. Does a stronger security than adaptive security exist or are the two synonymous.

If they are different, what is the difference? If they are not different, why are they referred to differently?


texts: Encryption that can only be decrypted once?

texts:
I want to encrypt a message so that it can only be decrypted once. I know that we can use nonces to do this when we exchange data over a communication channel, but in my case the cipher text will be stored on a disc.

Is there any way to do so?


texts:
Suppose that $\mu(n)$ is a negligible function, which means that for every $c>0$ there is some $N$ such that for all $n>N$ it holds that $\mu(n)\leq n^{-c}$.

Now, imagine that some encryption scheme, signature scheme, or some cryptographic primitive in general has an "error" (distinguishing error, forging error, etc.) of $\mu(n)$.
Imagine that now I want to set up my primitive so that this error is no larger than $2^{-80}$.
If I had the explicit expression for $\mu(n)$ (which is likely to be the case if I read the security proof of the given primitive) then I would solve the inequality $\mu(n)\leq 2^{-80}$ for $n$.
In practice (even though this is not necessarily the case), negligible functions look pretty much like exponentials $2^{-n}$, so we know that this $n$ will be polynomial in $80$ and therefore it won't be too large.

Now think of the general case.
Suppose I want to find some $n$ such that $\mu(n)\leq 2^{-\kappa}$ for some $\kappa$, let's denote the minimum of such $n$'s by $n(\kappa)$.
We know that such value must exist simply because $\mu$ tends to zero as $n$ approaches infinity.
Moreover, since $\mu$ is negligible, intuition on the definition says that $n(\kappa)$ shouldn't be too large in terms of $\kappa$ (e.g. if $\mu(n) = 2^{-n}$ then $n(\kappa) = \kappa$).
My question is: how do we actually prove this?

Here's my question, extracted from the motivation above:

  Let $\mu$ be a negligible function, and let $n(\kappa)$ be the smallest $n$ such that $\mu(n)\leq 2^{-\kappa}$.
  Prove that $n(\kappa)$ does not grow too fast as $\kappa\to\infty$.

Part of the question requires to specify precisely what is meant by "too fast".
I would love some statement like "$n(\kappa)$ is polynomial in $\kappa$", but I'm not sure how to prove this.

I believe this property is important as this is one of the reasons why we choose negligible functions (besides being closed on additions and multiplication by polynomials): it allows us to get small error probabilities without increasing the security parameter too much.

Any insights on this are welcome.


texts: In Multi-party communication, how can I find that one encrypted value is negative or not?

texts:
I'm using Pailier Cryptosystem as an additive homomorphic system in my scenario. I have two parties: Alice and Bob.
Alice has one pair of (SK, Pk) keys. She encryptes one value using her public key and sends it to Bob. In Bob's side, we need to define whether this value is negative or positive.
How can I achieve that?


texts: Testing speed of symmetric vs asymmetric encryption and decryption using gpg

texts:
I'm aware that symmetric is faster than asymmetric.

I want to test this, but my (obviously incorrect) tests show the reverse.

Symmetric test:

#!/bin/bash

echo create random 100Mib binary file
head -c 100M /dev/urandom > blob

echo encrypt
time gpg --symmetric --batch --passphrase 123 --output blob.gpg blob

echo decrypt
time gpg --decrypt --batch --passphrase 123 --output blob blob.gpg

Asymmetric test (using fred's 4096 bit keypair, generated by gpg):

#!/bin/bash

echo create random 100Mib binary file
head -c 100M /dev/urandom > blob

echo encrypt using public key
time gpg --encrypt --recipient fred --output blob.gpg blob

echo decrypt using private key
time gpg --decrypt --batch --output blob blob.gpg

Results:

encryption : symmetric  : 6.2s
encryption : asymmetric : 5.8s         # I expected this to be > 6.2

decryption : symmetric  : 2.5s
decryption : asymmetric : 1.4s         # I expected this to be > 2.5

Can someone spot my error?


texts: Fermat's FFT based large integer multiplication

texts:
I was going through the documentation of GMP (https://gmplib.org/gmp-man-6.1.2.pdf), specially section 15.1.6 where they refer to the use of Fermat's style FFT.

I tried to follow the reference but couldn't quite understand this technique, can anyone explain to me how the Fermat's FFT works?

I don't understand how and why the modulus changes from $(2^N+1)$ to $(2M+k+3)$ using FFT-k splitting?


texts: Value of “counter” when decrypting AES in CTR mode?

texts:
If – when using AES in CTR mode – you decide to use the setup where you combine the IV and the block count value into a single value, as suggested here, the first 12 bytes are your IV and the last 4 bytes the block counter value. But what exactly do you do with block count value in terms of storage and subsequent decryption?

I’ve looked at a number of questions at Crypto.SE and other sources but I can’t seem to find an explicit explanation of this. I’m at a very elementary level of understanding of AES, so maybe some things I’ve read assumed some level of reader knowledge, or it’s figured the answer should be obvious to most.

According to NIST SP800-38A, §6.5, if we let our 12 byte IV be $INPUT\ BLOCK$ in the diagram and our 4 byte block count value be $COUNTER$, the 16 byte IV/block count is incremented by $1$ up to $n$; the number of plaintext blocks you have.

When you are done encrypting and are ready to store the data, do you subtract $n$ from the 16 byte IV/block count (equivalently just storing the 12 byte IV with the ciphertext) or would you store the entire 16 byte IV/block count (not resetting the counter)?

I guess my confusion stems from the fact that – when using CTR mode – the counter just reset to 0 and because decryption with CTR is the same as encryption, decryption starts with the 16 IV/block count? Are all the bits in the 4 byte block count are set to zero since you’re starting over, or does the counter start at $n$?


texts: Application of MDS matrices in serial and round-based implementations

texts:
We know that MDS matrices are used in the diffusion layers of block ciphers.

My question: what types of MDS matrices can be applied to serial or
round-based implementations or both of them?

I appreciate you to address some references.


texts: Mathematical and empirical analysis of AES

texts:
Hello everyone and happy new year in advance.
I'm doing a work about the analysis of the AES algorithm, and I have some doubts about this.
First, I need to do the mathematical analysis of the algorithm:
Determine the computational complexity, worst-case, average-case and best-case
As AES performs n numbers of rounds (10, 12, or 14) and we have a loop, I made a summation for an iterative algorithm, and I have this:
$\sum_{i=1}^m 1=n$,
So, my conclusion is that, if I want to encrypt n number of bytes, the most, the average, and the least number of bytes that I must encrypt is n, I cannot encrypt more or less than that. Therefore:
$n \in O(n)$
$n \in \theta(n)$
$n \in \Omega(n)$
My conclusion is that, the cases (worst-average and best) are equivalent and AES have a linear complexity (depends on the number of bytes that I want to encrypt).
Determine de design paradigm
I don't know if this question is clear for you, I need to determine if AES is in one of the following design paradigm: Brute Force, Divide and Conquer, Decrease and Conquer, or Transform and Conquer
My analysis:
AES is designed to work in blocks of 16 bytes, and if we have more than 16 bytes it is supposed to DIVIDE the text in blocks of 16 bytes and work with each block until the whole text is encrypted.
Therefore, my conclusion is that AES has a Divide and Conquer design paradigm; and going deeper, is a divide and conquer by a constant factor (16).
I would really appreciate your opinion, and corrections, if necessary, to my analysis and conclusions.
Do the empirical analysis of the algorithm, and see if it is consistent with the mathematical results
For the empirical analysis, my idea is just to measure the runtime with different number of bytes, then fit a curve and see if it is linear. If you can suggest, maybe, a better or more advance way to do this, it would be great.
I would really appreciate your opinion and help with this.
Thanks again, and happy new year.


texts: Comparison Vigènere vs. Monoalphabetic cipher

texts:
I have a question for a class of secure communication, but I have no idea about how to proceed in order to answer it. I'll be very grateful to whom replies to me.

Assuming that brute force attack with 80bit keys is infeasible, let's compare the security of the Vigenere cipher with the security of the monoalphabetic cipher in the ciphertext-only attack model considering the encryption of 10 character messages with randomly chosen secret keys for each encryption.

Which cipher among Vigenere and monoalphabetic provides better security when the security criterion is only based on the size of the key space ( brute force attack )?
Is there any other consideration for which the answer would be different than in a)?
Can any of these ciphers provide absolute security? if so give a precise definition of the configuration that would allow for it.

Hint: $2^{80}=1.2 \cdot 10^{24}$ ; $26^{10}=1.4 \cdot 10^{14}$ ; $26! = 4 \cdot 10^{26}$


texts: Having trouble understanding reduction functions in rainbow tables

texts:
I'm continuing doing some personal research on rainbow tables, but forsome reason I cannot understand how to choose the correct reduction function. Wikipedia states that

"Only when the attacker has a good idea of what the likely plaintexts will be they can choose a function R that makes sure time and space are only used for likely plaintexts, not the entire space of possible passwords."

In this case, how can a reduction function like taking the last 6 characters of a hash as a reduction function serve in a rainbow table trying to find a password such as Password123? It would be really helpful if someone would explain this for me. Thanks


texts:
AES-GCM seems to be used by everyone, but I have never seen even one post about Salsa20-GCM. Is it secure? Wikipedia mentions that GCM uses a block cipher, but also that it uses CTR mode.

I am seeking an authoritative citation that I can reference in my project documentation, but personal opinions and arguments are welcomed too.


texts: Is there a deterministic one-way collision-free crypto algorithm?

texts:
I use usernames encrypted using a function f as ids of records. Users see records identified by f(username). I must not know real usernames.

I want to be protected from attack when adversary who has a username u1 and knows f generates another username u2 such that f(u1) = f(u2), logs in with this username and sees the data of user with username u1.

So, f must be:

deterministic: I use f(x) as identifier. It rejects RSA encryption with throwing out secret key.
one-way: I must not be able to get a real value from encrypted value.
collision-free to prevent attack describes above. It rejects md5/sha because as far as I understand they are easily crackable, especially because I don't use salt (unavoidable technical reasons).
quick to compute: I must handle tens of thousands messages per second. It rejects b/crypt.

Note that I don't care about length of output (it may be fixed or variable).

I was looking at MAC and Digital Signature algorithms but can't figure out which of them have required properties.


texts: Given a private RSA key, how do we get the public key?

texts: Is it possible to pre-choose a private RSA key, then obtain a public key from it?


texts:
I want to encrypt with AES CCM* and i dont understand the nonce generation.
the toolkit i'm using has a function to generate the nonce for CCM but it needs the following params:

param src_addr      The MAC address in EUI-64 format.
param frame_counter The MAC frame counter.
param size_of_t     AES-CCM* MAC (tag) byte size. Valid values = [0,4,8,16].

i know the MAC size but how do i get the other parameters BEFORE even running init?


texts: Do the limitations of PRNGs apply to CSPRNGs when shuffling a list?

texts:
Suppose, as an example, we want to use the Fisher-Yates algorithm along with a pseudorandom number generator to shuffle a deck of cards. We know that there are limitations with respect to the internal state of the PRNG and its ability to reach the distinct permutations of the deck. If, for example, the PRNG can only be seeded with $2^{32}$ bits, then it cannot possibly produce all the $52!$ distinct permutations. In addition, even if we could meet the 226 bits needed for a 52-card deck, the distribution may not be uniform.

Now, suppose we switch and swap the PRNG with a CSPRNG. How do these limitations apply? In practice, they're seeded and reseeded frequently, depending on implementation, but this is generally done behind the scenes. Since CSPRNGs are PRNGs, my initial thoughts would lead me to believe that they will suffer the same limitations. Yet, if we used a PRNG with the same seed, but continuously draw numbers from it, we could reach additional permutations.

Over yonder in response to this question, one answer suggests that a cryptographically strong source of unbiased numbers will reach the desired permutations. Would you agree?

Finally, I used a deck of cards as an example. I'm curious about list sizes with respect to this question. I know that with PRNGs, the seed bits must increase to accommodate larger lists.


texts: Are hash functions "intentionally" designed to be efficient?

texts: I am curious to know if the hash functions are intentionally designed to be fast, or it happens to be like this. This is very interesting to know because on the one hand, efficiency is not considered as a property to design a hash function. On the other hand, if they are not efficient, a lot of applications and protocols will be affected, e.g., the hash chain.


texts: Any famous approach for analyzing the randomness of data?

texts:
I'm writing a function that will allow me to analyze the randomness of some input data and return some stats about the probability of this data to be random.
Obviously it should be based on two things:

How often each byte value is found / not found (randomness / distribution)

And how much data we have (certainty)

So among the outputs of my function will be two values:

"randomness" (0 - 100) which tells how random the bytes look (regardless of how much data we have)
"randomlike" (0.001 - 99.999) which tells the general likelihood of the whole data to be random (a combination of randomness and length).

Is there a famous approach for this or I have to rethink the whole logic from scratch? This is probably something widely used in cryptography because this is how we can test keys: the decrypted data is highly random until the key is right.
I'm not looking for any particular language, just the math/logic approach.
One thing that puzzles me is: What does 50% randomness correspond to? Is it a subjective thing (like an art...) or math has some scientific ways to define what "50% randomness" means.


texts: Why hash ( clear text + Secret ) instead of hash (encrpt(clear text) [ + secret ] )

texts:
Here is an excellent article on how SSH Authentication and Encryption works.

While thinking about how MAC's work, I had the same doubt as one of the comments left on the post:

The client combines the decrypted number with the shared session key that is being used to encrypt the communication, and calculates the MD5 hash of this value. Any reason why the client combines the decrypted number with session key to calculate md hash? Why not calculate md hash directly for the decrypted value?

Is it just to avoid the negligible overhead of encrypting?

(Which will any way get masked after hashing and add no protection or value--assuming the shared secret size makes no difference for the hashing function.)


texts: What is the importance of Modular arithmetic in cryptography?

texts: Why do we use modular arithmetic so often in Cryptography?


texts: What information does $g^x$ reveal about $x$?

texts:
Let $p$ be a large prime number. Let $G$ be a subgroup of $\mathbb{Z}_p^*$ with order $q$ - again a large prime. Let $g$ be a generator of $G$.

Consider the following standard protocol for generating a random element $x \in \mathbb{Z}_P$:

Player 1 generates a random number $x_1 \in \mathbb{Z}_p$ and outputs $g^{x_1}$ as a binding commitment.
Player 2 generates a random number $x_2 \in \mathbb{Z}_p$ and outputs $g^{x_2}$ as a binding commitment.
The two players reveal $x_1, x_2$, and after checking consistency with the commitments, the output of the whole process is defined as $x = x_1 +x_2 \ (\mathrm{mod}\ p)$.

Suppose now that Player 2 would like to manipulate $x$. Her strategy is the following: She sees $g^{x_1}$. She generates $n$ random number $a_1, ...,a_n$. She computes $g^{x_1+a_1}, ..., g^{x_1+a_n}$, see which one she likes best, and sets $x_2$ accordingly: $x_2 = a_i$ for some $1 \leq i \leq n$. Finally, she outputs a commitment $g^{x_2}$.

This scheme is not considered secure, since Player 2 can obviously affects the distribution of $g^{x_1+x_2}$ and therefore the distribution of $x$.

  My question is, can Player 2 really manipulate $x$ to her benefit?

One way to formalise this question would be: Let $A \subset \mathbb{Z}_P^*$. If Player 2 is honest, we have
$$
\mathbb{P}[x \in A] = \frac{|A|}{p-1}.
$$
Can Player 2 increase this probability using the above strategy?

(Naturally, $A$ can be defined by "the set of all numbers $x$ in $\mathbb{Z}_p$ such that $g^x$ has a '1' in the last digit" and then Player 2 can easily make this probability equal 1, so this formalisation is not very good. Suggestions?)


texts: Authorities on password hashing best practice

texts:
I am trying to understand how best practices on password hashing come about. With password hashing, I mean specifically for the case of storing user passwords in a database in a hashed representation, in order to compromise user passwords if an adversary gets access to the database. I understand that recommendations (especially algorithm, number of rounds, etc.) continue to change.

My question is, who would be authoritative sources on what is currently best practice, and where and how can I keep up to date?

Right now my process is that I notice someone saying something about best practice in a StackOverflow answer that does not fit my understanding, and then I start digging for more information. This seems backwards, and I'd like to get ahead on this thing.


texts: For the LTV-FHE scheme, after how many additions should modulus switching be used?

texts:
From the LTV-FHE paper I find out that after every multiplication there must be a modulus switch to mitigate the noise in the resulting ciphertext, besides relinearization.

But, assuming the ciphertexts to be summed are the result of many operations and we have consumed many levels of the moduli ladder, that means that the room for noise is smaller. ( The assumption that the room for noise is getting smaller may be wrong, I haven't found any proof yet, is my personal observation.)

So, if we evaluate homomorphically many additions of ciphertexts like those aforementioned, should we use modulus switching to cut the noise before wrap around ?


texts: How to choose between AES-CCM and AES-GCM for storage volume encryption

texts: We are using the encryption built into Solaris 11 ZFS, which offers the choice between CCM (CBC counter mode) and GCM (Galois counter mode). What are the pros and cons of choosing each of these cipher modes?


texts: Secure modulus length for Diffie-Hellman

texts: What is secure modulus length for modular exponentiation so that finding discrete log is computationaly impossible?


texts: HMAC-SHA1( secret key ) with header of a transmitted file

texts:
Given:
an AES-128 secret key (ASecKey) encrypts a file (CBC mode).
(Assume good random)

Is is insecure to append (include) an HMAC-SHA1 of ASecKey to file?

Purpose:
The receiver can then quickly verify if the shared secret key was used to encrypt.


texts:
Unsure whether this is the right forum for this question, worth a try.

The task im faced with is to implement a poly-time algorithm that finds a nontrivial factor of a carmichael number. Many resources on the web states that this is easy, however, without further explanation why that is?

Furthermore, since miller-rabbin exits when a nontrivial square root of 1 is found, this can be used to find a factor to the carmichael number: $x^2 \equiv 1 = (x+1)(x-1)\equiv0\ mod\ N$, where N is the carmichael number we want to factor. Hence factors must be found using $\gcd(x+1,N)$ and $\gcd(x-1, N)$, correct?

Due to problems with strong liars, in some cases we will miss out on factors, is this a major problem? Since miller-rabbin tests only passes composites with a probability 1/4 is it correct to say that the chances of finding a factor is > 0.5?

Kind regards!


texts: Multiparty key exchange for end-to-end encryption

texts: I need to make end-to-end encrypted messaging between 2 and more parties without trusting a server. Each party has it's secret and private keys. The obvious solution is to make ECDH between all of them, but it may require N-1 key exchange rounds. Is there another way to generate shared secret among N participants with less rounds required than ECDH?


texts: Simple commitment scheme using secure hash function

texts:
Can I create a simple commitment scheme using a secure hash function?

If so, is concatenation with a random secret enough to preserve hiding? (i.e. $C = H( random\_string || message)$)

Thank you


texts: What's the difference between a Key Derivation Function and a Password-Hash?

texts:
It seems to me that anything that was sufficiently good as a KDF would work just fine as a password hash, though the reverse might not be true.  Are there considerations specific to password-hashing that don't apply to KDFs?

To clarify: This is about key-stretching KDFs.  Not the kind for diversifying keys (eg. HKDF)


texts: Decisional Diffie-Hellman: compute Legendre symbol of $g^{ab}$ from $g^a$ and $g^b$?

texts:
From https://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption:

  Importantly, the DDH assumption does not hold in the multiplicative group $\mathbb {Z} _{p}^{*}$, where $p$ is prime. This is because given $g^{a}$ and $g^{b}$, one can efficiently compute the Legendre symbol of $g^{ab}$, giving a successful method to distinguish $g^{ab}$ from a random group element.

The only way I can think of to distinguish $g^c$ from $g^{ab}$ is:

If $\left(\frac{g}{p}\right)=-1$, then $\left(\frac{g^{ab}}{p}\right) = 1$ if and only if $a$ or $b$ is even (which is $3/4$ of the times).
So if $\left(\frac{g^c}{p}\right) =-1$, probably $g^c\neq g^{ab}$. Nothing is certain.

How'd do you compute $\left(\frac{g^{ab}}{p}\right)$ given $g^a$ and $g^b$?


texts: Performance of RSA encryption when the public exponent is 3 and 65537

texts:
I wanted to test the performance of RSA encryption when the public exponent was 3 and when it was 65537. Python and M2Crypto library were used to generate keys and do encryption:

key = RSA.gen_key(KEY_SIZE, 65537)
key.public_encrypt(s, RSA.pkcs1_oaep_padding)

where s is a 256-bit string and KEY_SIZE is 2048 bit. For each exponent value, I generated 10000 RSA key pairs and measured the total time they took to encrypt the data string (not included the key-generating time).
I expected that when the public exponent was 3, the running time would be much shorter. However, they took almost the same time (around 27 seconds). I used the time.time() function in Python to measure the running time.
Can anyone explain me the reason?
Updated: I have tested the same operations with PyCrypto, Java (using Bouncy castle library) and C (using OpenSSL library) as well. Here are the results:

PyCrypto: around 5s for both public exponents (PE).
Java: 0.7s for PE = 3 and 1.5s for PE = 65537
C: 0.11s for PE = 3 and 0.27s for PE = 65537


texts: "hash trail", iterative hash function that can be traced back along many steps

texts:
What are some examples of an iterative hash function, where permutations along

A ---> B ---> C ---> D

can be compared, for example D/B, to see if D is a trail from B, and possibly the distance in steps from  C to D


texts: processing time for multiplication and exponentiation in pairing base cryptography

texts:
I'm using the Boneh-Boyen-Shacham signature scheme and want to estimate complexity in my scheme.

As reported in "Scott M., Efficient Implementation of Cryptographic pairings", if we set parameters as: MNT curve, k=6 and p~160, then P(point mul)=0.6 ms and P(pairing)=4.5 ms.

These two measured times are used in many references. I found another reference (Lu, Rongxing, et al. "A dynamic privacy-preserving key management scheme for location-based services in vanets.") stating P(point exponentiation)=0.6 ms and P(pair)=4.5 ms.

I cannot understand how can I compute processing time for multiplication and exponentiation operations in BBS scheme in following image…

Questions:

How many multiplications and exponentiations do we need, and
what is the processing time of each operation?


texts: Purpose of using a=2 in Pollard p-1 factorization method

texts:
The Pollard p-1 factorization method states if $\gcd(2^{B!}-1,n)=p$ where $p>1$ and $B$ bounds the prime factors of $p$, then $p$ is a prime factor of $n$.

Shouldn't it be $\gcd(a^{B!}-1,n)$ for any arbitrary $a$?
Why are we choosing $a=2$? Is it because it is computationally cheaper to compute powers of $2$? ( left shift ).
Moreover, should $B$ be an upper bound of the prime factor of $p-1$ or an upper bound of the prime factor of $p-1$ along with its powers?


texts: How to attack this authentication protocol from "Cryptography: An introduction"

texts:
Consider the following protocol (from the book "Cryptography: An introduction", by Nigel Smart):

A → B: A, Na
B → S: B, {A, Na, Tb}Kbs, Nb
S → A: {B, Na, Kab, Tb}Kas, {A, Kab, Tb}Kbs, Nb
A → B: {A, Kab, Tb}Kbs, {Nb}Kab

where the smaller letters are the suffix so example Kab means the Key shared by A and B.  Tb represents the timestamp for the message and Nb represents a nonce.

My question is: If an external attacker is impersonating A and S at the same time, how the attacker can manage to trick B into believing A is authenticated?  I'm told I should be able to describe how to do this in exactly 3 messages (omitting one of the messages in the protocol).

My attempted solution is: If A and S are impersonated then when B is sending a message to S, the external attacker will know what is being sent and therefore the attacker can forward the message as normal to A but can corrupt the message. I'm not able to write a protocol as it's a bit confusing.

See also What does this Authentication protocol achieve and what information is shared? for a related question about the same protocol.


texts:
I'm trying to understand the SIDH cryptosystem and got confused at this point:

Alice fixes base $\{P_A,Q_A\}$ so that it generates $E_0[l_A^{e_A}]$. Then she chooses secret parameters $m_A,n_A$ and computes the secret isogeny $\phi_A: E_0 \to E_A$  with kernel $\langle [m_A]P_A +[n_A]Q_A\rangle$. Further section 4 of the 2011 SIDH paper states that both $P_A$ and $Q_A$ have order $l_A^{e_A}$ and are independent of each other.

Doesn't that mean that $[m_A]P_A$ and $[n_A]Q_A$ also have order $l_A^{e_A}$ and therefore $ker(\phi_A) = E_0[l_A^{e_A}]$? That would mean that $\phi_A$ is not secret.


texts: Rainbow Table - Number of Chains and Chain Length

texts:
Is there a difference between having 10,000 of chains (with 1,000 chain length) and 10,000 chain length (with 1,000 of chains)? How does it affect the success rate of the rainbow table?

I understand that only start point and end point are kept in the table. The more chains you have, the disk space increases. Whereas the higher number of chain length would mean longer computing time is required to run through them.


texts: Security implications of repeated hashing

texts:
I have an hash function hash()

I can easily compute the hash of the string "hello" like this:

out = hash("hello");

What are the implications from a security point of view of hashing the same string as:

out = IV;
out = hash('h' + out);
out = hash('e' + out);
out = hash('l' + out);
out = hash('l' + out);
out = hash('o' + out);

I mean hashing single bytes one after another, concatenating the current byte with the previous hash (first hash could be all zeros or some IV).

I know I'll get a completely different hash. Apart from that, what are the security implications of such habit?


texts: Fiat-Shamir paradigm and the forking lemma

texts:
I am reading the proof by Pointcheval and Stern and by Bellare and Neven about the forking lemma. The papers discuss the security proof of digital signatures by applying the lemma. It seems also mentioned that the same proof idea works for showing the Fiat-Shamir transformed interactive proof system is sound in the random oracle model.

I am not sure I understand why the forking lemma implies the Fiat-Shamir transformed noninteractive protocol is sound using a random oracle, or it is essential to apply it for only the soundness. There are many papers about instantiation in the plain model, but that is beyond what I am trying to understand for now.

It would be appreciated if anyone could explain the connection, or point some good references about that.


texts: Pseudorandom permutations on domains of arbitrary (i.e. not a power of 2) size

texts:
The Feistel cipher algorithm produces a pseudorandom permutation with domain size equal to $2^{2m}$ (for some $m \in \mathbb{Z}^+$).  That is, a one-to-one function $\pi$ of the set $\{0, 1, 2, \dots, 2^{2m} - 1\}$ onto itself.

Furthermore, with so-called unbalanced Feistel ciphers, it may be possible (though I don't know this for certain) to produce pseudorandom permutations of the set $\{0, 1, 2, \dots, 2^m - 1\}$ onto itself.

Is there an algorithm (possibly a modification of one of the ones mentioned above) to produce a pseudorandom permutation $\pi$ of the set $\mathbb{m} = \{0, 1, 2,\dots, m - 1\}$ for an arbitrary $m \in \mathbb{Z}^+$?

(Actually, the domain of the function $\pi$ produced by the algorithm may be a proper superset of $\mathbb{m}$, as long as the restriction $\pi|_{\mathbb{m}}$ is a permutation of $\mathbb{m}$.)


texts: How to justify the lightweight symmetric PRESENT encryption algorithm is more secure?

texts:
My domain is VLSI design, currently, I'm working on PRESENT Lightweight cryptographic algorithm.

I want to know how to improve the security of the algorithm rather than increasing bit size?
Is there any possibility to improve the security of the algorithm by using automatically generated keys rather than manually giving data?

Any suggestion?


texts: Change in probability of collision when removing digits from MD5 hexadecimal hash values

texts:
I am aware that MD5 has a known collision vulnerability and should not be relied upon when uniqueness is required, but in the environment I am working on I only have access to MD5 hash function. Background detail below, but in general how much and how bad is the change in the probability of hash collision if I removed a few digits from the hexadecimal representation of MD5 hash values?

Background: I am working on migrating data between two systems. The target system has a built-in database column of length 30 characters that has unique/primary key resolution mechanism, meaning as long as I put a matching value in that column the system will map it to existing record if exists and create new record otherwise. Unfortunately the primary key from source system has length of between 50 to 100 characters so my best bet is to generate a shorter hash value from it. I only have access to MD5 hash function but the hexadecimal hash value is 32 digits long so I have to drop two of the digits. There is virtually zero probability of anyone wanting to use collision attack on the data so my concern is pretty much on the distant possibility of Heaven-assisted coincidence that two primary keys might generate the same hash value.

N.B. Possibly related to "Should I use the first or last bits from a SHA-256 hash?", but that question is about SHA-256 while this one is about MD5.


texts: How to calculate the exponential inverse in elliptic curve Diffie-Hellman?

texts:
In Diffie-Hellman over $Z_p$, I know that if I choose a random $a$ in $Z_p$ and compute the modular inverse mod p-1, not mod p, then, with generator $g$ of my group, I can compute, for example, $(g^{ab})^{(a^{-1})} = g^{aa^{-1}b} = g^{b}$.

I am asking if a similar process is possible over elliptic curves? If I have a generator $P$ and I choose a random $a$ and compute $aP$. How do I do about calculating $a^{-1}$ such that $(aP)a^{-1} = P$?


texts: In CPA, how does one-message security implies multi-message security?

texts:
I am learning modern cryptography and recently we reached the CPA mechanism.
In CPA game setting, A sends two messages to C and then C randomly chooses one message and encrypts it and sent the encrypted text back to A, then A will determine which one of the two messages is chosen by C.
However, if A sends two identical messages, say 'm', to C, A would definitely know the encrypted 'm' by the returned text of C. Then, for the second time, A can send a 'm' and any other message to C, then, if the returned text of C is the same as that of the returned text when inputting 'm', the message chosen by C is 'm', otherwise is that any other message. And this enables A to have a probability of 1 to guess the chosen message of C.
So, it seems that one-message security doesn't imply multi-message security, even in the one-message security scheme, if the two sent messages from A are the same, A still has a probability of 1 to guess the chosen one of C.
Could anyone help me in understanding this?
Thank you for the answering!


texts:
What's the definition of non-linearity of a boolean function? Roughly saying it is minimum number of times it equals any affine function. But I don't get it mathematically.

For example, if $f = x_1x_2$, then all the affine functions are $g_1 = 0$, $g_2 = x_1$, $g_3 = x_2$ and $g_4 = x_1+x_2$, then the non-linearity of $f$ is the minimum Hamming distance between $f$ and $g_i$'s. But what is the Hamming distance between two functions?


texts: AES-CTR and AES-CMAC using the same temporary key

texts:
Is it a severe security issue using a short-lived dynamic key for both AES-CTR and AES-CMAC?

CMAC is generated on the cleartext and 32 bit of it are attached to the message (MAC-and-Encrypt)

The key exchange ensures that dynamic key and NONCE values are never in the clear on the wire.


texts:
I am trying to manually create a GPG Public Key (see here). I am able to generate a GPG Public Key with a correct hash, but fail to RSA-sign that hash in a way that is accepted by the GPG CLI. For the GPG Public Key I have created see here.
To sign the hash I am using a private key on a PKCS#11 HSM. The HSM supports various signing mechanisms. I have tried signing with RSA-PKCS-PSS (with hash algorithm SHA512 and mask generation function MGF1-SHA512), SHA512-RSA-PKCS, and SHA512-RSA-PKCS-PSS, but neither produces a signature that the import command of the GPG CLI accepts. I suppose the GPG CLI expects a different padding.
Unfortunately, RFC 4880 does not explicitely cover GPG Public Key signature padding, but only specifies that EME-PKCS1-v1_5 and EMSA-PKCS1-v1_5 functions are used for PKCS#1 encoding. A quick search through the GPG source code shows that both PKCS#1 v1.5 and PSS are used at some points.
Does anybody know what padding exactly is supported in the import command of the GPG CLI?


texts: How hard to break a cipher if it has a different key for each word?

texts:
Recently I watched the movie 'The Prestige' again but this time the cipher diary impressed  me very well. I like to create my own cipher for my diary because I have some time to kill everyday after deactivating facebook.

So If I create my own substitution table like  'Vigenère_cipher', and use a different key for every page or every word (somehow I manage to remember the key and decipher it), Is it still possible to crack this cipher in anyway?

I read about it some articles, Crackers can detect text patterns and it is easy for them to crack if long text is ciphered using the same key, I think using different keys will reduce this kind of pattern analysis. But I am not an expert in this field, so you can tell me about the possibilities of cracking a cipher written in this way.

NOTE: I am not using this kind of thing to cipher any sensitive data, others data, I am just want to know the possibilities of this thing. I maybe in a wrong thought about all these because I'm not a expert in this field.


texts: The difference between MAC algorithms and what to use

texts:
I've been looking into message authentication codes and found several ways to create integrity for a message. I know of the following algorithms:

HMAC, this can use any cryptograhpic hash function and a key, for a HMAC to be secure the underlying hash function does not have to be (though I assume it would be a good thing to not use broken hash functions just for the sake of good practice) I also understand it is better not to use the same key for encryption and HMAC but to use a different key for both.

GCM, GCM is a mode operation for symmetric encryption ciphers. The benefit of this is that the key you encrypt with, also does the authentication.

CBC-MAC is a MAC based on the mode operation CBC, conterary to what i first thought you first encrypt the text with (for example) AES-CBC and then apply the CBC-MAC (If using encrypt then mac) and it is not the CBC mode for encryption with authentication.

I believe the best thing to do is encrypt then MAC as explained here

What i would like to know (given I'm working with data over internet): what is the best algorithm to provide integrity and did I miss any well-know-good-to-use algorithm.

Also, I've seen these terms used interchangeably but authentication is something different than integrity right? authentication is verifying the sender (PKI) and integrity is verifying the received data (MAC). but then why is it message authentication, i know an other word for it is MIC (which seems better to me) but is used in WPA (when MAC has an other meaning). Could someone be so kind as to explain the terminology as well?


texts: When trying to prove the security of an asymmetric signature, for instance, for existential (or strong) unforgeability against chosen messages attack, do we need to consider the signer as a possible adversary?


texts:
I am trying to figure out this question:

  Generalize the Merkle–Damgård  construction for any compression function that compresses by at least one bit . You should refer to a general
  input length £' and general output length E (with £' > E).

It is in my understanding that the Merkle–Damgård  takes an input of 2*l(n) and compresses it to l(n). How would I go about breaking up the input so that an arbitrary hash length L' can be outputted?


texts:
I've just started studying MACs and I faced the following challenge:

Let $F$ be a PRF over $(\mathcal{K,R,X})$ where $\mathcal{X} = \{0,1\}^{32}$

Let $\mathrm{CRC32}(m)$ be a function that takes inputs $m \in \{0,1\}^{\le \ell}$ and output a 32-bit string and

$\mathrm{CRC32}(m_1) \oplus \mathrm{CRC32}(m_2) = \mathrm{CRC32}(m_1 \oplus m_2)$.

Let's define a MAC system $(S,V)$ as:

$\quad S(k,m) = \{r \small\xleftarrow[]{R}\mathcal{R},\quad t \leftarrow F(k,r) \oplus\mathrm{CRC32}(m), \quad \text{output} \;(r,t)\} $
$\quad V(k,m,(r,t)) = \{ \mathtt{accept} \; \text{if} \;\; t = F(k,r) \oplus\mathrm{CRC32}(m), \quad \mathtt{reject} \; \text{otherwise}   \}  $

How can I prove that this MAC is insecure?

After thinking a lot about how an attacker could send queries (sending messages $m_i$ and receiving its correspondent tags $t_i$) to find an existential forgery, I read that although the attacker can send several queries, they may not help, so I wonder what else can I try in order to break it.


texts: Which crypto libraries/programs do we have the most confidence in?

texts:
I have recently begun studying crypto. If it's one thing I have learned it's that we should not implement our own crypto. Therefore we should look to using existing software and libraries.

When I go to implement something that needs data security, there are many options -- openssl, mcrypt, truecrypt, crypt, pycrypto, bouncycastle... how do I know what is "tried and true" with regard to crypto community scrutiny?
This probably depends on the application, your implementation language, and the data under encryption. What would be generic answers for common scenarios such as basic single-file encryption, full disk encryption, and encrypted network communication?

I could do an audit of source code myself, but I would be naive to say that I could catch even some obvious vulnerabilities.
If TrueCrypt, a high profile piece of crypto software itself, is having widespread calls for a public audit, then what crypto software IS sufficiently audited? It seems to me that if any crypto software should have high confidence with many eyes scrutinizing it, it would be truecrypt or openssl.

And of course, the usual disclaimer; I understand that we can't know all vulnerabilities and bugs ahead of time. And nothing can be infinitely secure. That leaves us with simply a high confidence or low confidence measurement of worth.
Is there a list of high-confidence crypto libraries/software? Maybe confidence isn't well-defined. Is there a list of time-tested crypto libraries/software?


texts:
What is the harm if I publish an encrypted RSA private key publicly?  Or in this case, what is the harm if I publish many thousands or millions of them?

Assuming that the private key is encrypted with a typical user password, the passphrase is some combination of password + user ID (which is not necessarily user-selected), some method of key stretching is used, and that it's not obvious what the key is used for, is there any harm?

The reason I ask is because I am wanting to investigate a way to store public and private keys on behalf of web users for use within a web browser.  The private key would be stored at an HTTPS URL that does not describe the user that owns it nor describes what the key would access.  The data stored at the private key URL would be read-only.

The intention is to assume that any private keystore would be eventually attractive enough to be attacked and breached and therefore assuming that keeping the private key files hidden or protected would be poor or insufficient security.

The fact that this private keystore exists would not be treated as private information.  All keys would be accessible by anyone that knows the URL for each.  There would be no key/directory index provided.  The key files may be stored on simple file storage/hosting systems like Amazon S3, but they would always be served over HTTPS.

Please ignore the issue of possible theft of password via keylogging and ignore the issue of possible theft of unencrypted key via direct JavaScript access.


texts: Combining two almost universal hash functions

texts:
We say that a set of functions $S$ is $\epsilon$-almost-universal if for any function $f \in S$, it holds that $\Pr[f(m) = f(m')] < \epsilon$ for $m \not = m'$.

Assume that we have the following two sets of hash functions:

$F = \{f:M \rightarrow X\}$, which is $\epsilon_1$-almost-universal.
$G = \{g:X \rightarrow Y \}$, which is $\epsilon_2$-almost-universal.

Then, there exists a third set of hash functions $H$ for that it holds:
$H=\{h:M \rightarrow Y\}$ where $h(M)=g(f(M))$ and $H$ is $(\epsilon_1 + \epsilon_2)$-almost-universal.

Now my question is: Why is this the case? Why is $H$ $(\epsilon_1 + \epsilon_2)$-almost-universal?


texts:
In 1999, a news article (Careless mistake reveals subversion of Windows by NSA) discussed "encrypted instruction sets". What exactly are these? Please provide a link so I can find more information.

Does it have anything to do with the following:

A First Practical Fully Homomorphic Crypto-Processor Design

Next-Generation Secure Computing Base

A similar question was asked here some time back (What are 'Encrypted Instruction Sets' ?), but it did not garner any useful responses.

I am already aware of hardware-based encryption & Intel's native support for AES. This one seems very different from the others.


texts: How can I geometrically understand LWE ciphertext and decryption step?

texts:
In the bottom of the wikipedia article of LWE (https://en.wikipedia.org/wiki/Learning_with_errors), we can see construction of Public-key cryptosystem based on the LWE.

But, I cannot understand whole thing geometrically.

From a $n$-dimensional vector space (modulo q), we sample a random vector $\mathbf{s} \in \mathbb{Z}^n_q$ which is exactly a secret key.
I can easily have geometric understanding of it.

A public key is obtained by choosing $m$ vectors $\mathbf{a}_1,..., \mathbf{a}_m $ where $\mathbf{a}_i \in \mathbb{Z}^n_q$.
Then, choose $m$-error offsets $e_1, ..., e_m \in \mathbb{T}$ from normal distribution.
The public key is $(\mathbf{a}_i, b_i = \langle \mathbf{a}_i, \mathbf{s}\rangle / q + e_i)^{m}_{i=1}$.

Using the public key, we can encrypt a bit $x\in \{0,1\}$ by choosing a random subset S of $[m]$ and then defining Enc(x) as

$(\mathbf{a}, b) = (\sum_{i\in S} \mathbf{a}_i, \frac{x}{2} + \sum_{i \in S}b_i)$)

The decryption of $Enc(x) = (\mathbf{a}, b)$is 0 if $b - \langle \mathbf{a}, \mathbf{s} \rangle/q$ is closer to 0 than to 1/2, and 1 otherwise.

$\textbf{What I can imagine}:$

There is one secret vector (point) in $n$-dimensional vector space mod q (is $\mathbb{Z}_q^n$ a lattice)?
There are $m$-public vectors (points) in the space.
For each public vector (point), one publicly noisy constant (inner product of the vector and the secret, which is then added to an offset) $\in \mathbb{T}$ is somewhere in between points in $\mathbb{Z}_q^n$).

$\mathbf{Question}$

Q1. What is the geometric interpretation of the public key $(\mathbf{a}_i, b_i) \in (\mathbb{Z}_q^n \times \mathbb{T})^m$?
  What I can know is we work on $\mathbb{Z}_q^n$ and $\mathbb{T}$. But, where does exactly an element in $\mathbb{T}$ belong along with $\mathbb{Z}_q^n$?
From  2 and 3 above, can we say that secret key is blurred?

Q2. What is the geometric interpretation of the ciphertext and its decryption formula?
  I do not know what's happening by adding public points and adding noisy constants (plus message).
  I guess the decryption works via inner product of $(\mathbf{a}, b)$ and $(-\mathbf{s}/q, 1) $, but why inner product?


texts:
I need to analyse a binary code and check if Keccak is used in this code.
I can identify AES, by using Rijndael S-box. Is there a similiar box for Keccak?


texts:
The CKM_RSA_PKCS Mechanism in PKCS#11 v2.20 section 12.1.6 PKCS #1 v1.5 RSA is a signature scheme commonly used to implement RSASSA-PKCS1-v1_5 of PKCS#1 signature of data hashed externally to a PKCS#11 token (such as an HSM).

With an RSA modulus $N$ of $k$ bytes ($2^{8k-8}\le N<2^{8k}$), CKM_RSA_PKCS signature

accepts any bytestring message to sign $\text{T}$ of $t$ bytes with $t\le t_\text{max}=k-11$; we note $T$ the corresponding integer per big-endian convention ($0\le T<2^{8t}$);
forms a message representative $R=2^{8k-15}-2^{8t+8}+T$
equivalently: $\text{R}=\text{'00'}\|\text{'01'}\|\text{'FF'}\|\dots\|\text{'FF'}\|\text{'00'}\|\text{T}$ of $k$ bytes, among which $k-t-3\ge8$ bytes at $\text{'FF'}$ starting from the third byte;
computes $S=R^d\bmod N$ (that's the textbook RSA private key function);
outputs the signature $\text{S}$ as $k$ bytes per big-endian convention.

The verification procedure checks that $\text{S}$ is $k$ bytes, $S<N$, and compares $S^e\bmod N$ to $R$ corresponding to an alleged message $\text{T}$ of at most $t_\text{max}$ bytes (or, in message recovery mode, $\text{T}$ and its size $t\le t_\text{max}$ are determined from $S^e\bmod N$, and are an output of the signature verification procedure).

CKM_RSA_PKCS signature is not secure when the adversary can obtain the signature of largely chosen messages: it is easy to find distinct $\text{T}_0$,$\text{T}_1$,$\text{T}_2$,$\text{T}_3$ leading to $R_0\cdot R_1=R_2\cdot R_3$, and thus $S_0=S_1^{-1}\cdot S_2\cdot S_3\bmod N$, an (existential) forgery.
Example for 1024-bit RSA: $k=128$, $t=80$, $T_0=2^{632}$, $T_1=2^{377}-2^{16}$, $T_2=0$, $T_3=2^{632}+2^{377}-2^{16}+1$.

Can CKM_RSA_PKCS signature be made secure by lowering its maximum input size? If yes, how does security relate to $t_\text{max}$ and $k$? The adversary's goal is to forge an admissible signature $\text{S}$ that was not obtained from the signer.

Hypothetical case where the issue matters: a time-stamping server generates and appends an 8-byte time-stamp in seconds to any bytestring it receives up to $t_\text{max}-8$ bytes (intended to be the hash of a message by a method irrelevant to the server), and provides the corresponding CKM_RSA_PKCS signature. An adversary able to query the server can forge a signature for the SHA-512 hash of (a slight variant of) any message, that passes verification and appears to have been made by the server before the attack. Techniques from Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures apply, and the attack is much easier, since only the forged signature is bound to have a hash in its message representative.


texts: How to prove correct decryption in Paillier cryptosystem

texts:
Bob sends a ciphertext obtained by Paillier encryption to Alice.

Alice has the private key. She decrypts the ciphertext and returns the plaintext to Bob.

How can Alice convince Bob that the plaintext is correct to this ciphertext? Bob only has the encrypted plaintext and the public key of this encryption.


texts: What public-key encryption protocol can use the same key pair as ECDSA?

texts:
Assume we wanted to use the same ECDSA public/private key pair (drawn for standard ECC parameters, perhaps P-256) for both its intended use (public-key signature), and for public-key encryption; this despite the sound and explicit prohibition in FIPS 186-4:

  ECDSA keys shall only be used for the generation and verification of ECDSA digital signatures.

Do we have an option with an argument that (implementation side channels set aside) it does not jeopardize security of ECDSA, and the encryption is safe under CPA?

Can we achieve this with access to the private key for decryption

strictly limited to ECDSA signing (preferred)
or is it required a more low-level access to the private key?

Note: I'm meaning ECDSA, if at all possible complete with generation of a true random secret at each signature, no mater how superior Schnorr or/and de-randomized signature is (as used in EdDSA).


texts: Length extension attacks, Merkle–Damgård constructions, and HMACs

texts:
The wikipedia page for Length Extension Attacks says "Note that since HMAC doesn't use [Merkle–Damgård constructions], HMAC hashes are not prone to length extension attacks."

However, HMACs can be constructed with hashing algorithms such as MD-5, SHA-1, and SHA-256 which use these constructions. I understand that HMACs are secure even when constructed from these hashing algorithms, but is it accurate to say that HMACs don't use Merkle–Damgård constructions? And if so, why not?


texts: When is $p^n$ negligible? ($p$ may depend on $n$)

texts:
For what $p \in [0,1]$ would the function $p^n$ be negligible? Specifically; if $p$ is allowed to depend on $n$.
If $p$ is a constant between 0 and 1, (say $p = \frac{1}{2}$), then it clearly is negligible. Judging from this plot, if one chooses $p = 1 - \frac{1}{n}$, the resulting function is not negligible.
What about $p = 1 - \frac{1}{\sqrt{n}}$? Or $p = 1 -  \frac{1}{\log{n}}$ ? (or even $p = 1 - \frac{1}{\log\log n}$ etc...?) At which point (between a constant and $1-\frac{1}{n}$) does the function stop being negligible?


texts: How are all necessary parameters shared between signer and verifier in the ED25519 signature scheme?

texts:
I want to use the ED25519 signature scheme in my application which requires frequent sharing of secret data between two entities in the public domain.

I know that the Schnorr signature scheme has a key authentication center (KAC) which decides and shares common parameters to be used by signer and verifier. The KAC also signs the public keys of everyone with its own private key. And then the signer signs the message and sends his public key along with the signature to the verifier [From Schnorr's paper 1991].

But is there any KAC in ED25519? And what are the parameters shared in ED25519 by the KAC?


texts: Can randomness protect a list of signatures against forgery attacks?

texts:
Suppose we have a list of signatures $S = [s_1, .., s_n]$ for a list of messages $M = [m_1, .., m_n]$, and we want to verify that $S$ is a valid signature of $M$, so each $s_i$ should be valid for each $m_i$.

If we proceed, instead of verifying all $n$ signatures, by verifying a set of $k \lt n$ messages chosen randomly and uniformly, for a random $k$, we could say that $S$ is valid for $M$ with a "certain probability" depending on how many messages we verify.

My question is: If an attacker wants to forge a list $M'$, say he uses $l$ messages from $M$ with their valid signatures, and adds $n - l$ new messages with invalid signatures, constructing new lists $M'$ and $S'$, hoping that $l \geq k$ and that we would only verify the $l$ valid ones, and assume that $S'$ is valid for $M'$ (which is not the case !).

Will he have a high chance or probability of forging such a list of messages, if he has no information about $k$ ($k$ chosen randomly on each verification)?


texts:
Say I have a key, an iv and an AES/GCM/NoPadding encoded string and I want to split this information between three people such that only jointly can they reveal the secret.

Is it safe to just split all this data to three equal chunks and provide to each party in a format "1/3 of key-1/3 of pass-1/3 of iv"? Under "safe" I mean, is it possible to come up with some kind of efficient attack while having 1/3 (or 2/3) of all the data?


texts:
It is known that computing $a^x \bmod N$ takes $O(|x| + \mathrm{pop}(x))$ multiplications modulo $N$, where $|x|$ is the number of bits of $x$ and $\mathrm{pop}(x)$ is the number of $1$ bits (Hamming weight). This suggests a side channel attack by measuring the run time of the exponentiation.

Can the number of $1$ bits be derived from the run time, and can it somehow speed up finding of $x$ if $a$ and $N$ are known (assuming no countermeasures are used)?

Which countermeasures can be done?


texts:
I'm experimenting with creating an entropy source for an environment where I have no hardware available and the language is very high level (executed in a virtual machine). I know it's not a good idea but I don't have /dev/random or CryptoAPI and the only possible sources are things like http://random.org but they need a network connection and is discouraged.

I have tried to execute a tight loop and get entropy from the elapsed times which, because of the CPU scheduling and other processes activities, has some variance. This source of entropy is of very poor quality but it seems unpredictable as long as someone has not access to the physical machine where the generator is running. Nevertheless, if I run the "ent" tool through the values I get it shows that they are strongly correlated and not truly random.

If I then iterate Von Neumann unbiasing between 2-4 times, until the point the resulting data passes the chi square test of "ent" (BTW: this process always converges), it seems that I get truly looking random numbers.

My question is: would this random numbers be unpredictable because their source is unpredictable or am I masking possible errors and fooling myself? What would happen if I used this numbers to seed a PRNG based on AES in CTR mode with a key and IV?


texts: What algorithm for AES key wrapping to choose in an embedded environment

texts:
In an embedded environment, what AES key wrap algorithm is best, in terms of performance and security coverage?

We are using RSA PKI asymmetric encryption.


texts:
Let $$(g,h=g^s,q)$$ be a tuple such that $g$ is a generator for a group $\mathbb{G}$ of ord $q$ and $s$ is uniformly random in $\mathbb{Z}_q$.

The knowledge of exponent (KEA1) assumption says that for any adversary $\mathcal{A}(g,h,q)$ that outputs a value $(C,Y)$ such that $C^s \equiv Y$ then there exists a extractor $\mathcal{B}$ that on the same input outputs a value $x$ such that $g^x \equiv C$.

The assumption, roughly speaking, says that the only way to compute the tuple $(C,Y)$ is, actually, by knowing the exponent $x$.

This assumption was first proposed by Ivan Damgård in the paper "Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks" in the '91.

My question is, how much do we trust this assumption? Is it reducible to something else?


texts:
I have a key size of 128 bits. My message size is fairly short (e.g., 32 bits - and widely known). Although I am doing a SHA256, the result of the HMAC will be truncated to 128 bits.
So my question is: is there a significant strength difference between the following?

HMAC256(K,m)
HMAC256(K,m||K)
HMAC256(K,K) 'note that in this case, there is no message) - I just need the result of the hash).

I am trying to prevent someone who knows m and the 128-bit result from figuring out the 128-bit key.


texts: Security of Salsa20 with some known plaintext?

texts:
Basic question- if I'm encoding a bunch of known filetypes with salsa20, will it still be secure if the plaintext header is known?

Assume that a different IV and Key are generated before each file is encrypted (or at least, it's statistically impossible for an attacker to know whether or not different files were encrypted with the same IV or key, and it's very unlikely that 2 in fact were)

I.e. the attacker will precisely know the first 64 bytes or so of the plaintext file, not the remaining mega/gigabytes, and does not have a comparison file which was likely to be encrypted with the same IV and Key


texts:
If I would use two different key-agreements e.g. SIDH and ECDH how would I handle these both derived keys?

Is there a different between XOR or SHA-256 the two keys? (Would one reduce the level of security?)
Or is there another safe method?

1. XOR

key = SIDH ⊕ ECDH

2. SHA-256

key = SHA-256(SIDH, ECDH)


texts:
Let us assume that a MAC is calculated as $t = a m + b$ with $a,b,m \in \mathbb{Z}_p$, $p$ prime. $a$ and $b$ denote the private generation keys, $m$ refers to the message.

This MAC is then one time secure, but not two time secure. One time secure means that an attacker who learns of one message-mac pair has only a small chance to find a separate message with a valid mac. Two time insecure means that as he learns two pairs, he is then easily able to solve the resulting system of linear equations for the secret $a$ and $b$.

How could the MAC generation scheme be changed to make it two time secure?

I understand that the $am$ and $b$ components are independently and evenly distributed in $[0..p-1]$, as $p$ is prime. Given that, I thought I could add a third component, derived from a newly added part $c$ of the private key, which again is independent and evenly distributed. But I could not figure out how.

First off, obviously, simply using something like $t = a m + b + c$ or $t = a m + b + c m$ does not work, as the new component can be combined with either $a$ or $b$, thus not providing any effective benefit.

Something like $t = a m + b + c m^2$ does not seem to work, as $m^2$ is not evenly distributed in $\mathbb{Z}_p$. (Am I missing something?)

Another idea might be to add a counter to the generation: $t = a m + b + c i$ where $i$ is a message counter. This appears to be two time secure for $p > 2$, but only given that the attacker cannot simply use $p$-apart messages, which obviously share the same $c i$ component. This requirement seem too high to me, so I'm not a fan of this idea.


texts: Encrypting text using Caeser cipher in CFB mode

texts:
I am interested in learning and understanding cryptography and its application in every day life. One thing I can't seem to get my head around is encrypting plaintext using a block mode such as CFB. I want to use a Caesar block cipher in CFB mode to encrypt the following plaintext: lucozade with a key: 3.

So in this case, I get that using the Caeser block cipher the ciphertext for lucozade would be oxfrcdgh as the letters have shifted three places to the right. What I can't do is this encryption using CFB mode. How do I go about doing that? Like would I have to use the ciphertext oxfrcdgh as the IV?

Any help would be great


texts: Are attacks on AES more efficient now (due to the new paper published at CHES2016??)

texts:
Recently, there has been a new paper accepted to CHES 2016 called "A High Throughput/Gate AES Hardware Architecture by Compressing Encryption and Decryption Datapaths" by R.Ueno et al.

In one line, they proposed a very efficient AES crypto processing technology via Galois filed arithmetic operations.
I am no professional in this area, but I was wondering

"Does faster computation of AES allows for faster attacks on AES??"

For example lets assume if differential cryptanalysis was feasible for AES (which is not true). Then since one can compute AES on an input in, say half the time of previous computations, would that lead to an attack that is twice as fast??

I am no expert in this area, so I would like to know out of curiosity whether the paper above has any particular impact on cryptanalysis of AES.


texts: Minimal size of share in Shamir's Sharing Scheme

texts: Why does the combined shared key in Adi Shamir's Sharing Scheme have to be smaller or equal than each secret share?


texts: I am trying to implement a small encryption tool in as little code as possible as a learning exercise, and currently have managed to get everything to depend only on a HMAC construct. However, most hash functions I know (sha256, blake2) tend to be quite large when written out in Python. Are there any small hash functions that are safe to use in a HMAC setup?


texts: Mathematical formula for switching the key for OTP?

texts: Instead of generating the random key for the one time pad cipher over and over again, is there a mathematical formula that allows you to switch the key to a new key? The new key must be as random and secure as the original key.


texts: Randomness extractors from Bourgain’s breakthrough- applications?

texts:
Some exciting progress to pure mathematics is due to Bourgain

Springer - Multilinear Exponential Sums in Prime Fields Under Optimal Entropy Condition on the Sources

with applications to randomness extractors and gave the first two source extractor with min entropy rate <0.5

Since this paper there’s been other innovations and simplifications of Bourgains work, such as

An explicit two-source extractor with min-entropy rate near 4/9

This is all exciting for mathematics. Is the same true from an applied crypto perspective? For example, would it help in any way with the issues discussed here

The GCD strikes back to RSA in 2019 - Good randomness is the only solution?

Other applications/places where these theoretical breakthroughs have already been applied?


texts: What is the recommended minimum key length for ECDSA signature

texts:
I want to identify the proportion of certificates that use unrecommend ECDSA key length for TLS certificates based on some data I collected.

By looking at a standard like NIST for example, I find this in this website:

My data shows use of ecdsa-with-SHA256.

My question is: Which if the following key algorithms the ECDSA is based on? Since ECDSA stands for (Elliptic Curve Digital Signature Algorithm) my understanding is that it is based on Elliptic Curve. So since we are in 2018/2019, I assume the recommended length is 224 bits?


texts: Hash collision resistance of $\mathcal H^\prime(m) = \mathcal H(\mathcal H(m)|m)$

texts:
So far as I can find, every method better at producing hash collisions in cryptographic hashes than generic collision search involves finding some metric for the distance between two messages' hashes and calculating alterations to each that will iteratively reduce that distance.

And further, unless I'm misreading it, none of the existing attacks is a "forgery" attack, allowing the attacker to converge on a known hash; they all work by iteratively altering multiple messages, eventually arriving at a set that all have some shared but unpredictable result.

Are these true?   If so,

wouldn't $\mathcal H^\prime(m) = \mathcal H(\mathcal H(m)|m)$ be completely immune to current attacks (at the cost of giving up on one-pass hashing)?

@RickyDemer pointed out in comments that available parallelism makes even random-walk search formidable, and it does seem to me that while appending the full hash forces full recalculation at each iteration, stripping that advantage isn't on average going to claw back more than say eight bits of strength....  though I suppose recursing the construction until at least a certain number of hash blocks have been processed could slow down attackers arbitrarily.

So, just for fun,
$$\mathcal H^0_H(m) = H(m)$$
$$ \mathcal H^n_H(m) = H(\mathcal H^{n-1}_H(m)|m)$$
$$|\mathcal H^n_H(m)|=1+n\cdot|m|$$ (with $|m|$ expressed in units of $H$'s block size)
 $$ \mathcal{\bar H}^e_H(m)=\mathcal H^n_H(m): \log_2|\mathcal H^{n-1}_H(m)| <e \le \log_2 |\mathcal H^n_H(m)|$$

So $\mathcal {\bar H}^{16}_{\rm SHA1}$ would be $\mathcal H^n_{\rm SHA1}$, $n$ large enough that at least $2^{16}$ additional blocks were hashed.

Leaving the question after accounting for his observation:

would $\mathcal {\bar H}^e_H$ be immune to current attacks (at the cost of giving up on one-pass hashing) even in the face of an attacker willing to throw $2^e$ parallel devices at it?


texts: Brute force attack expected running time

texts:
I am a bit confused about the expected running times of brute force attacks on different cryptosystems.

So let's assume a key size of $2^n$ bits.

Symmetric key cryptography:

$E(brute)$ = $2^{n-1}\cdot$ comparisons time

So if I understood correctly I need to generate all the possible $2^n$ keys to find the "right" key for sure. Now taken into account the definition of Expected Value of a random variable $X$, that can take the value $x_i$ with $p_i$: $E[X] = \sum p_i \times x_i$. So in our case we can say that $k=2^n$ and $E[X] = \frac{k(k+1)}{2}\cdot \frac{1}{k} = \frac{k+1}{2} \approx 2^{n-1}$.
Cryptographic hashes

Following the birthday paradox analogy and approximating the required time we end up with $E[X] = \sqrt{2^n} = 2^{n/2}$ comparisons.

My confusion comes from public key cryptography and from ECC: in this post ECC is nicely described, but it says that on average you must guess $2^{n/2}$ keys. I don't really understand where this number comes from as you are not searching for a collision as in the case of hashes, but for an exact match.