-snip-
Imagine a big bag full of green beans and only one red bean (the private key we're looking for). If I pick a random bean blindly from the bag and throw it back if it is not the red one, every bean I pick will have the same incredibly low probability of being the red one. And for each pick, the chance of getting the red one will be the same as taking the one I threw back before... So I might end up scanning a lot more keys than the size of the range before I find the private key.
So even if I count the number of beans I test, I have no guarantee that after testing as many beans as there are in the bag, there will be no red bean. Maybe I was just unlucky and didn't pick it.
Any constructive thoughts/opinions on this?
I don't think anyone searches for a key this way. Usually, if you want to search randomly, the entire range is divided into small subranges. These subranges are entered into the database. And each time after a random selection of a subrange from all the remaining ones, it is removed from the queue and does not participate in the future. Thus, green beans do not return to the bag. Hi,
Lately I was wondering if it is possible to modify JLPKangaroo_OW_OT to write DP's on SSD M.2 NVMe instead of RAM? Do You have some experience or theoretical knowledge about such an issue?
I know that RAM is something different than SSD, but concerning that main task in Kangaroo is to caclucate points, find DP's and search for colision, is there a chance to store DP's on NVMe SSD without losing performance?
Best Regards
Damian
For JLP you can try using client/server. The DPs will be saved and sent to the server, where they will be merged into 1 file. Or if you don't care what software to use, you can try Etarkangaroo where can save DPs after any period of time without losing much in performance. When saving, they merge. |
|
|
|
Please report speed for other cards, for old cards speedup is up to 40%.
Thanks! 1660Super 930-948Mkey/s |
|
|
|
|
@RetiredCoder I want to admit that unfortunately I did not win mini game #130, I just followed your explanations and found the key #130 0x33e7665705359f04f28b88cf897c603c9
|
|
|
|
|
r1_1 = 02de97092bfb7c02148a827b4f8b62db1e189a739c77815799df5e6fb35ae88a1f
r2_1 = 02838db77b981db321faf527a830461cfda01aed50d85c345a7b0a8f4e5e4fd3fc
delta = 031e283a9ebc4c50b0a93f27d411e69d0a97aad2a6d4ae26f5725f8b55fb5176f5
delta _k = 0xfffffffffffffffffffffffffffffffebaaedce6af487e246f4eac90b714b3bd
N- delta _k = 0x22175083b1fc19218d84
r1_2= 03de97092bfb7c02148a827b4f8b62db1e189a739c77815799df5e6fb35ae88a1f
r2_2= 03838db77b981db321faf527a830461cfda01aed50d85c345a7b0a8f4e5e4fd3fc
delta = 021e283a9ebc4c50b0a93f27d411e69d0a97aad2a6d4ae26f5725f8b55fb5176f5
delta _k = 0x22175083b1fc19218d84
PK = 33e7665705359f04f28b88cf897c603c9
P.S. @RetiredCoder thanks for the game, it was very interesting, although difficult.
|
|
|
|
Yes, you should have some understanding of ECDSA signature vulnerabilities.
2 most common vulnerabilities are repetitions of K for the same private key and weak K We have only 2 signed messages and their signature r does not match, only the weak K remains. I checked 02/03838db77b981db321faf527a830461cfda01aed50d85c345a7b0a8f4e5e4fd3fc in the 80-bit range it is not there. sha256 from the message also does not reveal r, as well as double hashing. The rabbit hole is too deep. I'm tired)) |
|
|
|
|
The main vulnerability of signatures is the use of the same value of K, which gives the same value of r.
for the first message the values of r and s were:
r 0xde97092bfb7c02148a827b4f8b62db1e189a739c77815799df5e6fb35ae88a1f
s 0x3f4fa38bcbb17615446fabc6fbebceefbb7d052eca9ce136b3a4a67b7f0d4f42
for the second message the values of r and s were:
r 0x838db77b981db321faf527a830461cfda01aed50d85c345a7b0a8f4e5e4fd3fc
s 0x288da41a03e78a23e2ac277921e2d19d17717a27a10f1c6cca7fd5ba351a5fca
I don't see the same r values here, maybe I'm being stupid.
|
|
|
|
You say: I can currently squeeze out 6.2 Gk/s on a RTX 4090, but some users here claim they can obtain 8 Gk/s or more
RetiredCoder say: Note that I have not included all possible optimizations because it's public code and I want to keep it as simple/readable as possible.
Git RCKangaroo say: about 8GKeys/s on RTX 4090.
You say: NB regarding RCKangaroo - it runs 1.5x slower than my kernel.
How can this be understood? You were able to reach 12GKeys/s on RTX 4090? |
|
|
|
Did you make a mistake?
I use visual studio. Oh, sorry it is in file RCKangaroo.cpp line 99 (changed previous post) if (deviceProp.major < 6)
{
printf("GPU %d - not supported, skip\r\n", i);
continue;
}
I also made other changes, which is probably why the line numbers don't match. But you can easily find the lines you need, because I didn't add anything new, I just changed it. |
|
|
|
@Etar how did you do everything to make your GTX 1660 work? Can you tell me all the changes and show me them? Many thanks
file: RCGpuCore.cu line 285: u64* table = LDS + 8 * JMP_CNT + 16 * THREAD_X; file: RCKangaroo.cpp Line 99: if (deviceProp.major < 6) file: defs.h #define LDS_SIZE_A (64 * 1024) #define LDS_SIZE_B (64 * 1024) #define LDS_SIZE_C (64 * 1024) #define JMP_CNT 512 file: RCKangaroo.vcxproj line 118: <CodeGeneration>compute_75,sm_75;compute_75,sm_75</CodeGeneration> line 141: <CodeGeneration>compute_75,sm_75;compute_75,sm_75</CodeGeneration> CUDA devices: 1, CUDA driver/runtime: 12.6/12.1
GPU 0: NVIDIA GeForce GTX 1660 SUPER, 6.00 GB, 22 CUs, cap 7.5, PCI 1, L2 size: 1536 KB
Total GPUs for work: 1
MAIN MODE
Solving public key
X: 29C4574A4FD8C810B7E42A4B398882B381BCD85E40C6883712912D167C83E73A
Y: 0E02C3AFD79913AB0961C95F12498F36A72FFA35C93AF27CEE30010FA6B51C53
Offset: 0000000000000000000000000000000000000000001000000000000000000000
Solving point: Range 84 bits, DP 16, start...
SOTA method, estimated ops: 2^42.202, RAM for DPs: 3.062 GB. DP and GPU overheads not included!
Estimated DPs per kangaroo: 570.958.
GPU 0: allocated 772 MB, 135168 kangaroos.
GPUs started...
MAIN: Speed: 599 MKeys/s, Err: 0, DPs: 88K/77175K, Time: 0d:00h:00m:10s, Est: 0d:02h:20m:43s
|
|
|
|
That's why I don't want to support old cards: if I support them officially but not optimize you will blame me that they have bad speed. But feel free to modify/optimize sources for your hardware  I'll be honest, your kangaroo finds the key faster than mine or jlp. Yes, the speed shows less, but in the end it finds it much faster. Works even on 1660 super (~600Mkeys/s). Thanks for sharing. |
|
|
|
Honestly, I'm just a lazy developer. My program, Keyhunt, isn't even optimized for GPUs yet! After more than three years, it's still riddled with bugs and quirks. But hey, despite all that, it's currently the fastest Baby-Step Giant-Step (BSGS) implementation available for CPUs. Not bad for a hobby project, right?
I am also lazy and I made the fastest (for now) implementation of bsgs for gpu. The difference between us and him is that we let people use our developments and sources, but he does not. If everyone sits in their own world and does not share knowledge, then there will be no progress. And this applies not only to him, but to others as well. |
|
|
|
|
And what is the meaning of calculating K? As soon as you increase the number of kangaroos, your K will fly into space.
With 65536 kangaroos in the classic version K will be 3.07
And when using the GPU, K increases even more due to dp overhead, in this case you will easily reach k=10
Your experiment is purely laboratory conditions, in real life on the GPU, the number of kangaroos is huge.
|
|
|
|
1BY8GQbnueY How did you know it was 56 bit?
If you look at the RMD hash (739437bb3dd6d1 9 83e66629c5f08c70e52769371), you will see that for your combination 1BY8GQbnueY 14 hex numbers are used, plus one more digit from 4 to a. In total, this gives 2^56 bits. And how did you come to the conclusion that in the 66-bit range there are only 4 combinations? |
|
|
|
So I guess everyone learned the answer to the question I wrote before, How many 1BY8GQbnueY starts are there in our 67 bit range? The correct answer is 4.  I disagree with you. Firstly, puzzle #67 has a range width of 66 bits. The second is that 1BY8GQbnueY has a length of 56 bits and accordingly in the entire range of 66 bits there are approximately 1024 such combinations. |
|
|
|
What grid size are you using with the "original JLP Kangaroo version 1.7" in order to see it at 700 Mk/s on a GTX 1660S? Are you sure about that speed being real?
Cause with no code changes and using the 1.7 release tag, I can't go beyond 300 Mk/s (or rather, ~250 in reality, since stats display is kinda broken) on a card that is both newer and superior to that model. And looking at the nvcc compile stats, I have some doubts that it would even be capable to go at a triple speed, on an inferior card with 25% less CUDA cores.
You probably configured the grid incorrectly. The Nsight shows that 4 blocks are working simultaneously. That's why I have a grid of 88*128. And yes, the speed is +/- correct since it matches the amount of DP accumulated over a certain period of time.Or you used a small DP value, then of course the speed will be much less. For example, with DP 13 the speed is only 950Mk/s (on the patched version) and 1100Mk/s with DP 20. P.S. But you are right there is a glitch with the speed calculation. JLP forgot to reset the average values before calculating the speed (thread.cpp) After making changes the speed became 950 Mk/s GPU: GPU #0 NVIDIA GeForce GTX 1660 SUPER (22x64 cores) Grid(88x128) (141.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.46 kangaroos [7.6s]
[952.59 MK/s][GPU 952.59 MK/s][Count 2^35.49][Dead 0][50s (Avg 01:06:23)][3.4/10.6MB]
@kTimesG you have written more than once that your program is several times faster than JLP and other clones. Can you really run 1660 Super at 2Gk/s? I would like to test this version with a 3060, can you share it?
the release is available you can try. |
|
|
|
I wonder what exactly you mean by 1.1Gk/s. Only one type of kangaroos included in that? Using my 1080 Ti, I get about 580Mk/s with my version.
The original JLP Kangaroo version 1.7 gives a speed of about 700 Mk/s for GTX 1660 Super, a few changes in the code and the speed will be 1.1 Gk/s and around 2.2Gk/s for 2080ti. 1080 Ti is old card, I don't know what speed you can get. P.S. It doesn't matter if it's 1 type of kangaroo or both. The speed is the same. Kangaroo v1.7Gfix (Only Wild)
Gx=79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
G Multipler: 0x1
JMP Multipler: 0x1
Loading: testwork
Start:0
Stop :7FFFFFFFFFFFFFFFF
Keys :1
KeyX :D2779258710A6FCD4E978335698E5C1B20795F8C3AAE524714E0E40EBACDB213
KeyY :D973566FFD3D6F79192827E1F93CCBF7E7F2EAF48F762C72C37578EA8154D978
LoadWork: [HashTable 1665.5/2088.3MB] [07s]
Number of CPU thread: 0
NB_RUN: 128
GPU_GRP_SIZE: 128
NB_JUMP: 32
Range width: 2^67
JMP bits DEC: 34
Jump Avg distance min: 2^32.95
Jump Avg distance max: 2^33.05
Jump multipled by: 0x1
Jump Avg distance: 2^32.97 [96]
Number of kangaroos: 2^20.46
Suggested DP: 13
Expected operations: 2^35.11
Expected RAM: 184.5MB
DP size: 13 [0xFFF8000000000000]
GPU: GPU #0 NVIDIA GeForce GTX 1660 SUPER (22x64 cores) Grid(88x128) (141.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.46 kangaroos [9.4s]
[1132.46 MK/s][GPU 1132.46 MK/s][Count 2^38.71][Dead 0][04s (Avg 32s)][1677.2/2103.0MB]
Key# 0 [1S]Pub: 0x02D2779258710A6FCD4E978335698E5C1B20795F8C3AAE524714E0E40EBACDB213
Priv: 0x7989031FDA5BA3BF5
|
|
|
|
I didn't touch the workfile or changed it using a script. I did try using a CPU. I'll try now using a GPU.
Edit - doesn't work with a GPU either. what did you change from JLP's version?
I downloaded the KangarooOT and KangarooOW version from GitHub to make sure we were using the same tools. For the experiment we will look for the public key 02d2779258710a6fcd4e978335698e5c1b20795f8c3aae524714e0e40ebacdb213 whose private key is 0x7989031fda5ba3bf5 in the 67-bit range from 0 to 7ffffffffffffffff Step 0: create a 67bitWrong.txt file with the following content: 0
7ffffffffffffffff
03633CBE3EC02B9401C5EFFA144C5B4D22F87940259634858FC7E59B1C09937852
Step 1: aor the accumulation of tame DPs create a step1.bat file with the following content and launch: kangarooOT -t 0 -gpu -gpuId 0 -g 88,128 -m 2.5 -d 13 -wi 120 -w testwork 67bitWrong.txt
for /l %%i in (1,1,6) do (
echo Iteration %%i
kangarooOT -t 0 -gpu -gpuId 0 -g 88,128 -m 2.5 -d 13 -wi 120 -w testwork -i testwork
)
pause
Step 2: To change the public key in the working file, make a step2.bat file and launch: py changewf.py -f testwork -pub 02d2779258710a6fcd4e978335698e5c1b20795f8c3aae524714e0e40ebacdb213 -rb 0 -re 7ffffffffffffffff
pause
Step 3: To find the public key make a step3.bat file and launch: kangarooOW -t 0 -gpu -gpuId 0 -g 88,128 -i testwork
pause
P.S. If you like it, I can add a version with a bit more speed (gtx 1160 Super - 1.1 Gk/s) |
|
|
|
When I try this trick, it just doesn't find the collision. even when it should take just a second, it never finds it. can you confirm these are the steps you did?
Choose a range (say, 48 bit)
Choose any key that is not in that range
run kangaroo on it for some time, (with -m 3 to be exact to your example), and make it save the work into a workfile.
Then load the work file into a new session with an actual key inside the range.
This is what I did, didn't work.
Before finding the public key in the range, did you change it in the working file using a script? P.S. 48 bit...? Maybe you are using CPU and not GPU, then it won't work. I remade the JLP program only for GPU, I don't know who uses CPU now. |
|
|
|
On-chip registers are insanely more times faster than reading and writing data from and into GPU memory, which is what the JLP kernel is all about. The loops are also in the bad order if what we care for are the jumps, not the kangaroos.
Maybe you wouldn't agree on this, but it is a really bad idea to dump millions of kangaroos into memory and read/jump/store them, to achieve the same efficiency as less kangaroos with a correct average jump size. Why? Because you can have a much much better efficiency by using fewer, faster kangaroos, and have the same results, but much faster.
Let's say instead of 128 kangaroos, we launch 4 kangaroos per thread. In this case, each kangaroo makes, say, 32 jumps. To get real coordinates after inverse batch, you need to store x,y,z coordinates of 32 points for each kangaroo somewhere. I don't understand how you store at least 128 x,y,z coordinates in registers. You'll have to use global memory. Shared memory won't fit all this. Can you explain a little? |
|
|
|
|
Show Posts
