hf mf nested will there be a remake?

iceman · 2013-07-18 20:25:41

An open question to Piwi,

will your awsome new timing for "hf mf mifare" also help out the nested command?

piwi · 2013-07-19 10:21:22

Hey, how could you know? I had a look at hf mf nested already. What I have found so far is not very promising. The dependency between time and nonce distance (between first and nested auth) is not obvious. I even could observe shorter nonce distances with a longer time difference. Probably the card's PRNG doesn't keep running at the same clock speed after the first auth? Or the PRNG depends on the first auth nonce somehow?

Anybody there who did some research already?

moebius · 2013-07-28 23:55:13

Hello, using svn756, this command just runs for a few seconds and then, nothing else happens... any other experiencing the same?

Thanks you!

(Solved.. I was using a VM, that was the main problem...)

piwi · 2013-09-15 10:29:32

I just have committed a major rework of "hf mf nested" and a small rework of "hf mf chk" as svn764 in trunk (the summer time and good weather prevented me from doing this earlier).

Both commands execute much faster now (for my CPU (2 core Intel i5), a 1K card with 1 known, 11 unknown and 20 standard keys: hf mf nested approx 8 times faster, hf mf chk approx 4 times faster).

For those who are interested in more details:
I tried to get an exact timing for hf mf nested using the FPGA clock GetCountMifare() which was so successful in hf mf mifare. For any reason I was not able to get the exact nonce based on the exact timing. There might still be some effects which influence the Mifare PRNG which are not fully understood (at least by me). What I learned during the rework on hf mf mifare: the PRNG doesn't advance during transmits (if we receive the NACK, the PRNG is delayed or paused by exactly 8 cycles). In contrast to hf mf mifare we are checking a different nonce each time in hf mf nested - maybe there is not only a PRNG dependency on the number of bits transferred (which is the same each time) but also on the content?

Nevertheless, hf mf nested can now rely on better timing and the number of possible nonces is at least reduced. The PM therefore now needs to check only a few nonces and would return a nonce only if it is the single valid nonce within the range. The probability of chosing the correct nonce is therefore much higher than before. By relying on the good nonce quality we need only to select exactly two nonces to be transferred to the client for further processing.

