По городу поползли противоречивые слухи о таинственном и страшном пришельце, а он сам тем временем явился к Какидзаки Идзуми-но Ками, приближенному князя Уэсуги, заявил, что он лучший ниндзя во всей стране, и попросил представить его князю. Самурай потребовал у Дандзо, чтобы тот продемонстрировал свое искусство, и тогда Летучий Като показал ему свой невероятный прыжок. Самурай пришел в восхищение от столь великого таланта и немедленно доложил о своей «находке» Уэсуги.
На аудиенции у князя Дандзо вел себя вызывающе и вновь похвастал, что равного ему по мастерству ниндзя во всем свете не сыскать. Тогда Кэнсин нахмурил брови и сказал: «Ну, ежели ты такой мастер, покажи нам свое мастерство. Есть у меня старый вассал Наоэ Ямасиро-но Ками. В его усадьбе хранится драгоценная алебарда. Если ты сможешь ее сегодня ночью украсть, я возьму тебя на службу и назначу большое жалованье».
Задача Дандзо была поставлена не из легких. Огромный дом Наоэ, защищенный высокими стенами, окружал широкий ров. Многочисленные сторожа неустанно вглядывались в темноту, и подобраться к усадьбе незамеченным не было никакой возможности. Вокруг усадьбы рыскал огромный свирепый волкодав по кличке Мурасамэ, способный учуять любого чужака за сотни метров и прославившийся тем, что как-то на охоте в одиночку загрыз дикого кабана. Кроме того, все комнаты в доме были ярко освещены, и в них постоянно находились десятки слуг.
И все же Дандзо решил во что бы то ни стало прокрасться ночью в дом Наоэ. Воспользовался он при этом отнюдь не магией, а вполне «посюсторонними» методами –обычными уловками ниндзя. Злобному Мурасамэ он подсунул колобок заранее припасенного и отравленного риса-якимэси, после чего псина, отведав «лакомства», тут же издохла. Затем Дандзо могучим прыжком преодолел ров –не зря же его прозвали «Летучим»! При помощи лазательных когтей (сюко) он взобрался на стену и беззвучно, как кошка, спрыгнул во двор.
Так как дело было уже под утро, у охранников, которые чересчур рьяно сторожили усадьбу вечером и ночью, к этому времени уже глаза слипались. Поэтому ниндзя даже решил немного покуражиться –он не только утащил драгоценную нагинату, но еще и усадил на спину сладко проспавшую все время его ночных похождений одиннадцатилетнюю прислужницу жены Наоэ и в таком виде –с алебардой в руках и девчонкой за спиной –явился во дворец Уэсуги.
Все были поражены невероятным мастерством ниндзя. И даже Кэнсин застонал от восторга. Он прекрасно понимал, что этот человек мог оказаться подарком судьбы в борьбе с Такэдой, и уже предвкушал, как при помощи Дандзо отправит своего заклятого врага на тот свет.
Правда, было тут одно «но». «Как бы Като Дандзо не был подослан врагами?» –думал князь. А тут еще оскорбленный Наоэ стал нашептывать ему, что Дандзо –человек совершенно неизвестный, прошлое его темно, и уж очень его неожиданное появление здесь напоминает уловку врага. Долго раздумывал Кэнсин. И в итоге это одно «но» перевесило все таланты великого синоби. Он подозвал к себе начальника охраны Оникодзиму Сётаро и шепнул ему на ухо приказ немедленно прикончить опасного чужака.
Однако Дандзо был не дурак. По каким-то признакам он разгадал план князя и решил дать деру пока не поздно. Правда, охранников в замке было слишком много. Тут-то и пригодилось ниндзя его магическое (фокусническое или гипнотическое) искусство. Обращаясь ко всем присутствующим, он сказал: «Ну что ж, господа. Я хочу показать вам кое-что интересное.» С этими словами, Дандзо подозвал к себе похищенную девочку и стал вынимать у нее изо рта одну за другой кукол размером в 3 суна каждая. Когда он извлек их уже штук 30, куклы тали забавно пританцовывать. Все зрители, словно завороженные, уставились на фантастическое зрелище. А хитроумный Като Дандзо тем временем беспрепятственно выбрался из недружелюбного замка.
После этого случая Дандзо, горевший желанием отомстить Уэсуги, отправился в земли его врага, Такэды Сингэна.
Прибыв в Кофу, Дандзо явился к одному из главных вассалов Сингэна Атобэ Оисукэ. Он заявил, что хотел бы поступить на службу к князю, чтобы отомстить злокозненному Кэнсину. Такэда испытывал острую нужду в ловких агентах и был рад принять к себе на службу мастера нин-дзюцу. Правда заносчивость и хвастливость Дандзо ему тоже не понравились, и он предложил ему для начала доказать свое мастерство. Существует несколько версий этого испытания.