Kangaroo vs. keyhunt BSGS

[citb0in]

Hi all,

to what extent can the performance and the hit probability of these two tools be compared and what significance do they then have?

For example:

- we run Kangaroo in multi-GPU mode on several modern GPUs and achieve a displayed speed of 15 GKey/s

- we run keyhunt in BSGS mode on 8 CPU threads with about 16GB RAM allocation and get about 80 PKey/s.

Is Kangaroo with multi-GPU usage more advantageous and more likely to get a hit, even though keyhunt with CPU usage in BSGS can process 80 PKey/s?

From this numerical example, one would think that keyhunt with the 80 PKey/s would have to be worlds better. But is that the case or is it not possible to compare this at all and the given speed rates are completely useless for the comparison?

[_Counselor]

These are completely different algorithms and it is incorrect to compare them by the numbers shown. A properly tuned kangaroo will always run faster than BSGS.

However, the main difference is that if the BSGS did not find the key and finished work, then you can be sure that the key is not in the given interval. Kangaroo is a probabilistic algorithm, and you cannot be sure that there is no key in interval, even if the kangaroo has completed the estimated number of operations.

[PawGo]

However, the main difference is that if the BSGS did not find the key and finished work, then you can be sure that the key is not in the given interval. Kangaroo is a probabilistic algorithm, and you cannot be sure that there is no key in interval, even if the kangaroo has completed the estimated number of operations.

That's true, but:
1) I would rather say the biggest difference is in resources needed, as BSGS requires much more memory
2) Kangaroo is "probabilistic", but with a big enough amount of work done, the chances for a final result are very close to 100%. That's well described on JLP program's page.

[citb0in]

Thanks for your replies so far. So, as already suspected, no direct comparison is possible.

If you could only use one of these two rigs, would you decide for the long-term use of Kangaroo or rather Keyhunt/BSGS ? Both examples are running on the same puzzle

Kangaroo:

15600 MKey/s, Average 3.6y

Keyhunt/BSGS:

176 PKey/s

? how would you decide, which way to go ?

[NotATether]

Kangaroo:

15600 MKey/s, Average 3.6y

Keyhunt/BSGS:

176 PKey/s

? how would you decide, which way to go ?

With that kind of speed, people would've solved a ton of puzzles with keyhunt by now, but my suspicion is that it searches in too many wrong ranges, and that could be why its hit rate is not so successful.

[citb0in]

is there anything I can do to mitigate this? AlbertoBSD (author of keyhunt) explains the details about speed rate measurement HERE.

[NotATether]

is there anything I can do to mitigate this? AlbertoBSD (author of keyhunt) explains the details about speed rate measurement HERE.

Considering that in most other brute-force types, even a couple MKey/s can break small ranges, I have a feeling that the speed needs to be deflated by 100,000x in order to make a fair comparison with the other algos.

Show me a CPU capable of 10 Petahertz/second and I will show you a ton of hacked websites with broken TLS ciphers.

[citb0in]

Show me a CPU capable of 10 Petahertz/second and I will show you a ton of hacked websites with broken TLS ciphers.

  absolutely agree!!

[SoulTrippin]

Hi,
I know this is an old thread but I was wondering what GPU you are getting 15.6 GK/s with?
Is there a current list of GPUs w/ associated Kangaroo key speeds somewhere?

Thanks!

Thanks for your replies so far. So, as already suspected, no direct comparison is possible.

If you could only use one of these two rigs, would you decide for the long-term use of Kangaroo or rather Keyhunt/BSGS ? Both examples are running on the same puzzle

Kangaroo:

15600 MKey/s, Average 3.6y

Keyhunt/BSGS:

176 PKey/s

? how would you decide, which way to go ?

[3dmlib]

How much RAM needed for BSGS algorithm to solve 130-bit puzzle?

[Baskentliia]

How much RAM needed for BSGS algorithm to solve 130-bit puzzle?

First of all, luck, but it requires 1000s of terabytes, yes, you heard right, thousands of terabytes.
1.5 terabytes= 60 Exakeys =very low
Understand Me!