Reputation
369
Top tag
Next privilege 500 Rep.
Cast close & reopen votes
Badges
1 8
Impact
~3k people reached

  • 0 posts edited
  • 0 helpful flags
  • 19 votes cast
Feb
5
comment How fast would a polynomial time factoring algorithm compute?
@AlexandreYamajako I agree there are some super-polynomial and sub-exponential algorithms. They are usually $2^{\frac{n}{k}}$ for some constant $k$. How should I name them? Almost-exponential? (By the way, I am not sure if any algorithm harder than polynomial and easier than $2^{\frac{n}{k}}$.)
Feb
4
answered How fast would a polynomial time factoring algorithm compute?
Jan
22
comment Secure way to encrypt and decrypt a folder on Mac or Linux?
I was using the eCryptFS for about two years. It forks, but it has some caveats. First, it leaks some information about the structure (file count, file sizes etc.). Second, long file names aren't supported. This wasn't an issue for many cases, but Scala compiler generates sometimes too long filenames. Third, eCryptFS is poor on performance. While it might be OK for some particular use cases (including the Xeoncross's use case), switching to dm-crypt brought a significant performance gain. (But eCrypyFS might be more comfortable for some use cases.)
Jan
19
awarded  Popular Question
Jan
17
comment Is javascript RSA signing safe?
This hack however does not seem to mitigate some HyperThreading-related attacks. That is, another process running on the same physical core might see some variance in the performance depending on the plaintext or key used.
Jan
16
comment What kind of attack does the current brokenness of SHA-1 allow?
@tylo Surely it can make a confusion. In general, it should work as a valid upper bound. Having an upper bound is not "absolutely no meaning". We can't use it for claiming "this algorithm is that secure", but rather for claiming "this algorithm is at most that secure". I've used it in a modified form for rough and very informal comparison of two algorithms.
Jan
15
comment Hypothetical unknown cipher - security in obscurity?
The generic 128b block encryption function is a bijection from $2^{128}$ values to $2^{128}$ values, thus there are $2^{128}!$ such functions.
Jan
15
comment Hypothetical unknown cipher - security in obscurity?
You should never consider a cipher algorithm as perfectly secret. The algorithm was a human invention. While some human inventions are very strange, they might be more repeatable than you might think. Moreover, it is very hard to calculate its "entropy". Well, we might try to solve it by constructing a tweakable algorithm: you add some random data to generate an algorithm automatically. Wait, the random data works at best as a key for the algorithm…
Jan
15
comment Unbreakable code and mathematical impossibility
Good, but there is some inaccuracy. You can guess the probability from the context, so some messages are likely to have higher probability than others. However, the ciphertext does not give you more information than the length of the plaintext. Having the length of the plaintext, you can guess exactly the same.
Jan
15
comment What kind of attack does the current brokenness of SHA-1 allow?
More inaccuracy seems to come from the $2^{16}$ assumption. It is said to be generally much lower for Merkle–Damgård construction. Moreover, if a hash has some weakness, it can be even lower. It's actually the reason why I believe that good design has contributed for better security more than additional 32 bits.
Jan
15
comment What kind of attack does the current brokenness of SHA-1 allow?
USD might mot be the ideal unit for comparison, but it might be OK under some conditions. If you compare how many collisions you can achieve with $700,000$ USD provided that you don't reuse precomputed data across collisions, it seems OK for rough comparison. Using EC2 trial is thus not OK, but estimating a low price for MD5 collision ($$0.01 was probably overestimated) seems OK for rough comparison. Note that I've used the numbers that are available without too much effort.
Jan
14
answered Updating the secret key used for HMAC
Jan
14
comment What kind of attack does the current brokenness of SHA-1 allow?
@user2700751 If we accept the numbers $65,536$ and $70,000,000$, it would mean that additional 32 bits make it $65,536$ times harder, while better construction make it $1,000$ times harder. There are, however, various pitfalls, namely: 1. Cost of MD5 collision was very roughly guessed. 2. Additional 32 bits seem to have added much less security. (This seems to apply for all Merkle–Damgård constructions.) 3. MD5 is slightly (but negligibly for there purposes) faster. I guess that better design has added more security than additional 32 bits, but I am not sure.
Jan
14
comment What kind of attack does the current brokenness of SHA-1 allow?
@user2700751: Hmm… Just some intuition: The additional 32 bits would likely make it harder just $2^{16}$ times, i.e. $65,536$ times, because of birthday paradox. The number $65,536$ however applies for brute-force attacks. Since there are more efficient attacks, the number is likely to be smaller. Generating a SHA1 collision is said to cost $700,000 USD by 2015 (see casecurity.org/2014/11/18/…). Generationg MD5 collision is almost free, say $$0.01. That would mean it is 70,000,000 times harder to find a SHA1 collision than MD5 collision.
Jan
14
comment What kind of attack does the current brokenness of SHA-1 allow?
Added a note about Merkle–Damgård construction.
Jan
14
revised What kind of attack does the current brokenness of SHA-1 allow?
Added a note about Merkle–Damgård construction
Jan
14
answered What kind of attack does the current brokenness of SHA-1 allow?
Jan
14
answered Programming language for modular arithmetic over large numbers
Jan
10
answered Question about key verification
Jan
10
answered Remove padding (CBC) from decrypted text