Faits: A. A._, ressortissant algérien né en 1976, a été arrêté à Genève le 9 janvier 2012 et mis en détention sous la prévention de brigandage aggravé, emploi d'explosifs, mise en danger de la vie d'autrui et dommage à la propriété, pour avoir participé le 26 novembre 2010 à l'attaque d'un bureau de change, à l'explosif et à l'arme lourde. Il est également prévenu de vols avec effraction dans un magasin et dans une station service de Genève, ayant emporté plusieurs dizaines de milliers de francs de marchandises. Il aurait également volé l'un des véhicules utilisés pour l'attaque du bureau de change, dans lequel ses traces ADN ont été retrouvées. Le prévenu prétend avoir simplement volé puis vendu ce véhicule à l'un des auteurs de l'attaque. L'un des participants (B._) avait été arrêté à l'issue du braquage. D'autres participants ont été arrêtés en France. Au mois de juin 2012, la France a demandé l'extradition des prévenus. La détention provisoire a été régulièrement prolongée, notamment par décision du Tribunal des mesures de contrainte (Tmc) du 28 septembre 2012, confirmée par arrêt de la Chambre pénale de recours de la Cour de justice genevoise (CPR). Les charges relatives aux deux cambriolages n'étaient pas contestées. Le fait d'avoir vendu la voiture à l'un des participants au braquage constituait un acte de participation, et il n'était pas exclu que le prévenu ait également pris part à l'attaque; les constatations médicales (opération subie par le prévenu le 23 décembre 2010) n'avaient pas valeur d'alibi. La détention a encore été prolongée le 24 décembre 2012, le 22 mars et le 22 avril 2013. L'extradition avait été accordée le 14 janvier 2013, mais, si elle devait être refusée par les instances de recours, une confrontation avec les prévenus en France (jusque-là refusée par les autorités françaises) pourrait être rapidement organisée. B. Par arrêt du 8 mai 2013, la CPR a confirmé l'ordonnance du 22 avril 2013. La cour n'avait pas à réexaminer les éléments déjà retenus précédemment. Un témoignage du 16 avril 2013 n'apportait aucun élément à décharge, et les risques de fuite et de réitération demeuraient d'actualité. L'argument relatif au principe de célérité avait déjà été rejeté dans un arrêt du 18 avril 2013, l'instruction se poursuivant notamment à propos de l'emploi du temps du prévenu durant la période litigieuse. C. Par acte du 14 mai 2013, A._ forme un recours en matière pénale avec une demande d'assistance judiciaire. Il conclut à l'annulation de l'arrêt cantonal et à sa mise en liberté, subsidiairement au renvoi de la cause à l'autorité cantonale pour nouvelle décision dans le sens des considérants. La Chambre pénale de recours se réfère à son arrêt, sans observations. Le Ministère public conclut au rejet du recours. Par arrêt du 7 mai 2013, la Cour des plaintes du Tribunal pénal fédéral a rejeté le recours formé contre la demande d'extradition. Le recourant a interjeté un recours en matière de droit public contre cet arrêt (cause 1C_515/2013 actuellement pendante). Le recourant a présenté de nouvelles observations le 27 mai 2013, persistant dans ses motifs et conclusions.