Proxmark3 community

Research, development and trades concerning the powerful Proxmark3 device.

Remember; sharing is caring. Bring something back to the community.


"Learn the tools of the trade the hard way." +Fravia

You are not logged in.

Announcement

Time changes and with it the technology
Proxmark3 @ discord

Users of this forum, please be aware that information stored on this site is not private.

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

iceman
Administrator
Registered: 2013-04-25
Posts: 9,495
Website

hf mf nested will there be a remake?

An open question to Piwi, 

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

Offline

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

piwi
Contributor
Registered: 2013-06-04
Posts: 704

Re: hf mf nested will there be a remake?

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?

Offline

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

moebius
Contributor
Registered: 2011-03-10
Posts: 206

Re: hf mf nested will there be a remake?

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...)

Offline

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

piwi
Contributor
Registered: 2013-06-04
Posts: 704

Re: hf mf nested will there be a remake?

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.

Offline

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

moebius
Contributor
Registered: 2011-03-10
Posts: 206

Re: hf mf nested will there be a remake?

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!

Offline

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

asper
Contributor
Registered: 2008-08-24
Posts: 1,409

Re: hf mf nested will there be a remake?

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)

Offline

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

moebius
Contributor
Registered: 2011-03-10
Posts: 206

Re: hf mf nested will there be a remake?

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.

Offline

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

asper
Contributor
Registered: 2008-08-24
Posts: 1,409

Re: hf mf nested will there be a remake?

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...

Offline

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

moebius
Contributor
Registered: 2011-03-10
Posts: 206

Re: hf mf nested will there be a remake?

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.

Offline

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

moebius
Contributor
Registered: 2011-03-10
Posts: 206

Re: hf mf nested will there be a remake?

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!

Offline

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

asper
Contributor
Registered: 2008-08-24
Posts: 1,409

Re: hf mf nested will there be a remake?

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).

Offline

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

asper
Contributor
Registered: 2008-08-24
Posts: 1,409

Re: hf mf nested will there be a remake?

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)

Offline

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

piwi
Contributor
Registered: 2013-06-04
Posts: 704

Re: hf mf nested will there be a remake?

asper wrote:

Does your patch also affect the darkside attack speed ?

No, it doesn't.

Offline

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

holiman
Contributor
Registered: 2013-05-03
Posts: 566

Re: hf mf nested will there be a remake?

Awesome work, piwi!

Offline

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

holiman
Contributor
Registered: 2013-05-03
Posts: 566

Re: hf mf nested will there be a remake?

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

Offline

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

moebius
Contributor
Registered: 2011-03-10
Posts: 206

Re: hf mf nested will there be a remake?

Great work hell yeah! it runs REALLY FAST.

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

Offline

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

piwi
Contributor
Registered: 2013-06-04
Posts: 704

Re: hf mf nested will there be a remake?

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).

Offline

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

iceman
Administrator
Registered: 2013-04-25
Posts: 9,495
Website

Re: hf mf nested will there be a remake?

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...

Offline

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

holiman
Contributor
Registered: 2013-05-03
Posts: 566

Re: hf mf nested will there be a remake?

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.

Offline

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

ikarus
Contributor
Registered: 2012-09-20
Posts: 249
Website

Re: hf mf nested will there be a remake?

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)

Offline

Board footer

Powered by FluxBB