texts: Understanding $\varepsilon$-advantage in cryptographically secure deterministic RNG

texts:
In Efficient and Secure Pseudo-Random Number Generation by Vazirani & Vazirani, it is stated that every pseudorandom number generator which satisfies the XOR Condition can securely output $\log n$ bits (where $\ n = |N|$). Such a condition is satisfied by the Blum-Blum-Shub (whose trapdoor is based on the quadratic residuosity assumption), thus up to $\log \log N $ bits at each step can be extracted.

My question is of information theoretic interest: what exactly do they mean when they state that the boolean predicates (the output bits) $b_1,\ldots,b_k$ are inversion secure if there exists a Las Vegas algorithm T that runs in probabilistic polytime, i.e $T^{O_{b_{i},N}}[i, E_{N}(x)] = x$ (with $E_{N}(x)$ the one-way function), where $O_{b_{i},N}$ is a $\frac{1}{2} + \frac{1}{poly(n)}$ advantage oracle for $b_i$ with respect to N?
Why the probability beyond 1/2 plus that $\varepsilon$-advantage, which, I assume, bounds the overall probability? So, if the XOR of each non-empty subset of these predicates is inversion secure,
boolean predicates satisfy the XOR Condition.

I think it's pretty close with what Rabin function says:

  If for a $\frac{1}{logN}$ fraction of the quadratic residues $q\pmod N$ one could find a square root of $q$, then one could factor $N$ in random polynomial time.

Still, where does $1/(\log N)$ come from?


texts:
I'm reading this paper:
Traceable Ring Signature.

I see this in section 4:

$A_1=(\frac{\sigma_s}{A_0})^{1/s}$

My question is how to compute this, such as:

$x^{1/y}$

where $x$ is a generator.


texts: CVP over $\Bbb Z_{q}$ - is the problem still hard?

texts:
I'm reading about the CVP problem, and all the papers I've read so far handle the case where the CVP matrix and vector are over $\Bbb R^{n}$ (or over $\Bbb Z^{n}$), and the distance is a real number.

However, I failed to find any references for the same problem over $\Bbb Z_{q}$. That is, where we have a matrix $A \in \Bbb Z_{q}^{n \times m}$ and vector $t \in \Bbb Z_{q}^{n}$ , and we have to decide whether there is some $v$ such that $A\,v - t\;\underline{\underline{\bmod q\;}}$ has a small norm.

