texts: Is there a way to make a non-specific algorithm to decypher substitutions with "anti-frequency analysis" measures?

texts:
There's a code I'm trying to decipher. What I know is that it's a simple substitution, with just a few added rules intended to make frequency analysis and other very common methods a little less efficient.

I know for example that:

there is no letter repetition, so there must be a way to code double letters (there is no spaces either so you can't just delete double letters)
there is more than 1 character that for the letter 'e'.
there are more rules. (I don't know how many but it's supposedly "very simple". All rules can be applied by head easily, without needing a chart, a grid or anything else.)

I can ask for data, but the challenge is to decipher it with as little data as possible.

My question is, is it possible to use a classical frequency analysis (like quipqiup) with increased "tolerance"? (provided I have enough data) Or do I necessarily have to hard-code every possible rule there could be in a custom algorithm?

Basically, how far would I have to go from a classic frequency and bigram/trigram analysis algs to crack the code without having to know all the rules?

I have no idea how to approach this but I refuse to think simple rules on top of a substitution can render all classical analysis useless.


texts: Are there any benefits to using ECB over CBC?

texts:
From what I have understood about ECB and CBC, CBC is far better as it doesn't reveal any pattern. There have been several questions here about how ECB is bad:

Should I use ECB or CBC encryption mode for my block cipher?
Can someone explain the ECB Penguin?
Why shouldn't I use ECB encryption?

But are there any cases where ECB is better than CBC, or at least is still usable?
My guess is that for high entropy messages, without any pattern, the major flaw of ECB is irrelevant, but are there any benefits to using ECB over CBC?


texts: Zero Knowledge Example using discrete log

texts:
I've been exploring Zero Knowledge Proofs and while the classic cave example by Jean-Jacques Quisquater makes sense, I find the discrete log example problematic.

Since the Verifier is given p, g and y, where p is a large prime, g the generator and y = g x mod p. The value x is secret. My problem is that that there is leakage of information since y depends directly on the secret x.

Alternatively, the security is that of the discrete algorithm problem. Is this a poor example or do all realizable ZKP leak information?


texts:
I'm pretty sure there are famous algorithms for my problem, but I don't have enough knowledge in this field, so I need your lights.

Here si the problem :

Alice sends key X to Bob.
Bob has an function that given the key X and the time, generates a key Y every 30 seconds, which is valid for 30 seconds.
If Bob send the most recent Y to Alice, she must consider the key as valid.
If Bob sens a more than 30sec old Y, Alice must not consider this key as valid.

Here is a more mathematical formulation with two functions E and D :

int Y = E(int X, int time)
bool result = D(int X, int Y, int time)

Variable X is the same for both functions
The variable time is a value that changes every 30sec
The function D must return true only if the time argument of the generated Y is the same as the one in argument of D.

(For the people that have a Battle.Net account, you will recognize that I'm looking for the same logic as the blizzard authentificator, in this case Alice is blizzard and the authentificator is Bob).

The question is what are the functions E and D. I guess there must be tons of possibilities, but what famous algorithms are used for this typical problem.


texts:
Is it possible to break the SHA-512 hash algorithm?

Are there any successful attacks out there?


texts: Factoring two RSA modulus with known $|p_1 - p_2| < \ell $

texts:
I have two 1024bit RSA modulus $N_1 = p_1q_1$ and $N_2 = p_2q_2$ such that $0 <|p_1 - p_2| < \ell$, and $\ell$ is at most 64bit integer. Can I factorise $N_1$ and $N_2$?
What's the answer when $p_1$ and $p_2$ are same $\alpha$-bit primes?


texts: Which method to generate one time password?

texts:
I'm looking for a concrete algorithm to generate one time passwords. The situation is as follows:

Alice and Bob exchanged a passphrase over a secure channel in the beginning. They want to symetrically encrypt data in the future, and every consecutive enryption/decryption process should use a one-time password.

For every single data exchange process it is considered that they remember the initial passphrase, but nothing else. It is possible to exchange additional metadata in cleartext alongside with the payload.

I looked at hash chains, but the problem with that is that they need to ensure that never use the same number of iterations twice and decrease it everytime. As I said above, they can't remember anything but the initial passphrase.

Second thought was to use a key derivation function, for example PBKDF2. The number of iterations could be statically (high enough), and the salt could be exchanged with the payload. But as a cryptography novice, I'm not sure if this is secury enough, because it wasn't made for that purpose, as far as I understand this. Or was it?

Are there alternatives? Or would it be sufficient to use a KDF in my case?


texts: Verify signature from set of public keys, but not revel which specific key it was

texts:
Does a system exist where it is possible to verify a signature is from a public key in a specific set of public keys, but also not know which key it was?

The idea being you know a member of a group signed the message without reveling who it was.


texts:
I read about 3DES encryption but I don't understand exactly what the specific meaning of key size is. For example I found that 3DES supports 64, 128, 192, and 256 bits key size. What are all the possible key sizes supported by 3DES?
Is there any function to determine if a key is valid for 3DES or not ?


texts: How to obtain private key in RSA when same message sent three times using same exponent

texts:
Suppose Alice, Abigail and Anna all have public keys with exponent e = 3, which
Bob uses to encrypt the same message to send to each of them. Show how an
attacker can obtain the key by intercepting these encrypted messages.

I have the answer for this question which says:

Bob sends $y1≡x^3\mod l,\ y2≡x^3\mod l,\ y3 ≡x^3 \mod l.$ An attacker can then
compute $Y < lmn$ such that:
$$Y ∼= y1\ mod\ l,$$
$$Y ∼= y2\ mod\ m,$$
$$Y ∼= y3\ mod\ n$$

But $x^3 < lmn$, and so $x = Y^{1/3}$

I assume there is a typo in the answer and that the 3 messages should be $mod\ l$, $mod\ m$ and $mod\ n$ respectively instead of all being $mod\ l$.

But I am unsure exactly how this answers the question. How does the attacker compute $Y$?


texts:
To my understanding, if a server “cert+key” (RSA) is compromised, than the SSL/TLS network traffic can be decrypted.

What about a client “cert+key” (RSA)? Could someone reuse client certificates?

For example: can somebody with the client “cert+key” decrypt (or in otherwise mess with) the traffic of another user?  (Yes, I know they can impersonate but that is not my question.)


texts:
(I cleaned up the question a bit, It was previously titled "extracting entropy without hashing" .. thus some of the comments / answers)

I'd like to extract the entropy of data without injecting "pseudo" entropy. For example, let's say I have a series of bytes, but only the low bit is changing (or something is changing that I'm not aware of beforehand) - how can I just output that low bit?

Is there a known way to extract the random part of the data without doing custom programming for each different type of data series?

edit:  To clarify, I'm looking to extract only the random part.  Eg, assuming F is the magical function, I want:

Length (F(X)) = # of bits of min-entropy in X.

As has been pointed out elsewhere, this is probably impossible to do automagically with any reasonably assured level of confidence in its real accuracy.


texts: Power analysis and exponentiation by squaring

texts:
I am trying to understand how one can retrieve the secret exponent via a simple power analysis.

Lets suppose that the exponentiation by squaring algorithm is implemented in its simplest form :

Function exp-by-squaring(x,n)
    if n<0 then return exp-by-squaring(1/x, -n);
    else if n=0 then return 1;
    else if n=1 then return x;
    else if n is even then return exp-by-squaring(x2, n/2);
    else if n is odd then return x * exp-by-squaring(x2, (n-1)/2).

As i understand,if i am to probe the consumption while the machine is calculating the exponent i will be able to see the individual operations on the spectrogram. There will be a spike between different operations so i will be able to tell when it entered the "even" condition or when it entered the "odd" condition. This simply gives me an idea about the exponent and not the actual exponent.

So if the secret exponent is 2012 (https://math.stackexchange.com/questions/563708/exponentiation-by-squaring), i will simply see that the even condition was entered 6 times and the odd condition was entered 4 times but how exactly do i use that information to find the secret exponent?

Thanks in advance


texts: What communications security protocols exist that aren't based on PKC?

texts:
Lets say that you have two devices that need to communicate in a secure manner. These devices can share secrets before communication takes place (This sharing of secrets occurs over another secure channel). Furthermore,
these devices can not use public key cryptography.

Assuming that underlying cryptographic primitives are soundly implemented, what communications security protocols exist that can secure such communications at both the message level (authentication, encryption, and integrity) and the protocol level (guard against replay attacks and so on)?


texts:
Blinding is often used to mask private key operations when the underlying problem is integer factorization. For example, it's used in both RSA and Rabin-Williams signature schemes. This presumes integer operations are not constant time.

I have two questions:

Is blinding used in schemes other than integer factorization?
Are there other options to guard the private key against timing attacks available to software implementations on commodity hardware?

The reason I ask is Evgeny Sidorov's Breaking the Rabin-Williams digital signature system implementation in the Crypto++ library (a.k.a. CVE-2015-2141). There was a bad interaction with the blinding value and Jacobi requirements on p, q, which resulted in a private key recovery.

One of the suggested remediations was to disable blinding. I'm trying to gauge the impact of doing it in libraries like OpenSSL and Crypto++, and how much needs to change if blinding is optional. (It is already optional in OpenSSL, but not Crypto++).


texts: How to implement security - authenticity/confidentiality/integrity for 6/14 bits radio messages?

texts:
I just took over two radio systems (using 433Mhz) - one communicates with 6 bit messages, one with 14 bit messages. Both have a lots of transmitters and one receiver (and, yes bits not bytes).

For the first, 4 bits are used for the ID of the device, and 2 bits for other info.
For the second, 10 bits are used for the ID of the device, and 4 bits for other info.

They work completely independent - all they have in common is that the messages are very small and are sent in CLEAR.

Now I have to implement authenticity/confidentiality/integrity for these messages - but I have to keep them short (as for the second system far less than the max 2^10 devices are already jamming each other)

I haven't decided yet, if it is better to use one key for the entire system, or one key for each transmitter. (for both situations, the keys will be considered known for both transmitter/receiver)

I agree with "don't implement your own security", so I have read about different standard solutions, but the end message gets monstrously big and I cannot use them.

What algorithms/combinations would give me the smallest size for the resulting message but with also a reasonable security?

P.S. I was thinking about a solution using umac, as you can get away with non cryptographic hashes which are smaller.

Edit:
To be more clear - I don't want for a third party to:

read the info part of the message (the ID part can be public)
emit messages and the receiver not to detect that are not from his system transmitters
replay a previously valid message and the receiver not to detect that

Edit2:
There is no time for either of the devices.


texts: Alternatives to simple bit-measured security for ciphers

texts:
For a cryptographic primitive, we usually see the security level measured in bits, where n-bit security means that the attacker would have to perform $2^n$ operations to break it.
For key-derivation functions, we often see functions that deliberately use large amounts of computation or memory in order to make them computationally expensive.
However computational expense seems to be rarely discussed when comparing the security level of ciphers.
My assumption: It would seem logical that a cipher that cannot be run in parallel is (in some ways) more secure compared to one which can.  Or two ciphers with equal security levels are not truly equal if one of them runs a billion times quicker on a supercomputer.
Questions

Is my assumption misguided?
Are there any alternative approaches to measuring cipher security that takes into account the computational expense of the algorithm? If not, why not?


texts: Non-interactive proof that an element is in a subgroup

texts:
I am just reading the DAA paper (http://eprint.iacr.org/2004/205.pdf, Appendix A). A party $\mathcal{I}$ generates two group elements $g' \in \mathrm{QR}_n$ and $h = g'^r \bmod n$ with $r \in_R \left| \mathrm{QR}_n \right|$. Now $\mathcal{I}$ wants to prove in zero-knowledge that $h$ has been created correctly, i.e. that $h \in \langle g' \rangle$.

In the paper the authors use binary challenges with a non-interactive proof of knowledge. I don't get why? This is quite inefficient so I guess that there is a reason for this. Why not just proving $h = g^r \bmod n$ where $r$ is the secret and using one "big" challenge instead of using only 0/1 as the challenge and repeat the protocol?

edited

I have made some further research. Can someone please tell me, if I am right or wrong. The prover P wants to prove to a verifier V that h = g'^r, i.e. $ZKP\ [(r): g'^r]$. $g', h \in G$. The protocol is something like

         P                                V
--------------------------------------------------
y = g'^k mod n           y
                 --------------->  choose challenge c
                         c
                 <---------------
s = k + c*r mod |G|
                         s
                 --------------->  check if g^s mod n = y*h^c mod n

To prove the zero-knowledge property, we have to define a simulator S which communicates with V (instead of P). If it is an honest verifier ZKP, we can define S as $S(y, c, s) = (\frac{g'^s}{h^c}, c, s)$ with $s \in_R \{0, \dots, |G|-1\}$, right? There are no differences between real transcripts (between P and V) and faked transcripts (between V and S) => so the protocol is zero-knowledge, correct??

Now, we have an dishonest verifier, which doesn't choose the challenge randomly. To solve this problem, we use a non-interactive proof, where the challenge is created by a random oracle (for practical use we use "a hash function H"). Instead of transferring $y$ to V (and getting a challenge back) the prover sets $c = H(y)$. We can take the same simulator as in the "interactive-case", or???

What I still don't get is why the authors in the paper separate the 160-bit Hash into 160 pieces and take each bit as the challenge? Is the reason for this that maybe the prover chooses the base $g'$? In other papers they say that you can prove $ZKP\ [(w): g'^w]$ "directly" without using binary challenge, but in these cases the base $g'$ is fixed.


texts:
Without taking into account security, which hash function is the fastest one among the following:

MD5, SHA-1, SHA-2 (for various internal size), Keccak, and other… ?


texts: Current mathematics theory used in cryptography/coding theory

texts:
What are the mainstream techniques borrowed from algebraic geometry (or some other branch of mathematics) which are currently used in cryptography/coding theory? I've only heard about a small subset of elliptic curves and hermitian curves. I've also heard about research of hyperelliptic curves but I don't know if some software has already implemented it.

Could you mention some other branches of mathematics being strongly used in cryptography/coding theory and its state? (mainstream/in research)


texts:
There is a number of block cipher modes, including ECB, CBC, CFB, OFB, CTR and others.
After reading "Serious Cryptography. A Practical Introduction to Modern Encryption" by Jean-Philippe Aumasson, where the author described CFB and OFB as folklore which no one really uses,
I am curious which ones are most commonly used in the real world?
I think the one I come across most often would be CBC.
Would anyone be able to share some stats (which I didn't manage to get to), or make and educated quess?


texts: How to prove that a encryption scheme is not IND-CPA secure

texts:
I am trying to construct a proof that a scheme is not CPA-secure. In IND-CPA experiment, can the adversary generate a key(that may not be real secret key) and compute Enc(key, message)? Does the adversary knows the encryption scheme in IND-CPA experiment?

I need this as I want to prove that if a scheme B1 is not CPA-secure, a scheme B2 is not CPA-secure by the following logic:
There exists an adversary A that can win IND-CPA experiment for scheme B1.
Then I construct an adversary A' with the help of A to win IND-CPA experiment for scheme B2.
But A' has to be able to compute Enc(key, message) for some key. I am unsure whether I can do so.


texts: How many encryptions are needed before OpenPGP key privacy is violated?

texts:
According to an excellent answer describing the pitfalls of key privacy in OpenPGP:

Theoretically, an all-zero key ID can be used as a way to discourage traffic analysis, but this is not a complete solution. For instance, with RSA keys, the packet still contains an integer between 0 and n-1, with n being the RSA modulus, with a fairly uniform distribution. Thus, observing many messages can yield, statistically, the first (most significant) few bytes of that modulus, which can be used to discriminate recipients from each other.

For an RSA key with an $n$-bit modulus, how many messages must be encrypted with that public key before it can be distinguished from $k$ other keys of the same size with non-negligible probability?


texts: Combining stream cipher with block cipher for disk encryption

texts:
You take something like chacha20 and use the disk block # to seek it, xor it with the data block and then encrypt it with a block cipher in ECB mode.

Would this be secure?

Edit:

To avoid getting bogged down in implementation pitfalls lets consider an ideal scenario:

You have a constant size file (that is a multiple of block cipher size) that may get altered through time. Using a stream cipher to encrypt is therefore not secure under some threat models. So you combine a stream cipher with an ECB mode block cipher - through chaining, first xor with stream cipher output then pass through block cipher. Would this now be more secure? As secure as XEX/XTS?


texts: A Zero knowledge proof for set membership?

texts:
Essentially, I am trying to build up a list of authorised public keys that will be stored in a database P by a verifier V. A public key will be considered authorised if belongs to a user in a database of verified users D. The problem is that it should not be possible for the verifier to ever link a public key to a specific authorised user.

I was thinking something along the following lines - Every user in D hashes a secret message that gets stored along with their account in D:

+-------+--------+
| User  |  Hash  |
+-------+--------+
| Bob   | abc123 |
| Alice | xyz789 |
| Eve   | 456fgh |
+-------+--------+

Then some sort of cryptographic accumulator can be used to combine the hashes. When a user wants to authorise their public key, they prove to V (in zero knowledge) that they know a message that when hashed, forms part of the accumulator. If V is able to confirm this, there public key is added to P, otherwise it is rejected.

To make matters even more complicated, a user should only be able to ever have one public key in P. In other words, Bob must not be able to continuously request multiple keys to be added to P. Thus, once everyone has had a public key authorised, P will look as follows:

+--------+
|   PK   |
+--------+
| MXH452 |
| B6HGJS |
| 67ZC6S |
+--------+

With it being impossible to know which public key belongs to which user. All we know is those public keys are verified and belong to one, and only one, user in D.

How can this be achieved? I have glanced at a few papers surrounding this issue, but they tend to get very technical very quickly.


texts: Is the concatenation of PRG output still a PRG?

texts:
I am puzzled by the following question, since I am not very familiar with proof methods of Pseudo-Random Generators (I only know how to use the inequality from the PRG definition to prove or disprove, but it may not work in this case?).

For any PRG $G$, if we partition an input binary string $s$ with length $n$, into substrings $s_1$ and $s_2$ with $s=s_1||s_2$ and where $|s_1|\leq|s_2|\leq|s_1|+1$, which means almost half and half, then is the following new generator $G'$ a PRG as well?
$G'(s)=G(s_1)||G(s_2)$,which means use the two sub-strings as input to $G$, and concatenate the results. Assume $|G(n)|=n+1$, and here clearly $|G'(n)|=n+2$

I think such $G'$ is a PRG but I do not know how to prove it, and I also wonder if it could be generalized like $s=s_1||s_2|| \ldots s_m$ and $G'(s)=G(s_1)||G(s_2)||\ldots G(s_m)$, is $G'(s)$ a PRG as well?


texts: Can it ever be impossible to invert a PRNG?

texts:
I've read about the possibility of inverting the Mersenne Twister after 624 numbers of output.  624 matches the state size of my implementation of the Twister.  Coincidence?  If the generator only output 623 numbers, i.e. less than the state size, might inversion still be possible with really clever maths?  Or is this mathematically and logically impossible?

This leads me to think about a general case.  I got this embryonic analogy from solving simultaneous equations.  Consider each member within the state array as a degree of freedom.  And consider each number output as a degree of freedom.  And if (for some generator) there is a group operation over the whole state such as an addition of all of the elements, this acts as a constraint. Can the following be true?

Let,

$F_o$ = degrees of freedom output,
$F_s$ = degrees of freedom within state,
$C_n$ = number of constraints on the state.

Is the random number generator “impossible to uniquely invert” if $F_o < F_s - C_n$?


texts: Text in random image encoder: is it flawed?

texts:
I have created a small cryptographic programme:

You input your text
A random image is generated
Random coordinate pairs in number equal to the chars of the message are generated.
The red component of the points at the coordinates given above is modified to become equal to the ASCII value of the letter.
The text can now be read only knowing which points actually encode the letters and which other points are just noise.

Can you tell me any flaws in the approach that would make my message crackable (having only the image and not knowing the key used)?

If you are wondering about the implementation details, the actual programme is provided down below:

from __future__ import print_function
from PIL import Image
import random

SIZE = 500
MESSAGE = "Boh i don't know what I know to be knowing"
RELEVANT_POSITIONS = [(random.randint(0,SIZE),random.randint(0,SIZE)) for _ in range(len(MESSAGE))]
FILENAME = "Crypted.png"

IMAGE = Image.new("RGB", (SIZE,SIZE))

def from_letter_to_colour(letter):
    value = ord(letter)
    return (value,random.randint(0,256),random.randint(0,256))

def from_colour_to_letter(colour):
    return chr(colour[0])

def draw(position,colour):
    IMAGE.putpixel(position,colour)

def random_colour():
    return (random.randint(1,256),random.randint(1,256),random.randint(1,256))

def all_positions():
    return ( (x,y) for x in range(SIZE) for y in range(SIZE) )

def get_pixels(image_name):
    image = Image.open(image_name)
    pixels = image.load()
    return pixels

def create_random_image():
    for position in all_positions():
        draw(position,random_colour())

def encode_message(message):
    create_random_image()
    for index,position in enumerate(RELEVANT_POSITIONS):
        try:
            draw(position,from_letter_to_colour(message[index]))
        except IndexError:
            break
    IMAGE.save(FILENAME)

def test_encode_decode():
    for char in ( chr(i) for i in range(1,128)):
        assert from_colour_to_letter(from_letter_to_colour(char)) == char

def decode_message():
    message = []
    pixels = get_pixels(FILENAME)
    for position in RELEVANT_POSITIONS:
        x,y = position
        message.append(from_colour_to_letter(pixels[x,y]))
    return ''.join(message)

def main():
    print("The key is: {}".format(RELEVANT_POSITIONS))
    encode_message(MESSAGE)
    print(decode_message())

if __name__ == "__main__":
    test_encode_decode()
    main()


texts: zero-knowledge proof of disjunctive statements (OR proofs)

texts: I know there are standard ways to prove disjunctive statements about discrete logs, e.g. OR proof. But are there similar approaches for other class of language? For example, how can one go about proving either $G_1$ or $G_2$ has a Hamiltonian path (without leaking which one)?


texts: Is it possible to spoof an identity cert modulus?

texts: I was looking at FOAF+SSL and wondering if its possible to spoof the modulus of the browser certificate so that the FOAF and browser certificate's modulus match?


texts:
I have a program which uses AES-256 in CBC mode to encrypt and decrypt files. As I have quickly realized, AES will even use an incorrect passphrase to decrypt data, which leaves me with no way to validate whether the passphrase was correct or not and, in turn, whether I'm decrypting things successfully.

One idea which was suggested before was to embed a known value in beginning of the encrypted data to validate whether decryption produced an expected result. Essentially, since the IV is a known value, I thought of simply hashing it and embedding it as the first 32 bytes in the file. If, after the first block is decrypted,  the first 32 bytes equal the hash of the IV, we can know that decryption succeeded. If not, we can know that it failed.

Does this in any way compromise my encrypted files?


texts: My pencil and paper One Time Pad works fine without modular math ...... or does it?

texts:
With no background in higher math or computer science, I could not quite grasp the value of modular math for simple OTP systems as described in other posts here.

I have an alphabet size of 40 characters, valued from 0 to 39.
The pad uses alphabetics "A" through "Z", valued from 0 to 25.
I am using modulo 40 math.

If my ciphertext for any given plaintext character is a single digit, I prepend a zero as a placeholder, this yields a consistent ciphertext of a pair of digits for any one character of plaintext.

This system is working just fine.
But then I realized that I could skip the mod math entirely and the system works just as well and is easier and quicker for both parties in the exchange....as far as I can tell.

So: Why bother using the mod math at all if the encryption/decryption is working just fine without it?

And, from an attacker's point of view, if he realized the ciphertext digit pairing and therefore could see the highest pair value of 40  (in the case of using the mod math)  or instead  64 (without the mod math), would one of those cases give him more advantage than the other?


texts: Are there any other highly trusted and secure symmetric encryption algorithms besides AES?

texts: AES is the gold standard for symmetric encryption. It is highly trusted and highly secure. Do any other symmetric ciphers - besides OTP - come close to AES's usability, security, trust-ability?


texts:
Alice publishes $(n,e)$ where $n$ is exponential modulus and $e$ is the public key. We have $n=80$ digit number and $e=3$. Bob, in correspondence with Alice, asked Alice to prove she is really Alice, by making her signature on the following five numbers: $m1, m2, m3, m4, m5$. Then Alice sent 6 numbers $y1, y2, y3, y4, y5, y6$ where all the 6 numbers are really long, around 80 integers.

How do verify that these five numbers are indeed signed by Alice?


texts: Simple secret key encryption with PyNaCl

texts:
I am playing around with PyNaCl to get a bit into cryptography atm.

Now I wrote two scripts to encrypt a file with a secret key and then decrypt it again using that key. The encryption part works fine but I am having trouble with decrypting the file again.
I get the error nacl.exceptions.ValueError: The nonce must be exactly 24 bytes long when I execute decrypt.py. When I explicitly hand the nonce generated in decrypt.py to the decrypt() function I get the error nacl.exceptions.CryptoError: Decryption failed. Ciphertext failed verification

When I use the last three lines of decrypt.py in encrypt.py however, it works for some reason. But of course I don't want to instantly decrypt the file I just encrypted, instead I want to do that with a separate script at a later point.

Also, I am only using SCRYPT here because PyNaCl does not contain Argon2 in my installation for reasons unknown. I am also aware that I hardcoded the salt in a variable, this is just for testing purposes. Later I want to generate that with utils.random and write it to the encrypted file.

My scripts look as follows:

encrypt.py

from nacl import pwhash, secret, utils

password = b'lala'
infile = "test.mp4"
outfile = "out.crypt"

kdf = pwhash.kdf_scryptsalsa208sha256
salt = '\x1b\r\xbfxrL\xee\x83x\x0b\x83\x13O\x1dv\xbc\xd5\x13\x18w;G\xd6\x88 \xae\x8b\x96^\xbd4\xbc'
ops = 33554432
mem = pwhash.SCRYPT_MEMLIMIT_SENSITIVE

with open(infile, "rb") as in_file:
    data = in_file.read()

derivatedKey = kdf(secret.SecretBox.KEY_SIZE, password, salt,
                 opslimit=ops, memlimit=mem)
secretBox = secret.SecretBox(derivatedKey)
nonce = utils.random(secret.SecretBox.NONCE_SIZE)
encrypted = secretBox.encrypt(data, nonce)

with open(outfile, "wb") as out_file:
        out_file.write(encrypted)

decrypt.py

from nacl import pwhash, secret, utils

password = b"lala"
infile = "out.crypt"
outfile = "decrypted.mp4"

kdf = pwhash.kdf_scryptsalsa208sha256
salt = '\x1b\r\xbfxrL\xee\x83x\x0b\x83\x13O\x1dv\xbc\xd5\x13\x18w;G\xd6\x88 \xae\x8b\x96^\xbd4\xbc'
ops = 33554432
mem = pwhash.SCRYPT_MEMLIMIT_SENSITIVE

key = kdf(secret.SecretBox.KEY_SIZE, password, salt,
               opslimit=ops, memlimit=mem)
box = secret.SecretBox(key)
nonce = utils.random(secret.SecretBox.NONCE_SIZE)
decrypted = box.decrypt(infile)

with open("outfile", "wb") as out_file:
    out_file.write(decrypted)

Any help would be greatly appreciated!


texts: Factoring a semiprime with part of one of its factors

texts:
This is part of a question I asked on information security stack exchange which might be better suited here.

I'm looking to implement a script in an ad-hoc scripting language with no crypto libraries, which can tell whether or not a password is valid without revealing the password.  I also need the password to be as short as possible without being crackable.

One possibility is to store a large semiprime and have the password be a factor.  But semiprimes need to have factors which are hundreds of bits long to be difficult to crack. I'd rather the password be around 64 bits.  I'm considering storing a 1024-bit semiprime along with 448 bits of one of its 512-bit factors, and have the other 64 bits be the password, but I have no idea if this is crackable.

So my question is:  If a 1024-bit semiprime is stored along with the first 448 bits of one of its 512-bit factors, can the remaining 64 bits of that factor be feasibly found?


texts: A "concatenation-like" cryptographic operation that has a fixed output?

texts:
I am designing a cryptographic protocol, and I was wondering whether or not there exists a simple cryptographic operation $\diamond$ that is:

Associative: $(x\diamond y)\diamond z = x \diamond(y\diamond z)$
Non-commutative: $x\neq y \Rightarrow x\diamond y \neq y \diamond x$
Collision-resistant: it's hard to find two different pairs $(x,y)$ and $(x',y')$ such that $x \diamond y = x' \diamond y'$.

The obvious operation that fits these properties is concatentation with some sort of unique separator, and that's indeed what I'm currently using in my protocol.

But is there such an "append-like" binary operation that produces a fixed-size result? Append-and-hash wouldn't work since it is not associative: $H(H(x||y)||z)\neq H(x||H(y||z))$. XOR won't work since it's neither unique nor non-commutative. Ideally such an operation would be a simple construction using a hash function or other "standard" crypto primitive.


texts: How to get ramdom number between 1 and 2048 from /dev/hwrng?

texts:
I am (perhaps naively) evaluating the security considerations of using the following code to create BIP39 seed phrases (on a read-only and offline Raspberry Pi).
Apparently, using jot -r 1 1 2048 is not ideal and I would like to leverage the HRNG (/dev/hwrng) on Raspberry Pi hardware.
printf "%s\n" "Create random 24-word BIP39 seed phrase…"
seed=()
for i in $(seq 1 24); do
  seed+=($(sed "$(jot -r 1 1 2048)q;d" "/path/to/bip39.txt"))
done
echo ${seed[@]}

$ cat bip39.txt | head
abandon
ability
able
about
above
absent
absorb
abstract
absurd
abuse

Edit: this approach would not work given BIP39 seeds use last word as a checksum (see spec).


texts:
In the X3DH protocol a signed prekey ($SPK_B$) is used as part of the handshake. What is the purpose of this key? There seem to be no obvious cryptographic drawbacks by omitting this key.

One rationale could be that these "semi static" keys can be renewed without the need of changing the identity key ($IK_B$) and hence provide better forward secrecy. But is this a benefit in real world scenarios like Signal or WhatsApp?

What's the drawback of following variant:

Bob publishes $IK_B$ and signed $OPK_B^1$
Alice gets Bob's $IK_B$ and $OPK_B^1$ and verifies the signature
Alice then generates $EK_A$ and calculates:
$$DH1 = DH(IK_A, OPK_B^1)\\
    DH2 = DH(EK_A, IK_B)\\
    DH3 = DH(EK_A, OPK_B^1)\\
    SK = KDF(DH1 || DH2 || DH3)$$

One could argue that in this variant one cannot omit $OPK_B$. Is this really so bad in real life?

Alternative: what about another modification where you drop $SPK$ and instead renew your identity key $IK$ as often as you would renew your $SPK$ in X3DH? Same forward secrecy properties. When used as part of chat app you do X3DH only the first time you send a message. So what's the harm in changing your $IK$?


texts:
I know and I have understood the details of RSA, elliptic curve cryptography, (EC)DH and (EC)DSA.

I keep reading everywhere that (if we don't consider non-deterministic computers) "ECC can achieve the same level of security as RSA, but with lower key sizes". While I can guess why this is true, how do we mathematically prove that?

Here's what I think:

The fastest algorithm for the ECC discrete logarithm problem is the Baby-step Giant-step, which is $O(2^{b/2})$ (https://en.wikipedia.org/wiki/Baby-step_giant-step).
The fastest algorithm for the RSA problem/integer factorization is $O(\exp((64 b / 9)^{1/3} \cdot (\log b)^{2/3}))$ (http://en.wikipedia.org/wiki/Integer_factorization).

Here $b$ is the bit-length of the key/of the group order.

Therefore, an ECC key of $b_1$ bits has the same strength of an RSA key of $b_2$ bits when: $2^{b_1/2} \approx \exp((64 b_2 / 9)^{1/3} \cdot (\log b_2)^{2/3})$.

Using that formula I can calculate that if I have a 2048-bit RSA key, I can achieve the same level of security with a 273-bit ECC key. But this number (273) is too high.

My question is: is my reasoning wrong? Where is the mistake?


texts: Finding two primes that satisfy the conditions

texts:
I want to implement partially blind signature, and I looked at Zheng Gong's scheme. (Title: Efficient Partially Blind Signature Scheme with Provable Security)

In the scheme, there is a initialization phase.
Signer S selects two large prime numbers p and q (length of p = 1024, q = 160), which satisfied q|p-1. Then chosses a generator g (element of Zp), and g^q = 1 mod p.

I wonder how can I find "quickly" the two primes that satisfy the condition (q|p-1) and the generator g that satisfy g^q = 1 (mod p).

Thank you


texts: Why not to use curve over field of $p^m$ with $p > 2$ for ECDSA?

texts: I'm reading the ECDSA paper and they say you can only use ECDSA with odd-power fields $p$ or with binary fields $2^m$. Why not other power prime fields?


texts: Hypothetical unknown cipher - security in obscurity?

texts:
I'm curious what would happen in the following scenario:

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

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

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

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


texts:
Can someone please explain to me what are the steps used to get this result (0.9154n+0.8876) from this equation
$$(2n+2){T}_{ecc}^{sm}+(2n){T}_{h}+(2n+2){T}_{ecc}^{pa}+(2n){T}_{ecc}^{sm-s} \approx 0.9154n + 0.8876?$$
where ${T}_{ecc}^{sm}$ =0.442,  ${T}_{h}$= 0.0001,  ${T}_{ecc}^{pa}$= 0.0018, and  ${T}_{ecc}^{sm-s}$= 0.0138
PS: These variables represent the Execution time of cryptographic operations in ms


texts: Indistinguishability versus semantic security?

texts:
I found some foundations of crypto course notes that mention that these two are equivalent statements of their own degrees of security and was given the following definitions:

I was always under the impression that the second definition (the one on the bottom) was the prescribed one for Semantic Security, and that computational indistinguishability was a completely separate thing? I do not understand the necessity or intuition behind the need for a "simulator" as it is called. Can someone shed some light?


texts: Why do we use 1024 / 160 bit primes in DSA?

texts:
I am looking at DSA's parameter generation and don't understand why for $p$ a 1024 bit prime is needed if $q$ is chosen as a $160$ bit prime. I thought that the security of DSA relates on the discrete logarithm problem. A good protection against algorithms solving the DLP is to work in a big order subgroup. I would choose $p$ as a safe prime, so that $p = 2q + 1$. Then $p$ has a bit size of $\approx 160$ bit and the biggest sub group has size $q$. I guess I cannot do this but what is the explanation for this?
I have taken the variable names from Wikipedia (https://en.wikipedia.org/wiki/Digital_Signature_Algorithm). Here an excerpt of the parameter generation part:

Decide on a key length $L$ and $N$. This is the primary measure of the cryptographic strength of the key. FIPS 186-3 specifies $L$ and $N$ length pairs of (1024,160), (2048,224), etc.
Choose an $N$-bit prime $q$. $N$ must be less than or equal to the hash output length.
Choose an $L$-bit prime modulus $p$ such that $p–1$ is a multiple of $q$.
Choose $g$, a number whose multiplicative order modulo $p$ is $q$. This may be done by setting $g = h^{(p–1)/q} \bmod p$ for some arbitrary $h (1 < h < p−1)$, and trying again with a different $h$ if the result comes out as 1. Most choices of $h$ will lead to a usable $g$; commonly $h=2$ is used.

The algorithm parameters (p, q, g) may be shared between different users of the system.


texts: Will current encryption always remain secure? Is there mathematical proof?

texts:
Current encryption algorithms, such as AES, RSA, elliptic curve, etc. work based on known mathematical problems. I am specifically interested in the RSA.

Will such security always remain secure?

One way of breaking them would be due to a revolutionary increase computing speeds, making brute-force a viable option. This could be due to invention of quantum computers, neural-network-based hardware, etc. Such technology is at a very early phase, and will take some years to develop.

The other means is to find loopholes in the algorithm itself, using mathematics. Has it been mathematically proved that these algorithms can not be cracked, or is it a possibility? If so, how likely is it that cracking the RSA via a mathematical weakness will be possible in the near future?

This should be an important question, since being able to crack such a system potentially could let you blackmail companies, and even governments, since it is their data which is at risk.

Note: I first asked this question on Security SE, a user there told me to post it here.


texts: Low entropy - how does it compromise the crypto

texts:
One of the often pointed out mistake in dealing with crypto is not having enough entropy in the system. Without enough entropy the random numbers generated are not random enough.

But what I am not able to piece together is how exactly the lack of randomness can lead to less secure systems. In what does a key generation on a low entropy system make it vulnerable for attacks ?


texts: If $((p-1)*(q-1) -1)$ divisible by $e$ ($e$ is odd number) , then $\text{gcd}(e,(p-1)*(q-1)) = 1$

texts: If $((p-1)(q-1) -1)$ divisible by $e$ ($e$ is odd number) , then $\text{gcd}(e,(p-1)(q-1)) = 1$. ($p,q$ are prime numbers ) Is this true, if yes why, if not why not ?


texts: Machine Learning to improve Encryption algorithms

texts: Can machine learning be used to improve encryption algorithms e.g.image encryption algorithms that use ECC ?


texts: Correctly generating cryptographically secure pseudorandom numbers (in C)?

texts:
I am learning about cryptography, purely for my own interest. As part of that, I am implementing a simple one-time-pad toolset in C.

Naturally, I need to generate random numbers to create the pad, and they need to be cryptographically strong. I know about rand(), but from what I can tell it is not strong.

Is there a standard algorithm (or library) that I should be looking at to accomplish this?


texts: Proof of Knowledge/Data Integrity using Hash Function

texts:
Objective: A verifier wants to ensure that a block of data M is also known to a prover. The protocol should exchange little information and should not leak information about the value of M.

Proposed Protocol:
V -> P: challenge c
P -> V: response r = f(M, c)

Question:
What is a suitable and efficient function f?

What comes to mind first is to use a hash function, such as SHA2(c concatenate M), which may meet the objective. We could also compute SHA2(M xor c'), where c' is derived by repeating c as required to get to the length of M.

What concerns me is that SHA2(M concatenate c) will not meet the requirement. The prover could simply compute SHA2(M) partially up to the last full block of M, store the intermediate state of the hash function, and then delete the part of M that was already processed.
When confronted with a challenge c the prover can pick up the state where
it was left and finalize the computation without actually knowing M anymore.

Does anyone see such pitfalls with SHA2(c concatenate M) or SHA2(M xor c) or have other suggestions?


texts: Can I use a one time pad key twice with random plaintext?

texts:
I understand the basics of OTP: $|\text{key space}| = |\text{plaintext space}|$ implies perfect security, key reuse destroys this.

Cryptanalysis on the $N$-Time Pad for $N > 1$ involves finding patterns in the ciphertext; this, however, all seems based on the premise that patterns exist in the plaintext (e.g. English language).

My question is: if $m_1$ and $m_2$ are two truly random strings, and they are both encrypted with the same OTP key to yield $c_1$ and $c_2$, is it possible to recover $m_1$ and $m_2$ from $c_1$ and $c_2$?

In other words: while "perfect security" (aka perfect indistinguishability) is obviously lost (constructing a distinguisher for two messages is trivial), is the plaintext still safe?


texts: How to prove that two EC public keys created with two different generators share the same secret key?

texts:
Consider a situation where there is a (scalar) secret key $x$, known only to Alice.

There are two well known generator points $G$ and $H$, known to both Alice and Bob. $H$ is chosen such that discrete log of $H$ base $G$ is unknowable.

Alice provides Bob with the points $A$ and $B$, where $A = xG$ and $B = xH$.

Without Alice revealing $x$ to Bob, how can Alice prove to Bob that both $A$ and $B$ were constructed with the same $x$? The proof should be non-interactive.

Is it safe to simply provide a Schnorr signature using the private key $x$ and public key $(A+B)$ on the basis of a generator point $(G+H)$?

The Schnorr signature would be:

$sig.c = Hs( (A+B)$  $||$  $k(G+H))$

$sig.r = k - x * sig.c$

where $k$ is a random number generated only for this Schnorr signature.

The Schnorr signature would be verified by checking that:

$sig.c == Hs((A+B) $ $||$ $ (sig.r*(G+H) + sig.c*(A+B)))$

$Hs()$ means hash the contents to produce a scalar

$||$ means byte concatenation.


texts:
My colleague remembers and old backup tool, packaged as a standard bootable ISO image. He thinks the file was about ~250 MB, containing a MD5SUM.txt, which included the MD5 Checksum of the entire ISO image.

I am no crypto/hash expert, but according to my understanding of checksum methods, he is wrong. He should have downloaded checksum separately, or else, the vendor should have had a hard time guessing the right MD5 such that adding it's hex form in a text file beside all other contents of the image makes the exact same checksum, right? I can't think of any shortcut to calculate such checksum.

(Unfortunately we don't have the ISO right now, so that I can win the bet and get a free beer.)


texts: Protocol to generate Client Certificates at the start of a SSL session automatically?

texts:
A more secure form of 'cookie' could be created for SSL communications through the following method.

The client generates and requests the server to sign a certificate.
Then the client authenticates to the https server using the client certificate.
Additional basic auth is used to tie the client certificate to the site credentials.

That would allow the 'client computer' to be able to prove it's identity (knowledge of private key) to the server (also assuming that the server certificate is authenticated using PKI).

I am not aware of this protocol being used, advantages? disadvantages? or is it just pointless because cookies give us enough security?


texts: encrypting data signals using the time variations between two independent coupling functions

texts:
There was a recent article about a new encryption technique that encrypts "using the time variations between two independent coupling functions".

What is this technique they are referring to?


texts: How does RSA signature verification work?

texts:
I understand how the RSA algorithm works for encryption and decryption purposes but I don't get how signing is done.

Here's what I (think) I know and is common practice:

If I have a message that I want to sign, I don't sign the message itself but I create a hash of it and then sign that hash by using my private key.
The signature gets attached to the message and both are transferred to the recipient.
The recipient recalculates the hash of the message and then uses my public key to verify the signature he received.

Here are the questions:

Why is it common practice to create a hash of the message and sign that instead of signing the message directly?
The important part and this is where I really started scratching my head: How can the recipient verify that I own the private key if the public key seems to be enough to recreate the signature?


texts: Java recover the public key by only having the privatekey possible?

texts:
Source:

https://stackoverflow.com/questions/48521925/java-recover-the-public-key-by-only-having-the-privatekey-possible

How to solve this problem programmatically

try {
    KeyPairGenerator keyGen = KeyPairGenerator.getInstance("ECDSA", "BC");
    SecureRandom random = SecureRandom.getInstance("SHA1PRNG");
    ECGenParameterSpec ecSpec = new ECGenParameterSpec("prime192v1");
    // Initialize the key generator and generate a KeyPair
    keyGen.initialize(ecSpec, random); // 256 bytes provides an
                                        // acceptable security level
    KeyPair keyPair = keyGen.generateKeyPair();
    // Set the public and private keys from the keyPair
    privateKey = keyPair.getPrivate();
    publicKey = keyPair.getPublic();

    System.out.println("Private and public keys:");
    System.out.println("PRIVATE: " + StringUtil.getStringFromKey(this.privateKey));
    System.out.println("PUBLIC: " + StringUtil.getStringFromKey(this.publicKey));

} catch (Exception e) {
    throw new RuntimeException(e);
}


texts: Is forward secrecy overhyped or necessary?

texts:
Forward Secrecy, also perfect forward secrecy, gives assurance about session keys even the private key is compromised. This is achieved by generating a random key per session without using a deterministic generation algorithm.

In this answer's quote Thomas Pornin says

  Reusing encryption keys goes contrary to forward secrecy, and forward secrecy has become a selling point (though it's a bit overhyped, in my opinion).

While almost everywhere forward secrecy is recommended why it should be a bit overhyped?


texts: Is it possible to derive a homomorphic signature from homomorphic encryption

texts:
At the moment I am trying to find a practical way to implement a linearly homomorphic signature.

Background:

"In a homomorphic signature scheme, a user Alice signs some large dataset x using her secret signing key and uploads the signed data to an untrusted remote server. The server can then run some computation y=f(x) over the signed data and homomorphically derive a short signature σf,y certifying that y is the correct output of the computation f. Anybody can verify the tuple (f,y,σf,y) using Alice's public verification key and become convinced of this fact without having to retrieve the entire underlying data."

At the moment I can't find anything in the literature, but it seems like it should be possible to implement a homomorphic signature using homomorphic encryption. Specifically, I want to use Microsoft SEAL to do this.

It looks like it should be possible (and quite simple) to implement all the required components of a linearly homomorphic signature using microsoft SEAL. Does anyone know if this is possible?

Thanks!!


texts: Using Shor's algorithm to solve the discrete logarithm problem

texts:
I have read about Shor's algorithm and my understanding is that it can be used to factor large numbers efficiently. Can Shor's algorithm, though, be used to solve this problem:

Find the number $e$ given the following information (Assume that $P$, $C$, $N$ and $e$ are all large, say 2048-bit integers):

the integers $P$ and $N$
the integer $C$ where  $C = P^e \bmod N$

If so, how does this algorithm work? Please explain it simply as I am not familiar with quantum mechanics.


texts: How to handle authenticated encryption for big files?

texts:
First I need to mention that I can't use BouncyCastle to implement this solution.
I have to encrypt files into the file system. Those files are not going to be tranfered over the wire to any other location. They are only going to be stored in the server for later use by an application installed there. The file system may or may not be encrypted at an OS level, but that's something that I can't count on.
My files are going to be big files (say from several hundreds of megs to some times a couple of GBs). And they will be created on a regular basis, so I can expect to have a growing number of them. Also, sometimes some of this files are going to be deleted cause they may no longer be needed, and some other times files will be kept for years.
I already have the encryption in place, with AES/CBC/PKCS5Padding, using a 256 bit key and  I/O Cipher Streams. I have no authentication thought.
I don't think I can assume that it is safe to just encrypt and not use authentication as the server could be hacked I guess and the files stolen.
Also, by reading several questions it's clear that no authentication is just someting I shouldn't even think of.
So what are my options here then? I see 2 with some pro/cons analysis:
Option 1: AES/CBC + MAC (say with SHA-256)
Pros

Already have the encryption part working
Supported by Java with no extra libs

Cons

I have to deal with the computation of the MAC
I have to deal with appending the mac to the file and extracting it later
I will have to handle validation myself.
Lots of room for me not getting that right I'm affraid.

Option 2: Use GCM operation mode
Pros

Forget about handling tag computation / message authentication
Supported by Java (I'm using 1.8, so the default provider supports it)

Cons

I found that there are people who wouldn't recommend it.
Also this post seems to suggest that performance is somewhat an issue with Java8, but that's something I haven't verified (Update: @archie pointed to here and here that comfirm the performance issues).
It is badly broken in Java 1.7. I have yet to verify it works ok in Java 1.8 (update: this thread verifies that problems are still present in Java 8)
I'm using a single symmetric key for encryption. I'm worried about how to manage the nonce so I don't break the security properties of the algorithm (My current implementation gets the IV from cipher.getIV() after the Cipher is initialized. I'm not sure if that's good enough for GCM or if I need to take other special considerations.)

Are those options that I mention valid? What about the pro/con analysis? Is there any other suggestion you would have? Which approach would you choose?


texts:
Some papers count the number of the fixed points in the RSA encryption algorithm. They're a minimum of 9 and the real number depends on the smoothness of primes $p$ and $q$.

It very unlikely that a real plaintext is one among those fixed points.

One of those fixed point message is the message $m=1$, indeed: $1^e \equiv 1 \pmod N$. Other trivial fixed points are $0$ and $N-1$.

Is it possible to exploit the knowledge of a non-trivial fixed point in the RSA (schoolbook) permutation to factor the modulus $N$?

Saying it differently, given a integer $\bar m \not \in \{0, 1, N-1\}$ such that $\bar m^e \equiv \bar m \pmod N$ is possible to recover the factorization of the modulus $N$?


texts: Proportion of RSA moduli factorable by NFS with less effort than average?

texts:
When applied to integers $N$ of comparable size, the Number Field Sieve is notoriously much faster if $N$ is known to be of the form $r^k\pm s$ with $r$ and $s$ suitably small integers, and $k$ an integer: using $L$-notation, the running time of this Special NFS is $L_N(1/3,\sqrt[3]{32/9})$, versus $L_N(1/3,\sqrt[3]{64/9})$ for the General NFS. Correspondingly, public factoring records are higher for SNFS than GNFS (1199 versus 768 bits at time of writing).

GNFS is applicable to most RSA public moduli; but there is some small odd that SNFS is applicable to a random RSA public moduli; and perhaps a more sizable odd that some speedup of NFS is enabled by a suitable form of $N$ (perhaps more general than for the original SNFS).

I'm asking for an evaluation of the proportion of RSA moduli of $n$ bits factorable by NFS with $\alpha\ll1$ times the average GNFS effort.

If that proportion was sizable, and the time to identify such moduli not an insurmountable obstacle, that could matter to situations (which abound) where a potential adversary is content with factoring any of many RSA moduli.


texts: Generate fixed length cipher text from arbitrary length plaintext

texts: Using an encryption algorithm like AES, is it possible to generate a fixed length cipher text no matter how long the plain text becomes?


texts:
Reaching the end of an ECDSA signature verification, we need to compute multiple point multiplication and addition as following: $R=(x_R, y_R) = u_1G + u_2Q$, where $u_1$ and $u_2$ are scalars, $G$ is the curve generator and $Q$ is the public key point. As we're using elliptic curve operations we're computing our curve operations $\mod q$, with $q$ being the field order.

If $R$ is a valid point on the curve and $R \neq\infty$, we need to compute $x_R\mod n$, with $n$ representing the order of the generator, and compare that to the $r$-part of the signature. Why do we need another reduction $\mod q$ if we have already reduced $\mod n$ after the multiplication part?


texts: Oracle version of the IND-PRG game with q queries

texts:
Consider the following oracle-based game:

  $O_0$:  Init: $1^n$; Query: output $y \stackrel{u}{\in} \{0,1\}^{l(n)}$

  $O_1$:  Init: $1^n$; Query: output $G(x)$ with $x \stackrel{u}{\in} \{0,1\}^{n}$

Alice and Bob toss a coin $b \stackrel{u}{\in} \{0,1\}$ and send a black box $O = O_b$ to Eve. Now, consider Eve can do $q$ queries to $O$.

Analyze the advantage of the following distinguisher $D$ which is allowed to query the oracle $q$ times:

  Init: $L = \emptyset$

  Repeat:

  query $O$ to obtain $y$;

  if $y \in L$ output 1; else if $|L| > q$, output $0$;

  else $L = L \cup \{y\}$ and continue

My try

$P[Win] = \frac 1 2 (P[Win|b = 0]+P[Win|b = 1])$

$P[Win|b = 0] = 1 \cdot \frac{2^{l(n)}-1}{2^{l(n)}} \cdot \frac{2^{l(n)}-2}{2^{l(n)}} \cdot \ldots \cdot \frac{2^{l(n)}-(q-1)}{2^{l(n)}}= \frac{(2^{l(n)}-1)!}{2^{l(n)}(2^{l(n)}-q)!} \le \Big( 1 - \frac{1}{2^{l(n)}} \Big)^{q-1} $

$P[Win|b = 1] \ge P[\text{collision in the input}] \le \binom{q}{2} \frac{1}{2^{l(n)}}$

My solution

For future readers I leave my own solution, I am happy if someone can copy it/improve it, etc and post it as an answer. I will then delete the hand-written version:


texts:
I just picked up cryptography and have some questions on RSA cryptosystem:

Say there are two public keys (n, e1), (n, e2), e1 is coprime to e2. They share the same n. Is it possible to find the plaintext if both of them encrypt the same message if I have both 2 public keys and 2 ciphertexts?
Usually, we use two primes p, q to construct modulo n = pq. I am wondering if we change n to pqr....... which is the multiplication of more than two primes, is the phi(n) equal to (p-1)(q-1)(r-1)..... and nothing else need to be changed to make RSA still work?


texts: What is the need for Diffie-Hellman key exchange when we have asymmetric encryption?

texts:
I am new to cryptography and I am having a hard time to understand what is the need for DHKE procedure. I think I fully understand the principle in which it happens and also the mathematics behind it however I feel it is not needed (most probably I am wrong that's why I asking you guys here).
Let's say a client wants to communicate with a server - everything makes perfect sense with the first part of the handshake:
The client sends: "Hello server, this is my TCP max version, this and that, etc."

Then the server responds: "Hello, I am the Foo server. This is my public key (go check my certificate) this is my signature (so you can be sure it is me and not a 'middle man')"

Now due to the properties of the public-private key encryption, the client can send the server HIS public key (we don't care how, it's public anyway, but still the message can be encrypted with the server's public key) and then the secure communication can begin by using asymmetric encryption - when the client send something to the server it will be encrypted with the server's public key (so only the server can decrypt it) and vice versa (when server has to send something to the client it will be encrypted with the client's public key).
If my understanding is correct the DHKE procedure brings nothing new to the table in terms of security and I don't understand the need for using it (I doubt that the symmetric key encryption/decryption is much more efficient in terms of computing power).
Thanks in advance!


texts: How to solve the reverse of an equation that uses MOD?

texts:
I've been tasked with reverse engineering an unknown crypto function.  The function uses the following constants:

$a=380951$:
I noticed that this is a prime number
$b=3182$:
I noted that this is a prime number + 1

The math function applied is as follows:
$\mathrm{result}=((\mathrm{value} \bmod a) \cdot b) \bmod a$

The value is a 24 bit number, as is the result (obviously). The result is subsequently fed into a lookup table of which bits it represents. My plan is to find an efficient algorithm to determine what number $\mathrm{value}$ needs to be to achieve a desired $\mathrm{result}$. If this answer is not within the 24 bit limit, then retry with one of the others that result in the same answer through the lookup table data.

If someone can identify possible algorithm names then I can use that directly, I just can't figure out what this scheme is...

Here is an example:

1434758 becomes 83172 -> lookup table results in 0x37e5 (decrypted 2 bytes of data)

Better answer:
291905 becomes 83172 -> lookup table results in 0x37e5 (decrypted 2 bytes of data)

Lookup table:
7,
15,
23,
47,
93,
186,
372,
744,
1488,
2976,
5952,
11904,
23808,
47616,
95233,
190465

The algorithm used for that is if the result is >= the lookup table then the bit in that position is 1, its number is subtracted and we move to the next bit.

Does anyone recognize this routine?

Alternatively:

Let $x=((y \bmod 380951) \cdot 3182) \bmod 380951$.

How can I efficiently find $y$ given a value of $x$?


texts:
What desirable properties should an S-box have?

My current standard selection process is to just pick them at random and verify that they fit the following criteria:

The probability that any random two bits $S[a]_b$ and $S[c]_d$ are equal (for any random $a$, $b$, $c$ and $d$) is 50%.
The probability that any random two bits $S[a]_n$ and $a_n$ are equal (for any random $a$ and $n$) is 50%.
No entries exist such that $S[a] = a$
No entries exist such that $S[a] = \bar{a}$

Are there any other important properties that need to be applied?

Edit My reasons for asking are that I wish to combine this S-Box design with a CBC mode cipher as discussed on this question.


texts: What does this Big-O notation mean based on appendix?

texts:
I am reading the following book: Introduction to Modern Cryptography Second Edition by Jonathan Katz and Yehuda Lindell.
I am going through page 533 where they list what some of the notation means, and I came across the following:

$O(·)$, $Θ(·)$, $Ω(·)$, $ω(·)$ see Appendix A.2

I believe the first symbol is the Big-O notation, but what are the other symbols called? Do they all do the same thing?
I found Appendix A.2 mentioned above on page 537 which says:

PROPOSITION A.2 For all $x ≥ 1$ it holds that $(1 − 1/x)^x ≤ e^{−1}$.

However, I have no idea what this appendix definition is trying to say. I could not even begin to guess as I do not know what the e is. Could someone please explain this to me? I am very new to both maths and cryptography.
This video explained things well, especially the second post on the video. However, it did not cover what Big-W does, or even what the "W" symbol is called.


texts: Can we reduce Diffie-Hellman problem to "Discrete-log inversion" problem?

texts:
Let $G$ be a cyclic multiplicative group of order $n$. Let $g$ be a (public) generator of $G$.
The Diffie-Hellman (DH) problem asks: Given $g^x, g^y\in G$ for $x, y\in \mathbb{Z}^*_n$, to compute $g^{xy}\in G$.

Let $O$ be an oracle that works as follows: it takes as input $g^x\in G$ for any $x \in \mathbb{Z}^*_n$, it outputs $g^{1/x}\in G$. In other words, $O(g^x)=g^{1/x}$. I call this the "Discrete log inversion" oracle for lack of a better name.

Can we use $O$ to solve the DH problem. I remember reading about this somewhere but can't locate the reference.

Note: $1/x$ is defined as the inverse of $x \in\mathbb{Z}^*_n$.

EDIT: To visualize such a group, let $n=15$ and consider the subgroup of $\mathbb{Z}_{31}^*$ generated by 7, which is $\{1, 7, 18, 2, 14, 5, 4, 28, 10, 8, 25, 20, 16, 19, 9\}$, containing exactly 15 elements. In this case $G=\{7^i \bmod{31}|i \in \mathbb{Z}_{15}\}$


texts: How to choose the size of the IV in AES-GCM?

texts:
In The Galois/Counter Mode of Operation (GCM) by McGrew and Vega (PDF) it's stated that:

  An initialization vector IV , that can have any number of bits between
  $1$ and $2^{64}$. For a fixed value of the key, each IV value must be
  distinct, but need not have equal lengths. 96-bit IV values can be
  processed mor e efficiently, so that length is recommended for
  situations in which efficiency is critical.

But how to choose the IV's size and how - if so - it affects the security of the algorithm?


texts: Let's say I am making an encryption algorithm, and in the algorithm in have the following step: "multiply the integer from the previous step by 9 and take the sum of the digits of the resulting number."  By doing this, I've guaranteed that the result will be divisible by 9 in base 10, which let's say I did not expect.  My question is:  What is this error called, if it is an error?  Is this a specific case of a general class of flaws in crypto algorithms?


texts: Use signed email as method for deriving encryption key

texts:
I'm trying to create a solution to decrypt a file at rest on a server by sending an email to a given address and receiving a reply from that address. I'm struggling to see if its possible and haven't identified a methodology yet; so I'm writing to see if such a solution actually exists.

I don't wish to store an encrypted password on the server, I'd like to be able to derive it based on some exchange via email.  Obviously no data sent or received via the email can give away any part of the secret.  I've been thinking along the lines of leveraging the email sender signing the message (either s/mime or pgp) and using that signature as an input to generating the encryption key. (Assume the email public key part is available to the server) But I haven't hit upon a way to achieve it.

End result is that when some server process requires access to the encrypted file it sends an email. The recipient simply replies, signs the reply and sends.  This is then sufficient for the server to derive the key previously setup.

So anyone know of a methodology or solution that implements something like this?

Many thanks.

r.


texts:
I will be implementing JSON web tokens into my website and have a question about implementing them. I have a choice of using two algorithms, HMAC-SHA256 and ECDSA-SHA256. I have used HMAC-SHA256 in the past for jwt, but now I noticed ECDSA is being added to a lot of jwt libraries. As someone who does not have a strong background in security, I was wondering what the advantages/disadvantages are between these two? Trying to Google HMAC vs ECDSA did not bring up any great results. My areas of concern include:

Speed (Since my server will need to sign many tokens, how do they perform?)
Security (How do they fair against brute force attacks and rainbow tables? This will probably relate to my first concern.)
Stability (Are these algorithms accepted as stable, proven, and reliable?)


texts: I have a ciphertext which has been padded with spaces from left the message is 31 bytes long and e = 3 how can I recover the message with python code .


texts: Is the ChaCha20 block function reversible using known plaintext?

texts:
I've been recently implementing the chacha20 stream cipher with Poly1305. As the core operations which make up the Quarter Round of chacha20 (ARX - Addition Rotation Xor) are indeed reversible, does that make reversing the ChaCha20 possible if an attacker knows the 512 bit key stream generated by the function, by a known plaintext attack on ciphertext that was generated by XORing the former keystream with the known plaintext?

I understand that the design of Chacha20 that uses the processor friendly ARX at its core, makes it very efficient, fast and secure, and hence widely adopted, and I'm also confident about the confusion and diffusion that it offers.

But,
Will it be reversible in the face of a Quantum Computer, if not by a classical computer?

Sorry if my concerns are naive!


texts: Are these functions pseudo random? Why or why not?

texts:
So I am stuck on this problem and have absolutely no intuition as to what the right answer is or how to prove it. Any help would be appreciated.

Let $F$ be a length-preserving pseudorandom function. For the following construction of a keyed function $F':\{0,1\}^n\times\{0,1\}^{n-1}\rightarrow\{0,1\}^{2n}$, state whether $F'$ is a pseudorandom function.

a. $F_k'(x)=F_k(0||x)||F_k(1||x)$

b. $F_k'(x)=F_k(0||x)||F_k(x||1)$

The little bit of intuition that I have makes me think that a isn't pseudo random but b is because in a you know that a 1 was originally in the middle so maybe that helps, but I don't know why. Its mostly just a wild guess.

(here || denotes concatenation)


texts: Solving discrete logarithm when p is not a safe prime

texts:
If you have the cyclic group of integers modulo $p$, where $p$ is not a safe prime, as well as a generator $g$ with which for all factors $q$ of $(p-1)$,

$g^{(p-1)/q} \ne 1$,

This answer says that given $g$ and $g^x \bmod p$, we can determine $x \bmod q$ in $O(\sqrt{q})$ time.

What algorithm lets us do that?


texts: In perfectly secret scheme, if key and message space are uniformly distributed, is ciphertext space always uniform as well?

texts:
Following up on a similar question, Does perfect secrecy imply uniform ciphertext distribution?, the answer seems to be that in a perfectly secret encryption scheme, the distribution of the ciphertext space is not necessarily uniform because the message space is not always uniformly distributed (although the key space is assumed to be uniform).

Question: If we say that the message space and key space are uniformly distributed, this seems to me to imply that the ciphertext space must also be uniform. How would one go about proving this fact?


texts: How message digest hash is used in RSA digital certificate verification

texts:
This is how I understand digital signature verification to work in general:

Plaintext gets run through a hashing mechanism to make a message digest (IBM's terminology, there appear to be plenty of other terms for the hashed data).
Message digest is encrypted using sender's private key.
Both encrypted message digest and plaintext are sent to recipient.
Recipient decrypts message digest using sender's public key.
Plaintext gets run through hashing mechanism to make message digest, as in step 1.
If hashed plaintext and decrypted message digest are equivalent, test passes.

What I can't figure out is how this process is specifically applied in RSA verification of a digital certificate. I can't find the plaintext! If it's generated at random for each request, then what's the point of having a digital signature from the assigning CA in the certificate? If it isn't, then where does whoever is verifying the certificate get the plaintext to compare the signature to? I don't see that it's part of the certificate.

So, first, do I understand the general signature verification process as it applies to digital certificate verification? And if I do, can someone solve the "mystery of the missing plaintext" for me?


texts: What are the known weaknesses in AES and is it being considered for upgrade or replacement?

texts:
I was at a conference earlier this week sponsored by a library about data archiving. The conference was not about cryptography. One of the speakers said that the Advanced Encryption Standard (AES) was going to be 20 years old next year (Rijndael was first published in 1998) and that it was getting near the end of its life.

I'm familiar with cryptography, and I've been troubled by this statement ever since, because I didn't think that AES was in any danger. The algorithm has sufficient key lengths, even to resist quantum computer attacks, and there are no algorithmic flaws that have been discovered.  Recall that DES was showing its age in the mid 1990s, but that was because it's key length was unreasonably short, not for any other reason.

Are there current reasons to consider upgrading or replacing AES?


texts:
I have a confusion in a concept under cryptography context. What is the major difference between an encrypted hash and digital signed hash?

I have used PKI Encryption i.e. public / private key based encryption.

I calculated the hash and encrypted it with the private key of sender. Now, the receiver can unlock the hash with the public key of sender. Hence it proves the authenticity of the data. Now receiver can regenerate the hash and match with the decrypted one and if matches then it proves the data integrity.

Similarly, the signature is created by an hash and same is encrypted; and it is done by private key of sender. Now the receiver can verify the signature by public key of sender. It proves both authenticity and integrity.

I have used both in my case (that i am developing). I think I am using signature / hash as an extra element and only one of them will suffice.

Or is their any benefit of using both or any difference?


texts: Not getting idea how to formally chose chosen cipher attack so adversay wins with non-negligible probability

texts: I was going through this question and intuition came that same message can be used to break security but I an not able formalize it well...can someone help how to create chosen ciphertext attack formally so that adversary wins with significant probability.


texts: Hash-based signature scheme XMSS/LMS susceptible to preimage/second preimage attack?

texts: Are the quantum secure hash based signatures (XMSS/LMS) susceptible to preimage/second preimage attack?


texts: Can this hash-based, short signature scheme work, given a decentralized log of messages as a primitive?

texts:
Suppose we had a decentralized log of messages, i.e., an ever-growing array of information on which anyone could append arbitrary data to. Given such primitive, could a party broadcast authenticated messages using just hash functions? Here is what I have in mind:

1. Register

To start submitting authenticated messages, one must first introduce himself by logging an unsigned message:

pvtKey = uint256.random() // random 256-bit string
pubKey = hash256(pvtKey)  // 256-bit hash function
LOG("REG" + pubKey)

In other words, just logg the hash of the private key. User then waits the LOG above to be globally confirmed (i.e., permanently and irreversibly stored on the decentralized log; that'd be 6 block confs if using Bitcoin, for example).

2. Prepare a message

Before submitting a message, the user must prepare it as follows:

newPvtKey = uint256.random()
newPubKey = hash256(newPvtKey)
msg = "some arbitrary string"
pre = hash256(pvtKey + newPubKey + msg)
LOG("PRE" + pre)

User then waits the log above to be globally confirmed.

3. Submit the message

LOG("SUB" + pvtKey + newPubKey + msg)

Now, every user takes hash256(pvtKey + newPubKey + msg). This is found to be equal to pre, as submitted on the 2nd log. Every user then takes hash256(pvtKey), which is equal to pubKey, as submitted on the 1st log. Every user then concludes the owner of the first pubKey signed msg. To sign a new message, the user repeats steps 2 and 3 using his new pub/pvt key pairs.

Does this scheme work?


texts: What lightweight cryptographic hash function for short input could I use for HMAC?

texts: I am looking for a cryptographic hash function that I can configure for HMAC. The input that I will hash is around 50 bytes. The function must be fast, and computationally lightweight.


texts: What is the importance of the $r$ and $c$ values for the Sponge Construction?

texts:
What is the importance of the $r$ and $c$ values?

Keccak[r=1600,c=0] is stated on a calculator on the Keccak website to be a checksum. But I figured if c=0, then there's only one possible output?

If C is 128, is there only 2^64 possible outputs, despite have infinite output length and an infinite number of inputs?


texts: Bitcoin mining nonce and birthday attack

texts:
Having read the basics of mining and this about SHA256 (probabilistic?) partial preimage possible? and SAT solving - An alternative to brute force bitcoin mining, I have the following question:

Wouldn't it be better to select a random nonce instead of incrementing the first by one? This way, the miner would make use of the birthday attack, which would make the probabilities of finding it higher (for a given number of trials).

I'm not sure that my understanding is correct.


texts: I am very curious on the fact that SHA, MD5 and all related Hash Functions change the output even by changing one bit in input Message. Why is that?


texts: BGW Multiplication: Linearizing the polynomial

texts:
I have some trouble understanding the linearization of the degree 2t polynomial generated by multiplication in BGW. It would be great if someone could decode this linearization in simple terms from a 2t degree polynomial to a t degree polynomial.

I've understood that in multiplication, we calculate r(x) = p(x)q(x) but this means that r(x) is a polynomial of degree 2t. How is this polynomial distributed linearly in the circuit?

Addition in BGW is easy to understand but multiplication has been difficult to comprehend.

Reference: https://www.csa.iisc.ac.in/~arpita/SecureComputation15/Lecture18.pdf


texts:
The question is not about mathematical cryptography but about the practical usage of certificates and their chained verification. Please let me know, if this is the wrong place to post the question.

Lets say I have the end certificate E, signed by S, which is itself signed by the (self signed) root R:

R <--- S <--- E

R is the certificate I can trust per definition (independently of how it finds its way into the system)

During verifying E against S I have to verify S against R.

Now, two cases:

1)

after some period of months I get a new version of E, lets say E2:

R <--- S <--- E2

Is it now OK to "trust" S, because it has been verified against R previously? Can I stop at S or do I need to go up until R again?

In other words: can I rely on a given certificate to be trusted when it already got verified before?

2)

When I get a new S, lets say S2

R <--- S2

is it acceptable to verify S2 immeadiately against R and make it to a trusted certificate in the sense, that when I get a new end certificate E3

R <--- S2  <--- E3

I can stop verification at S2 and skip the remaining chain, because S2 has already been verified (once)?

To ask the other way around: What is the meaning of a trusted certificate and what is the difference to the "root" certificate?


texts: Does the encryption algorithm DES perform random permutations? If so how is information not lost?

texts:
Before round 1 begins, all 64 bits of an incoming message and all 56 bits of the secret key are separately permuted (shuffled)

My question is this : Is the shuffling of the bits performed randomly? If it is performed randomly then how does the reciever decrypt the message successfully even though he/she does not know the order in which the shuffling was carried out (since the shuffling was performed randomly and the only information known to the reciever is only the key and nothing else)?


texts: Anonymity of Paillier cryptosystem in e-voting system

texts:
I'm not an expert so at the moment I'm trying to figure out (at high level) how such cryptosystem would exploit it's homomorphic properties to guarantee anonymity in a e-voting system.

As far as i have understand given two plain number $x$ and $y$, I can sum those numbers and obtain $z$, with such cryptosystem I can encrypt them before the sum, so the adder has no idea of which numbers are involved :

$E(x) + E(y) = E(z)$

When decrypted $D(E(z)) = z$

Reading wikipedia, I find a statement that is not clear to me :

  Semantic security is not the only consideration. There are situations under which malleability may be desirable. The above homomorphic properties can be utilized by secure electronic voting systems. Consider a simple binary ("for" or "against") vote. Let m voters cast a vote of either 1 (for) or 0 (against). Each voter encrypts their choice before casting their vote. The election official takes the product of the m encrypted votes and then decrypts the result and obtains the value n, which is the sum of all the votes. The election official then knows that n people voted for and m-n people voted against. The role of the random r ensures that two equivalent votes will encrypt to the same value only with negligible likelihood, hence ensuring voter privacy.

So if I understand this is like the previous example, with the difference that all the votes are zeroes (against) or ones (for) and are casted for each option.

Eg :

There are four people ($A,B,C$ and the evil Trudy, when only first three people are valid voters).They can only cast $E(0)$ (against) or $E(1)$ (for) that is encrypted in a probabilistic way using election official's public key so $E_c(0) \neq E_a(0)$ and nobody can understand the vote of someone else simply comparing the encrypted votes.

After the votes are casted the election offical will see a sequence like that :

$E_a(0) , E_b(1) , E_c(1)$

Now if each vote is not signed (or identifiable in some way) how can I exclude that Trudy has not forged a huge amount of fake votes? For that reason I suppose that each vote has to be identifiable when still encrypted.
Now the election official sum all the encrypted votes

$E_a(0) + E_b(1) + E_c(1) = E(2)$

And then decrypt the result $D(E(2)) = 2$ obtaining the election result (2 on 3 valid voter is a win of the 'for' and a lose of 'against').

What I can't understand is what prevent the election official to decrypt that votes one by one and see who vote for what.


texts: How 'safe' is a 12-digit alphanumeric key?

texts:
To Access my data over a Portal i got a 12-digit alphanumeric key like:

VGW8-U98T-TXLV

How safe is this key? I don't want to know the chance to win with brute force. I want to know there are several standards to calculate keys like this? It is the one and only way to get access / safe my really personal health data. The portal can easily reached by a website.

I can't tell more informations about how the key is generated or used.
Maybe I'm a bit paranoid, but to get access with just these key and nothing else (e.g. birthday as second check) seems a bit easy. Even if the key give a lot of combination for a brute force.


texts: Making brute force attacks less effective through obfuscation?

texts:
This page on Wikipedia states

  "Brute-force attacks can be made less effective by obfuscating the
  data to be encoded making it more difficult for an attacker to
  recognize when the code has been cracked or by making the attacker do
  more work to test each guess."

This might make sense, but are there any examples of widely used encryption software doing such a thing?


texts: How to generate backup key for PBKD functions?

texts:
I would like to encrypt some files using AES, Ill derive key from password using some standard PBKD function and use that as AES encryption key.

My question is, if user forgets the main password, then he has no input into PBKD function thus no way of getting the AES encryption key.

What algorithm/technique should I use to generate together with the key also a kind of "backup key", preferably a 16 digit number (so ~53 bit key) which can also be used to derrive correct AES encryption key? User would be encouraged to write down this key on paper and save it on a safe place in case main pwd is forgotten.

My idea was to actually encrypt the password used by client using a 53 key, and when needed decrypt it and let user replace or view his lost password, but this would severely compromise the security, as itd lower the difficulty of attack to just getting the 53bit backup key.

So it looks to me that I have to use at least 128bit random key (same strength as the main derived key), which I can convert to ~38digit decimal number or 32digit hexadec number. This is way longer than Id like.

Now while using a 53bit key as a backup key may seem as a crypto joke, when we actually consider that an average password would be 8 digit alphanum string, using lowercase, uppercase, numbers and something like 10 special chars (if only users followed at least these guidelines...), this gives us about 72^8 ~~ 2^50 options, i.e. the output key from PBKD func is an equivalent to 50bit key. a 128bit key would require PBKD input to be at least 21 of these mixed chars and I dare guess users dont usually use such long passwords.

So what are your suggestions and comments on the scenario I described? Thanks.


texts: SHA-256 Partial Collision of initial 36 bits and more

texts:
I was lucky enough to, by brute force, have found two different messages, whose SHA-256 hashes collide in the first 9 hexadecimal characters, which are 36 bits, let's call this hash-prefix.

Given the Birthday Problem, I had to put together 2^18 or rather 2^(36/2) hashes so the chance of success at finding the two messages that have hash-prefix collision would increase to about 50%. I did find them by just gradually comparing the prefixes of each hash with another. The process didn't take too long, but that's why I was lucky.

I want to find 2 different messages that, after hashing, collide in more than 36 initial bits. Can you please help me to come up with a better strategy when comparing hashes?

Here is my method for comparing the hash-prefixes:

class FindPartialCollision {
private:
    ...

public:
    ...

    bool compare(vector<string> sv, int n_Hashes) {
        for (int i = 0; i < n_Hashes; i++) {
            for (int j = i + 1; j < n_Hashes; j++) {
                if (sv.at(i) == sv.at(j)) {
                    cout << "COLLISION FOUND." << endl;
                    return true;
                }
            }
        }
        cout << "No collision found." << endl;
        return false;
    }

    ...
}

Note that vector<string> sv only contains the initial x-character string taken from each SHA-256 hash of each messages, where x is the desired length to compare.

For example, if I were to look for a pair of messages, whose hashes collide in the first 10 hexadecimal characters, the n_Hashes value passed into this method would be 16^(10/2) = 2^(40/2) = 2^20 = 1 048 576, which is already too big and would result in a huge time complexity.

Any help is much appreciated and
I'm sorry for the amateurish question.


texts: How secure is using a hash function as Key Derivation Function?

texts:
I am developing a personal project and I have the following need:
given a randomly generated seed (with enough entropy) I need to generate a number $x$ of Ed25519 key pairs.
These key pairs are not stored. Therefore I need to generate with this seed the exact same key pairs anytime.

To achieve that I have the following algorithm to generate one address number $y$:

I concatenate the seed and $y$ and I calculate the SHA-3 hash: hash = SHA-3(seed+y).
Using this hash I generate an Ed25519 key pair using this hash as a seed: keyPairY = new ed25519KeyPair(hash) (ed25519KeyPair is nacl.sign.keyPair.fromSeed which expects a seed as its argument).

How secure is this kind of algorithm?


texts: What are the known attacks on $\phi$-hiding assumption? How to chose its parameters?

texts:
$\phi$-hiding assumption states the following.

Sample 2 random primes $e_0$ and $e_1$ in the range $[5, 2^{\lambda/4}]$. Sample $N = pq$ of length $\lambda$ ($p$ and $q$ are large primes of length $0.5\lambda$) such that only one of $e_0$, $e_1$ divides $\phi(N) = (p-1).(q-1)$. If an poly-time adversary is given $e_b$ for a random bit b, he cannot tell whether $e_b$ divides $\phi(N)$ or not with advantage significantly greater than $0.5$.

What are the currently known attacks on this assumption?
Does it hold for any randomly chosen N?
Why should $e_0$ and $e_1$ be random primes? Are there any attacks if they are composite? Should $e_0$, $e_1$ be random? Can't they be fixed?
Why should $e_0$ and $e_1$ be chosen in the range $[5, 2^{\lambda/4}]$? Are there known attacks if they are less than $5$ or greater than $2^{\lambda/4}$.
In case $e$ divides $\phi(N)$, we say that "$N$ $\phi$-hides $e$". What does the phrase mean?
Is $\phi$-hiding equivalent to RSA?
For 256 bit security, I need to choose RSA modulus N to be 3072 bits long. If I am using $\phi$-hiding assumption instead of RSA, how long should  modulus N be?


texts: What are the time considerations with regard to security against birthday attack?

texts:
When designing security for a physical safe, one of the critical specifications is how long will the safe resist attack, this tells you how quickly you must detect and respond to an attack on the safe.

As I understand it for hash functions about 80 bits is considered minimally secure, in considering the number of bits for a hash to thwart a birthday attack is there a time consideration as well?


texts: Example of a problem for which Zero-Knowledge proof is not sequentially composable

texts: There are notions that a Zero-knowledge proof with auxiliary input is necessary for sequential composition. However, the authors here give a very convoluted example of a system which is not sequentially composable under the original ZK definition. Could you please give me an example where the original definition by Goldwasser et al. is not enough for sequential composability?


texts:
I'm actually new to cryptography and a friend of mine requested that I should read the Katz and Lindell book – “introduction to modern cryptography”.
As I read the book I found it very interesting but I'm finding some problems answering a few questions from the book,(for someone new like me I managed to to answer section 1 and almost section 2), but enough talk I'm getting straight to the questions:
First of all, I needed to prove witch of these two assumptions is perfectly secret :

The message space is $M = \{m \in \{0, 1\}^l \text{ | the last bit of }m \text{ is }0\}$.
Gen chooses a uniform key from $\{0, 1\}^{l−1}$. $Enc_k(m)$ returns ciphertext
$m \oplus (k || 0)$, and $Dec_k(c)$ returns $c \oplus (k || 0)$.

The message space is $M = \{0,..., 4\}$. Algorithm Gen chooses
a uniform key from the key space $\{0,..., 5\}$. $Enc_k(m)$ returns
$[(k + m) \bmod 5]$, and $Dec_k(c)$ returns $[(c − k) \bmod 5]$.

Suppose that we have $\pi(Gen,Enc,Dec)$.
For the first one I guess that I answered it but I need you guys to correct me since I'm not sur if my method is true or not :

$M = \{0, 1\}^l$
$n$ and $k = \{0, 1\}^{l-1}$
with $Enc_k(m)$ outputting $c = m_{[1,ℓ-1]} \oplus (k||0)$, i.e the xor of the first $(l-1)$ bits of $m$ with the key $k$.
The decryption outputs $Dec_k(c)$ as $c \oplus (k||0)$ concatenated with a random 1 bit string (0 on each of the cases $Enc$ & $Dec$).
This scheme satisfies the $2^{−1}$ property that
$Pr[Dec(Enc(m)) = m] \geq 2^{-1}$ for every $m$, which means that in the first assumption the scheme is perfectly secure.

For the second case I have no idea how to put that proof on the line.


texts: I'm thinking of implementing text encryption and decryption in my program using AES using key sharing thanks to MPC (the point is that the key should never be provided in full), however, all public libraries that I found offer this option only assuming that one member has the whole key and another plaintext. Does anyone know libraries that allow you to implement such a solution?


texts: How to compare two post quantum digital signature schemes in terms of latency?

texts: I want to compare two digital signature schemes of different nature. One is Hash-based (Winternitz one time signature scheme) and the other is lattice-based (Dilithium Crystals). What about be an academically accepted way to compare their latency and security?


texts: Using a Secure RNG in Probabilistic Fair Exchange

texts:
I am attempting to implement probabilistic fair exchange described in Probabilistic Non-Repudiation without Trusted Third Party.

A secures a message using AES with 512 bit keys (in my implementation). A then generates N random 512 bit sequences. The cyphertext is then transmitted to B who signs it to provide proof of receipt. N is kept secret from B and a timeout t is agreed upon. A then sends the N random bit sequences one by one to B who signs each sequence and returns it to A. The signing must happen before the timeout (and the timeout is assumed to be significantly shorter than the time taken to decrypt the message) otherwise protocol execution ends. At the end the key is then transmitted and B would sign it as normal (not knowing if it is a fake key or the real key, but must continue to participate in case it is not the real key). A would then indicate to B that it is the real key and the fair exchange is completed.

This gives us an approximate 1/n probability that B can correctly guess the number of the real key (and potentially unfairly deprive A of a receipt).

For performance reasons n has to be limited to a sensible amount but for UX reasons, n is generated using a secure RNG between 500-1500 as a default value (which can be changed). This is public to both parties using the standard client implementation. If a user was to attack the protocol and attempt to guess the key without providing receipt, would it not make sense to guess n+1 to be approaching 1500? For instance it would nearly always make sense to an attacker to not provide a receipt for round 1500?

Should the source of the random number be the user (and risk severe performance penalties if they were to choose a random number too high) and only prompt the user if they provide a number outside a sensible range (and not give them a guideline) or is using the Secure-RNG sufficient to achieve probabilistic fair exchange


texts:
Everywhere I look in PCP literature I find the soundness error advertised as $1/2$. For example, here on page 17 it says (regarding soundness)

  SCI uses 14 repetitions to reduce the probability of error to $error = 1/2$

and then

  the security analysis guarantees that this verdict is correct with probability $1 − error$

This implies that even after additional tests, soundness is no less than $1/2$. I interpret this and similar statements in other papers to mean that on average an adversarial prover's false proof will be accepted half the time. This would be unacceptable for most applications (such as computational integrity). I must be misunderstanding the context for these statements.

It seems that in order to minimize the error below $1/2$, the verification process (and maybe even the proving process) must be repeated $k$ times for a soundness error of $2^{-k}$.


texts: Can knowing the ephemeral key recover the private key in ECDSA

texts:
If the attacker - some guy who really, really wants to steal bitcoins - somehow finds the ephemeral key used in an 256-bit ECDSA signature, can he recover the private key?

If so, would knowing the partial bits of the ephemeral key be sufficient to recover the private key entirely?


texts:
ECDSA and ECDH give us the following methods:

// ECDSA
var signature = ECDSA.sign(privateKey, hash);
var isValid = ECDSA.verify(publicKey, hash, signature);

// ECDH
var sharedSecret1 = ECDH.compute(node1.publicKey, node2.privateKey);
var sharedSecret2 = ECDH.compute(node2.publicKey, node1.privateKey);
// sharedSecret1 == sharedSecret2;

ECDSA give as a very long signature (73 bytes).

I am wondering why we need ECDSA if we can do signing only with ECDH and get much smaller signature:

function sign(priavteKey, hash) {
  // generate public key from private key
  var publicKey = computePublicKey(hash);
  var sharedSecret = ECDH.compute(publicKey, privateKey);
  var signature = hash(sharedSecret);
  return signature;
}

function verify(publicKey, hash, signature) {
  var sharedSecret = ECDH.compute(publicKey, hash);
  return (hash(sharedSecret) == signature);
}

This method exposes one of the private keys of ECDH and uses it for generating the signature hash. Is there any way that this method can expose the real private key?

I've been reading these answers and it seems ok…


texts: When is AES chosen instead of a stream Cipher (e.g., RC4) during an SSL connection?

texts:
During an SSL handshake, the browser sends a list of cipher suites to the server, from which the server selects one option.

For data encryption, two of the several possibilities for the ciphers in this suite are AES (a block cipher) and RC4 (a stream cipher).

I understand that AES would be a better choice for applications where all the data is available at once, permitting the use of large blocks. RC4 on the other hand is more suited for applications where  continuous data (that may not be available all at once) is to be encrypted (e.g., real-time data).

My question is: By the time the cipher suites are negotiated (the very first steps of the handshake),  the server is not yet aware of what kind of data the browser is going to ask for. For example, by this time, the server does not know whether the browser will be downloading some large file (suited for AES than RC4).

As a result, the server may select a poor cipher for the process. Can anyone give me some idea on how SSL handles this challenge (of choosing the optimal cipher for the task at hand)?