On the client side of hf mf nested I found that the most time was spent in lfsr_recovery32() and of this time quite a good fraction was spent in sorting (quicksort) and searching (binsearch). I therefore replaced the quicksort with a bucketsort - which is not only faster but also eliminates the following searching - at the cost of additional memory required. For further speedup I introduced multithreading to calculate the two (one for each nonce) lfsr_recovery32() in parallel - those of us with a multicore CPU (who hasn't?) will notice an additional speedup. Could we use more than 2 threads? Probably - but I doubt that this would further increase speed. My 2 CPU cores aren't saturated - lfsr_recovery32() runtime is probably bound by memory accesses.

hf mf chk (which is also called from hf mf nested) used to power down the card and start it up again - which is time consuming. I therefore abstained from powering down the card for each authentication try. Instead a "halt" command sent to the tag now brings it to a known state independent of a successful or unsuccessful previous authentication attempt.

moebius · 2013-09-15 21:21:41

Hey @piwi nice to have news from your side! Your contrib's are always amazing!

Look, I'm using OSX, latest version, and while trying to compile, I've got:

gcc -std=c99 -I. -I../include -I../common -I/opt/local/include -Wall -Wno-unused-function -g -O4 -DHAVE_GUI -c -o obj/mifarehost.o mifarehost.c
mifarehost.c:44: warning: declaration does not declare anything
mifarehost.c:48: warning: declaration does not declare anything
mifarehost.c: In function ‘nested_worker_thread’:
mifarehost.c:64: error: ‘StateList_t’ has no member named ‘slhead’
mifarehost.c:65: error: ‘StateList_t’ has no member named ‘slhead’
mifarehost.c:66: error: ‘StateList_t’ has no member named ‘slhead’
mifarehost.c:67: error: ‘StateList_t’ has no member named ‘sltail’
mifarehost.c:68: error: ‘StateList_t’ has no member named ‘slhead’
mifarehost.c:70: error: ‘StateList_t’ has no member named ‘slhead’
mifarehost.c: In function ‘mfnested’:
mifarehost.c:125: error: ‘struct <anonymous>’ has no member named ‘slhead’
mifarehost.c:132: error: ‘struct <anonymous>’ has no member named ‘slhead’
mifarehost.c:133: error: ‘struct <anonymous>’ has no member named ‘slhead’
mifarehost.c:134: error: ‘struct <anonymous>’ has no member named ‘sltail’
mifarehost.c:134: error: ‘struct <anonymous>’ has no member named ‘sltail’
mifarehost.c:138: error: ‘struct <anonymous>’ has no member named ‘sltail’
mifarehost.c:145: error: ‘struct <anonymous>’ has no member named ‘sltail’
mifarehost.c:159: error: ‘struct <anonymous>’ has no member named ‘slhead’
mifarehost.c:160: error: ‘struct <anonymous>’ has no member named ‘slhead’
mifarehost.c:161: error: ‘struct <anonymous>’ has no member named ‘sltail’
mifarehost.c:162: error: ‘struct <anonymous>’ has no member named ‘sltail’
mifarehost.c:166: error: ‘struct <anonymous>’ has no member named ‘keyhead’
mifarehost.c:167: error: ‘struct <anonymous>’ has no member named ‘keyhead’
mifarehost.c:170: error: ‘struct <anonymous>’ has no member named ‘keyhead’
mifarehost.c:171: error: ‘struct <anonymous>’ has no member named ‘keyhead’
mifarehost.c:172: error: ‘struct <anonymous>’ has no member named ‘keytail’
mifarehost.c:172: error: ‘struct <anonymous>’ has no member named ‘keytail’
mifarehost.c:182: error: ‘struct <anonymous>’ has no member named ‘keyhead’
mifarehost.c:183: error: ‘struct <anonymous>’ has no member named ‘keytail’
mifarehost.c:190: error: ‘struct <anonymous>’ has no member named ‘slhead’
mifarehost.c:199: error: ‘struct <anonymous>’ has no member named ‘slhead’
mifarehost.c:200: error: ‘struct <anonymous>’ has no member named ‘slhead’
make[1]: *** [obj/mifarehost.o] Error 1
make: *** [client/all] Error 2

Please, check.

Thank you!

asper · 2013-09-15 22:10:44

It compiles correctly (firmware+bootrom+client) under Windows 7 (but still not tested "on the filed" flashing and executing with PM3); I am waiting for new jonor patches to compile a new version to release in Windows Client thread.

Last edited by asper (2013-09-15 22:11:20)

moebius · 2013-09-15 22:15:50

OK, I'll try to make it compile under OSX then...

I believe the best way to include new stuff is to try to make it work under *ux, win and osx (*ux like)...

thanks.

asper · 2013-09-15 22:34:25

If you manage to compile under mac why don't you open a specific thread for it like for win ? Linux is the main code so I don't think it will be necessary...

moebius · 2013-09-15 22:39:30

hey asper, It's always better to have the same source that can be compiled in linux, osx and win. I'll try to fix this and post my results. Thanks.

moebius · 2013-09-16 01:42:29

Hey there guys!

this "issue" can be fixed by adding "-fms-extensions" as a new flag in CFLAGS inside the client's Makefile. This is because the use of anonymous structs and unions.

See:

http://stackoverflow.com/questions/1972003/how-to-use-anonymous-structs-unions-in-c

for a reference.

If someone can test this new flag under linux and win, maybe we can add this flag in the svn just to be sure we're still ok with the main OS used by the community.

Be good!

asper · 2013-09-16 06:19:30

With the new extension added ad the end of CFLAGS line it still compiles fine:

...
CFLAGS = -std=c99 -I. -I../include -I../common -I/opt/local/include -Wall -Wno-unused-function $(COMMON_FLAGS) -g -O4 -fms-extensions
...

I agree with you with sources moebius but in my opinion it will be good also to have an already compiled version for all the platforms expecially for the "non-linux-friendly" ones (Win and Mac).

asper · 2013-09-16 09:10:51

I tested the new firmware+client (r764 Win) and I can say it is REALLY FAST !!! Thank you man !!!
Does your patch also affect the darkside attack speed ?

Last edited by asper (2013-09-16 09:12:13)

piwi · 2013-09-16 11:23:17

asper wrote:

Does your patch also affect the darkside attack speed ?

No, it doesn't.

holiman · 2013-09-16 19:26:04

Awesome work, piwi!

holiman · 2013-09-16 20:06:51

piwi wrote:

Both commands execute much faster now (for my CPU (2 core Intel i5), a 1K card with 1 known, 11 unknown and 20 standard keys: hf mf nested approx 8 times faster, hf mf chk approx 4 times faster).

It would be interesting to know how much faster it would be for you to do "script run mfkeys.lua" instead... You patches are now also in scripting-branch, as of r767

moebius · 2013-09-18 01:01:12

Great work hell yeah! it runs REALLY FAST.

Well, maybe I can open a new topic for OSX precompiled versions of the env.

piwi · 2013-09-18 06:44:34

holiman wrote:

It would be interesting to know how much faster it would be for you to do "script run mfkeys.lua" instead... You patches are now also in scripting-branch, as of r767

That's hardly comparable. hf mf chk tests 13 keys, mfkeys.lua tests 69. And the script assumes a 4K card, i.e. it tests additional blocks which would only be available with 4K cards.

For hf mf chk (like for most of the commands) the client CPU has not much to do - most of the time is spent waiting for the Proxmark to return results. For comparable legacy and script commands I therefore wouldn't expect any difference in timing.

The Proxmark part of hf mf chk has changed. Therefore there is a difference between r766 and 767. The benefit for the script is the same as for the legacy command (approx. 4 times faster):

time for script run mfkeys.lua in r766: 00:07:53
time for script run mfkeys.lua in r767: 00:01:56

(for my testcard: Mifare 1K classic with 21 "standard" keys).

iceman · 2013-09-18 20:46:05

Great work Piwi!

I had some problems compiling under win7, but with the -fms-extensions in the makefile the client compiled. Lots of warnings however.
Anyway, I only get v765 for Bootrom & os in the PM3 (hw ver), despite the svn says v767...

holiman · 2013-09-19 07:58:31

iceman wrote:

Anyway, I only get v765 for Bootrom & os in the PM3 (hw ver), despite the svn says v767...

That's nothing to worry about, it's because of the svn branches.

ikarus · 2013-09-19 09:54:46

Hi piwi,

just want to say: Thanks for this awesome remake of nested!
Every thing is just working fine and fast using s767 + ubuntu linux!

Edit: Oh, and thank you for remaking the "hf mf mifare" too!!!

Last edited by ikarus (2013-09-19 10:01:23)

Proxmark3 community

Announcement

#1 2013-07-18 20:25:41

hf mf nested will there be a remake?

#2 2013-07-19 10:21:22

Re: hf mf nested will there be a remake?

#3 2013-07-28 23:55:13

Re: hf mf nested will there be a remake?

#4 2013-09-15 10:29:32

Re: hf mf nested will there be a remake?

#5 2013-09-15 21:21:41

Re: hf mf nested will there be a remake?

#6 2013-09-15 22:10:44

Re: hf mf nested will there be a remake?

#7 2013-09-15 22:15:50

Re: hf mf nested will there be a remake?

#8 2013-09-15 22:34:25

Re: hf mf nested will there be a remake?

#9 2013-09-15 22:39:30

Re: hf mf nested will there be a remake?

#10 2013-09-16 01:42:29

Re: hf mf nested will there be a remake?

#11 2013-09-16 06:19:30

Re: hf mf nested will there be a remake?

#12 2013-09-16 09:10:51

Re: hf mf nested will there be a remake?

#13 2013-09-16 11:23:17

Re: hf mf nested will there be a remake?

#14 2013-09-16 19:26:04

Re: hf mf nested will there be a remake?

#15 2013-09-16 20:06:51

Re: hf mf nested will there be a remake?

#16 2013-09-18 01:01:12

Re: hf mf nested will there be a remake?

#17 2013-09-18 06:44:34

Re: hf mf nested will there be a remake?

#18 2013-09-18 20:46:05

Re: hf mf nested will there be a remake?

#19 2013-09-19 07:58:31

Re: hf mf nested will there be a remake?

#20 2013-09-19 09:54:46

Re: hf mf nested will there be a remake?

Board footer