(The norm I'm interested at is L1, since other norms might not be defined $\bmod q$ ).

Am I missing something, and this version of CVP is trivially easy / trivially equivalent to the "regular" CVP problem? If not, are you aware of papers that considered this version?


texts: In which situation is HMAC mandatory rather than signature?

texts:
I’ve seen that the question has been asked already but this is still confusing to me.

In a digital signature, Alice sends a message M and the hash(M) which is signed by her private key. Bob recomputes hash(M) (that he retrieves with Alice’s public key) and ensures that he finds the same hash value as Alice.
Therefore he knows that the message M is coming from Alice and that M has not been tampered with during the transit. So, it looks like we get both authentication and integrity.

In the HMAC construction (or more generally MAC this is not the subject here), a shared key between Alice and Bob is appended to the hash of data. I agree that it provides also both message authentication and integrity but what does it provide more? In other words, in which situation is HMAC absolutely required?


texts: What should I be aware of when implementing algorithms myself?

texts:
I plan to build my own crypto library. The project will be primarily for me to learn (and if useful for no other purpose, that is fine). In the past I have implemented a few hashes, and AES quite a few times while learning about it, but those projects were solely for me to learn, not for any field use. With this one I'd like it to work on it as if it were be to used outside of myself.

I understand that using/implementing your own crypto is usually a bad idea (if not always), so the answer to how to approach this is always "just don't". What makes sense in my head is: if all the tests work, the implementations should be valid. So I guess what I mean to ask is, does matching all the test vectors mean my implementations are valid mathematically? Is implementing mathematics correctly not enough because there are other things I need to plan ahead for? I know pretty much nothing about side-channel attacks, so I don't know if that has to do with the primitives in use or the system using them.

tl;dr: I don't intend to put it into production, but I want to build as if I were, to learn.


texts: AES/GCM/PKCS5Padding giving issues while AES/CBC/PKCS5Padding works fine for my use case

texts:
I have a requirement to read-encypt-save plus its reverse i.e. read-decypt-save files through chunk/block mechanism (single operation not feasible because of huge(GBs) file sizes).
So essentially the two functionalities should work as below :

loop (read-plain-text-block-from-external-source -> encrypt -> save-encrypted-text-block-to-external-target)
loop (read-encrypted-text-block-from-external-source -> decrypt -> save-plain-text-block-to-external-target)

Also requirement is to have flexibility to use different chunk/block sizes while encryption / decryption. so either party (Encrypter or Decrypter) does not know other's size at all.
Now we have successfully implemented this functionality using AES/CBC/PKCS5Padding but we are facing issues while trying the same using AES/GCM/PKCS5Padding. Decryption was returning blank plain chunks and we finally received aggregated plain chunks at loop completion. this stops us from saving individual decrypted-chunks to external target during single iteration of the loop.
Any idea if AES/GCM/PKCS5Padding is even an option for our use case ? what must be causing above issue ?


texts: What is the difference between exhaustive search and factorization in relationship to determining a key?

texts: It seems to me an exhaustive search would simply try to use all the possible bit combinations of a key, while factorization is some mathematical formula for determining the key? When discussing the NSA's cryptography "breakthroughs" some articles discuss factorization as the contributing factor. However, others go further and mention that they have only found a flaw in how some programs use factorization. I guess I'm not understanding how that term should actually be used as it relates to cryptography.


texts: How is the MD2 hash function S-table constructed from Pi?

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

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

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

In the reference code, there is the following comment:

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

Looking at the first few bytes:

  41, 46, 67

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

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


texts:
For primes p and q used to create a keypair, I understand that the following operation is used to create a signature:

$M^d (\bmod\ N)$

where d and N have their usual meanings and M is the message. In this case, however you need to possess the public key in order to verify the signature S as follows :-

$S^e (\bmod\ N)$

In the case of a certificate (CA signed or self signed), is the plaintext public key part of it?


texts: Using same key twice with Vigenere cipher

texts:
Could someone please give a walkthrough of how this works: Decrypting a vigenere cipher with a reused one-time pad.

It was never fully answered with the example given in the comment.

e.g

Plaintext 1 - apples

Plaintext 2 - orange

Key : fruits

They are all 6 letters. If 'fruits' was used to encrypt both 'apples' and 'oranges' using vigenere, how could an attacker obtain the plaintexts and key with only knowing the ciphertexts?


texts: Choosing good parameter for Lenstra's elliptic curve factorization

texts:
In Wikipedia, there is an article explaining Lenstra's factorization algorithm. As far as I got it, we choose some $e \in \mathbb{N}$ and a point $P$ on the curve and then calculate $eP$. While calculating, we must invert elements, and if that does not work, we are rewarded with a factorization.

So far, so good. Now, Wikipedia (and some other books) suggest that $e=B!$ for some small $B \in \mathbb{N}$. Can someone please explain why this is so good? Also, why is there a relation in the choice of $B$ to Pollard's $p-1$ algorithm?


texts: Length Extension attacks in SHA1 and MD5?

texts:
From my understanding on the internet about length-extension attack, I have understood that hash(secret_key|known_data) can be exploited to produce hash(secret_key|known_data|appended_data) even without knowing the exact value of the secret_key by just knowing the length of the key. I tried implementing this using hashpumpy python module and this did not match.

import os
import sys
import hashpumpy

secret_key="secretkey"
known_data="data"
appended_data="append"

hash_1="9885f8af04289135df259e34bd22d17fe45ea81e" # hash of secret_key+known_data
hash_2="e9163e43652a921df34f76e635d32f6aad1286b8" # hash of secret_key+known_data+appended_data

new_hash,msg=hashpumpy.hashpump(hash_1,'data','append',len(secret_key))
print(new_hash,msg)

Output:

  475bdd96a25e7717842072c5be2944076ba31143
  b'data\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00happend'

But the hash I want to calculate is of secretdataappend


texts: What is the runtime complexity of the `BLAKE2` hash function?

texts:
Assume you want to calculate the blake2 hash function for an arbitrary input of $n$ bytes. I am wondering about the runtime, in particular:

Does the runtime of scale linearly with the input length, i.e., can the runtime of blake2 be estimated as O(n)?
Is the landau even something that is sensible here, given how optimized cryptographic operations are on modern day processors (say on an intel-i7)


texts: I know that asymmetric cipher shouldn't be used for encryption large files because it is slow. It is better to use symmetric cipher. But, what worse, I've read that it is unsecure to encrypt a large file with a public key. But, why?


texts: Additive homomorphic encryption scheme without change in operator

texts:
I'm looking for an additive homomorphic encryption that the addition operator (+) in its plaintext space be the same as addition operator in its ciphertext space. (Schemes like Paillier do addition in plaintext space by multiplication in ciphertext space).

Does anybody know such a scheme?


texts:
Considering CBC-MAC as:

$\qquad H_0 = IV = 0$

$\qquad H_i = E_k(P_i \oplus H_{i-1})$

$\qquad MAC = H_n$

What are the properties that makes this "safer" (less exposed to failure) than just:

$\qquad H_0 = IV = 0$

$\qquad H_i = P_i \oplus H_{i-1}$

$\qquad MAC = E_k(H_n)$

Please use simple terms (a didactic explanation for non cryptographers is appreciated)


texts: Why does HMAC need a fixed length padding?

texts:
As everybody knows in order to calculate HMAC we have to concatenate padding to the message. I am just curious why the padding needs to be fixed-length. Why do we need the blocksize parameter here?

Why not use an arbitrary length key with arbitrary length 0x5c5c5c…5c, 0x363636…36?

Why do we need to truncate the key when it is larger than the blocksize?


texts:
Premise
Several cryptographic primitives employ randomized numerical constants. To avoid suspicious that the designer selected such constants in order to plant a backdoor, "nothing-up-my-sleeve numbers" are used. These are numbers constructed from the first digits of some important constants, like $\pi$, $e$, $\sqrt{2}$, ... so that they do not appear to be well-crafted to hide a backdoor.
The Problem
However, designers of different systems use different constants. Below some examples copied from the wikipedia's page:

Small roots of small integers (SHA-1, SHA-2)

$\sin 1, \sin 2, \dots$ (MD5)

$e$ (DFC)

$\pi$ (Blowfish and many other)

$1/\pi$ (ARIA)

0x123456789ABCDEFFEDCBA9876543210 (KASUMI)

ASCII string "expand 32-byte k" (Salsa20)

But with enough degrees of freedom, it is clear that nothing-up-my-sleeve numbers lose their purpose. For example, who does guarantee that the sentence "expand 32-byte k" was not selected among thousands of similarly innocent ones ("expanding 32-byte k", "expansion of 32-byte k", "32-byte expanded k", ...) in order to hide a backdoor? Likewise for numerical constants.
The Question
In light of the previous considerations, was a "nothing-up-my-sleeve numbers standard" ever proposed? If not, why not?
A very simple standard could be: "A cryptographic primitive employing a randomized constant $C$ (if there are more randomized constants, $C$ is their binary concatenation) must fix $C$ to be the first digits of the binary representation of $\pi$."


texts: How secure is ECDH if the public keys are never changed?

texts:
I have a scenario where I'd like to use Diffie Hellman keys where the public keys are exchanged once and then never changed.

So server generates a key pair (secp256k1 or secp256r1) and sends its public key to client and the client does the same. From that point onward, all the communication is secured by using the derived symmetric key. But these key pairs are never changed.

My question is how secured is how easy would it be for someone to figure out the symmetric key now that the same key is used for encryption/decryption?


texts:
I don't want to discuss the security problem with MD-based hashfunctions when using them as KDF. Since the existence of SHA3 or Skein hashfunction it is possible to use them as key prefix KDF.

What I mean with key prefix KDF is the following:
In https://eprint.iacr.org/2010/264.pdf you can find it or in short:

KDF(x) = H(x||1)||H(x||2)||...||H(x||n)

H is a Hashfunction, x the seed, the numbers are a counter.
While it is not specified what the counter is exactly is, I have a question.
The Counter starts with 1 and goes to N. How many Bytes is that Counter? Is it a single Byte?


texts:
In the EEA2 option for encryption in LTE the AES-128 algorithm is mechanized. There, the nonce used in the CTR Mode is a 128-bit value. The first 64-bits are covered by a COUNTER, a BEARER, a DIRECTION, and a LENGTH parameter. LENGTH parameter is supposed to control the output of the KEYSTREAM length (not changing the bits themselves).

However, I was not able to find anywhere a useful description of how this parameter actually works. Available documentation gives detailed descriptions of the COUNTER, BEARER, and DIRECTION parameters (these amount to 38-bits) and the rest 26-bits are set to 0 (the remaining 64-bits are set to 0 and then incremented).

Does anyone know what this LENGTH parameter does and how it works? It seems to me it has no particular reason to be mentioned...


texts: Signing a binary hash vs character representation of the same hash

texts:
I have a hash that I want to sign, with the hexadecimal representation: hash_bin=0x11223344 (length 4 bytes).
The same hash also has a character representation hash_text=”11223344”, which is the binary stream {0x31, 0x31, 0x32, 0x32, 0x33, 0x33, 0x34, 0x34} (length 8 bytes).

Which of the hash versions (hash_bin – 4 bytes / hash_text – 8 bytes) is better to use for signing the hash by RSA, security-wise?


texts:
I am building an app in which I would like to encrypt user data and support offline login.

From this answer about using passwords for encryption:

  Best practice is to use a PBKDF to generate a 'key encryption key' (KEK), then a full entropy random key is used to encrypt the data, and the KEK is used to encrypt that key.

Would it be reasonable to include in the data a known value such as "hello everybody" (or the username, if the variability per user would help?), and authenticate users by attempting to decrypt their data and checking that the decrypted value matches the known value?


texts: What is a good algorithm to scramble data in a 2-D grid

texts:
I want to know if there exists an algorithm i can use where the input is a string of data and the output is a scrambled version of the same but in a 2 D array
ie given something like:

|1 2 3 4 5 6 7 8 9|

I want an output somewhat like:

|2 8 * 3 |

|7 9 4 1 |

|* 5 * 6 |

The scrambling would ideally be on the basis of a key and the same key or its pair can be used to unscramble the message.


texts: Digital Signature Algorithm for large files - bottle-necked by hash function?

texts:
I am new to studying digital signatures like ECDSA and EdDSA, and was curious about something.

Lets say hypothetically I want to create a digital signatures of millions of files, with a total size of 10TB.

From what I understand, digital signature algorithms are hash-then-sign, and the hash functions used must be cryptographic hashes such as SHA-2 or SHA-3. However, looking up the typical benchmarks of SHA-2 and SHA-3, their speed in terms of throughput (bytes/second) seem to be well under 500MB/s per core on modern laptop CPUs, which is not bad.

But in environments without hardware acceleration, it is probably at least 4x slower. On mobile devices, SHA-3 seems to perform 20MB/s on my phone according to a javascript benchmark.

It seems like in certain environments, the hash function will be the bottleneck in both creating the signature, as well as verifying it. Especially for mobile devices -- it would take several days to sign/verify a 10TB inventory of files.

Are there any cryptographically secure digital signature algorithms that are optimized for large files in terms of throughput? Or are we always bottlenecked by the hash function?

Are there any fast, non-cryptographic hash function we could use for digital signatures while keeping the cryptographic security?


texts: Random Oracle to prove an Authenticated DH protocol

texts:
I am trying to understand how they use the random oracle to solve the CDH. For example, in the security proof on page 7 of the following paper; A Lightweight Message Authentication Scheme for Smart Grid
Communications, Fouda et al. 2001. The authors used a random oracle to break the security of an authenticated DH protocol. They assumed an adversary who can break the semantic security of the shared key and used this adversary along with a random oracle to solve CDH.

to my understanding a random oracle is like a hash function where the input is a random string and the output also is another random string, so how can we use to solve the CDH;
in the paper, they gave the adversary a tuple $(g, g^a, g^b)$ and allowed him to make a query to the random oracle. Then, they tracked the queries to the random oracle to monitor of $g^{ab}$ was queried. But Why would the adversary query g^ab to the random oracle? Is it part of the game?


texts:
I was thinking about stretching salt.

Key-stretching is good against brute force guessing and assumes your system isn't compromised.

Salting a one-way makes it so you have to compute * n for each password and assumes your system is compromised.

Assuming the system is compromised, derived salts are found, static keys are found, would it make sense to stretch anything at that point?


texts: ElGamal message signatures retrieving the secret value x

texts:
If the GCD(r, p-1) is small and the value k is used to sign a message using ElGamal is also small.  Then the secret value of x can be determined.

Why is this true?  How would one retrieve x?


texts: Precisely how does CBC mode use the initialization vector?

texts:
As I understand it, AES in CBC mode does an XOR of the 128-bit initialization vector and the first 128 bits of plain text. Is this correct?

I am using the PHP 5.3 openssl extension in aes-256-cbc mode. I'm experimenting with a round trip, that is, encrypting and then decrypting to make sure I get back the original string.

I find that if I encrypt with one initialization vector and decrypt with another initialization vector, using the same secret key, the first 128 decrypted bits are corrupt (as expected) and the rest is the correct plain text.

I find that if I encrypt with one initialization vector, and decrypt with a barely-different initialization vector, the decryption shows barely-different plain text. That is, when I change the third byte of the initialization vector, the decrypted plain text shows the third byte corrupt and everything else correct.

This does seem to show how the initialization vector affects AES cipher-block chaining. Is the initialization vector simply XOR'd with with the first 128 bits of plain text, and that's it?


texts: Clarification of NIST Digital Identify Guidelines and "Pepper" in Password Hashing

texts:
For password hashing the NIST Digital Identity Guidelines state

  In addition, verifiers SHOULD perform an additional iteration of a key derivation function using a salt value that is secret and known only to the verifier. This salt value, if used, SHALL be generated by an approved random bit generator [SP 800-90Ar1] and provide at least the minimum security strength specified in the latest revision of SP 800-131A (112 bits as of the date of this publication). The secret salt value SHALL be stored separately from the hashed
  memorized secrets (e.g., in a specialized device like a hardware security module). With this additional iteration, brute-force attacks on the hashed memorized secrets are impractical as long as the secret salt value remains secret.

This additional salt is typically referred to as "pepper" in most literature.  The thing is that the NIST document says "an additional iteration" as if it's a single iteration of the hash function adding in this data.  However, most of the implementations I've seen concatenate the salt and the pepper to create the salt value that the hashing function uses.

Am I right that NIST guidance is to do a single additional iteration?  And if so, is there a difference in real world security between the two?


texts: How to do Hexadecimal multiplication in GF(2^8)

texts:
I'm trying to do a hexadecimal multiplication in GF(2^8).
Now, I know the technique of shifting left the binary numbers in some cases, for example:

02 * 9E
0000 0010 * 1001 1110

you shift one time the 9E part, which results in the following:
0011 1100
and since it went above x^8, you must calculate the XOR operation with the Irreducible polynomial x^8 + x^4 + x^3 + x

and the result would be
0010 0110

I know how many spaces to shift when the first polynomial is a simple one, like
0010 or 0100, but how about when it is a little more complex?
Such as
0111 or 1011?? Hoy many spaces must i shift it?

0111 = 7, so i shift 7 times? or 2 because the greates expoent in the polynomial is 2??

Your help would be very much appreciated!


texts: Idea for secure password hash-likes, is this feasible/usable/workable?

texts:
(Hand moved from stackoverflow.com,due to suggestion)

Since breaking password hashes has become a new passtime for scriptkiddies, I thought of the problem and came up with a novel(?) idea.

store the pass as offset+number instead of hash
the number is a product of two large primes
the password is converted into a number , offset is added and that prime is used to divide the number. If it divides AND the divisor is the larger of the two primes the password is correct.

by definition , each hash is unique and each password can be hashed in many different ways depending on the offset. Breaking one hash means you have to factor the number(which is hard), then find a word which corresponds to a number that is largerprime-offset (which is trivial).

To generate use function f() to turn password into a password-number (not important) , generate two random primes larger than 2^4096 or however much is enough. Take the larger prime and calculate prime-passwordnumber=offset. Multiply the primes to get "number". store number and offset.

To check. use function f() to turn password into a password-number, add offset to find prime. divide number with prime to get the other prime. Check that the first prime was the bigger of the two. If so, password was correct.

f() might be for example utf-8 encoding of the password understood as a large binary integer.


texts: Reusing the random exponent for ElGamal encryption with different plaintexts

texts:
In the basic ElGamal encryption scheme, we encrypt a message $m$ as $(g^r, h^r m)$, where $g$ is the group generator and $h$ is the public key of the recipient.

If the sender has another message $m'$ to send to the recipient, can they use the same random $r$ in the construction without decreasing the security of the scheme? More generally, with $n$ different messages $(m_1, m_2, \dotsc, m_n)$, is it safe to encrypt them as $(g^r, h^r m_1, h^r m_2, \dotsc, h^r m_n)$?


texts:
Ok, so I have this question and I honestly have no idea how to prove it. I know that the function is linear and I know it works for every possible combination, I just don't know how to prove it in an arbitrary manner. Here is the question:

Suppose that instead of using those S-boxes, DES would just substitute a 6-bit string with its first 4 bits, that is T(b1 b2 b3 b4 b5 b6 ) = b1 b2 b3 b4. We have called this transformation T. Show that T is a linear transformation (Note: you need to prove that T(x xor y) = T(x) xor T(y), for all 6-bit strings x and y, not just for a particular pair x and y; so write down a proof that works for arbitrary x and y).

I have no idea where to start since this class isn't about writing proofs.


texts: The security of Zero knowledge proof performance

texts: I recently learned to study the security of zero knowledge proof. As you can see on the wiki (link), it seems to be the most popular example of the Ali Baba cave. I have a question about the security of ZKP (Zero knowledge proof) in the Ali Baba cave. The reasons are as follows: During the verification process, the prover will deliver the value of $e = [0,1, \ldots]$. And $e$ will have a solution to either left or right depending on $0$ or $1$. And according to the length of list $e \space (2 ^ n)$, this process is said to be more secure. However, there are only two paths, and depending on the value of $e$, the secret key value is not changed in directions $A$ and $B$. So, should not the safety of this algorithm be just $2$ ?


texts: Is it possible for an attacker to determine the original input to the S-Boxes in DES?

texts: I am learning about DES, a Feistel 64-bit block cipher with 16 rounds. Is it possible that an intruder can determine the original input to the S-Boxes?


texts: Which is the correct duration of an AES execution?

texts:
I  want to verify if my trigger gives me the correct duration of an AES-128 execution in a specific chip; I need only to have the duration of an AES block encrypt without any other functionality.

The frequency of the CPU is 128 MHZ, the frequency of the AES execution is 64 Mhz.

How can I calculate the duration of an execution of AES in order to verify with what I found with my oscilloscope?


texts: What is the Geometric Generalised T' Method?

texts:
This page by Nicolas T. Courtois  mentions Geometric Generalised T' Method. It is described as

  an advanced geometric algorithm, never published, for finding extra linearly independent equations at a given degree, which would normally be found by Gröbner bases techniques, but at a higher degree(!) with much higher memory and with much higher complexity. So in practice, this algorithm has no competitors in producing such equations on current computers.

The other page of the same site mentions T' method (not geometric and not generalized) as one of the steps of the AES attack and it even says that it is described in several papers (but sadly without any link):

  In general, it is likely that in the future, the best attack on AES will be of the following form:
  1. Use the equations over GF(256).
  2. Apply one of the versions of XSL.
  3. Apply a final step. The so called T' method, described in several papers, may or may not be sufficient.

So, my questions are: What is the T' method? Where it is described? What could be its geometric generalization?

Will be grateful for any reference or clue.


texts: ECDH anonymous key exchange to avoid PKI

texts:
I want to use TLS to encrypt the communication between peers in a P2P network.  Each peer has a well known 256bit peer identifier (the public key of a 256bit elliptic curve keypair). Both peers need to be authenticated against the ECC key.

Each peer has only one ECC key, no RSA key. During the key exchange step, I do not want each peer to generate a self-signed certificate with a bogus RSA key because that would render the authentication meaningless. The peers would have to blindly accept the self-signed RSA certificate because they would not be able to link the RSA key to the ECC key.

Since there is no PKI "authority" to sign each peer certificate, I am considering using ECDH in anon mode to perform the key exchange (TLS_ECDH_anon_WITH_AES_256_CBC_SHA). The anon mode of ECDH will not authenticate the peers at the TLS level, so I want to do the authentication at the application level, by sending/answering a challenge signed by the well known ECC key.

Is this a proper use of ECDH anon, and will a simple challenge/response scheme at the application level guarantee peer authentication?

Also, will this scheme provide forward secrecy?


texts: Encrypting h(k) for defeating partition oracle attacks

texts:
Is encrypting $h(k)$ (or even just $k$) and verifying it before checking the MAC enough to defeat partition oracle attacks and thus make the whole scheme robust/committing (without depending on properties of the cipher, unlike 0-padding)?
update 1:
basically $E_k(h(k)\mathbin\|m)$ or $E_k(k\mathbin\|m)$ where $E$ is an AEAD mode like $(x)chacha20poly1305$. The $k$ is derived from a password from a pkdf like argon2/scrypt/etc. At the start it is computed on both ends but then the party decrypting the ciphertext also checks if $h(k)$ (or just $k$) is correctly appended before the message.


texts: Encryption through multiplication of encoded key

texts:
Yesterday I finished programming my own encryption program. It is using an input and a key. Here are all the steps it is going through. For an example, let say the input is "Hello" and the key is "Hi"

You take the input and convert it into binary:

01001000 01100101 01101100 01101100 01101111

You make this Binary string into one long string:

0100100001100101011011000110110001101111
You convert this long binary number into a decimal number:

0100100001100101011011000110110001101111 = 310939249775
You do the same 3 steps above with the key. So the key "Hi" in Decimal is:

18537
You now take the length of the key, in this 2 because "Hi" has 2 characters.
You multiply the two decimal value, and multiply that by the length of the key:

310939249775*18537*2 = 11527761746158350
You lastly convert this big number into Base36(0-9 a-z). This is the final output:

35i90mxoaa6

Now this is how my encryption program works. You can reverse this my dividing the numbers. If someone only has the output but not the key, he has no way to get to the original message right? Also, if this doesn't exist, can I name this the way I want?


texts: Expected entropy in $P(x)\oplus x$ for random $x$, where $P$ is a random permutation

texts:
Let $P$ be a random permutation of $n>1$ bits. Let $F$ be the function on the same domain $\{0,1\}^n$, defined by $F(x)=P(x)\oplus x$. When $P$ is a block cipher with key a message block, that's the Davies-Meyer construction of a one-way compression function, a variant of which being used in MD5, SHA-1, and SHA-2.

Let $H_F$ be the entropy (in bits) of the source $F(x)$ where $x$ is a vector of $n$ random unbiased independent bits. That is
$$\begin{align*}
H_F&=\sum_{y\in F(\{0,1\}^n)}-\Pr(F(x)=y)\cdot\log_2\big(\Pr(F(x)=y)\big)\\
\\
& = n-{1\over2^n}\cdot\sum_{y\in F(\{0,1\}^n)}\big(\#{\{x, F(x)=y)\}}\big)\cdot\log_2\big(\#{\{x, F(x)=y)\}}\big)
\\
& = n-{1\over2^n}\cdot\sum_{2\le\,j\,\le2^n}\big(\#{\{y,(\#\{x:F(x)=y\})=j\}}\big)\cdot j\cdot\log_2(j)
\end{align*}$$
Note: $\#{\{x, F(x)=y)\}}$ of the 2nd equation is the number of preimages of vector $y$; and $\#{\{y,(\#\{x:F(x)=y\})=j\}}$ of the 3rd is the number of vectors with exactly $j$ preimages.

$H_F$ can be from $0$ (when $P$ happens to be XOR with some constant) to $n$ bits (when $F$ happens to be a permutation, e.g. for $P:$ $00\to00$, $01\to10$, $10\to11$, $11\to01$ ).

Let $H(n)$ be the expected value of $H_F$; that is, the average of $H_F$ over all $(2^n)!$ permutations $P$. A plausible conjecture is that
$$\lim_{n\to\infty}{H(n)\over n}=1$$
How to prove this, and what's a first order approximation of $n-H(n)$ for large $n$?

If $F$ was a random function, we'd have $n-H(n)\approx0.8272\dots$ starting with moderate $n$ according to my analysis there. But I fail to rigorously derive that for the much narrower class of $F$ in the question.


texts:
I am learning about digital signature. For performance, we normally do hash then sign.

One approach is to sign $H(m)$ where $H(\cdot)$ is collision resistant, but under chosen message attack, this approach only has security level of $n/2$ because of birthday attack.

Another approach is to sign $H(m \oplus r)$ where $H(\cdot)$ is  a second-preimage resistant hash function and send $r$ along with the signature, but this is not efficient.

is there a different approach? can we do better on the second approach?


texts: Has a collision ever been found for SHA-1/2/3 when truncated to 128 bits?

texts:
I'm aware that MD5 is broken, and collisions have been found for it. I'm interested in other hashes (SHA-1, SHA-2, SHA-3) when truncated to the same digest size, i.e. 128 bits.

The time complexity of a collision attack is 2^(n/2) (the "birthday attack"). So in the case of a 128 bit hash, one would have to hash 2^64 inputs for a 50% probability of finding any two inputs hashing to the same value (though a collision might be found much earlier in practice).

The currently fastest single Bitcoin mining machine performs about 5 trillion double SHA-256 hashes per second, so assuming 10 trillion/sec for single ones, and assuming the inputs tested would not be larger than one block it would amount to:

2^64 / 10*10^12 / 31536000 = 5.85 years

To scan enough hashes to yield a 50% chance of a collision. Though at that point the machine would have to allocate at least 16 * 2^64 ~= 2.95+e20 bytes ~= 295 exabytes of memory for storing the previous hashes. With today's computing capabilities, this seems somewhat reachable (though not very trivial, and may be extremely expensive to handle the enormous memory/storage  requirements).

Has this already been tried/achieved? any references? (I'm interested mostly in attacks using brute-force search, but more sophisticated ones are also relevant).


texts: What is meant by $\tilde\Omega(\lambda^4)$?

texts:
I'm currently reading the paper (Leveled) fully homomorphic encryption without bootstrapping , and the following paragraph was near the start:

What is meant by the symbol used? Is it merely to represent polynomial time or something else entirely?


texts: Is there an efficient solution? Finding the number of matching items in lists with a threshold

texts:
Alice and Bob both have a list of n items. They want to know the number of items that are occurring in both lists. The catch is, that they should receive 0/no result as a result if less than k items occur in both lists. If more than k items occur in both lists, they can learn anything from each other.

I think this can be done by generating all possible subsets of k items and multiplying the hashes of the items in the subsets with the generator point on an elliptic curve.
Then all resulting points for Alice and Bob for all subsets could be compared.

However, that solution would grow exponentially with k. Is there a better solution to solve this problem?


texts: Is it possible to compute the y-coordinate of a point on SECP256K1, given only the x-coordinate

texts:
Given an x-coordiante of a point on the SECP256K1 curve, is it possible to calculate the corresponding y-coorindate? (Assuming the point is a verifying public key that complies with the Bitcoin standards.)
I am new to the cryptographic realm so please forgive me if the question is naive. From what I know, the public key is a point, or a pair of integers. The SECP256K1 curve is a curve where any point (x, y) on it satisfies
(y ** 2) mod p == (x ** 3 + 7) mod p

where p = 2**256 - 2**32 - 977.
Now let's confine the discussion within the Bitcoin scope. Assume we have a private key that complies with the Bitcoin standards, and from it we can derive the public key, which can be represented as a point (x, y) on the SECP256K1 curve.
Now given only such a x, is it possible to calculate the y?
As a real example, given only x as
0x6778ec0abf66f1ba4d93aa45cad77dc26c593f520448f6fff5b70357270154ba

is it possible get the y as
0x6a5e8cd7276f80ee2f7c081702eff3e14134b006acd0afc8467be94a0a3a0558


texts:
I am trying to compute the multiplicative inverse in galois field $2^8$.The question is to find the multiplicative inverse of the polynomial $x^5+x^4+x^3$
in galois field $2^8$ with the irreducible polynomial $x^8+x^4+x^3+x+1$. To get it I used the Extended Euclidean division but with operations used in galois field $2^8$ My answer is $x^7+x^6+x^5+x^4+x$ while the other answer is $x^6+x^4+x^2+x+1$. I am not sure if this answer is right so i need to make sure. If my answer is not right can someone please show me the details of getting to the solution. Thank you


texts: What is the advantage of guessing PRG impossible outputs?

texts:
Lets say we have a length-tripling PRG  $$ G:\{0,1\}^l \to \{0,1\}^{3l}$$
What would the advantage of an adversary to guess one of the impossible outputs of G?


texts:
In De Canniere & Rechberger's 2008 paper "Preimages for Reduced SHA-0 and SHA-1", the following statement appears on page 6:

  Suppose that we restrict ourselves to the first $j$ + 1 bits of each expanded
  message word $W_i$ (denoted by $W^{j...0}_i$), and that we keep all state bits constant except for those at bit position $j$ + 2 (referred to as $a^{j+2}_i$). In this case, we can derive a simple relation (by collecting all constant parts into a $j$ + 1-bit word $C^{j...0}_i$ and a 1-bit variable $c^j_i$), which holds as long as $0 \leq j < 25$:
  $$
W^{j...0}_i = C^{j...0}_i − (f(c^j_i , a^{j+2}_{i−2} , a^{j+2}_{i−3}) \ll j) − (a^{j+2}_{i−4} \ll j).
$$

I've been trying to understand why this relation holds for many hours, and still can't figure out how it can be true.

The $f$ function takes three inputs: $a_{i-1}^{j}$, $a_{i-2}^{j+2}$, and $a_{i-3}^{j+2}$.  Therefore, $c_i^j = a_{i-1}^{j}$, but the text indicates that $c_i^j = a_{i}^{j+2}$.  How is this possible?
What has happened to the $A_{i+1}$ and $A_i$ terms?  Have they somehow been incorporated into $C_i^{j..0}$ by the text "collecting all constant parts"?

I'd be grateful for anyone who can point me in the direction of source code that implements a preimage attack like this, but if no such thing exists, then I'll be happy for an explanation of the above, and I'll try to work out the rest of the details myself.

Edit: is there a typo?  If so, what is the correct relation?  I ask because I've just noticed that on the previous page, the error word relation is definitely incorrect.  It should be

$$
E_i = W_i \oplus ((W_{i+3} \oplus W_{i+8} \oplus W_{i+14} \oplus W_{i+16}) \ggg s)
$$


texts:
I'm trying to duplicate an RSA signature, and am having trouble at the last couple of steps. I'll detail what I've tried.

I used OpenSSL to generate some 128-bit RSA parameters. Here are my public modulus and exponent:

N = 0xdb52a89a63825f9e498144c240f5c23b
e = 65537

The (hashed, unpadded) message and signature are:

m = 200491217728191104277162087173636532728
s = 238661990926400143633637156414542417630

To verify the signature, we check $s^e = m \mod N$. I want to craft public parameters $(N',e')$ such that $s^{e'} = m \mod N'$. I found an algorithm to do this here, in Section 4.1.  To do this, I choose two primes such that:

$N < pq$
$p-1$ is smooth
$q-1$ is smooth
$m$ and $s$ should each be primitive roots mod $p$ and mod $q$
$\gcd(p-1,q-1) = 2$

The primes need to be smooth so that I can solve the discrete log problem in small subgroups with the Pohlig-Hellman algorithm. $m$ and $s$ need to be primitive roots so that the discrete logs exist.

I chose two primes:

p = 18446744073709558081
q = 18446744073709755467

$p-1$ has factorization $2^6\cdot 3^2 \cdot 5 \cdot 167^2 \cdot 409 \cdot 761 \cdot 859^2$.

$q-1$ has factorization $2 \cdot 13 \cdot 107 \cdot 701 \cdot 15647 \cdot 23099 \cdot 26171$.

They satisfy all the properties listed above. $N'$ is easy:

N_prime = p*q = 340282366920942343108801213731143778827

I used Pohlig-Hellman to compute $e'_p = e' \mod p$ and $e'_q = e' \mod q$. I verified these exponents solve $s^{e'_p} = m \mod p$ and $s^{e'_q} = m \mod q$.

ep = 12805870501641979644
eq = 12267640565537452735

Now here's where I'm stuck. I think I should be able to stitch together $e'_p$ and $e'_q$ with the Chinese Remainder Theorem to get $e'$:

e_prime = CRT( (ep, p-1), (eq, q-1) ) = 199703471997348597303557477228581222008

But I don't think this will work since the $p-1$ and $q-1$ are not coprime (the GCD will be at least 2 since $p-1$ and $q-1$ are always even). Besides, when I test it, it doesn't work:

pow(s, e_prime, N_prime) = 20617548250412763970655475611439323667
m % N_prime = 200491217728191104277162087173636532728

Also, for RSA, we need $\gcd(e', (p-1)(q-1)) = 1$, but for me, this quantity is 24. The source I linked to also proposes a solution, but it didn't work for me either.

Anyone have any advice and where I'm going wrong?


texts:
Reference to SSL 2.0 specs. from: Mozilla - SSL 2.0
Can I conclude that SSL 2.0 Finish messages does not provide AMC for all the messages sent/received by both parties (as in TLS 1.2)? Due to lack of SSL 2.0 official detailed documentation, I am unable to confirm this.

2.2.1 Assuming no session-identifier

client-hello         C -> S: challenge, cipher_specs
server-hello         S -> C: connection-id,server_certificate,cipher_specs
client-master-key    C -> S: {master_key}server_public_key
client-finish        C -> S: {connection-id}client_write_key
server-verify        S -> C: {challenge}server_write_key
server-finish        S -> C: {new_session_id}server_write_key


texts: Is it easier to crack the Vernam Cipher with more than two ciphertexts

texts: I have just started looking into the cracking of the Vernam cipher with two ciphertexts encrypted with the same key by XORing them and then crib dragging and I was wondering if it is made easier if you have more ciphertexts like 3 or 4, and if so how that would be used to the crackers advantage?


texts: Envelope Encryption with asymmetric keys vs KMS

texts:
In Envelope encryption a symmetric secret key is used to sign the data and then another key is used to encrypt the secret to produce an encrypted secret key. The encrypted messages is packaged with the encrypted secret key and sent to the client/consumer which then decrypted the encrypted secret key to get the secret key, which in turn is used to decrypt the message

There are 2 ways to implement it:

Asymmetric encryption: The producer encrypts the secret key(s) with the consumers public key. The consumer uses a private key to decrypted the encrypted secret
KMS (such as AWS KMS): The secret key is encrypted by the KMS, and client that needs access to the secret key has to ask the KMS to decrypt it

The advantage of the KMS approach is that key management is centralized, and revoking permissions from a client can be done by removing the client from the KMS and rotating the key.

Are there any good reasons to use asymmetric keys instead of KMS?


texts:
Given the following PHP code (assuming PHP 5.6.x):

$chars = array_merge(range('A','Z'), range(0,9));
$tokens = array();
for ($i = 0; $i < 1000; $i++) {
    $token = '';
    for($j = 0; $j < 12; $j++) {
        $token .= $chars[array_rand($chars)];
    }
    $tokens[] = $token;
}

If I have one token from the array, but don't know from which index nor what the seed was, I'm trying to understand the probability of predicting other values in the array.

I've got very little experience with the c programming language, but looking at the src it appears the randomness comes from php_rand, which in turn proxies php_mt_rand, which as I understand it is an implementation of Mersenne Twister. I managed to find another question on here with an answer that explains quite well some details on mt_rand, including the fact that with 2496 bytes of consecutive data, we can recover the state. I've actually seen several articles about attacking mt_rand in this manner, but unfortunately I haven't come across any that dealt specifically with 'truncated' random values (i.e. with applied min / max bounds discarding bits from the returned value) and I'm not sure how that interacts with the probability. The articles I've read have also dealt specifically with cracking the state, rather than whether we can reduce probability of predicting a set of consecutive return values without actually fully cracking the state (maybe this is just a dumb question, and you can't).

Assuming I can validate if a 'guess' is in the array, does knowing one token actually significantly narrow the probability below testing the complete C(36,12) set?

Apologies if any of my use of mathematical terminologies are incorrect, I've not studied Math since I finished my Computing Science degree 10 years ago. Consequently the use of Layman's terms in any answers will be appreciated.


texts:
I'm supposed to prove that OTP without the zero key $k=0^n$ is not perfectly secret anymore. I understand that it's not because an attacker learns something by looking at the plaintext and ciphertext. But I don't know how to prove it formally.

I was thinking about using Shannon. But to do so $|K|$ needs to be equal to $|P|=|C|=|{0,1}^n|$, which is not the case if I define $K={0,1}^n$ \ $0^n$. So my idea was to include the zero key to the key space K, but set the probability for $p(k=0^n)=0$. Doing so would allow me to have $|K|=|P|=|C|$ and to use Shannon.

PS: I'm aware of the somewhat similar question (One-time pad and zero key), but we didn't have any rule for $|K|>=|P|$ in order to achieve perfect secrecy. Also I am interested in my question about Shannon.


texts: How vulnerable is one-time pad (OTP) encryption, if the OTP is used twice, with a random substitution scheme

texts:
After reading up on the one-time pad (OTP) encryption method, I could see how it would offer unbreakable encryption if used properly.

Moreover, I looked at how the OTP could be broken if the OTP-key is used on more than one message.

What I now wonder is this: if classically you use a Vigenère Square to substitute letters according to your OTP-key, you can break the encryption by finding cribs and then applying the substitution of the letter in the second message. This is possible since I know the substitution scheme.

Now the interesting point: if I randomize my substitution table, I would think that a decryption using the same OTP-key would no longer be possible, unless I have enough messages to successfully map (almost) each letter to this unknown table.

Correct?


texts: Question about the definition of a secure PRF

texts:
I'm taking a cryptography introduction course, and we're covering the definition of a secure PRF.

I understand the test goes as follows: A challenger picks a function $f$ such that

$f \leftarrow \left\{
     \begin{array}{lr}
       b=1: k\leftarrow K, f\leftarrow \left(k,\cdot \right ) \\
       b=0: Funs \left(X,Y \right )
     \end{array}
   \right.$

Where $Funs(X,Y)$ is the set of all possible PRFs, The entire experiment is defined as $EXP\left(b \right )$, such that the output is the adversary's guess as to whether or not the challenger chose a function at random. A secure PRF is then defined as the conditions where

$\left | Pr\left[EXP\left(0 \right ) =1\right ] - Pr\left[EXP\left(1 \right ) = 1\right ] \right |$ is negligible. Or in other words, when the probability that the attacker's result is zero minus the probability that the attacker's result is one is negligible.

However, what if the adversary's detection method always returns one? This would imply that the cipher is not secure, but that can't be true.

What am I missing here?


texts:
From a definition stand point, can a hashing algorithm have more than one input, ex: $H(m_1, m_2, m_3)$?

If not why are algorithms like bcrypt, scrypt and pbkdf2 referred to as password hashing algorithms?


texts: How to find element g order q, given 2 large primes p and q where q|p-1


texts: Hash algorithm with the least chance for collision

texts:
Out of these algorithms…

MD5
SHA1
SHA224
SHA256
SHA384
SHA512

… which has the least chance of collision, and which is the most secure at the time of writing this?


texts: What was the BassOmatic cipher, and what made it so weak?

texts:
According to Wikipedia, this homebrew cipher was originally used in PGP, before Phil Zimmermann replaced it with IDEA. Supposedly, insecurities in the algorithm were pointed out to him, leading to this change. While I have read the PGP 1.0 source code and saw the implementation of the cipher, that didn't help me actually understand it. I can't seem to find any complete description of the algorithm or, particularly, its weaknesses other than what is provided on Wikipedia:

  The chosen key schedule produces a total of 8 permutation tables, each a permutation of the numbers 0 to 255. Each round consists of 4 operations: XORing the block with one of the permutation tables, shredding or permuting individual bits throughout the block, an unkeyed diffusion called raking, and a substitution step using the permutation tables as S-boxes. The shredding step can either permute all 8 bit-planes independently, or in groups of 4, depending on control bit 3. The permutation tables stay the same through all rounds of encryption on a given block, but if control bit 5 is set, then the tables are regenerated after each block.

I could also find a published quote from the book which Wikipedia used as a citation:

  After Biham and Zimmermann go their food and sat down, Zimmermann took out a few pages of computer listings.  Within minutes, Birham was finding fundamental flaws in Bass-O-Matic.  Some of the flaws were subtle-weaknesses that made the algorithm susceptible to differential cryptanalysis, which was Birham’s speciality. Others were more embarrassing, like a conceptual error in Zimmermann’s algorithm that prevented the last bit of each byte from being properly encrypted.  After ten minutes of Birham’s onslaught, Zimmermann realized that Bass-O-Matic was a lost cause.

How did BassOmatic work, and what were the weaknesses that lead to its replacement?


texts: Split TOTP/HOTP secret and generate pin without trusted dealer

texts:
Many site use time-based one time password (totp) as second factor auth method, such as aws.

So we can split the totp secret and distribute each part to different party to achieve threshold login ( need at least k parties to login ).

We can split secret using shamir secret share scheme, but the problem is when we need to get current pin, we need to reconstruct the secret. Is there any method to do something similar without revealing each one's secret part?

General multiparty computation seems to be a method. But I can't find any practical implementation to do hmac-sha1 algorithm.


texts: Is it ever safe to use encryption with compression?

texts:
In the wake of compression-based side-channel attacks like CRIME and BREACH, are there any safe ways to combine compression and encryption?

The JWE Specification was finalised almost 2 years after BREACH, but still includes DEFLATE compression as an option. Are there cases where that could be used safely?

In my use case (storing encrypted data in a user session token), experimentation has shown compression of around 42% on average, and every bit counts, so I would dearly love to be able to turn this on safely!


texts: How can I change the length of PRF output?

texts:
Say if I have a Pseudo Random Function PRF E: {0,1}^k x {0,1}^l -> {0,1}^l.

Hence it takes a key of length k and outputs text of length l bits. Is it possible to use this PRF E to construct another PRF H (with same inputs)
that outputs t bits instead l bits, where t < l.

Also, is it possible to construct a different PRF G (using E) such that on inputs: (k-bit key and (l-n) bit plain text) G outputs t-bit string such that t = 2 x l

I can't seem to figure out how to construct H so that it outputs a string that has less bits than the input string's length. Because to my understanding, it is impossible to do this yet maintain the one-to-one function property.

As for G, I was thinking of taking the output from E and feed it back to E again as an input, then concatenate everything together. Basically the output will be E{input} + E{E{input}}. But is this Pseudo Random and secure?


texts: Can one use a reversible hash algorithm as a compression function?

texts: As we know any text, file, byte...in SHA-256 output will be returned as 64 hex length. Is it possible to create cryptography that can do the same thing as SHA-256 but can be reversed, so if we have the output of 64 length of hex number, we can reverse it and get started input like "i love programming"? This will be soo cool way to compress huge text. Is it possible?


texts:
From a paper Outsourcing Large Matrix Inversion Computation to A Public Cloud (IEEE Transactions on Cloud Computing, Vol. 1, N°1, 2013; alternate source requiring registration; preprint), I got to know about an encryption-decryption system. As I know only the basics of cryptography, I can't just figure out which cryptosystem this is. The basic algorithm is:

Generate keyspace using some security parameter.
Randomly pick two keys.
Generate a random permutation.
Shuffle the matrix coefficients using the random permutation and key.
Decrypt the resulting matrix using the random permutation and key.


texts: How would quantum computers affect password based encryption?

texts:
At first glance: Assuming that the output of the password hashing function is large enough,
quantum computers should have no effect on password encryption as on symmetric cryptography in general.
Is that correct?

More precisely: Grover's search invokes an oracle instead of searching a dataset. Does this mean that
dictionary attacks cannot be performed efficiently with quantum computers?
Is there any other way in which quantum computers could be used for password cracking?


texts: How to sign different messages using deterministic ECDSA?

texts: The elliptic JavaScript library implements a .sign function which seems to give the same result when signing the same message. That means the k param is constant. Doesn't that mean signing different messages exposes the private key? If that is the case, how can I correctly sign several messages with the same private key?


texts: Can I implement key recovery without compromising security?

texts:
I'm no crypto expert but I'm trying to figure out if this is possible:

I'm building an application that has access to very sensitive user data.
I receive this data in plain text but I'm not allowed to persist it in this state.
When I receive data for user X, I must immediately encrypt the data using the key of user X. I can then persist the encrypted data.
User X needs to be able to grant the ability to decrypt their data to any other user in the system, for a defined period of time. All users in the system are trusted i.e. their identity is not in question.
The ability to decrypt user X's data can only be gained via user X explicitly granting permission i.e. even system admins should not be able to decrypt user X's data without permission being granted.

But, the most important part of all this is:

User X should be able to recover their key if they lose it. We can assume that I will have a solid multi-factor authentication flow to establish and verify the identity of user X.

So my questions are:

If a user loses their key, is there a way to recover their key without having to regenerate the key? So unlike the usual password-recovery flow, I'm not looking to simply regenerate a new key, because that would effectively orphan user X's data already encrypted with the previous key. Is this possible and/or feasible?
With [1] in mind, if an attacker gained full access to my database, is it possible to avoid keeping all the user keys in a central location that would expose me to this kind of attack?
How would I handle providing the ability to decrypt data to an arbitrary number of users without having to re-encrypt the data for each user? i.e. I will only ever have a single encrypted version of user X's data.

I hope this makes sense. I'm happy to try to provide a better explanation.

This answer feels very close, but I'm not sure it satisfies all my requirements: https://mathoverflow.net/a/62111

Any advice and/or guidance would be most welcome.


texts: Are there any standards of multi-prime RSA key generation?

texts:
FIPS 186-3 specifies a method to generate DSA parameters.

Is there anything similar (official standard or widely-accepted recommendation) that shows how to generate the primes for multi-prime RSA?


texts: How does future secrecy fail for Signal group messaging?

texts:
In the paper More is Less: On the End-to-End Security of Group Chats in
Signal, WhatsApp, and Threema, the abstract claims that

  We additionally show that strong security properties, such
  as  Future  Secrecy  which  is  a  core  part  of  the  one-to-one
  communication in the Signal protocol, do not hold for its group
  communication.

Failure of future secrecy makes sense for Whatsapp and Threema, since Threema uses a static key and Whatsapp uses a single symmetric key ratchet for group messaging, both of which are vulnerable to session state compromise. However, the paper states that Signal uses a normal double ratcheting scheme for group messaging such that group messages are indistinguishable from pairwise messages.

How does future secrecy fail for group messaging when the session state is refreshed whenever the keys are ratcheted?

Note: It seems that future secrecy fails due to the ability to join a group just by knowing its GroupID. Assuming that group update messages are properly authenticated, does future secrecy still fail for Signal's group messaging?


texts:
I want to create a $4\times4$ multiplicative inverse table in $GF(2^4)$. The primitive polynomial given is $P(x)= x^4+x+1$
(NOTE: the values in the table need to be in hexadecimal format, hence I'll be using both polynomial and hexadecimal notations in the question henceforth).
Now, I was able to compute multiplicative inverse for the first row of the matrix i.e. (00,01,02,03). The inverse of 03 or $(x+1)$ comes out to be 0E or $(x^3+x^2+x)$.
However, when I try to compute the inverse of 10 or $x^4$, it again comes out to be 0E or $(x^3+x^2+x)$. Is it possible that two polynomials have exactly the same inverse? If not, I'm unable to figure out where I'm going wrong. Please help.


texts: How is the inter and the intra distance of a PUF calculated?

texts:
I was wondering, if I want to calculate the intra distance of a PUF, and I have already measured $n$ times a response to a challenge. Do I choose one reference value and compare the hamming distance of it to all other values $n-1$ comparisons? Or do I compare each response to each other $(n \times(n-1))/2$ comparisons?

The same question for the inter distance. Furthermore would be interesting how great should be $n$ in both cases to get meaningful values? Can this somhow be statistically "proven" by some kind of tests?


texts: Using raw encrypted network data for randomness

texts:
I've read that encrypted data should be, theoretically, indistinguishable from random data. Using this principle of encryption, could I combine encrypted network traffic streams to generate either a seed for a randomness algorithm or simply combine them for the random number itself?
For example: I could take data from a Tails or other Tor connected device and simply specify which incoming node to listen to and for how long, not only would the attacker have to know I used this system but they'd have to know the index and duration of the nodes I choose.
For context: I only need a few MB of extremely random data at very infrequent intervals. So time  and memory efficiency doesn't matter all that much.
To address a comment by DannyNiu: Obviously they now know this system exists but if it can run on any encrypted network then, as opposed to using a random number generator website, you do not know which computer is collecting network traffic for this purpose since any encrypted data could be used.


texts:
I have STRING and MD5(STRING+SALT) for any infinitely many STRING's. Is their any way that I can recover the SALT itself? (SALT is constant) I actually know SALT, but this is an intellectual exercise.

Also, I know that the salt is of length 21 and consist of lowercase letters and digits. So there are 36^21 possibilities to enumerate if I just try brute force testing all of the possibilities, which is clearly unreasonable.


texts: If my server utilises an RSA based certificate, why does firefox think I am using Diffie Hellman?

texts:
I am not a beginner in crypto, but not that far from it, so please be gentle.

I look after a web server app that I generated the SSL certificate for, and I used an RSA public/private keypair.

When connecting to the web app via firefox 40.0.3, it doesn't let me, with Error code: ssl_error_weak_server_ephemeral_dh_key

As I understood it using RSA or Diffie Hellman for session key exchange did similar things, but were entirely separate.

So how can I have Diffie Hellman vulnerabilities if I am not using it?

P.S. The web app is HP Network Automation 9.20, which is based on jboss.

Sorry if this is the wrong exchange, the other questions I see look more pure maths based than applied crypto.


texts: Quantative criteria to measure confusion and diffusion property of encryption algorithm

texts:
I am new to crypto subject.
I am studying the confusion and diffusion in AES etc.
Is there any general quantitative method to measure these properties.
Let us say Algorithm A produces cipher having more confusion/diffusion with respect to Algorithm B. How can one quantify these criteria? Any specific Model or formula for same?


texts: Proving that a function is not a OWF (One-way-function)

texts:
I was trying to prove that a given function is not a one way function and I was not sure how to do it because maybe I had unclear what a one way function was (OWF).

The definition that I have for a OWF is the following:

Easy to compute for all inputs: for all PPT A (probabilistic polynomial time algorithms), A(x) = f(x) $\forall x$

But hard to invert:

$$Pr[B(1^k, f(x)) = x' \ s.t. \ f(x) = f(x')] < neg(k)$$

for all probabilistic polynomial time adversaries.

However, the part that I was unclear about is, if EVERY f(x) has to be hard to invert, or if its ok for it to be easy to invert say for only and only two values (say f(x) and f($\neg x$) ). I guess I was a little confused about the "invertibility" part of the definition. Is there a problem if its easy to invert for some inputs?

Thanks in advance!


texts: Can the SHA256 hashes of consecutive integers be attacked?

texts:
Suppose that the attacker knows the SHA256 values of integers $n, n+1, n+2 ... n+k$.

$n$ is sufficiently big, so we do not expect to be able to brute force $n$ just by $\operatorname{SHA256}(n)$ itself. $k$ is very small compared to $n$.

Is there risk that he can calculate $n$ in reasonable time?


texts: Is there a way to make RC4 (ARCFOUR) secure, or is it completely broken?

texts:
I need a method to authenticate a process with another in order to establish interprocess communication between them, to prevent malicious processes from trying to hook onto the system. Currently I just send a password in plaintext between the two processes and the host process just performs a string comparison with its copy of the password, and will disconnect the connecting process if they don't match. It was fine when I was limited to connecting each process on localhost, but obviously this is not secure if someone just happens to have access to a network between each process and could sniff the packets. Do note that I only care about encryption for the password exchange and I don't really need it to secure the communication.

So basically I need a encryption algorithm that doesn't need to protect its contents well but does need to protect its key, and needs to be as fast as possible with minimal RAM usage and I/O overhead. Yes, data exchange is more CPU-bound than I/O bound since the two processes will be doing loads of calculations and they most likely will be connecting through localhost. Now, I came across RC4, which has a throughput of over twice that of AES-128, but it is evident that it has some weaknesses and I have a lot of questions about how to implement it in a secure way.

Well first question - it's in the title. Is RC4 completely broken and should be avoided? I hear a lot of "it is secure if properly used" and then a lot of "use of RC4 is discouraged."

I was planning to keep the plaintext password on both processes and have them SHA-224 hashed, and concatenate the hash with a 32-bit IV as a 256-bit key for RC4. Are there any security risks with this approach? Perhaps I could then hash the concatenated IV and hashed password with SHA-256? I'm well aware that WEP was cracked because it used a 24-bit IV, but a 32-bit IV has over four billion more unique values. Should I avoid incrementing the IV after each packet like WEP?

And when it comes to RC4-drop[n], what is a reasonable value for n? 256, 512, 768 bytes? How would you implement drop n on a library whose only public operation is encrypting a byte array - pass a byte array of length n after the engine is initialized with the key? Would that mean you would have to basically process n empty bytes after every time you change the IV (which happens after every packet)?

Sources: http://www.rsa.com/rsalabs/node.asp?id=2009

EDIT: after reading all these excellent responses, I realized how ignorant I sounded about the whole subject. I had no experience with cryptography before this day, and I only was able to read about RC4's risks from the limited Google results that I could barely follow. thank you to everyone who has been patient with me!

Correct me if I'm wrong, but I believe a better solution is to either use AES (which is not slower because re-keying RC4 after each packet is expensive) or an universal message authentication code. I can easily work with AES, but my understanding of MAC is a bit shaky. An IV is only secure if the update sequence is randomized and unpredictable, meaning I would have to send a 128 bit IV for every message that is sent, which can add a 400% overhead to the short, 4 byte packets that are commonly sent by my application. HMAC can add more than twice that amount if SHA-256 is used. I am going to have to investigate this matter further.


texts:
Consider everyone's favourite pseudo random number generator, RANDU where V is the output of any successive iteration.

$$ V_{j+1} = 65539 \cdot V_j \; mod \; 2^{31} $$

I've purposefully  chosen RANDU because it's not so good a PRNG, but works well in my example. Such linear congruential generators can be easily inverted to recover the state, and hence predict all future values.

Now let's replace the 65539 constant with a normal probability distribution, A. And let's define A as:-

A = NORMAL(μ =~ 65538.5, σ =~ 998) where the values are rough approximations obtained by mysterious empirical means. An integer rounding operation happens somewhere.  It's my cunning model of a diode that might be used for an  entropy source inside a TRNG. A represents the Avalanche Effect inside certain diodes, and looks like a children's Galton board as electrons tumble through the semiconductor material.

Lastly,  assume we have a mega quantum computer slurping up all the output from this random generator.  Are we able to predict the future output, given enough samples? And if not, can we say anything at all about the security of this generator? Would it now be a true unpredictable entropy source, or would we able  to get almost perfect estimates of the future output sequence?

This is a highly theoretical question, but I'm trying to get a perspective on what may /may not be possible in derandomising entropy sources given quantum computers.  I emphasise derandomising, as this and equivalent terms have previously been used in discussions of classical entropy sources for true random number generation. There is a long list of Similar Questions on my screen suggesting the upcoming end of traditional randomness. Some will posit that if the quantum computer can form sufficient simultaneous equations, it can determine the internal state  of the diode via  ersatz linear cryptanalysis. This is my attempt at countering.

Even some at America's NIST say that only a quantum device can produce true randomness, and that everything else produced by classical physics is just not. They say:

  No device that relies on classical physical principles or operations can certify that its output is absolutely unpredictable.

News(?) to the UK government who regularly certify ERNIE running the country's national savings scheme. And he runs on diodes. Are NIST suggesting that he can be predicted, perhaps in the future with bigger computers?


texts: Is Poly1305 an information-theoretically secure MAC?

texts:
I have heard some people say that the Poly1305 authenticator is a "nuclear" MAC i.e. it is information-theoretically secure. After reading the paper I see it is based on the Wegman-Carter MAC which is supposedly the natural authentication pairing with the one-time pad cipher.

Is it true though that Poly1305 is really an information-theoretically secure MAC? Here is an excerpt from the paper:

  1 Introduction

  This paper introduces and analyzes Poly1305-AES, a state-of-the-art secret-key
  message-authentication code suitable for a wide variety of applications.

  Poly1305-AES computes a 16-byte authenticator Poly1305r(m, AESk(n)) of
  a variable-length message m, using a 16-byte AES key k, a 16-byte additional
  key r, and a 16-byte nonce n. Section 2 of this paper presents the complete definition of Poly1305-AES.

  Poly1305-AES has several useful features:

  Guaranteed security if AES is secure. The security gap is small, even
  for long-term keys; the only way for an attacker to break Poly1305-AES is
  to break AES. Assume, for example, that messages are packets up to 1024
  bytes; that the attacker sees 264 messages authenticated under a Poly1305-AES
  key; that the attacker attempts a whopping 275 forgeries; and that the
  attacker cannot break AES with a probability above δ. Then, with probability
  at least 0.999999−δ, all of the 275 forgeries are rejected.
  Cipher replaceability. If anything does go wrong with AES, users can
  switch from Poly1305-AES to Poly1305-AnotherFunction, with an identical
  security guarantee. All the effort invested in the non-AES part of Poly1305-AES
  can be reused; the non-AES part of Poly1305-AES cannot be broken.

So it appears Poly1305 is only secure if AES is secure. So in theory if I do not like AES I can swap it out for something else like ChaCha20 (as many have done e.g. SSH and TLS 1.3). However then the authentication is still only as secure as ChaCha20 which in itself is not information-theoretically secure. So then, what if I need an authentication tag that will remain secure for a long period of time (100+ years) and even resist cryptanalysis indefinitely?

I understand the point of the Poly1305 is to re-use the keys for many messages as long as the nonce changes each time. However, assume a hypothetical system which has many one-time pads generated by a HWRNG and they are pre-shared between two parties via a physical exchange. The key material for each message is divided up as follows:

92 byte key for encrypting the 92 byte message using XOR $\oplus$
16 byte Poly1305 encryption key $k$ (formerly the AES key)
16 byte Poly1305 additional key $r$
16 byte Poly1305 nonce $n$

So in this scenario the $k$, $r$ and $n$ are unique and truly random per message sent. So per one-time pad encrypted and authenticated message it uses up 140 bytes of true random data. Now given that this construction creates the Poly1305 tag:

Poly1305$_r$($m$, AES$_k$($n$))

Can the AES$_k$($n$) portion be simply replaced with $k$ $\oplus$ $n$? In other words, encrypt the nonce with a one-time pad. Will this remain theoretically secure indefinitely?


texts: Why is it better to have the private key as the multiplicative inverse mod phi(n) in RSA?

texts:
I'm studying the RSA algorithm and the theory says to select $d$ to be the multiplicative inverse of.

$$
e \mod \phi(n)
$$

If we take this approach I know that it is important that $e$ and  $\phi(n)$ are coprime.

Why is this "better" as opposed to say the following equation where $e$ is still selected as a coprime to $\phi(n)$:

$$
 d = \frac{\phi(n) + 1}{e}
$$

I would like to have a deep explanation. I do not have formal math training, so any links to help understand the answer is very much appreciated.


texts: Converting a 5-bit s-box to its bit-sliced format

texts:
I'm currently trying to convert a 5-bit sbox (the one from this cipher: http://primates.ae/wp-content/uploads/primatesv1.02.pdf) to its bit-sliced format (i.e. to a boolean network).

Most papers only address techniques for converting up to 4-bit s-boxes into their bitsliced format.

I have done some work trying to brute-force my way to the results, as a 5-bit s-box does not seem as much, this however still proved tricky, as their is in the end an infinite possibility og AND, NOT, OR and XOR that you can do on the 5 input bits... Is there any accepted/known way of doing this, or does it come down to trying to bruteforce different combinations till a matching one is found? (I hope not, as I have no guarantee on it being the optimal then).

I have considered trying to make truth tables and synthesize the logic network from them. I'm not sure this is the way to go though.


texts: What is a proof of data possession that accounts for fake mirrors?

texts:
Alice pays Bob $5/month to host a gigantic file for her. She wants to
  occasionally verify that Bob is actually hosting the file. To do this,
  she selects random blocks from the file, and challenges Bob to hash
  those same blocks with her chosen salt. The digests should match.

This is a solved problem because Bob won't know what blocks in the file Alice will audit next. But what can be done if Bob decides to host in multiple places?

  Bob proposes to Alice that he can host the file on four more hosts,
  for a total of $25/month. Alice agrees, and continues using her old
  audit method. But Bob never actually hosted the files in more than one
  place; every time Alice audited a host without the file, that host
  asked Bob's main host for the answers, and sent them to Alice.


texts:
I need to design a system where there is a secure device (a.k.a. HW wallet), with the following functionality:

Deterministic key generation for key parameters (speaking simply: key ID).
Never expose/compromise secret keys.
Participate in signing schemes, such as Schnorr, Bulletproof.
Support multisignatures.
Should have simple design, limited memory capabilites, etc.

Now, all our cryptographic schemes follow more-or-less the same ritual: Prover generates a nonce, exposes its image, receives a challenge, and then exposes the pre-image, which is in fact a blinded secret key. And, of course, we're using the Random Oracle Model (a.k.a. Fiat–Shamir heuristic) to generate challenges.

In order to guarantee (2), there is an assumption that the Prover must never answer to different challenges for the same nonce. And this is absolutely vital!

When used in a standard signature protocol, there is no problem. Once the nonce is generated and revealed - the challenge can also be generated in a deterministic way by the wallet itself. So that the whole signing process is atomic.

For multisignatures, however, this is not the case. There are 2 (or more in case of Bulletproof) iterations, where first all the nonce-dependent images are revealed by all the parties, aggregated, and then during the next iteration the preimages should be revealed.

And this is the problem actually. Ideally I'd like the HW wallet to be stateless, just generate everything when needed in a deterministic way. But, as we see, in a multisignatures challenges just can't be calculated from visible data, hence the HW wallet may easily be cheated.
Also the multi-signature ritual may be time consuming, during which I'd like the HW to be able to operate normally.

The best solution I could think about is adding some amount of memory slots dedicated to mutlisignatures.
The caller would allocate the slot number for each multisignature in progress (in case there are several such). It would generate a unique nonce (i.e. not deterministic from the being-signed message). Then to finalize the signature the caller would supply the challenge and the slot number, and the HW wallet would reveal the expected preimage and then immediately erase the contents of this slot.

So this seems to solve the problem, but, naturally, has disadvantages. The device with state is obviously more complex, which isn't good for security. Limited number of ongoing signatures isn't an advantage either. The device should have a writable non-volatile memory, which is presumable an attack target, and so on.

So, my question is: are there alternatives, which assume stateless HW wallet? Is there a ritual where we can convince it that we don't use different challenges for the same nonce, perhaps in expense of more iterations?


texts: How to securely encrypt/decrypt data with a maximum chunk size?

texts:
I am aware of the different modes so that a "raw" block cipher such as AES (ECB) can be used to encrypt more than a single block of data (CBC, OFB, CTR, etc) and modes such as AES-GCM which provide a full AEAD implementation.
When looking at the known limitations for Amazon AWS CloudHSM, there is a maximum data size restriction for AES-GCM (https://docs.aws.amazon.com/cloudhsm/latest/userguide/ki-pkcs11-sdk.html#ki-pkcs11-8):

Issue: Buffers for the C_Encrypt and C_Decrypt API operations cannot exceed 16 KB when using the CKM_AES_GCM mechanism
You cannot use the CKM_AES_GCM mechanism to encrypt data larger than 16 KB
You can use an alternative mechanism such as CKM_AES_CBC or you can divide your data into pieces and encrypt each piece individually. You must manage the division of your data and subsequent encryption. AWS CloudHSM does not perform multipart AES-GCM encryption for you. Note that FIPS requires that the initialization vector (IV) for AES-GCM be generated on the HSM. Therefore, the IV for each piece of your AES-GCM encrypted data will be different.

This question is about how to securely "manage the division of your data and subsequent encryption".
Are there any well-known, documented standards for working with such "big blocks", creating an AEAD mode from a "unit" of AES-GCM which can only encrypt/decrypt 16KB at a time? It would obviously need to protect against truncation of data (if ciphertext was N "big blocks" and only the first M blocks given to decrypt operation, this should fail) and substitution of blocks from a different ciphertext encrypted with the same key should fail too. And are there other potential concerns?
It "feels like" the same class of problem going from ECB → CBC/OFB, but obviously, we want authenticated encryption.
Tweakable block ciphers are used for disk encryption, but the substitution of blocks (same block number/rollback) isn't really protected against there.
Clearly appending the last 128 bits of the ciphertext of the first "big block" to the associated data going into the encryption of the second "big block" would prevent substitution of blocks from another ciphertext, but how to prevent truncation attacks? Would it be sufficient to append the overall data length to the associated data for the first "big block"?
I'd ideally rather not switch to CBC + HMAC (especially as the CloudHSM hash of > 16KB data ends up being done locally!)
But: is this already a solved problem? (Ideally with an IND-CCA2 proof!)


texts:
I don't have much formal background, and I could not find a suitable explanation for this after searching on Google/Wikipedia.

What is the meaning of the term "language" as used in cryptographic protocols?

Sample sentence from a recent paper:

  Every language in BQP admits a classical-verifier, quantum-prover zero-knowledge argument system which is sound against quantum polynomial-time provers and zero-knowledge for classical(and quantum) polynomial-time verifiers.


texts: Homomorphic Encryption for Deep Learning

texts:
I'm interested in the two following processes:

Perform deep learning on homomorphic encrypted data

Perform deep learning predictions with a homomorphic encrypted model on unencrypted data. By this, I mean encrypting weights of a deep learning model, sending them to the data owner, and performing an encrypted prediction. The owner of the data will return me the encrypted prediction. See, for instance, this blog post for an example with logistic regression.
I'm wondering if it's possible to do deep learning (with many hidden layers) with PHE (partially homomorphic encryption, e.g., Paillier) or if I need a FHE (fully homomorphic encryption).

References are welcome!


texts: Designing a simple challenge-response symmetric mutual authentication protocol

texts:
I am designing a protocol that 2 devices will use to mutually authenticate over an unreliable, unsecure channel. The system must be fast and low-power, so symmetric cryptography is a requirement. I was thinking of using a challenge-response protocol, but cannot find existing ones that offer mutual authentication and use keys instead of passwords; so I decided to design my own and wanted your opinion.
Let Alice and Bob be 2 parties, with their respective identities encoded as $id_A$ and $id_B$. They share a symmetric key $K$ of 128 bits or more. Note: it's a key, not a password. $n_A, n_B$ are true-random nonces. $hash$ is a secure one-way function without length-extension vulnerabilities, like SHA3 or HMAC-SHA256.
The "simple version" of the protocol would be this one:

$A \rightarrow B: id_A, n_A$ --- challenge
$B \rightarrow A: id_B, n_B, hash(K||n_A)$ --- response and 2nd challenge
$A \rightarrow B: hash(K||n_B)$ --- 2nd response

I also have a "hardened version" like the following, where I'm adding better MACs, binding between messages and hardcoded values (1, 2 and 3) in the hashes to enforce a message order and difference between them.

$A \rightarrow B: id_A, n_A, hash(K||1||id_A||n_A)$ --- authenticated challenge
$B \rightarrow A: id_B, n_B, hash(K||2||id_A||n_A||id_B||n_B)$ -- response and authenticated 2nd challenge
$A \rightarrow B: hash(K||3||id_A||n_A||id_B||n_B)$ --- response to 2nd challenge

My question is: which one should I use? Is the "simple" enough? Is the "hardened" overengineered? Is there a better protocol out there with this level of simplicity?


texts: Is there a specification for the "BEGIN RSA PRIVATE KEY" format?

texts:
Until now I didn't find a specification (RFC or similar) for the file format that uses the BEGIN RSA PRIVATE KEY prefix and END RSA PRIVATE KEY suffix. Where is it defined? Is there an official name for it? It seems to be at least related to the series of PEM RFCs.

I am looking for reference information about the details of whitespace handling,
base64 details, joining of different keys in one file etc..

This question is NOT about the ASN encoding of the payload.


texts: Creating own ciphertext after a padding oracle attack?

texts:
I've written a script that breaks a cipher text based on a padding oracle for an assignment, but was wondering how I would continue on to create my own cipher text with any plain text I desired?

Someone on the class forum mentioned XORing the intermediate step (or the $D(C_i)$ before XOR with $C_{i-1}$) (taken from the process of breaking the original cipher text) with the plain text of my choice to generate $C_{i-1}$. I don't see how this works, or if I misunderstood what the poster was XORing together. I see how $D(C_i) \oplus C_{i-1} = P_i$, but not sure how you can use your own plain text in that way.

I'm looking for hints on how to approach this, or a clarification on the 2nd paragraph.


texts:
Given $p$ and $q$ prime with $q = \frac{p-1}{2}$.
$h \equiv g^{a} \pmod{p}$ with $g$ and $h$ primitive roots modulo $p$ and $a$ unknown.
Hash function: $H(m) = g^{x}h^{y} \mod{p}$, where $0 \leq x,y \leq q-1$ such that $m = x + yq$.
In steps I have to show that $H$ is strong collision resistance if it is unfeasible to find discrete logaritmen modulo $p$.
Suppose $H(m) = H(m')$ for $m = m'$ with $m,m' < q^{2}$
And $m = x + yq$, $m' = x' + y'q$. I already showed that we then have this congruence: $a(y-y') \equiv x' - x \pmod{p-1}$. And this congruence has exactly $d$ solutions if $d = ggd(y - y', p-1)$.
Now I have to show that: $\vert{y-y'}\vert \leq q-1$.
And I really have no idea how to show this.
Next we show that $H$ is also a one-way function: Assume that there exists a fast algorithm $A$ to find a message $m$ from a hash value $y = H(m)$. Choose $m$ arbitrary, determine $y = H(m)$ and from that $m' = A(H(m))$. Assume that $A$ determines every $m$ from $H(m)=y$ with the same chance. Show that: the chance that $m \neq m'$ is on average $1 - \frac{2}{q}$.
So in other words I have to show: the chance that $m = m'$ is on average $\frac{2}{q}$.
And I know that $m < q^{2}$ and $H(m) \leq  2q$.
I don't see why this chance must be $\frac{2}{q}$.


texts: Does this PBKDF2-SHA1 payload hint at a cryptographic security issue?

texts:
Blockchain first 16 encrypted bytes, IV, and iter_count – all encoded in Base64:

Yms6xqrzCfFsQadVZ5gQonMtnQAAAAAAAAAAAAAAAAAAAAAQJwAA69tYNg==

Does it looks like “correct” PBKDF2-SHA1 or does AAAAAA… indicate that something was broken?

During the login attemp to blockchain.info I get a response with a base64-encoded payload, that in fact authorizes my encrypted PBKDF2-SHA1 wallet. I have had no success trying to decrypt this (original BCI server/utils). I am absolutely sure that I’m using the correct passphrase (it's written on paper and was used successfully in 2016 and earlier 2017 before application update).

Anyway, the reason I’m asking if this looks like something suspicious and/or broken is that during my other analysis projects I never met a Base64 payload starting with 21 "A":

<Buffer 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 c6 aa f3 09 f1 6c 41 a7 55 67 98 10 a2 73 2d 9d f0 b0 39 32 ec e9 96 22 ab 2f 76 ff 6b 2b c5 c9 c1 5a ... >

When I compare that to my other newly created accounts, this seems to be a bit weird, since all other accounts produce payloads with a more random sequence at start… for example 3pV6yxnoKYKjj….

Do those 21 As in that one payload (related to one specific account) point to a security or cryptographic problem?


texts:
Context
I recently came across a video on the net showing the process of key exchange in Diffie Hellmann.
Alice and Bob want to communicate. Eve is the (wo)man in the middle.
This video is the basis of my question
http://youtu.be/YEBfamv-_do?t=6m22s
Question
Alice sends the modulo and the prefix to bob. Eve gets that.
What prevents Eve to have a giant table of all the calculations possible given a prefix and a modulo and the public value and intersect thos possibilities with the public value from bob ?
Yes the table would be very big but you can then iterate over the intersecting possibilities and try the numbers on the message up to the point to get something right.
i may miss something, but it is not that hard, even with very big numbers.
So what did I miss ?
Thanks


texts: Alternatives to Diffie Hellman and other Public Key Exchange schemes

texts:
I've been researching public key exchange algorithms. I am not a cryptography expert but I have a couple of questions on the subject that I can't resolve on my own.

Strictly concerning public key exchange methods, do many of these ideas exist? Dozens? Hundreds? I'm trying to understand if many exist that accomplish the idea of private key building in a public "space". I am aware that each would have various strengths and weaknesses, etc. Though I've found a handful of these ideas (Diffie, RSA) it is not clear to me if they are "rare" in a mathematical sense.
Would commercial value exist in creating a new method? To this end, is it a problem being pursued in the world today? (Classical computing - I am aware quantum is an academic direction at this time)

I realize that second question is maybe opinion based, and so I would just really appreciate any thoughts on the subject.


texts:
I tried to make a script to encode a txt with the autokey cipher. From my poor understanding of the cipher I created another cipher which has nothing to do with autokey:

first I encoded a txt with a key which give me a result as long as the original txt -Vigenère cipher used
then I encoded the original txt with first result -Vigenère cipher

How can I get the original txt from the original key?!

$$\begin{array}{}
\text{txt} &+ &\text{key} &\to &\text{etxt}\\
\text{txt} &+ &\text{etxt} &\to &\text{final result}
\end{array}
$$

Editor's note: the + stands for vigenere cipher algorithm


texts: Is this a good implementation of digital signature with timestamp?

texts:
Is this a good practice ?.
How good or bad is this compared to appending a timestamp to the actual data and hashing it as represented below.
Signature = sign(sha256( File + Timestamp ))


texts: with RSA encryption, how do I find the md5sum of the private key from the public key?

texts:
This is a purely mathematical question on RSA encryption.

Having $e$ as the public key exponent and $n$ the modulus of a public key. Can I recover the md5sum of the private key $d$ (inverse of $d$ according to the modulus.)

Thanks for your help.


texts: Binary format of encrypted PGP private key?

texts:
Short Version of the Question:
I would like to remove any predictable information from an encrypted private keys binary representation. Does anyone have a hint where the binary format for encrypted GnuPG private keys (.gpg) is documented?

Longer Explanatory Version of the Question:
Hey guys,
 basically I'm trying to write a program which hides the encrypted private key in a random user-selectable medium (e.g. JPEG image) using steganography.

I'm assuming the attacker knows the kind of medium, but not the specific file, it would be rather useless if the private key doesn't appear completely random.

Basically, I would like to remove any predictable information for example on the type of encryption (maybe AES-128-CBC) used, and reconstruct the key after retrieval from the medium. A wrongly chosen medium should deliver a seemingly valid private key. So the attacker would have to brute-force all possible passphrases for all possible storage mediums.

Is that generally a stupid and futile endeavor?

From the encrypted keys I looked at and the information I collected I would guess that the key is concatenated like "SALT + EncryptedByteStream + InformationOnEncryptionAlgorithm". Does anyone have a hint where to find that? I'm a little tired from digging haphazardly through source code right now.


texts: If a private key decrypts what its public key encrypts, can the public key conversely decrypt what its private key encrypts?

texts:
Whilst studying the material for the CCNAS exam, I have encountered something on the cryptographic systems chapter that I am not sure about. Cisco Netacad states that "Asymmetric algorithms use two keys: a public key and a private key. Both keys are capable of the encryption process, but the complementary matched key is required for decryption. For example, if a public key encrypts the data, the matching private key decrypts the data. The opposite is also true. If a private key encrypts the data, the corresponding public key decrypts the data.".

Can someone clarify whether the last statement made is correct; that if the private key encrypts the data then the corresponding public key decrypts the data. As far as I know this is not true?

Any clarification here would be appreciated!


texts: Chosen Ciphertext Attack with a theoretical decryption machine

texts:
Say we have an encryption algorithm that encrypts data blocks of 128 bits size, and makes them cipher blocks $C = E(P)$ without chaining.

Also assume there is a linearity rule for XOR: For every pair of plaintext blocks $P_1$, $P_2$ there is: $E(P_1 \oplus P_2) = E(P_1) \oplus E(P_2)$ for all patterns. Encryption is done using a specific secret key.

Now assume the attacker has a decryption machine, and can do Chosen Cipertext Attacks:
He can pick a set of 128 cipher blocks say ${C_j}$, and the decryption machine gives him the matching ${P_j}$ Plaintext blocks.

I am wondering, how to prove that he can decipher ANY cipher block without knowledge of the secret key?


texts: Chosen-Ciphertext Attack on Rabin: Factorize n

texts: At the end of this Wikipedia section, you can see that $$\gcd(|r-s|,n)=q$$ or $$\gcd(|r-s|,n)=p$$ holds. I don't understand why.


texts: MD5 hash: retrieve an element of a source string

texts:
Suppose you have a string, precisely an MD5 hash string, which basically it is computed in the following way:

"element1:element2:element3"

So, in order to get the hash (MD5 hash) you can issue the command:

echo -en "element1:element2:element3" | md5sum

MD5_hash_output

Given that MD5 is a one-way function (it is now considered broken, no more secure...etc), think that you want to retrieve element3 and you know:

element1
element2
MD5_hash_output

Is my reasoning correct if I say:

you can get element3 if there's a rainbow table which includes MD5_hash_output
you can get element3 if it is guessable (easy to guess: a default device password ...for instance)

It may sound a trivial question...the answer is, of course, that MD5 is a one-way cryptographic function..but I just wanted to have some other different opinions


texts: Securely send public key from client to server in RSA?

texts:
I have a client and a server communicating with messages encrypted using RSA.

Initially, the client knows server's public key, but the server does not know the client's public key. Is it possible to securely receive the client's public key over a network (i.e. without a man in the middle intercepting and changing the public key the client is trying to send with their own).

I was thinking that the client can generate a random secret and then send it to the server using the server's public key for encryption. Then the server can decrypt the secret, use it as a key for AES, and echo it back (this time encrypted with AES). The client then verifies that the decrypted secret is the same as the one it sent.

I'm scratching my head trying to figure out if this is secure, and how I should incorporate hashing to verify the integrity of the data.. Would this even work?


texts: Rekeying procedure - how "far" from bijection?

texts:
Imagine that I want to change the key in order to prevent side-channel attacks on key and to protect against big load on the one key. It is desirable that key change procedure would look like random function from key space to itself.

I want to consider the function of the type:
$$ F : KeySpace \to KeySpace$$
$$ F(k) = E_k(k) $$
E is my block cipher, for example we can assume that encryption is in ECB mode.

I understand that this is maybe not the best decision: there are numerous of provable secure algos, but now I want to consider this one.

The natural question is: does it look like random function and is it really bijective? If not, then what is the size of this compressed range of the function? Are there any estimates?


texts:
I'd like to implement a "Product Registration" scheme into my software where upon initial use, the User must enter a key to unlock it.

The key they enter is compared to their encrypted Username.
They would have to acquire the key from myself if they wished to use the software.
Their encrypted Username must be reasonably short so it's not too difficult for them to enter the key. They would however, only have to enter the key once.
(I'm aware this isn't actually how keys are issued)

What kind of encryption is appropriate for this?
(It needs to encrypt a string into letters and numbers only and be reasonably short).
There's no thought needed over decryption, since I'll only be comparing encrypted strings.

I'm basically looking for a cipher that produces the shortest code possible so that it's not tedious for the User to enter.
(Though still difficult to break)

Any suggestions?
Thanks!

(You needn't worry over the actual security.
I'm a noob programmer and all my software is free anyway)


texts: What does CA certs contains? public key of site or CA?

texts: I believe it contains public key but whose? the site like a bank or the certificate authority who has signed?


texts: How to break a 32 bit block cipher without key?

texts:
From what I know Skip32 is the only 32 bit block cipher and I heard its not secure. What do I do or which tool do I use to break a 32-bit block cipher?
I did search for this but all I find is attacks for DES(64 bit) and AES(128 bit) but none for Skip32.


texts:
If the 48-bit input to the S-box is 0xAAAAAAAAAAAA, what are the first four bits emitted by S-box 1?

Answer: 0110

I know that an S-Box takes n inputs and give m outputs and that n != m, but I really don't see how they got that answer.

Since a S-Box takes 3 bits and maps it to 2 bits how can you predict what AAA will be?